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

Содержание
Введение
Дискретное преобразование Фурье (ДПФ), на сегодняшний день, один из распространенных инструментов анализа, который применяется во всех отраслях науки и техники. Однако до появления компьютеров ДПФ использовалось редко, поскольку вычисление 32-точечного ДПФ требует 1024 операции комплексного умножения и сложения.
Первое упоминание об алгоритме разложения функций в тригонометрический ряд, в котором использовались свойства периодичности тригонометрических функций для ускоренного расчета, относится к работам Гаусса [1]. На эту работу долгое время никто не обращал внимания, до тех пор пока алгоритмы быстрого преобразования Фурье (БПФ) не получили широкое распространение.
Первая программная реализация алгоритма БПФ была осуществлена в начале 60-х годов XX века Джеймсом Кули в вычислительном центре IBM под руководством Джона Тьюки, а в 1965 году, ими же, была опубликована статья [2], посвященная алгоритму быстрого преобразования Фурье. С этого момента начинается настоящая БПФ-мания. Публикуется множество работ, посвященных алгоритму БПФ, одна за одной выходят монографии, программисты соревнуются в эффективности реализации алгоритма. БПФ становится основным инструментом спектрального анализа сигналов.
Нужно заметить, что принцип построения быстрых алгоритмов, путем рекурсивного сведения к задачам меньшего размера был впервые использован советским математиком Анатолием Алексеевичем Карацубой для реализации быстрого алгоритма перемножения чисел (умножение Карацубы) [3]. В результате была опровергнута «гипотеза $n^2$», сформулированная Колмогоровым для оценки сложности перемножения $n-$значных чисел. Сегодня данный принцип построения быстрых алгоритмов носит название «разделяй и властвуй» [4] (англ. divide and conquer) и используется для широкого круга задач: БПФ, быстрого поиска, быстрого матричного умножения и других.
Принцип построения алгоритмов БПФ
Рассмотрим выражение для дискретного преобразования Фурье:
$$ S(k) = \sum_{n= 0}^{N-1} s(n) \cdot \exp \left( -j \cdot \frac{2\pi}{N} \cdot n \cdot k\right), \text{ } k = 0 \ldots N-1. $$
(1)
ДПФ $N$ отсчетам сигнала $s(n)$, $n=0 \ldots N-1$ (в общем случае комплексного) ставит в соответствие $N$ комплексных спектральных отсчетов $S(k)$, $k=0 \ldots N-1$. Для вычисления одного спектрального отсчета требуется $N$ операций комплексного умножения и сложения. Таким образом, вычислительная сложность алгоритма ДПФ составляет $N^2$ операций комплексного умножения и сложения.
Поскольку сложность алгоритма растет квадратично относительно размера входного сигнала, можно достичь существенного ускорения вычисления, если нам удастся свести расчет $N-$точечного ДПФ к двум $\frac{N}{2}-$точечным ДПФ, как это показано на рисунке 1.

Рисунок 1. Замена $N-$точечного ДПФ двумя $\frac{N}{2}-$точечными ДПФ
Замена одного $N-$точечного ДПФ двумя $\frac{N}{2}-$точечными ДПФ приведет к уменьшению количества операций в 2 раза, но дополнительно требуются операции разделения последовательности на две и объединение двух $\frac{N}{2}-$точечных ДПФ в одно $N-$точечное.
При этом каждое из $\frac{N}{2}-$точечных ДПФ также можно вычислить путем замены $\frac{N}{2}-$точечного ДПФ на два $\frac{N}{4}-$точечных, которые, в свою очередь, можно рассчитать через $\frac{N}{8}-$точечные ДПФ. Эту рекурсию можно продолжать, пока возможно разбить входную последовательность на две.
В нашем случае, если $N = 2^L$, $L$ — это положительное целое, мы можем разделить последовательность пополам $L$ раз. Для $N = 8$ ($L=3$) такое разделение представлено на рисунке 2.

Рисунок 2. Разделение и объединение последовательности для $N=8$
Алгоритмы БПФ, которые используют выборки длиной $N = 2^L$, называются «алгоритмами БПФ по основанию 2». Данные алгоритмы получили наибольшее распространение из-за их высокой эффективности и относительной простоты программной реализации.
Мы рассмотрим два способа разделения — объединения: прореживание по времени и прореживание по частоте.
Обратное быстрое преобразование Фурье
Эффективный алгоритм вычисления прямого БПФ можно использовать и для обратного преобразования. Обратим внимание, что комплексные экспоненты в выражениях для прямого и обратного ДПФ являются комплексно-сопряженными:
$$ \exp \left( j \cdot \frac{2\pi}{N} \cdot n \cdot k \right) = \Biggl(\exp \left( -j \cdot \frac{2\pi}{N} \cdot n \cdot k \right) \Biggr)^{*}, $$
(2)
где $(\bullet)^*$ - оператор комплексного сопряжения.
Нетрудно показать, что для двух комплексных чисел $x = a+j \cdot b$ и $y = c+j \cdot d$ справедливо следующее равенство:
$$ x \cdot y^* = \left(x^* \cdot y \right)^*. $$
(3)
Применительно для выражения ОДПФ можно записать:
$$ s(n) = \frac{1}{N} \sum_{k = 0}^{N-1} S(k) \cdot \Biggl(\exp \left(-j \cdot \frac{2\pi}{N} \cdot n \cdot k \right) \Biggr)^* = \frac{1}{N} \Biggl(\sum_{k = 0}^{N-1} S^*(k) \cdot \exp \left(-j \cdot \frac{2\pi}{N} \cdot n \cdot k \right) \Biggr)^*. $$
(4)
Таким образом, берется комплексно-сопряженный спектр $S^*(k)$, выполняется прямое ДПФ и результат подвергается комплексному сопряжению. Вычисление ОДПФ при использовании ДПФ приведено рисунке 3.

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

Ваши комментарии, вопросы и пожелания вы можете оставить на форуме или в гостевой книге.
Список литературы
[1] M. Heideman, D. Johnson, C. Burrus Gauss and the history of the fast fourier transform. IEEE ASSP Magazine, Vol. 1, Issue 4, October 1984, p. 14-21

[2] James W. Cooley and John W. Tukey An Algorithm for the Machine Calculation of Complex Fourier Series. Mathematics of Computation, 1965 p. 297–301.

[3] Офман Ю.П., Карацуба А.А. Умножение многозначных чисел на автоматах. Доклады АН СССР. 1962, Т. 145, С. 293—294

[4] Ахо Альфред В., Хопкрофт Д., Ульман Джеффри Д. Структуры данных и алгоритмы. Москва, Вильямс, 2003.

[5] Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. Москва, Мир, 1989.

[6] Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. Москва, Радио и связь, 1985.

[7] Оппенгейм А., Шафер Р. Цифровая обработка сигналов. Москва, Техносфера, 2006.

[8] Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов. Москва, Радио и связь, 1985.

[9] Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. Москва, Мир, 1978.

[10] Сергиенко А.Б. Цифровая обработка сигналов. Санкт-Петербург, Питер, 2002.

Oбнаружили ошибку в тексте? Выделите ее мышкой и нажмите