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

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

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

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

Идея состоит в том, чтобы вычислить короткие сегменты 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 {otherwise}}.\end{cases}}}$

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

Тогда для и, что эквивалентно , мы можем записать: ${\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]\,}$

где :

• 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) позиция = позиция + размер_шагаконец

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

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

Когда DFT и IDFT реализуются алгоритмом FFT, псевдокод выше требует около N (log ₂ (N) + 1) комплексных умножений для FFT, произведения массивов и IFFT. ^[E] Каждая итерация производит 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}}.}$

Таким образом, стоимость метода перекрытия-сохранения масштабируется почти как , в то время как стоимость одной большой круговой свертки составляет почти . ${\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]}

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

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

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

Примечания

1. Рабинер и Голд, рис. 2.35, четвертый след.
2. Смещение нежелательных краевых эффектов на последние выходы M-1 является потенциальным удобством во время выполнения, поскольку IDFT может быть вычислен в буфере , а не вычислен и скопирован. Затем краевые эффекты могут быть перезаписаны следующим IDFT. Последующая сноска объясняет, как выполняется сдвиг, путем временного сдвига импульсной характеристики. ${\displaystyle y[n]}$
3. Не путать с методом перекрытия-сложения , который сохраняет отдельные эффекты переднего и заднего фронта.
4. Краевые эффекты можно переместить с начала на конец вывода IDFT, заменив на , что означает, что буфер длины N циклически сдвинут (повернут) на M-1 выборок. Таким образом, элемент h(M) находится при n=1. Элемент h(M-1) находится при n=N. h(M-2) находится при n=N-1. И т.д. ${\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n])}$ ${\displaystyle \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1])=\ \scriptstyle {\text{DFT}}_{N}\displaystyle (h[n+M-1-N]),}$
5. Алгоритм Кули–Тьюки FFT для N=2 ^k требует (N/2) log ₂ (N) – см. FFT – Определение и скорость
6. Карлин и др. 1999, стр. 31, столбец 20.

Ссылки

1. "Overlap-Add (OLA) STFT Processing | Spectral Audio Signal Processing". www.dsprelated.com . Получено 2024-03-02 . Название «overlap-save» происходит от того факта, что L-1 выборок предыдущего кадра [здесь: M-1 выборок текущего кадра] сохраняются для вычисления следующего кадра.
2. Харрис, Ф. Дж. (1987). DFElliot (ред.). Справочник по цифровой обработке сигналов . Сан-Диего: Academic Press. стр. 633–699. ISBN 0122370759.
3. Фреркинг, Марвин (1994). Цифровая обработка сигналов в системах связи . Нью-Йорк: Van Nostrand Reinhold. ISBN 0442016166.
4. Боргердинг, Марк (2006). «Превращение Overlap–Save в многополосный микшерный банк фильтров понижения частоты дискретизации». Журнал IEEE Signal Processing . 23 (март 2006 г.): 158–161. doi :10.1109/MSP.2006.1598092.

4. Рабинер, Лоуренс Р.; Голд, Бернард (1975). "2.25" . Теория и применение цифровой обработки сигналов . Энглвуд Клиффс, Нью-Джерси: Prentice-Hall. стр. 63–67. ISBN 0-13-914101-4.
5. Патент США 6898235, Карлин, Джо; Коллинз, Терри и Хейс, Питер и др., «Устройство перехвата и пеленгации широкополосной связи с использованием гиперканализации», опубликовано 10 декабря 1999 г., выдано 24 мая 2005 г.  , также доступно по адресу https://patentimages.storage.googleapis.com/4d/39/2a/cec2ae6f33c1e7/US6898235.pdf

Внешние ссылки

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