Интернет-журнал "Домашняя лаборатория", 2007 №8

Журнал «Домашняя лаборатория»

На рис. 5.6 показаны исходные данные и результаты вычислений вещественного и комплексного БПФ (FFT). Обратите внимание, что результат вычисления вещественного ДПФ дает вещественное и мнимое значения Х(k), где к находится в диапазоне от 0 до N/2. При этом мнимые точки ImX(0) и ImX(N/2) всегда равны 0, потому что равны 0 sin(0) и sin(?n).

Результат вычислений в частотной области X(N/2) соответствует частотному диапазону, равному половине частоты дискретизации f_s. Ширина каждого элемента разрешения по частоте равна f_s/N.

Комплексное ДПФ

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

Рис. 5.7 раскрывает отношение между вещественным и комплексным ДПФ более подробно.

Выходные точки вещественного ДПФ располагаются в диапазоне от 0 до N/2, причем значения ImX(0) и ImX(N/2) всегда равны 0. Точки между N/2 и N — 1 содержат отрицательные частоты в комплексном ДПФ. Обратите внимание, что ReX(N/2+1) имеет такое же значение, как и ReX(N/2 — 1). Точно так же, ReX(N/2 + 2) имеет такое же значение, как и ReX(N/2 — 2) и т. д. Видно, также, что ImX(N/2 + 1) равно ImX(N/2-l), но взято со знаком минус, и ImX(N/2 + 2) равно ImX(N/2 — 2), но взято со знаком минус и т. д. Другими словами, ReX(k) имеет четную симметрию относительно N/2, a ImX(k) имеет нечетную симметрию относительно N/2. Таким образом, на основе вещественных компонентов ДПФ могут быть сгенерированы отрицательные частотные компоненты комплексного БПФ.

Уравнения для комплексного и вещественного ДПФ приводятся на рис. 5.8.

Видно, что уравнения для комплексного ДПФ работают почти одинаково, будь то процедура вычисления ДПФ Х(k) или обратного ДПФ х(n). Вещественное ДПФ не использует комплексные числа, и уравнения для Х(k) и х(n) существенно различаются. Также перед использованием уравнения для вычисления отсчетов во временной области х(n), значения ReX(0) и ReX(N/2) должны быть поделены на два. Эти подробности объясняются в главе 31 книги, приведенной в списке литературы под номером 1, и читатель может изучить данный материал перед тем, как использовать эти уравнения.

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

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

Для понимания принципов работы БПФ, рассмотрим ДПФ на 8 точек, представленное на рис. 5.10 в развернутом виде. Обратите внимание, что для упрощения таблицы мы вводим следующее определение:

W_N = е^{– j2?/N}

Это ведет к определению коэффициентов поворота (поворачивающих множителей):

W_N^nk = е^{– j2?k/N}

Коэффициенты поворота представляют базисные гармонические функции, записанные в экспоненциальной форме. Обратите внимание, что 8-точечное ДПФ, представленное на диаграмме, требует 64 операций умножения с комплексными

числами. N-точечное ДПФ требует N² операций умножения с комплексными числами. Знание количества умножений важно потому, что на реализацию операций умножения затрачиваются существенные вычислительные ресурсы DSP. В действительности, общее время, требуемое для вычисления ДПФ, прямо пропорционально числу умножений с учетом необходимого числа дополнительных операций.

Быстрое преобразование Фурье (FFT) является не более чем алгоритмом для ускоренного вычисления ДПФ путем сокращения требуемого числа операций умножения и сложения. Данное преобразование было предложено Кули и Таки (J.W.Cooley и J.W.Tukey) в 1960-ых годах и фактически являлось открытием заново идеи Рунге, Даниэльсона и Ланкоса (Runge (1903), Danielson и Lanczos (1942)). Первое упоминание данной идеи встречается еще задолго до появления компьютеров и калькуляторов, когда численные вычисления могли занимать много часов. Кроме того, более чем столетием раньше данный метод использовал немецкий математик Карл Фридрих Гаусс (1777–1855).

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

Результатом переработки выражений для ДПФ является быстрое преобразование Фурье (FFT), которое требует только (N/2)log2(N) умножений комплексных чисел. Вычислительная эффективность БПФ по сравнению с ДПФ становится весьма существенной, когда количество точек БПФ увеличивается до нескольких тысяч, как это следует из рис. 5.12. Очевидно, что БПФ вычисляет все компоненты выходного спектра (или все, или ни одного!). Если необходимо рассчитать только несколько точек спектра, ДПФ может оказаться более эффективным. Вычисление одного выходного отсчета спектра с использованием ДПФ требует только N умножений с комплексными числами.

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

8-точечное БПФ с прореживанием во времени (decimation-in-time, DIT) вычисляет окончательный результат с использованием трех каскадов, как это следует из рис. 5.14.

Восемь входных отсчетов из временной области сначала разделяются (или прореживаются) на четыре группы 2-точечных ДПФ. Затем четыре 2-точечных ДПФ объединяются в два 4-точечных ДПФ. Затем два 4-точечных ДПФ объединяются для того, чтобы получить окончательный результат Х(k). Подробно процесс рассмотрен на рис. 5.15, где показаны все операции умножения и суммирования. Нетрудно заметить, что базовая операция «бабочки» 2-точечного ДПФ формирует основу для всего вычисления. Вычисление осуществляется в трех каскадах. После того, как заканчивается вычисление первого каскада, нет необходимости сохранять какие-либо предыдущие результаты.