Быстрое преобразование Фурье

Быстрое преобразование Фурье (БПФ) - это алгоритм вычисления преобразования Фурье для дискретного случая. В отличие от простейшего алгоритма, который имеет сложность порядка O(N² ), БПФ имеет сложность всего лишь O(Nlog₂ N). Алгоритм БПФ был впервые опубликован в 1965 году в статье Кули (Cooly) и Тьюки (Tukey).

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

Если у вас нет времени и желания разбираться с теорией, то можете сразу скопировать текст программы на C++. Здесь находится заголовочный файл fft.h и исходник fft.cpp для быстрого преобразования Фурье для числа отсчетов, равного степени двойки. Вызывать надо функцию fft. А здесь находится заголовочный файл и исходник для произвольного (!) числа отсчетов. Он чуть медленнее, но скорость там тоже порядка Nlog₂ N. Вызывать надо функцию universal_fft.

Определение 1 .

Дана конечная последовательность x₀ , x₁ , x₂ ,...,x_N-1 (в общем случае комплексных). Дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности X₀ , X₁ , X₂ ,...,X_N-1 элементы которой вычисляются по формуле:

(1).

Определение 2 .

Дана конечная последовательность X₀ , X₁ , X₂ ,...,X_N-1 (в общем случае комплексных). Обратное дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности x₀ , x₁ , x₂ ,...,x_N-1 элементы которой вычисляются по формуле:

(2).

Основным свойством этих преобразований (которое доказывается в соответствующих разделах математики) является тот факт, что из последовательности {x} получается (при прямом преобразовании) последовательность {X}, а если потом применить к {X} обратное преобразование, то снова получится исходная последовательность {x}.

Определение 3 .

Величина

называется поворачивающим множителем .

Рассмотрим ряд свойств поворачивающих множителей, которые нам понадобятся в дальнейшем.

Верхняя цифра в поворачивающем множителе не является индексом, это - степень. Поэтому, когда она равна единице, мы не будем ее писать:

Прямое преобразование Фурье можно выразить через поворачивающие множители. В результате формула (1) примет вид:

(3).

Эти коэффициенты действительно оправдывают свое название. Нарисуем на комплексной плоскости любое комплексное число, в виде вектора, исходящего из начала координат. Представим это комплексное число в показательной форме: re^jφ , где r - модуль числа, а φ - аргумент. Модуль соответствует длине вектора, а аргумент - углу поворота:

Теперь возьмем какой-нибудь поворачивающий множитель . Его модуль равен единице, а фаза - 2π/N. Как известно, при умножении комплексных чисел, представленных в показательной форме, их модули перемножаются, а аргументы суммируются. Тогда умножение исходного числа на поворачивающий множитель не изменит длину вектора, но изменит его угол. То есть, произойдет поворот вектора на угол 2π/N (см. предыдущий рисунок).

Если теперь посмотреть на формулу (3), то станет ясен геометрический смысл преобразования Фурье: он состоит в том, чтобы представить N комплексных чисел-векторов из набора {x}, каждое в виде суммы векторов из набора {X}, повернутых на углы, кратные 2π/N.

Теорема 0 .

Если комплексное число представлено в виде e ^j2πN , где N - целое, то это число e ^j2πN = 1.

Доказательство :

По формуле Эйлера, и ввиду периодичности синуса и косинуса:

e ^{j2 π N} = cos(2πN) + j sin(2πN) = cos 0 + j sin 0 = 1 + j0 = 1

Теорема 1 .

Величина периодична по k и по n с периодом N. То есть, для любых целых l и m выполняется равенство:

(4).

Доказательство :

(5)

Величина -h = -(nl+mk+mlN) - целая, так как все множители целые, и все слагаемые целые. Значит, мы можем применить Теорему 0:

Что и требовалось доказать по (4).

Теорема 2 .

Для величины справедлива формула:

Доказательство :

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

1. Необходимо разделить сумму (1) из N слагаемых на две суммы по N/2 слагаемых, и вычислить их по отдельности. Для вычисления каждой из подсумм, надо их тоже разделить на две и т.д.
2. Необходимо повторно использовать уже вычисленные слагаемые.

Применяют либо "прореживание по времени" (когда в первую сумму попадают слагаемые с четными номерами, а во вторую - с нечетными), либо "прореживание по частоте" (когда в первую сумму попадают первые N/2 слагаемых, а во вторую - остальные). Оба варианта равноценны. В силу специфики алгоритма приходится применять только N, являющиеся степенями 2. Рассмотр

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать