1.3.2.    Введение в быстрое преобразование Фурье

Быстрое преобразование Фурье (или Fast Fourier Transform – FFT) является не более чем алгоритмом для ускоренного вычисления ДПФ путем сокращения требуемого числа операций умножения и сложения. Данное преобразование было предложено Кули и Тьюки (J.W.Cooley и J.W.Tukey) в 1960-х годах и фактически являлось открытием заново идеи Рунге, Даниэльсона и Ланкоса (Runge (1903 г.), Danielson и Lanczos (1942).

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

Для понимания принципов работы БПФ, рассмотрим ДПФ на 8 точек, представленное в развернутом виде:

;

;

При вычислении частотных коэффициентов необходимо выполнить N2 умножений с комплексными числами. Масштабный коэффициент (N/2) для упрощения не учитывается. Обратите внимание, что для упрощения таблицы мы вводим следующее определение:

.              (1.26)

Это ведет к определению коэффициентов поворота (поворачивающих множителей):

          (1.27)

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

Вычислительная эффективность БПФ по сравнению с ДПФ становится весьма существенной, когда количество

точек БПФ увеличивается до нескольких тысяч, как это следует из таблицы 1.2.

Таблица 1.2 Вычислительная эффективность БПФ в сравнении с ДПФ

Таким образом, БПФ является лишь алгоритмом эффективного вычисления ДПФ. Вычислительная эффективность N-точечного БПФ:

· ДПФ – N2 вычислений с комплексными числами;

· БПФ – (N/2)log2(N) вычислений с комплексными числами

Очевидно, что БПФ вычисляет все компоненты выходного спектра (или все, или ни одного!). Если необходимо рассчитать только несколько точек спектра, ДПФ может оказаться более эффективным. Вычисление одного выходного отсчета спектра с использованием ДПФ требует только N умножений с комплексными числами.