Секционная свёртка

Шаблон:Значения Секционная (секционированная) свёртка — метод вычисления свёртки, используемый, когда количество элементов одной из входных последовательностей во много раз больше, чем количество элементов другойШаблон:Sfn. Основные методы вычисления секционной свёртки — Шаблон:Нп3 и Шаблон:Нп3.

Вычисление

Пусть $x=\{x(1),x(2),\dots \}$ — неограниченная последовательность, $h=\{h(1),\dots ,h(N)\}$ — последовательность длины $N$, $L$ — некоторое натуральное число.

Метод перекрытия с суммированием

Для вычисления линейной свёртки $y=x*h$ методом перекрытия с суммированием необходимо разделить последовательность $x$ на смежные секции длины $L$:

$x(n)=\sum _{k=0}^{+\mathrm{\infty }}{x}_k(n),$

где

$x_k(n)=\{\begin{array}{cc}x(n),& n\in [kL,(k+1)L-1],\\ 0,& n\notin [kL,(k+1)L-1].\end{array}$

Тогда

$y(n)=\sum _{m=0}^{N-1}h(m)\sum _{k=0}^{+\mathrm{\infty }}{x}_k(n-m)=\sum _{k=0}^{+\mathrm{\infty }}h(n)*x_k(n)=\sum _{k=0}^{+\mathrm{\infty }}{y}_k(n).$

Длина каждой из частичных свёрток в данной сумме равна $L+N-1$, то есть имеется участок длины $N-1$, на котором $k$-я и $(k+1)$-я частичные свёртки перекрываются, поэтому их отсчёты на участке перекрытия нужно сложить. Отсюда и происходит название данного методаШаблон:Sfn.

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

Пусть теперь длина секций $x_k$ последовательности $x$ равна $L+N-1$ и у этих секций есть участки перекрытия длиной $N-1$. Для каждой секции вычисляется циклическая свёртка $h$ и $x_k$, содержащая $L+N-1$ отсчёт и обозначаемая $y_k$. Необходимо отбросить последние $N-1$ отсчётов этой последовательности, а остальные присоединить к последовательности $y_{k-1}$. После выполнения этой процедуры для каждого $k$ получится искомая последовательность $y=x*h$Шаблон:Sfn.

Замечание

Число $L$ удобно выбирать так, чтобы число $L+N-1$ было степенью двойки. Тогда каждую из частичных свёрток можно эффективно выполнять с помощью быстрых алгоритмов, значительно снижая вычислительную сложность.

Литература

• Шаблон:Книга