21. Алгоритмы быстрого преобразования Фурье и их применения.

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

(1)

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

Рисунок 1: Замена N-точечного ДПФ двумя N/2-точечными ДПФ

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

Рисунок 2: Разбиение и объединение последовательностей при N = 8

Каждое разбиение делит последовательность на две половинной длительности (красную и синюю), а каждое объединение «собирает » из двух последовательностей одну удвоенной длительности.

Алгоритмы БПФ, которые используют выборки длиной  называются «алгоритмами БПФ по основанию 2». Данные алгоритмы получили наибольшее распространение, из-за того что в машинной арифметике  является «круглым» числом. Далее мы будем рассматривать только алгоритмы по основанию 2.

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

Существует два способа разбиения — объединения: прореживание по времени и прореживание по частоте.

Перед тем как рассматривать способы разбиения — объединения нужно рассмотреть обратное дискретное преобразование Фурье (ОДПФ):

,

(2)

которое ставит в соответствие  комплексным отсчетам спектра ,   комплексных значений сигнала , .

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

Имея алгоритм вычисления БПФ очень бы хотелось использовать его и для обратного преобразования. Для этого обратим внимание на то что:

.

(3)

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

Рассмотрим произведение на комплексно-сопряженное :

.

(4)

Теперь рассмотрим произведение комплексно-сопряженного  на :

.

(5)

Сравнивая (4) и (5) можно сделать вывод:

.

(6)

Применительно для выражения ОДПФ можно записать:

(7)

Таким образом берется комплексно-сопряженный спектр  выполняется прямое ДПФ и результат подвергается комплексному сопряжению. Вычисление ОДПФ при использовании ДПФ приведено рисунке 3.

Рисунок 3: Вычисление обратного ДПФ через прямое

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