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

В обработке сигналов перекрытие-сохранение — это традиционное название эффективного способа оценки дискретной свертки между очень длинным сигналом и фильтром с конечной импульсной характеристикой (FIR) : ${\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 и объединить эти сегменты вместе. Рассмотрим сегмент, начинающийся с 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. ^[Б] ${\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 представляет собой целую степень двойки, а преобразования для повышения эффективности реализуются с помощью алгоритма БПФ .
• Эффекты переднего и заднего края круговой свертки перекрываются и добавляются, ^[C] и впоследствии отбрасываются. ^[Д]

Псевдокод

( Алгоритм сохранения перекрытия для линейной свертки )h = FIR_impulse_responseM = длина (ч)перекрытие = M - 1N = 8 × перекрытие (более лучший выбор см. в следующем разделе)Step_size = N — перекрытиеН = ДПФ(ч, Н)позиция = 0в то время как позиция + N ≤ длина (x) yt = IDFT(DFT(x(position+(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}}}$

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

Например, когда M = 201 и N = 1024, уравнение 3 равно 13,67, тогда как прямая оценка уравнения 1 потребует до 201 комплексного умножения на выходную выборку, причем худший случай - это когда и x , и h имеют комплексные значения. Также обратите внимание , что для любого заданного M уравнение 3 имеет минимум по отношению к N. На рисунке 2 представлен график значений N, которые минимизируют уравнение 3 для диапазона длин фильтра (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)}$

Перекрытие – отбросить

«Перекрытие-выброс» ^[1] и «Перекрытие-отходы» ^[2] — менее часто используемые метки для того же метода, который описан здесь. Однако эти метки на самом деле лучше (чем перекрытие–сохранить ) отличать от перекрытия–добавить , потому что оба метода «сохраняют», а отбрасывает только один. «Сохранить» просто относится к тому факту, что для обработки сегмента k + 1 необходимо M  — 1 входных (или выходных) выборок из сегмента k .

Расширение перекрытия – сохранить

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

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

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

• Перекрытие – метод добавления

Примечания

1. Рабинер и Голд, рис 2.35, четвертый след.
2. Перенос нежелательных краевых эффектов на последние выходные данные M-1 является потенциальным удобством во время выполнения, поскольку IDFT можно вычислять в буфере , а не вычислять и копировать. Тогда краевые эффекты могут быть перезаписаны следующим IDFT. В последующей сноске объясняется, как осуществляется сдвиг, путем временного сдвига импульсной характеристики. ${\displaystyle y[n]}$
3. Не путать с методом Overlap-add , который сохраняет отдельные эффекты передней и задней кромки.
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. Алгоритм БПФ Кули – Тьюки для N = 2 ^k требует (N/2) log ₂ (N) - см. БПФ - Определение и скорость
6. Карлин и др. 1999, стр. 31, столбец 20.

Рекомендации

1. Харрис, Ф.Дж. (1987). Д.Ф. Эллиот (ред.). Справочник по цифровой обработке сигналов . Сан-Диего: Академическая пресса. стр. 633–699. ISBN 0122370759.
2. Фреркинг, Марвин (1994). Цифровая обработка сигналов в системах связи . Нью-Йорк: Ван Ностранд Рейнхольд. ISBN 0442016166.
3. Боргердинг, Марк (2006). «Превращение перекрытия – сохранения в набор фильтров многополосного микширования и понижающей дискретизации». Журнал обработки сигналов IEEE . 23 (март 2006 г.): 158–161. дои : 10.1109/MSP.2006.1598092.

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

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

• Доктор Дипа Кундур, «Добавление перекрытия и сохранение перекрытия», Университет Торонто