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

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

Вычисление

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

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

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

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

где

$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.$

Тогда

$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).$

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

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

Пусть теперь длина секций $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$.

Замечание

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

Литература

• Рабинер, Л., Гоулд, Б.. Теория и применение цифровой обработки сигналов. — М.: Мир, 1978.