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

В обработке сигналов метод перекрытия-сложения является эффективным способом оценки дискретной свертки очень длинного сигнала. $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 ).

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

x_{k}[n]\ \triangleq \ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\text{otherwise}},\end{cases}}

где $L$ — произвольная длина сегмента. Затем :

x[n]=\sum _{k}x_{k}[n-kL],\,

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

{\begin{aligned}y[n]=\left(\sum _{k}x_{k}[n-kL]\right)*h[n]&=\sum _{k}\left(x_{k}[n-kL]*h[n]\right)\\&=\sum _{k}y_{k}[n-kL],\end{aligned}}

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

$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-add algorithm for linear convolution)h = FIR_filterM = 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 = 0y(1 : Nx + M-1) = 0while 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_sizeend

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

Когда ДПФ и 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)$ . Эти два метода также сравниваются на рисунке 3, созданном с помощью моделирования Matlab. Контуры представляют собой линии постоянного соотношения времени, необходимого для выполнения обоих методов. Когда метод перекрытия-добавления работает быстрее, соотношение превышает 1, и видны отношения, достигающие 3.

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

См. также

Примечания

^ Это условие подразумевает, что $x_{k}$ сегмент имеет как минимум $M-1$ добавленные нули, что предотвращает циклическое перекрытие переходных процессов повышения и спада выходного сигнала.
^ Алгоритм БПФ Кули – Тьюки для N = 2 ^к требуется (N/2) log ₂ (N) – см. БПФ – Определение и скорость

Ссылки

^ Рабинер, Лоуренс Р.; Голд, Бернард (1975). «2,25» . Теория и применение цифровой обработки сигналов . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр. 63–65 . ISBN 0-13-914101-4 .

Дальнейшее чтение

Оппенгейм, Алан В.; Шафер, Рональд В. (1975). Цифровая обработка сигналов . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN 0-13-214635-5 .
Хейс, М. Гораций (1999). Цифровая обработка сигналов . Серия набросков Шаума. Нью-Йорк: МакГроу Хилл. ISBN 0-07-027389-8 .
Сенобари, Надер Шакибай; Фаннинг, Гарет Дж.; Кио, Имонн; Чжу, Ян; Да, Чин-Чиа Майкл; Циммерман, Закари; Муин, Абдулла (2019). «Сверхэффективная кросс-корреляция (SEC-C): код быстрой согласованной фильтрации, подходящий для настольных компьютеров» (PDF) . Письма о сейсмологических исследованиях . 90 (1): 322–334. дои : 10.1785/0220180122 . ISSN 0895-0695 .

[2] Это условие подразумевает, что $x_{k}$ сегмент имеет как минимум $M-1$ добавленные нули, что предотвращает циклическое перекрытие переходных процессов повышения и спада выходного сигнала.

[3] Алгоритм БПФ Кули – Тьюки для N = 2 ^к требуется (N/2) log ₂ (N) – см. БПФ – Определение и скорость

[Rabiner-1] Рабинер, Лоуренс Р.; Голд, Бернард (1975). «2,25» . Теория и применение цифровой обработки сигналов . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. стр. 63–65 . ISBN 0-13-914101-4 .

[1]

[А]

[Б]