Метод перекрытия–добавления

В обработке сигналов метод перекрытия-сложения является эффективным способом оценки дискретной свертки очень длинного сигнала с помощью фильтра с конечной импульсной характеристикой (КИХ) : ${\displaystyle x[n]}$ ${\displaystyle h[n]}$

где для за пределами области   В этой статье используются общепринятые абстрактные обозначения, такие как или , в которых подразумевается, что функции следует рассматривать в их совокупности, а не в конкретные моменты времени (см. Convolution#Notation ). ${\displaystyle h[m]=0}$ ${\displaystyle m}$ ${\displaystyle [1,M].}$ ${\textstyle y(t)=x(t)*h(t),}$ ${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$ ${\textstyle t}$

Рис. 1: Последовательность из пяти графиков отображает один цикл алгоритма свертки с перекрытием и добавлением. Первый график — это длинная последовательность данных, которые будут обработаны низкочастотным КИХ-фильтром. Второй график — это один сегмент данных, которые будут обработаны кусочно. Третий график — это отфильтрованный сегмент, включая переходные процессы повышения и понижения фильтра. Четвертый график показывает, где будут добавлены новые данные с результатом предыдущих сегментов. Пятый график — это обновленный выходной поток. КИХ-фильтр — это низкочастотный фильтр с выборками, длина сегментов — выборки, а перекрытие — 15 выборок. ${\displaystyle M=16}$ ${\displaystyle L=100}$

Идея состоит в том, чтобы разделить задачу на несколько сверток с короткими сегментами : ${\displaystyle h[n]}$ ${\displaystyle x[n]}$

${\displaystyle x_{k}[n]\ \triangleq \ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\text{otherwise}},\end{cases}}}$

где — произвольная длина сегмента. Тогда : ${\displaystyle L}$

${\displaystyle x[n]=\sum _{k}x_{k}[n-kL],\,}$

и может быть записана как сумма коротких сверток : ^[1] ${\displaystyle y[n]}$

${\displaystyle {\begin{aligned}y[n]=\left(\sum _{k}x_{k}[n-kL]\right)*h[n]&=\sum _{k}\left(x_{k}[n-kL]*h[n]\right)\\&=\sum _{k}y_{k}[n-kL],\end{aligned}}}$

где линейная свертка равна нулю вне области И для любого параметра ^[A] она эквивалентна -точечной круговой свертке с внутри области Преимущество состоит в   том, что круговая свертка может быть вычислена более эффективно, чем линейная свертка, согласно теореме о круговой свертке : ${\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]\,}$ ${\displaystyle [1,L+M-1].}$ ${\displaystyle N\geq L+M-1,\,}$ ${\displaystyle N}$ ${\displaystyle x_{k}[n]\,}$ ${\displaystyle h[n]\,}$ ${\displaystyle [1,N].}$

где :

• DFT _N и IDFT _N относятся к дискретному преобразованию Фурье и его обратному преобразованию, вычисляемому по дискретным точкам, и ${\displaystyle N}$
• ${\displaystyle L}$Обычно выбирается таким образом, чтобы было целой степенью числа 2, а преобразования реализуются с помощью алгоритма БПФ для эффективности. ${\displaystyle N=L+M-1}$

Псевдокод

Ниже приведен псевдокод алгоритма :

( Алгоритм перекрытия-сложения для линейной свертки )h = FIR_фильтрМ = длина(ч)Nx = длина(x)N = 8 × 2^ceiling( log2(M) ) (8 раз наименьшая степень двойки, большая, чем длина фильтра M. См. следующий раздел для немного лучшего выбора.)
step_size = N - (M-1) (L в тексте выше)Н = ДПФ(h, N)позиция = 0у(1 : Nx + M-1) = 0пока позиция + размер_шага ≤ Nx делать y(позиция+(1:N)) = y(позиция+(1:N)) + IDFT(DFT(x(позиция+(1:размер_шага)), N) × H) позиция = позиция + размер_шагаконец

Соображения эффективности

