БПФ сложный алгоритм, и его детали обычно оставляют для тех, кто специализируется в этих вещах. Этот раздел описывает основные операции БПФ, но обходит стороной ключевой вопрос, использование комплексных чисел. Если вы знакомы с основами математики комплексных чисел, вы можете между строк прочитать истинную природу алгоритма. Не переживайте, если детали ускользнут от вас, немногие ученые и инженеры, которые используют БПФ, могут написать безукоризненную программу.
В комплексной записи временная и частотная области содержат один сигнал из N комплексных точек. Каждая из этих точек состоит из двух чисел, реальной части и мнимой части. Например, когда мы говорим о комплексном числе X[42], это означает комбинацию из ReX[42] и ImX[42]. Другими словами, каждая комплексная переменная содержит два числа. Когда две комплексные переменные перемножаются, четыре индивидуальных компонента должны быть скомбинированы в две компоненты полученного числа (так как в формуле 9-1). Этот раздел «Как работает БПФ» использует жаргон комплексных чисел. То есть, термины: сигнал, точка, отсчет и величина означают комбинацию из реальной части и мнимой части.
БПФ работает путем разложения N точек сигнала временной области на N сигналов временной области, каждый из которых состоит из одной точки. Следующий шаг заключается в вычислении N частотных спектров, соответствующим этим N сигналам. Наконец, N спектров синтезируются в один частотный спектр.
РИСУНОК 12-2
БПФ разложение. N-точечный сигнал раскладывается на N сигналов, каждый из которых содержит одну точку. На каждом этапе проводится чередующееся разложение, разделяя четные и нечетные номера отсчетов.
Рисунок 12-2 показывает пример разложения сигнала временной области, используемый в БПФ. В этом примере 16точечный сигнал раскладывается за четыре отдельных шага. На первом шаге 16-точечный сигнал разделяется на два 8-точечных сигнала. На втором шаге – на четыре сигнала из 4 точек. Эта процедура продолжается пока сигнал не разложится на отдельные точки. Чередующееся разложение используется каждый раз, когда сигнал разделяется на два, то есть сигнал разделяется на четные и нечетные номера отсчетов. Наилучший способ понять эту процедуру - изучать рисунок 12-2 до тех пор, пока вы не усвоите этот шаблон. Требуется Log2N шагов для разложения сигнала, то есть 16-точечный сигал (24) потребует четыре шага, 512-точечный сигнал (27) – 7 шагов, сигнал из 4096 точек (212) – 12 шагов и так далее. Запомните эту величину, Log2N, она будет встречаться много раз в этой главе.
Нормальный порядок отсчетов
Отсчеты после битового реверсирования
Десятичный
Двоичный
Десятичный
Двоичный
РИСУНОК 12-3
Сортировка побитового реверсирования при БПФ. Разложение временной области может быть выполнено сортировкой отсчетов способом битового реверсирования.
Теперь, когда вы поняли структуру разложения, она может быть выполнена очень просто. Разложение есть ничего более, как переорганизация отсчетов. Рисунок 12-3 показывает шаблон переорганизации. Слева исходный порядок отсчетов. Справа новый порядок отсчетов. Идея заключается в том, что бинарные числа реверсируются друг с другом. Например, отсчет 3 (0011) изменяется на отсчет 12 (1100). Подобным образом отсчет номер 14 (1110) меняется с отсчетом номер 7 (0111) и т.д. При БПФ разложение временной области обычно выполняется алгоритмом сортировки битового реверсирования (bit reversal sorting). Новый порядок N отсчетов временной области получается пересчетом двоичного номера путем переброски битов справа налево (как в правой колонке рисунка 12-3).
Следующий шаг алгоритма БПФ заключается в нахождении частотного спектра одной точки сигнала временной области. Нет ничего легче, частотный спектр 1‑точечного сигнала равен самому сигналу. Это означает, что ничего не требуется делать на этом шаге. Хотя ничего и не требуется делать, однако не забывайте, что каждая точка теперь частотный спектр, а не сигнал временной области.
Последний шаг БПФ есть комбинация N частотных спектров в порядке обратном разложению временной области. В этом месте алгоритм сложен. К несчастью, тут побитовое реверсирование не годится, и мы должны идти назад по шагам. На первом шаге 16 частотных спектров (по 1 точке каждый) синтезируются в 8 частотных спектров (по 2 точки каждый). На втором шаге 8 частотных спектров (по 2 точки каждый) синтезируются в 4 частотных спектра (по 4 точки каждый) и т.д. На последнем шаге получается выходной спектр БПФ из 16 точек.
Рисунок 12-4 показывает, как два частотных спектра, состоящих из 4 точек, комбинируются в один частотный спектр из 8 точек. Этот синтез должен уничтожить чередующееся разложение, выполненное во временной области. Другими словами, операции над частотной областью должны соответствовать во временной области процедуре комбинации двух сигналов из 4 точек с помощью чередования. Рассмотрим два сигнала временной области, abcd и efgh. Сигнал временной области из 8 точек может быть сформирован за два шага: разбавить каждый 4-точечный сигнал нулями, сделав их 8-точечными, и затем сложить их. То есть abcd становится a0b0c0d0, а efgh становится 0e0f0g0h. Сложив эти два 8‑точечных сигнала, мы получим aebfcgdh. Как показано на рисунке 12-4, разбавление сигнала временной области нулями соответствует удвоению частотного спектра. Поэтому частотный спектр БПФ получается путем удвоения спектров и, затем, сложения удвоенных спектров.
РИСУНОК 12-4
Синтез БПФ. Когда сигнал временной области разбавляется нулями, частотная область удваивается. Если сигнал временной области был сдвинут при разбавлении, то спектр дополнительно умножается на синусоиду.
РИСУНОК 12-5
Диаграмма синтеза БПФ. Здесь показан метод комбинации двух 4-точечных спектров в один 8-точечный спектр. Оператор ´S означает, что сигнал умножается на синусоиду с соответствующей частотой.
Что бы осуществить правильное сложение, необходимо учитывать, что сигналы временной области немного различно разбавляются нулями. В одном сигнале нечетные точки равны нулю, в другом – четные. Другими словами один из сигналов временной области (0e0f0g0h на рисунке 12-4) сдвинут на один отсчет вправо. Сдвиг во временной области соответствует умножению спектра на синусоиду. Видя это, вспомните, что сдвиг во временной области эквивалентен свертки сигнала со сдвинутой дельта функцией. А это есть перемножение спектра сигнала на спектр сдвинутой дельта функции. Спектр сдвинутой дельта функции есть синусоида (смотри рисунок 11-2).
Рисунок 12-5 показывает диаграмму комбинации двух 4-точечных спектров в один 8-точечный спектр. Чтобы упростить ситуацию еще больше, рассмотрим рисунок 12-5 как повторение рисунка 12-6.
РИСУНОК 12-6
Бабочка БПФ. Это базовый элемент вычисления в БПФ. Он преобразует две комплексные точки в две другие комплексные точки.
Эта простая диаграмма называется бабочкой, так как похожа на крылья. Бабочка основной элемент вычисления в БПФ, он преобразует две комплексные точки в две другие комплексные точки.
Рисунок 12-7 показывает структуру БПФ целиком. Разложение временной области выполняется сортировкой с помощью битового реверсирования. Преобразование разложенных данных в частотную область не требует никаких операций, и поэтому оно не показано.
Синтез частотной области требует три цикла. Внешний цикл включает Log2N шагов (т.е. каждый уровень на рисунке 12-2, начиная снизу и двигаясь вверх). Средний цикл проходит через каждый отдельный частотный спектр в шаге (т.е. через каждый квадрат на любом уровне рисунка 12-2). Внутренний цикл использует бабочку для вычисления точек каждого частотного спектра (т.е. петляя через все отсчеты внутри любого квадрата на рисунке 12-2). Прямоугольники заголовков (overhead box) определяют начало и конец индексации для циклов, а также вычисляют синусоиды, необходимые для бабочки. Теперь мы подошли к сердцу этой главы – реальной программе БПФ.
РИСУНОК 12-7
Диаграмма БПФ. Она базируется на трех шагах. (1) разложение N-точечного сигнала временной области на N сигналов из одной точки. (2) Нахождение каждого спектра для этих сигналов (ничего не требуется). (3) Синтез N спектров в один частотный спектр.
