Метод перекрытия–сохранения

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

${\displaystyle y[n]=x[n]*h[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot x[нм]=\sum _{m=1}^{M}h[m]\cdot x[нм],}$

Ур.1

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

Идея состоит в том, чтобы вычислить короткие сегменты y [ n ] произвольной длины L и объединить сегменты вместе. Для этого требуются более длинные входные сегменты, которые перекрывают следующий входной сегмент. Перекрывающиеся данные «сохраняются» и используются во второй раз. ^[1] Сначала мы описываем этот процесс с помощью обычной свертки для каждого выходного сегмента. Затем мы описываем, как заменить эту свертку более эффективным методом.

Рассмотрим отрезок, начинающийся с n = kL  +  M , для любого целого числа k , и определим :

${\displaystyle x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {иначе}}.\end{cases}}}$

${\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[нм].}$

Тогда для и, что эквивалентно , мы можем записать:${\displaystyle kL+M+1\leq n\leq kL+L+M}$${\displaystyle M+1\leq n-kL\leq L+M}$

${\displaystyle y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL].}$

При замене задача сводится к вычислению для . Эти шаги проиллюстрированы на первых трех трассах рисунка 1, за исключением того, что желаемая часть выходных данных (третья трасса) соответствует 1  ≤  ​​j  ≤  L . ^[B]${\displaystyle j=n-kL}$${\displaystyle y_{k}[j]}$${\displaystyle M+1\leq j\leq L+M}$

Если мы периодически расширяем x _k [ n ] с периодом N  ≥  L  +  M  − 1, согласно :

${\displaystyle x_{k,N}[n]\ \triangleq \ \sum _{\ell =-\infty }^{\infty }x_{k}[n-\ell N],}$

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

${\displaystyle y_{k}[n]\ =\ \scriptstyle {\text{IDFT}}_{N}\displaystyle (\ \scriptstyle {\text{DFT}}_{N}\displaystyle (x_{k}[n])\cdot \ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])\ ),}$

Ур.2

где :

• DFT _N и IDFT _N относятся к дискретному преобразованию Фурье и его обратному преобразованию, вычисляемому по N дискретным точкам, и
• L обычно выбирается таким образом, чтобы N = L+M-1 было целой степенью числа 2, а преобразования реализуются с помощью алгоритма БПФ для эффективности.
• Эффекты переднего и заднего фронтов круговой свертки накладываются и добавляются ^[C] , а затем отбрасываются. ^[D]

( Алгоритм сохранения перекрытия для линейной свертки )h = FIR_impulse_responseМ = длина(ч)перекрытие = М − 1N = 8 × перекрытие (см. следующий раздел для лучшего выбора)размер_шага = N − перекрытиеН = ДПФ(h, N)позиция = 0пока позиция + N ≤ длина(x) yt = IDFT(DFT(x(позиция+(1:N))) × H) y(position+(1:step_size)) = yt(M : N) (отбросить M−1 значений y) позиция = позиция + размер_шагаконец

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

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

Ур.3

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

Вместо уравнения 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}}.}$

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

Overlap–discard ^[2] и Overlap–scrap ^[3] — менее часто используемые метки для одного и того же метода, описанного здесь. Однако эти метки на самом деле лучше (чем across–save ) отличать от across–add , потому что оба метода «сохраняют», но только один отбрасывает. «Save» просто относится к тому факту, что для обработки сегмента k + 1 требуется M  − 1 входных (или выходных) выборок из сегмента k .

Алгоритм перекрытия-сохранения может быть расширен для включения других общих операций системы: ^{[F] [4]}

• Дополнительные каналы ОБПФ могут быть обработаны дешевле, чем первые, путем повторного использования прямого БПФ
• Частоту дискретизации можно изменять, используя различные размеры прямого и обратного БПФ.
• Частотное преобразование (микширование) может быть достигнуто путем перестановки частотных ячеек

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

• Доктор Дипа Кундур, Overlap Add и Overlap Save, Университет Торонто