Принцип построения алгоритмов быстрого преобразования Фурье

Вводные замечания Принцип построения алгоритмов БПФ Обратное быстрое преобразование Фурье Выводы Список литературы

DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов Распространяется под лицензией LGPL v3 Страница проекта на SourceForge

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

Первое упоминание об алгоритме разложения функций в тригонометрический ряд, в котором использовались свойства периодичности тригонометрических функций для ускоренного расчета, относится к работам Гаусса [1]. На эту работу долгое время никто не обращал внимания, до тех пор пока алгоритмы быстрого преобразования Фурье (БПФ) не получили широкое распространение.

Первая программная реализация алгоритма БПФ была осуществлена в начале 60-х годов XX века Джеймсом Кули в вычислительном центре IBM под руководством Джона Тьюки, а в 1965 году, ими же, была опубликована статья [2], посвященная алгоритму быстрого преобразования Фурье. С этого момента начинается настоящая БПФ-мания. Публикуется множество работ, посвященных алгоритму БПФ, одна за одной выходят монографии, программисты соревнуются в эффективности реализации алгоритма. БПФ становится основным инструментом спектрального анализа сигналов.

Нужно заметить, что принцип построения быстрых алгоритмов, путем рекурсивного сведения к задачам меньшего размера был впервые использован советским математиком Анатолием Алексеевичем Карацубой [3] для реализации быстрого алгоритма перемножения чисел (умножение Карацубы). В результате была опровергнута «гипотеза , сформулированная А.Н. Колмогоровым для оценки сложности перемножения -значных чисел.

Сегодня данный принцип построения быстрых алгоритмов носит название «разделяй и властвуй» [4] (англ. divide and conquer) и используется для широкого круга задач: БПФ, быстрого поиска, быстрого матричного умножения и других.

Рассмотрим выражение для дискретного преобразования Фурье:

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

Поскольку сложность алгоритма растет квадратично относительно размера входного сигнала, можно достичь существенного ускорения вычисления, если нам удастся свести расчет -точечного ДПФ к двум -точечным ДПФ, как это показано на рисунке 1.

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

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

В нашем случае, если ,  — это положительное целое, мы можем разделить последовательность пополам раз. Для () такое разделение представлено на рисунке 2.

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

Мы рассмотрим два способа разделения — объединения: прореживание по времени и прореживание по частоте .

Эффективный алгоритм вычисления прямого БПФ можно использовать и для обратного преобразования.

Обратим внимание, что комплексные экспоненты в выражениях для прямого и обратного ДПФ являются комплексно-сопряженными:

где  — оператор комплексного сопряжения.

Нетрудно показать, что для двух комплексных чисел и справедливо следующее равенство: . Применительно для выражения ОДПФ можно записать:

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

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

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

В следующих разделах мы подробно рассмотрим алгоритмы БПФ по основанию два с прореживанием по времени и с прореживанием по частоте .