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

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

ВычислениеПравить

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

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

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

$x(n)=\underset{k=0}{\overset{+\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{x}_k(n),$$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)=\underset{m=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}h(m)\underset{k=0}{\overset{+\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{x}_k(n-<!--\; -\; -->m)=\underset{k=0}{\overset{+\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}h(n)\ast <!--\; \ast \; -->x_k(n)=\underset{k=0}{\overset{+\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{y}_k(n).$$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$$L+N-1$ , то есть имеется участок длины $N-<!--\; -\; -->1$$N-1$ , на котором $k$$k$ -я и $(k+1)$$(k+1)$ -я частичные свёртки перекрываются, поэтому их отсчёты на участке перекрытия нужно сложить. Отсюда и происходит название данного метода.

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

Пусть теперь длина секций $x_k$$x_k$  последовательности $x$$x$  равна $L+N-<!--\; -\; -->1$$L+N-1$  и у этих секций есть участки перекрытия длиной $N-<!--\; -\; -->1$$N-1$ . Для каждой секции вычисляется циклическая свёртка $h$$h$  и $x_k$$x_k$ , содержащая $L+N-<!--\; -\; -->1$$L+N-1$  отсчёт и обозначаемая $y_k$$y_{k}$ . Необходимо отбросить последние $N-<!--\; -\; -->1$$N-1$  отсчётов этой последовательности, а остальные присоединить к последовательности $y_{k-<!--\; -\; -->1}$$y_{k-1}$ . После выполнения этой процедуры для каждого $k$$k$  получится искомая последовательность $y=x\ast <!--\; \ast \; -->h$$y=x*h$ .

ЗамечаниеПравить

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

ЛитератураПравить

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