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

У этого термина существуют и другие значения, см. Свёртка.

Секционная (секционированная) свёртка — метод вычисления свёртки, используемый, когда количество элементов одной из входных последовательностей во много раз больше, чем количество элементов другой^[1]. Основные методы вычисления секционной свёртки — метод перекрытия с суммированием^[англ.] и метод перекрытия с накоплением^[англ.].

Вычисление

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

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

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

${\displaystyle x(n)=\sum \limits _{k=0}^{+\infty }x_{k}(n),}$

где

${\displaystyle x_{k}(n)=\left\{{\begin{array}{rl}x(n),&n\in [kL,\,(k+1)L-1],\\0,&n\notin [kL,\,(k+1)L-1].\end{array}}\right.}$

Тогда

${\displaystyle y(n)=\sum \limits _{m=0}^{N-1}h(m)\sum \limits _{k=0}^{+\infty }x_{k}(n-m)=\sum \limits _{k=0}^{+\infty }h(n)*x_{k}(n)=\sum \limits _{k=0}^{+\infty }y_{k}(n).}$

Длина каждой из частичных свёрток в данной сумме равна ${\displaystyle L+N-1}$, то есть имеется участок длины ${\displaystyle N-1}$, на котором ${\displaystyle k}$-я и ${\displaystyle (k+1)}$-я частичные свёртки перекрываются, поэтому их отсчёты на участке перекрытия нужно сложить. Отсюда и происходит название данного метода^[2].

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

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

Замечание

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