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

Эта статья посвящена методу выполнения свертки, не путать с WOLA (Weight, OverLap, Add), который представляет собой метод создания каналов. См. Выборку DTFT В этой статье используются общие абстрактные обозначения, такие как или, в которых подразумевается, что функции следует рассматривать в их совокупности, а не в определенные моменты (см. Обозначение свертки ). ${\ textstyle у (т) = х (т) * час (т),}$${\ textstyle у (т) = {\ mathcal {H}} \ {х (т) \},}$${\ textstyle t.}$

При обработке сигналов метод перекрытия – сложения является эффективным способом оценки дискретной свертки очень длинного сигнала с фильтром конечной импульсной характеристики (КИХ):${\ Displaystyle х [п]}$ ${\ Displaystyle ч [п]}$

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

${\ displaystyle y [n] = x [n] * час [n] \ \ треугольник q \ \ sum _ {m = - \ infty} ^ {\ infty} h [m] \ cdot x [nm] = \ sum _ {m = 1} ^ {M} h [m] \ cdot x [нм],}$

( Уравнение 1 )

где h [ m ] = 0 для m вне области [1, M ].

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

${\ Displaystyle х_ {к} [n] \ \ треугольник \ {\ begin {case} x [n + kL], amp; n = 1,2, \ ldots, L \\ 0, amp; {\ text {else}}, \ end {case}}}$

где L - произвольная длина отрезка. Потом:

${\ Displaystyle х [п] = \ сумма _ {k} x_ {k} [n-kL], \,}$

а y [ n ] можно записать как сумму коротких сверток:

${\ Displaystyle {\ begin {выровнено} y [n] = \ left (\ sum _ {k} x_ {k} [n-kL] \ right) * h [n] amp; = \ sum _ {k} \ left (x_ {k} [n-kL] * h [n] \ right) \\ amp; = \ sum _ {k} y_ {k} [n-kL], \ end {выровнено}}}$

где линейная свертка равна нулю вне области [1, L + M - 1]. И для любого параметра это равносильно тому, N - точечное круговой свертки из с в области [1, N ]. Преимущество заключается в том, что круговая свертка может быть вычислена более эффективно, чем линейная свертка, в соответствии с теоремой круговой свертки :${\ Displaystyle у_ {к} [п] \ \ треугольник \ х_ {к} [п] * ч [п] \,}$${\ Displaystyle N \ geq L + M-1, \,}$ ${\ Displaystyle х_ {к} [п] \,}$${\ Displaystyle ч [п] \,}$

${\ 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 представляет собой целое число степени двойки, а преобразования для эффективности реализуются с помощью алгоритма FFT.

• 1 Псевдокод
• 2 Соображения эффективности
• 3 См. Также
• 4 Примечания
• 5 ссылки
• 6 Дальнейшее чтение
• 7 Внешние ссылки

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

(Overlap-add algorithm for linear convolution) h = FIR_impulse_response M = length(h) Nx = length(x) N = 8 × 2^ceiling( log2(M))  (8 times the smallest power of two bigger than filter length M. See next section for a slightly better choice.) step_size = N - (M-1) (L in the text above) H = DFT(h, N) position = 0 y(1 : Nx + M-1) = 0 while position + step_size ≤ Nx do y(position+(1:N)) = y(position+(1:N)) + IDFT(DFT(x(position+(1:step_size)), N) × H) position = position + step_size end

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

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

${\ Displaystyle {\ гидроразрыва {N (\ log _ {2} (N) +1)} {N-M + 1}}. \,}$

( Уравнение 3 )

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

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

Рис. 3. Преимущество метода сложения с перекрытием по сравнению с одной большой круговой сверткой. По осям показаны значения длины сигнала N x и длины фильтра N h.

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

• Оппенгейм, Алан В.; Шафер, Рональд В. (1975). Цифровая обработка сигналов. Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN   0-13-214635-5.
• Хейс, М. Гораций (1999). Цифровая обработка сигналов. Обзорная серия Шаума. Нью-Йорк: Макгроу Хилл. ISBN   0-07-027389-8.