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

Во многих практических задачах необходимо вычислять свертку двух конечных последовательностей, когда одна из них гораздо длиннее другой (скажем,  или). Конечно, всегда можно выбрать  равным , но такой подход неэффективен и по ряду причин неудобен. Во-первых, перед вычислением свертки нужно иметь всю более длинную последовательность. На практике, например в радиолокации или при обработке речевых сигналов, это условие не всегда выполнимо. Во-вторых, поскольку обработка начинается только после приема всей последовательности, то результат получается с большой задержкой. И наконец, при слишком больших  вычисление ДПФ значительно усложняется, так как для этого требуется большой объем памяти и возникают некоторые другие, чисто практические трудности, связанные с алгоритмами БПФ. От перечисленных недостатков свободны следующие два метода вычисления свертки. Они основаны на разбиении более длинной последовательности на секции и вычислении частичных сверток, из которых затем формируется искомая выходная последовательность.

Первый из них называется методом перекрытия с суммированием. Сущность этого метода иллюстрируется на фиг. 2.32. Для простоты положим, что последовательность  не ограничена, a  содержит  отсчетов. Разделим последовательность  на смежные секции длиной по  отсчетов (фиг. 2.32). Выбор  довольно сложен, но хорошие результаты получаются, если  является величиной того же порядка, что и .Итак, входная последовательность  представляется в виде

                  (2.166)

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

где

             (2.167)

Линейная свертка последовательностей  и  равна

       (2.168)

           (2.169)

Фиг. 2.33. Формирование выходных значений свертки при использовании метода перекрытия с суммированием.

Длина каждой из частичных сверток в сумме (2.169) равна  отсчетам, т. е. имеется участок длиной в  отсчетов, на котором -я и -я частичные свертки перекрываются, поэтому их отсчеты на участке перекрытия нужно сложить. На фиг. 2.33 показано, как расположены и как суммируются соседние частичные свертки . Каждая из них вычисляется методом быстрой свертки, описанным в разд. 2.24. Рассмотренный метод был назван методом перекрытия с суммированием именно потому, что промежуточные частичные свертки перекрываются и для получения конечного результата их необходимо сложить.

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

Другой метод вычисления линейной свертки последовательностей, одна из которых значительно длиннее другой, также основан на секционировании более длинной последовательности. Его называют методом перекрытия с накоплением, причем в данном случае перекрываются входные, а не выходные секции. Ошибочные отсчеты круговых сверток отдельных секций отбрасываются. Остальные отсчеты накапливаются и из них формируется конечный результат. Рассмотрим конкретный пример (фиг. 2.34). Последовательность  содержит  отсчетов, а последовательность  разделена на секции  длиной по  отсчетов, перекрывающиеся друг с другом на участках длиной по  отсчетов. (Отметим, что участок перекрытия находится в конце последовательности . Это удобно для вычисления круговой свертки с помощью ДПФ.)

Фиг. 2.35. Формирование выходных значений свертки при использовании метода перекрытия с накоплением.

Для каждой секции вычисляется круговая свертка последовательностей  и , содержащая  отсчет. В результате получается набор последовательностей , изображенных па фиг. 2.35. Последние  отсчетов каждой из последовательностей  отбрасываются (они неверны из-за циклического характера свертки), а остальные присоединяются к правильным отсчетам последовательности  и т. д. В результате получается искомая последовательность, тождественная свертке . Итак, используя метод перекрытия с суммированием или метод перекрытия с накоплением, можно сравнительно легко найти свертку короткой и очень длинной последовательностей, причем результат получается в виде отдельных небольших секций, которые объединяются соответствующим образом в одну последовательность.