Рис. 2: График значений N (целая степень числа 2), которые минимизируют функцию стоимости. ${\displaystyle {\tfrac {N\left(\log _{2}N+1\right)}{N-M+1}}}$

Когда DFT и IDFT реализуются алгоритмом FFT, псевдокод выше требует около N (log ₂ (N) + 1) комплексных умножений для FFT, произведения массивов и IFFT. ^[B] Каждая итерация производит N-M+1 выходных выборок, поэтому количество комплексных умножений на выходную выборку составляет около :

Например, когда и Eq.3 равны , тогда как прямая оценка Eq.1 потребует до комплексных умножений на выходной образец, худший случай — когда и являются комплексными значениями. Также обратите внимание, что для любого заданного Eq.3 есть минимум относительно Рисунок 2 — это график значений , которые минимизируют Eq.3 для диапазона длин фильтров ( ). ${\displaystyle M=201}$ ${\displaystyle N=1024,}$ ${\displaystyle 13.67,}$ ${\displaystyle 201}$ ${\displaystyle x}$ ${\displaystyle h}$ ${\displaystyle M,}$ ${\displaystyle N.}$ ${\displaystyle N}$ ${\displaystyle M}$

Вместо уравнения 1 мы также можем рассмотреть применение уравнения 2 к длинной последовательности выборок длины. Общее количество комплексных умножений будет: ${\displaystyle N_{x}}$

${\displaystyle N_{x}\cdot (\log _{2}(N_{x})+1).}$

Для сравнения, количество комплексных умножений, требуемых алгоритмом псевдокода, составляет:

${\displaystyle N_{x}\cdot (\log _{2}(N)+1)\cdot {\frac {N}{N-M+1}}.}$

Следовательно, стоимость метода перекрытия-сложения масштабируется почти как , в то время как стоимость одной большой круговой свертки составляет почти . Два метода также сравниваются на рисунке 3, созданном с помощью моделирования Matlab. Контуры представляют собой линии постоянного отношения времени, необходимого для выполнения обоих методов. Когда метод перекрытия-сложения быстрее, отношение превышает 1, и видны отношения вплоть до 3. ${\displaystyle O\left(N_{x}\log _{2}N\right)}$ ${\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}$

Рис 3: Выигрыш метода перекрытия-сложения по сравнению с одиночной большой круговой сверткой. Оси показывают значения длины сигнала N _x и длины фильтра N _h .

Смотрите также

• Метод перекрытия–сохранения
• Круговая_свёртка#Пример

Примечания

1. Это условие подразумевает, что сегмент имеет по крайней мере добавленные нули, что предотвращает циклическое перекрытие переходных процессов нарастания и спада выходного сигнала. ${\displaystyle x_{k}}$ ${\displaystyle M-1}$
2. Алгоритм Кули–Тьюки FFT для N=2 ^k требует (N/2) log ₂ (N) – см. FFT – Определение и скорость

Ссылки

1. Рабинер, Лоуренс Р.; Голд, Бернард (1975). "2.25" . Теория и применение цифровой обработки сигналов . Энглвуд Клиффс, Нью-Джерси: Prentice-Hall. стр. 63–65. ISBN 0-13-914101-4.

Дальнейшее чтение

• Оппенгейм, Алан В.; Шефер, Рональд В. (1975). Цифровая обработка сигналов . Энглвуд Клиффс, Нью-Джерси: Prentice-Hall. ISBN 0-13-214635-5.
• Хейс, М. Хорас (1999). Цифровая обработка сигналов . Серия Schaum's Outline. Нью-Йорк: McGraw Hill. ISBN 0-07-027389-8.
• Сенобари, Надер Шакибай; Фаннинг, Гарет Дж.; Кеог, Имонн; Чжу, Ян; Йе, Чин-Чиа Майкл; Циммерман, Закари; Муин, Абдулла (2019). «Сверхэффективная кросс-корреляция (SEC-C): быстрый согласованный код фильтрации, подходящий для настольных компьютеров» (PDF) . Seismological Research Letters . 90 (1): 322–334. doi :10.1785/0220180122. ISSN  0895-0695.