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

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

Вычисление

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

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

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

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

где

x k ( n ) = { x ( n ) , n ∈ [ k L , ( k + 1 ) L − 1 ] , 0 , n ∉ [ k L , ( k + 1 ) L − 1 ] . {displaystyle x_{k}(n)=left{{egin{array}{rl}x(n),&nin [kL,,(k+1)L-1],,&n otin [kL,,(k+1)L-1].end{array}} ight.}

Тогда

y ( n ) = ∑ m = 0 N − 1 h ( m ) ∑ k = 0 + ∞ x k ( n − m ) = ∑ k = 0 + ∞ h ( n ) ∗ x k ( n ) = ∑ k = 0 + ∞ y k ( n ) . {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).}

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

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

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

Замечание

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