Быстрое преобразование Фурье (БПФ) является ключевым алгоритмом в современной цифровой обработке сигналов (ЦОС) – это общее имя любого метода для уменьшения вычислительной сложности дискретного преобразования Фурье (ДПФ). Первая теоретическая работа над БПФ принадлежит немецкому математику К. Ф. Гаусу. Широкое использование БПФ началось после публикации в 1965 году статьи Д. Кули и Дж. Туки с оригинальным описанием алгоритма (Cooley–Tukey FFT Algorithm). Компьютеры того времени уже справлялись с задачей практической реализации БПФ, но метод Кули-Туки позволил ускорить расчеты в 5-6 раз. Поскольку схема компьютеров значительно изменилась, появились новые алгоритмы для вычисления БПФ, но алгоритм Кули-Тьюки остается популярным.
В настоящее время БПФ реализуется в основном с помощью ЦПОС и ПЛИС. Значительное увеличение емкости и производительности микросхем программируемой логики облегчает реализацию алгоритмов БПФ. Статья содержит описание модуля быстрого преобразования Фурье, предназначенного для семейства ПЛИС Xilinx. Как упоминалось выше, БПФ является алгоритмом для вычисления ДПФ, который является методом разложения дискретного периодического сигнала в ряд тригонометрических функций. Теоретический метод был разработан французским физиком и математиком Ж. Б. Фурье, который доказал, что любой дискретный периодический сигнал может быть представлен комбинацией простых тригонометрических функций (синус и косинус).
Существует два типа преобразований Фурье – действительный ДПФ и комплексный ДПФ. Для реализации БПФ необходимо использовать комплексный ДПФ. Предположим, что введен дискретный сигнал X (k), состоящий из N выборок. ДПФ будет выглядеть следующим образом:
Комплексные уравнения компонентов WN в английской литературе часто называют фактором twiddle factor (поворачивающий коэффициент), и также могут быть выражены комбинацией синусов и косинусов:
Количество входных выборок N обычно равно степени 2 , хотя доступны методы для расчета БПФ для произвольного количества входных выборок. При малом значении N время вычисления ДПФ прямым методом и методом БПФ сопоставимы. Однако с увеличением размерности входного сигнала преимущества БПФ в скорости вычислений могут достигать сотен раз. Рассмотрим более подробно реализацию метода БПФ, Кули–Туки для входного сигнала с размером 128 выборок.
Суть БПФ заключается в том, что входной сигнал имеет большую размерность N, в этом случае 128 делится на N сигналов одного измерения. Затем для каждого отдельного сигнала рассчитывают спектр, то есть происходит переход от временной области к частотной области. На последнем этапе N отдельных спектров объединяются в один спектр. Первый этап разделения входного сигнала называется декомпозицией. Он применяет так называемую бит-реверсную адресацию. Например, отсчеты входного сигнала нумеруются в порядке 0, 1, 2, 3 и т. д.
Для формирования бит-реверсной последовательности необходимо единицы адреса отсчёта в двоичной форме переставить в обратном порядке, как показано в таблице. Для адресации 128 выборок требуется семь битов адреса. В таблице показаны первые девять отсчетов, все остальные счетчики бит-реверсального адреса вычисляются аналогичным образом. После бит-реверной сортировки входные отсчеты должны выполняться в порядке 0, 64, 32, 96, 16, 80 и т. д. А затем для каждого отдельного сигнала рассчитывается спектр. На данном этапе, не требуется каких-либо действий программного обеспечения, так как спектр одного сигнала равен соответствующиму ДПФ базисного сигнала. Последний шаг БПФ состоит в объединении отдельных спектров. Этот шаг является самым сложным и требует нескольких этапов. Основная операция объединения спектров, показанных на рисунке 1, называется «бабочкой» (butterfly).
Рисунок 1- базовая операция БПФ
Алгоритм, в котором операция «бабочка» выполняется одновременно для двух входных сигналов, называемых БПФ с основанием 2. Этот алгоритм рассматривается в этой статье. Другим распространненым основанием БПФ является 4. Операция «бабочка», в свою очередь, состоит из нескольких этапов. Сначала второй входной сигнал IN2 умножается на коэффициент WN (коэффициент поворота). Затем первый выходной сигнал OUT1 получается путем суммирования результата умножения первого входного сигнала IN1. Второй выходной сигнал представляет собой разность между первым входным сигналом IN1 и результатом умножения. Для полной унификации размерности спектра N выборок требуется log2N циклов операций «бабочка». Когда размеры 128 требуют 7 циклов, и каждый цикл состоит из 64 операций, так как при основании 2 одна базовая операция БПФ включает в себя два входных отсчета.
Полная схема БПФ для 128 выборок довольно громоздка, поэтому на рисунке 2 в качестве примера показана схема БПФ для 8 выборок, которая состоит из трех циклов (log28). В зависимости от процедуры использования коэффициентов поворота и операций «бабочка» различают БПФ с прореживанием во времени и БПФ прореживанием по частоте. На рисунке 2 показан алгоритм с прореживанием во времени, тот же алгоритм реализован в модуле для ПЛИС; видно, что входные выборки сортируются в соответствии с обращением бит-реверсного адреса. Во время первого цикла для всех «бабочек», используюется тот же самый коэффициент поворота W0. Пары отсчетов для второго цикла формируются согласно рисунку 2, поэтому поворачивающие коэффициенты начинают чередоваться: для первой «бабочки» коэффициент W0, а для второй – W2, третьего и четвертого – коэффициенты W0 и W2 соответственно.
Рисунок 2- БПФ для 8-ми разрядного входного сигнала
В течение третьего цикла используются все коэффициенты поворота W0 – W3. Обратите внимание, что общее количество коэффициентов twiddle равно половине размерности входного сигнала, то есть для ввода размерности 128 выборок потребуется 64 коэффициента. Пары сигналов в этом случае будут сформированы аналогично БПФ для 8 образцов. В течение первого цикла умножение будет выполняться с коэффициентом поворота W0, тогда как второй цикл будет чередовать коэффициенты W0 и W32, в течение третьего цикла будут чередовать коэффициенты W0-W16-W32-W48, в течение четвертого цикла W0-W8 -W16-W24-W32-W40-W48-W56.
Таким образом, количество задействованных коэффициентов будет увеличиваться, и в течение последнего седьмого цикла будет задействован весь 64 поворачивающих коэффициента.
В настоящее время существует большое количество алгоритмов БПФ с разной производительностью, размерами, вычислительными ресурсами и другими параметрами. Важной характеристикой реализации алгоритма БПФ является арифметика, используемая для расчетов (плавающая или фиксированная точка). Реализация алгоритма с плавающей точкой имеет высокую точность, но является сложным и дорогостоящим вычислительным ресурсом. В приложениях, которые не требуют высокой точности, более простая реализация алгоритма БПФ с фиксированной точкой оправдана, так как для этого требуется меньшее количество ресурсов, что важно для ПЛИС. Модуль БПФ, описанный в статье, показал удовлетворительные результаты в тестировании и подходит для приложений, которые не требуют высокой точности.
Количество просмотров публикации: Please wait