3.2.2. Реализация КИХ-фильтров с помощью дискретного преобразования Фурье (ДПФ)

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

Пусть  - линейная свертка последовательности конечной протяженности  с импульсным откликом  КИХ-фильтра

.                                        (3.7)

Выполнив преобразование Фурье обеих частей этого выражения, получим

.                                     (3.8)

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

.                   (3.9)

Тогда

.                                         (3.10)

Будем считать, как и в разд. 2.2.3, что последовательность  является результатом обратного ДПФ-произведения . В этом случае  в соответствии с выражениями (2.52) и (2.53) представляет собой циклическую свертку  и . Если  и  выбраны достаточно большими, то, как и требуется, . Для выполнения -точечных преобразований Фурье последовательностей  и  опорные области обеих этих последовательностей должны быть расширены и дополнены отсчетами с нулевыми значениями.

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

Чтобы определить число умножений, необходимых для вычисления значений всех выходных отсчетов, предположим, что коэффициенты  вычислены заранее и хранятся в памяти. Тогда для вычисления значений отсчетов выходного массива требуется выполнить два ДПФ (одно прямое и одно обратное). При использовании алгоритма разбиения на строки и столбцы с учетом вещественности значений  и  общее число вещественных умножений для вычисления  составит

                                                             (3.11)

в предположении, что  и  являются степенями числа 2. Для опорной области линейной свертки , представляющей собой прямоугольник размером  отсчетов, потребуется

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