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

Во многих практических задачах необходимо вычислять свертку двух конечных последовательностей, когда одна из них гораз­до длиннее другой (скажем, N₁ » N₂ или N₂ » N₁). Конечно, всег­да можно выбрать L = N₁ + N₂ – 1, но такой подход неэффективен и по ряду причин неудобен. Во-первых, перед вы­числением свертки нужно иметь всю более длинную последователь­ность. На практике, например в радиолокации или при обработ­ке речевых сигналов, это условие не всегда выполнимо. Во-вторых, поскольку обработка начинается только после приема всей после­довательности, то результат получается с большой задержкой. И наконец, при слишком больших (N₁ + N₂ – 1) вычисление ДПФ значительно усложняется, – требуется большой объем памяти и возникают некоторые другие, чисто практические трудности, связанные с алгоритмами БПФ.

От перечисленных недостатков свободны два метода вычисления свертки: метод перекрытия с суммирова­нием и метод вычисления линейной свертки последовательно­стей. Методы основаны на разбиении длинной последовательности на секции и вычислении частичных сверток, из которых затем форми­руется искомая выходная последовательности.

Первый из двух методов, называемый методом перекрытия с суммирова­нием, иллюстрируется рисунком 6.4. Для простоты положим, что последовательность x(n) не ограничена, а последовательность h(n) содержит N₂ отсчетов. Разделим последовательность x(n) на смежные секции длиной по N₃ отсчетов – рис. 4.

Выбор N₃ довольно сложен, но хорошие результаты получаются, если N₃ – величина того же порядка, что и N₂. Входная по­следовательность x(n) представляется в виде

x(n) = x_k(n), (6)

где x_k(n) =

Линейная свертка последовательностей x(n) и h(n)

y(n) =h(m)x_k(n – m)

или y(n) =h(n)_*x_k(n) =y_k(n). (7)

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

Каждая из частичных сверток в сумме (7) длиной (N₁ + N₂ – 1) отсчетов содержит участок длиной в (N₂ – 1) отсчетов, на котором k-я и

(k + 1)-я частичные свертки перекрываются, поэтому их отсчеты на участке перекрытия нужно сло­жить.

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

На рис. 5 показано расположение и суммирование соседних частичных сверток y_k(n). Каждая из частичных сверток вычисляется методом быстрой свертки (с помощью БПФ). Рассмотренный метод был назван методом перекрытия с суммированием имен­но потому, что промежуточные частичные свертки перекрывают­ся и для получения конечного результата их необходимо сложить.

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

Другой метод вычисления линейной свертки последовательно­стей, одна из которых значительно длиннее другой, также основан на секционировании более длинной последовательности. Его на­зывают методом перекрытия с накоплением, причем в данном слу­чае перекрываются входные, а не выходные секции. Ошибочные отсчеты круговых сверток отдельных секций отбрасываются. Остальные отсчеты накапливаются и из них формируется конеч­ный результат.

Рассмотрим пример – рис. 6. По­следовательность h(n)содержит N₂ отсчетов, а последователь­ность x(n) разделена на секции x_k(n) длиной по (N₃ + N₂ – 1) отсчетов, перекрывающиеся друг с другом на участках дли­ной по (N₂ – 1) отсчетов. (Отметим, что участок перекрытия находится в конце последовательности x_k(n). Это удобно для вычисления круговой свертки с помощью ДПФ.) Здесь перекрытие носит условный характер: последние (N₂ – 1) отсчетов секции повторяют первые (N₂ – 1) отсчетов предыдущей секции. Для каждой секции вычисляется круговая свертка последовательно­стей h(n) и x_k(n), содержащая (N₃ + N₂ – 1) отсчет. В резуль­тате получается набор последовательностей y_k(n) – рис. 7

Последние (N₂ – 1) отсчетов каждой из после­довательностей y_k(n) отбрасываются (они неверны из-за цикличе­ского характера свертки), а остальные присоединяются к правиль­ным отсчетам последовательности y_k–1(n) и т. д. В результате получается искомая последовательность, тождественная свертке y(n). Итак, используя метод перекрытия с суммированием или метод перекрытия с накоплением, можно сравнительно легко найти свертку короткой и очень длинной последовательностей, причем результат получается в виде отдельных небольших секций, кото­рые объединяются соответствующим образом в одну последова­тельность.

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

Лекция 6

Цифровые фильтры