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

Вычисление

Пусть ${\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)}$ -я частичные свёртки перекрываются, поэтому их отсчёты на участке перекрытия нужно сложить. Отсюда и происходит название данного метода .

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

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

Замечание

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

Примечания

Литература

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