2.3. Вычисление дискретного преобразования Фурье

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

2.3.1. Прямое вычисление

Прямое вычисление двумерного ДПФ - это просто вычисление двойной суммы

 для  и ,                       (2.71)

где, как и прежде, .

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

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