1.4.4. Секционированные свертки

В том случае, когда одна из последовательностей гораздо длиннее другой или используют процедуры, основанные на разбиении длинной последовательности на короткие секции и вычислении частичных сверток, из которых формируется искомая линейная свертка. Существуют два метода с

Рис. 1.14 (см. скан)

секционированием свертки [1.6]: метод перекрытия с суммированием и метод перекрытия с накоплением.

Метод перекрытия с суммированием. Графическая иллюстрация метода приведена на рис. 1.14.

Пусть более длинной, а в общем случае неограниченной является последовательность содержит отсчетов. Последовательность делится на смежные секции по отсчетов, так что

Вычисляем частичную линейную свертку последовательностей Каждая частичная свертка имеет длину и перекрывается с -частичной сверткой на участке длиной в отсчетов. Поэтому на участке перекрытия их отсчеты нужно сложить. Проделывая указанные действия для всех получаем искомую свертку:

Метод перекрытия с накоплением. Графическая иллюстрация метода приведена на рис. 1.15. В данном случае перекрываются не выходные, а входные секции. Пусть содержит отсчетов. Длинная последовательность делится на секции по отсчетов, так что каждые две соседние перекрываются на участке длиной в отсчетов. Последовательность дополняется нулями до получения длины в отсчетов:

Находим частичную круговую свертку последовательностей Последние (неверные из-за циклического характера круговой свертки) отсчетов каждой из последовательностей отбрасываются, а остальные присоединяются к верным отсчетам -й секции. Проделывая описанную процедуру для всех получаем искомую свертку.