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

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