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

В сигналов обработке «перекрытие-сохранение» — это традиционное название эффективного способа оценки дискретной свертки между очень длинными сигналами. $x[n]$ и фильтр с конечной импульсной характеристикой (FIR) $h[n]$:

$y[n]=x[n]*h[n]\ \triangleq \ \sum _{m=-\infty }^{\infty }h[m]\cdot x[n-m]=\sum _{m=1}^{M}h[m]\cdot x[n-m],$     ( Уравнение 1 )

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

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

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

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

$x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {otherwise}}.\end{cases}}$

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

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

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

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

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

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

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

$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 представляет собой целую степень двойки, а преобразования для повышения эффективности реализуются с помощью алгоритма БПФ .
• Эффекты передней и задней кромки круговой свертки перекрываются и добавляются: и впоследствии отброшены.

Псевдокод

(Overlap-save algorithm for linear convolution)
h = FIR_impulse_response
M = length(h)
overlap = M − 1
N = 8 × overlap    (see next section for a better choice)
step_size = N − overlap
H = DFT(h, N)
position = 0

while position + N ≤ length(x)
    yt = IDFT(DFT(x(position+(1:N))) × H)
    y(position+(1:step_size)) = yt(M : N)    (discard M−1 y-values)
    position = position + step_size
end

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

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

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

${\frac {N(\log _{2}(N)+1)}{N-M+1}}.\,$     ( Уравнение 3 )

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

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

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

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