Колей (J.W. Cooley) и Туки (J.W. Turkey) открыли БПФ двери в мир своей работой «Алгоритмы для машинного вычисления комплексных рядов Фурье» (Математические вычисления, том 19, страницы 297-301). В ретроспективном плане, много раньше эту технику открыли другие. Например, великий германский математик Карл Фридрих Гаусс (1777-1855) использовал этот метод более чем за столетие раньше. Его ранняя работа была сильно забыта потому, что отсутствовал инструмент для выполнения этого на практике, цифровой компьютер. Колей и Туки оказались героями потому, что они открыли БПФ в нужное время, в начале компьютерной революции.
БПФ базируется на комплексном ДПФ, более изощренной версии реального ДПФ, которое обсуждается в последних четырех главах. Эти преобразования названы по способу, которым представляются данные, то есть, используются для этого реальные числа или используются комплексные числа. Термин «комплексный» не означает, что это представление трудно или сложно, оно обозначает специфический тип используемой математики. Комплексная математика часто является трудной и сложной, но имя пришло не оттуда. Глава 29 обсуждает комплексное ДПФ и обеспечивает необходимое понимание деталей алгоритма БПФ. Тема этой главы проще: показать, как используется БПФ для вычисления реального ДПФ, без погружения в глубины математики.
Поскольку БПФ есть алгоритм для вычисления комплексного ДПФ, важно понимать, как получаются данные реального ДПФ на входе и на выходе из формата комплексного ДПФ. Рисунок 12-1 дает сравнение того, как хранятся данные при реальном ДПФ и при комплексном ДПФ. Реальное ДПФ преобразует N точек сигнала временной области в два набора из N/2 + 1 точек частотной области. Сигнал во временной области так и называется: сигнал временной области. Два сигнала частотной области называются реальная часть и мнимая часть, в них содержатся амплитуды косинусных волн и синусных волн, соответственно. Это должно быть хорошо знакомо из предыдущих глав.
РИСУНОК 12-1
Сравнение реального и комплексного ДПФ. Реальное ДПФ берет N точек сигнала временной области и создает два набора из N/2+1 точек сигнала частотной области. Комплексное ДПФ берет два набора по N точек сигнала временной области и создает два набора из N точек сигала частотной области. Штриховкой показаны области величин общие для двух преобразований.
По сравнению с реальным ДПФ, комплексное ДПФ преобразует два набора по N точек сигнала временной области в два набора по N точек сигнала частотной области. Два набора сигнала временной области называются реальной частью и мнимой частью, так же как и сигналы частотной области. Не смотря на их названия, все величины в этих массивах так же обычные числа. [Если вы знакомы с комплексными числами, то j не включено в массивы этих величин, они часть математического способа; вспомните, что оператор Im( ) возвращает реальные числа].
Предположим, что вы имеет N точек сигнала и вам необходимо вычислить реальное ДПФ с помощью комплексного ДПФ (как в случае использования алгоритма БПФ). Первое, помещаете N точек сигнала в реальную часть временной области комплексного БПФ и затем устанавливаете все отсчеты мнимой части в нули. В результате вычисления комплексного ДПФ в реальной и мнимой частях частотной области получается N точек. Отсчеты от 0 до N/2 этих сигналов соответствуют спектру реального ДПФ.
Как обсуждалось в главе 10, частотная область ДПФ периодическая, и в нее включены негативные частоты (смотри рисунок 10-9). Выбор сигнального периода произволен; он может быть выбран между -1,0 и 0, между -0,5 и 0,5, между 0 и 1 или между каким либо другим единичным интервалом, определяемым частотой дискретизации. Частотный спектр комплексного ДПФ включает негативные частоты в интервале 0-1,0. Другими словами, один полный период от отсчета 0 до отсчета N-1 соответствует интервалу от 0 до 1 частоты дискретизации. Положительные частоты находятся между отсчетами 0 и N/2, что соответствует интервалу 0 – 0.5 частоты дискретизации. Отсчеты между N/2+1 и N-1 содержат величины негативных частот, которые обычно игнорируются.
Для вычисления реального инверсного ДПФ используют комплексное инверсное ДПФ с небольшими изменениями. Это вызвано тем, что вам необходимо убедится, что негативные частоты загружены в правильном формате. Помните, точки от 0 до N/2 в комплексном ДПФ те же самые, что и в реальном ДПФ для реальной части и мнимой части. Для реальной части точка N/2+1 та же самая, что и точка N/2-1, точка N/2+2 та же, что и точка N/2-2 и так далее. Это продолжается до точки N-1, которая то же, что и точка 1. Тот же подход используется и для мнимой части, за исключением изменения знака. Так точка N/2+1 есть негативная точка N/2-1, точка N/2+2 есть негативная точка N/2-2 и так далее. Заметим, что точки 0 и N/2 не имеют пар при этом подходе. Используйте рисунок 10-9 для объяснения этой симметрии. На практике вы загружаете спектр реального ДПФ в отсчеты от 0 до N/2 массива комплексного ДПФ, и затем используете подпрограмму для генерации негативных частот от N/1+1 до N-1. Таблица 12‑1 показывает эту программу. Что бы убедится, что симметрия правильная, после взятия инверсного БПФ посмотрите на мнимую часть временной области. Она должна состоять из одних нулей, если все правильно (за исключением миллионных долей шума за счет точности вычисления)
6000 'ГЕНЕРАЦИЯ НЕГАТИВНЫХ ЧАСТОТ
6010 'Эта подпрограмма создает комплексную частотную область из реальной частотной области
6020 'На входе этой подпрограммы N% содержит число точек в сигнале, и
6030 'REX[ ] and IMX[ ] содержат реальную частотную область с отсчетами от 0 до N%/2.
6040 'На выходе в REX[ ] и IMX[ ] комплексная частотная область с отсчетами от 0 до N%-1.
