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

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

С другой стороны, реализация с ДПФ требует значительных объемов памяти. Методы секционирования свертки являются компромиссным решением. Суть их заключается в том, что операция свертки выполняется над секциями или блоками данных с использованием ДПФ. Ограничение размера секций уменьшает объем требуемой памяти, а использование ДПФ сохраняет вычислительную эффективность процедуры.

Простейший для понимания метод секционированной свертки носит название метода перекрытия с суммированием. Разделим двумерный массив  на -точечные секции, определив секцию с индексами  следующим образом:

                (3.12)

Опорная область для одной такой секции изображена на рис. 3.1,а. Опорные области секций не перекрываются, и все вместе покрывают всю опорную область массива , поэтому

.                                                        (3.13)

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

а - секция входной последовательности ; б - опорная область результата свертки этой секции с .

В силу того что операция дискретной свертки дистрибутивна по отношению к сложению, можно записать

     (3.14)

Выходная секция  представляет собой результат свертки  с секцией  последовательности . Для получения полного выходного сигнала фильтра  эти частичные результаты нужно сложить. Поскольку опорная область секции  больше опорной области секции , выходные секции должны перекрываться, хотя степень перекрытия ограничена. На рис. 3.1,б изображена такая опорная область одной из выходных секций.

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

Другой разновидностью секционированной свертки является метод перекрытия с накоплением. Взглянув еще раз на рис. 3.1, можно заметить, что если размер секции существенно превышает размер опорной области отклика , то отсчеты  в центре каждой секции не перекрываются отсчетами из соседних секций. Точно так же при циклической свертке последовательности  с другой последовательностью , имеющей гораздо меньшую опорную область, только часть отсчетов циклической свертки будет испытывать эффект пространственного наложения. Остальные отсчеты будут идентичны отсчетам линейной свертки. Расположение этих отсчетов показано на рис. 3.2. Таким образом, если выполнить циклическую свертку -точечной секции последовательности  с -точечным импульсным откликом с использованием -точечного ДПФ, результат этой свертки будет содержать область, состоящую из  отсчетов, идентичных отсчетам линейной свертки . Полный выходной массив можно составить из этих «хороших» отсчетов при правильном выборе опорных областей входных секций. Если входные секции перекрываются, можно добиться того, чтобы «хорошие» области соседних секций примыкали друг к другу. Таким образом, метод перекрытия с накоплением требует перекрытия входных секций, в то время как при использовании метода перекрытия с суммированием перекрываются выходные секции.

Рис. 3.2. Метод перекрытия с накоплением. Заштрихованная область содержит отсчеты , для которых циклическая свертка с периодом  и линейная свертка  с  дают идентичные результаты.

Для процедур перекрытия как с суммированием, так и с накоплением выбор размеров секций сильно влияет на эффективность реализации. Прежде всего этот выбор очевидным образом влияет на объем требуемой памяти, а также и на объем вычислений. Из рис. 3.2 видно, что доля полезных отсчетов циклической свертки возрастает по мере увеличения размеров секции по отношению к размерам импульсного отклика. Хотя какие-то общие утверждения относительно того, сколь велики должны быть входные секции, затруднены из-за сильной зависимости результатов от конкретной ЭВМ, эксперименты Тугуда и др. [1] показали, что для фильтров с размерами опорной области от  до  выборок требуется размер секций . Это слишком много для большинства мини-ЭВМ. Таким образом, получается, что быстродействие алгоритма ограничивается доступной памятью. Если это так, то следует выбирать входные секции максимально возможного размера.