Быстрое преобразование Фурье, БПФ, Fast Furier Transform, FFT
-
алгоритм вычисления преобразования Фурье для дискретного случая. В отличие от простейшего алгоритма, который имеет сложность порядка O(N2), БПФ имеет сложность всего лишь O(Nlog2N). Алгоритм БПФ был впервые опубликован в 1965 году в статье Кули (Cooly) и Тьюки (Tukey).
Данное руководство содержит исходный код работающей программы для вычисления
БПФ, подробное объяснение принципа ее работы и теоретическое обоснование.
Все это можно найти и на других ресурсах, но трудно найти именно в таком
комплекте: и программа, и объяснения, и теория, и на русском языке.
Если у вас нет времени и желания разбираться с теорией, то можете сразу
скопировать текст программы на C++. Здесь находится
заголовочный файл fft.h и исходник fft.cpp для быстрого преобразования Фурье
для числа отсчетов, равного степени двойки. Вызывать надо функцию fft.
А здесь находится заголовочный файл и исходник для
произвольного (!) числа отсчетов. Он чуть медленнее, но скорость там тоже
порядка Nlog2N. Вызывать надо функцию universal_fft.
Определения
Определение 1
Дана конечная последовательность x0, x1, x2,...,xN-1 (в общем случае комплексных). Дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности X0, X1, X2,...,XN-1 элементы которой вычисляются по формуле:
(1).
Определение 2
Дана конечная последовательность X0, X1, X2,...,XN-1 (в общем случае комплексных). Обратное дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности x0, x1, x2,...,xN-1 элементы которой вычисляются по формуле:
(2).
Основным свойством этих преобразований (которое доказывается в соответствующих разделах математики) является тот факт, что из последовательности {x} получается (при прямом преобразовании) последовательность {X}, а если потом применить к {X} обратное преобразование, то снова получится исходная последовательность {x}.
Определение 3
Величина
называется поворачивающим множителем.
Рассмотрим ряд свойств поворачивающих множителей, которые нам понадобятся в дальнейшем.
Верхняя цифра в поворачивающем множителе не является индексом, это - степень. Поэтому, когда она равна единице, мы не будем ее писать:
Прямое преобразование Фурье можно выразить через поворачивающие множители. В результате формула (1) примет вид:
(3).
Эти коэффициенты действительно оправдывают свое название. Нарисуем на комплексной плоскости любое комплексное число, в виде вектора, исходящего из начала координат. Представим это комплексное число в показательной форме: rejφ, где r - модуль числа, а φ - аргумент. Модуль соответствует длине вектора, а аргумент - углу поворота:
Теперь возьмем какой-нибудь поворачивающий множитель . Его модуль равен единице, а фаза - 2π/N. Как известно, при умножении комплексных чисел, представленных в показательной форме, их модули перемножаются, а аргументы суммируются. Тогда умножение исходного числа на поворачивающий множитель не изменит длину вектора, но изменит его угол. То есть, произойдет поворот вектора на угол 2π/N (см. предыдущий рисунок).
Если теперь посмотреть на формулу (3), то станет ясен геометрический смысл преобразования Фурье: он состоит в том, чтобы представить N комплексных чисел-векторов из набора {x}, каждое в виде суммы векторов из набора {X}, повернутых на углы, кратные 2π/N.
Знаете ли Вы, как разрешается парадокс Ольберса? (Фотометрический парадокс, парадокс Ольберса - это один из парадоксов космологии, заключающийся в том, что во Вселенной, равномерно заполненной звёздами, яркость неба (в том числе ночного) должна быть примерно равна яркости солнечного диска. Это должно иметь место потому, что по любому направлению неба луч зрения рано или поздно упрется в поверхность звезды. Иными словами парадос Ольберса заключается в том, что если Вселенная бесконечна, то черного неба мы не увидим, так как излучение дальних звезд будет суммироваться с излучением ближних, и небо должно иметь среднюю температуру фотосфер звезд. При поглощении света межзвездным веществом, оно будет разогреваться до температуры звездных фотосфер и излучать также ярко, как звезды. Однако в дело вступает явление "усталости света", открытое Эдвином Хабблом, который показал, что чем дальше от нас расположена галактика, тем больше становится красным свет ее излучения, то есть фотоны как бы "устают", отдают свою энергию межзвездной среде. На очень больших расстояниях галактики видны только в радиодиапазоне, так как их свет вовсе потерял энергию идя через бескрайние просторы Вселенной. Подробнее читайте в FAQ по эфирной физике.
(1). 
(2). 
(3). 
. Его модуль равен единице, а фаза - 2π/N. Как известно, при умножении комплексных чисел, представленных в показательной форме, их модули перемножаются, а аргументы суммируются. Тогда умножение исходного числа на поворачивающий множитель не изменит длину вектора, но изменит его угол. То есть, произойдет поворот вектора на угол 2π/N (см. предыдущий рисунок). 
