Как работает быстрое преобразование Фурье
(перевод с английского)
Англоязычный вариант статьи: http://www.dspguide.com/ch12/2.htm
Быстрое преобразование Фурье (БПФ) - это сложный алгоритм, и его детали, обычно изучают те, кто занимается вопросами цифровой обработки сигналов. Этот раздел описывает общие принципы работы БПФ, основанного на использовании комплексных чисел. Если вы имеете опыт работы в комплексной математике, то легко поймете истинный смысл алгоритма. Не волнуйтесь, если от вас ускользнут некоторые детали: мало ученых и инженеров, которые используют БПФ, могут написать программу с нуля.
В частотной и временной области сигнал представлен N комплексными точками. Каждая из этих точек состоит из двух чисел: действительной и мнимой части. Например, когда мы говорим о комплексном отсчете X [42], речь идет о комбинации ReX [42] и ImX [42]. После умножения двух комплексных переменных, необходимо объединить четыре отдельные компоненты в две. Дальнейшее обсуждение темы «Как работает БПФ» использует специфические термины: сигнал, точка, отсчёт и значение представляют собой сочетание реальной и мнимой частей.
БПФ работает с разложением N-точечного временного промежутка сигнала на N временных сигнальных промежутков, каждый из которых состоял из одной точки. Второй шаг заключается в расчете N частотных спектров, соответствующего этим временным сигнальным промежуткам. После этого, на основе N спектров синтезируется единый частотный спектр.
Рисунок 12.2 показывает пример разделения временной области с использованием БПФ. В этом примере 16-ти точечный сигнал разлагается на четыре отдельные компоненты. Первый этап заключается в разбиения 16-ти точечного сигнала на два сигнала по 8 точек. На втором этапе происходит разложение данных сигналов на четыре сигнала по 4 точки. Данная процедура продолжается до тех пор, пока не будет сформировано N сигналов состоящих из одной точки. Черезстрочное разложения используется при разделении выборки сигнала на две выборки. Сигнал разделяется как при четном, так и при нечетном количестве отсчетов в выбороке. В системе проводится 2N этапов в разложении, т.е. на 16–ти точечный сигнал (24) предусматривает 4 этапа, 512 точки (27) требует 7 этапов, 4096 точки (212) предусматривает 12 этапов и т.д. Запомним, это значение - оно будет много раз встречаться в этой главе.
Рисунок 12.2 - Процедура разбиения сигнала
Теперь, когда понятна структура разложения, ее можно значительно упростить. Разложения является не более чем перераспределение отсчетов сигнала. Это иллюстрирует рисунок 12.3. Слева представлены номера отсчетов первоначального сигнала, вместе с их двоичными эквивалентами. Справа, измененные номера, а также их двоичные эквиваленты. Идея состоит в том, что двоичные числа являются инверсией друг друга. Например, отсчёт №3 (0011) можно получить из отсчёта №12 (1100). Отсчёт № 14 (1110) получается из отсчета № 7 (0111), и так далее. Разбиение временной области в БПФ обычно, проводится с использование алгоритма сортировки инвертированных бит. Это предполагает изменение N временных областей, с подсчетом в двоичном виде и переворачиванием бит слева на право (например, в крайней правой колонке в Рис. 12.3).
Рисунок 12.3 - Процедура перераспределения отсчетов сигнала
Следующим шагом алгоритма БПФ является нахождение частоты спектров одноточечного сигналов, определенного во временной области. Это делается элементарно: спектр одноточечного сигнала равен самому себе. Это означает, что на этом шаге ничего не надо. Хотя не стоит забывать, что каждый из одноточечных сигналов теперь представляет собой спектр частот, а не сигнал во временной области
Последний шаг в БПФ состоит в том, чтобы объединить N спектров частот в обратном по отношению ко временному разделению порядке. В этом случае алгоритм работает некорректно. К сожалению, обратное быстрое преобразование не применяется, а мы должны вернуться на каком-то этапе ко времени. На первом этапе, 16 одноточечных частотных спектра объединяются в 8 частотных спектра по 2 точки каждый. На втором этапе 8 частотных спектров синтезируется в 4 спектра, и так далее. На последнем этапе получаем результат БПФ в виде 16 точечного частотного спектра.
Рисунок 12.4 показывает, как два частотных спектра, каждый из которых состоял из 4 точек, объединены в единый частотный диапазон на 8 очков. Объединение должно исключить одинаковые разложения во временной области. Иными словами, операция в частотной области должна соответствовать операции во временной области с исключением пересечений. Рассмотрим два сигналы временной области. 8 точечный временной сигнал формирутеся в два этапа: разбавлением каждого 4-точечного сигнала нулями, для того, чтобы получить 8-ми точечный сигнал, а затем объединять сигналы вместе. Поэтому сигнал 1 превращается в a0b0c0d0, а 2 станет 0e0f0g0h. Суммирование этих двух сигналов дает 8-точечный сигнал aebfcgdh. Как показано на рис. 12.4, дополнение временной реализации сигнала нулями соответствует дублированию частотного спектра. Таким образом, спектры частот в БПФ, дублируются, а потом прибавляет один к другому.
Рисунок 12.4 - Процедура синтеза частотного спектра сигнала
Для достижения соответствия, двух сигналов во временной области разбавляются нулями в немного другом виде. В одном сигнала, нечетные отсчеты равны нулю, а в другом сигнале четные отсчеты равны нулю. Иными словами, один из сигналов временной области (0e0f0g0h на рис. 12.4) сдвигается вправо на один отсчет. Этот сдвиг во временной области соответствует умножения на спектр синуса. Чтобы увидеть это, вспомним, что сдвиг во времененной области эквивалентен свертыванию сигнала со смещенной дельта-функцией. Спектр смещенной дельта функция является синусоидой.
Рисунок 12.5 показывает схема совмещения двух 4-х точечных спектра в один 8-ми точечный. Заметим, что рис. 12.5 формируется по базовой схеме рис 12.6 с повторением вновь и вновь.
Рисунок 12.5 - схема совмещения двух 4-х точечных спектра в один 8-ми точечный.
Эта простая схема называется «бабочка» в силу своего крылатого вида. «Бабочка» является основным вычислительным элементом БПФ, преобразовывая две комплексные точки в две другие.
Рисунок 12.6 - Cхема «бабочки»
Рисунок 12.7 показывает структуру БПФ. Разбиение во временной области выполняется с помощью ранее рассмотренного алгоритма сортировки.
Синтез в частотной области требует трех циклов. Внешний цикл проводится Log2N раз. Средний цикл движется по каждой отдельной частоте спектра. Внутренний цикл использует бабочку для расчета точек в каждой частоты спектра (т.е. циклы через образцы внутри одного окна на рис. 12.2). Накладных клетки на рис. 12.7 определяют начало и окончания индексов в циклах, а также расчета необходимых синусоиды бабочек. Блок-схема программы, реализующая БПФ приведена на рис. 12.7.
Рисунок 12.7 - Блок-схема программы, реализующая БПФ