СОВРЕМЕННАЯ ЭЛЕКТРОНИКА №7/2012

В ВЕДЕНИЕ Быстрое преобразование Фурье (БПФ) является важнейшим алгорит мом современной цифровой обработ ки сигналов (ЦОС) и является общим названием любого метода уменьшения вычислительной сложности дискрет ного преобразования Фурье (ДПФ). Первые теоретические работыпо БПФ принадлежат немецкому математику Карлу Фридриху Гауссу. Широкое при менение БПФ началось после опубли кования в 1965 г. Д. Кули и Д. Тьюки статьи с оригинальным описанием ал горитма (Cooley–Tukey FFT Algorithm). Вычислительные машины того време ни уже справлялись с задачей практи ческой реализации БПФ, но метод Ку ли–Тьюки позволял ускорить вычис ления в 5–6 раз. С тех пор элементная база вычислительной техники значи тельно изменилась, появились новые алгоритмы вычисления БПФ, однако алгоритм Кули–Тьюки остаётся попу лярным. В настоящее время БПФреализуют в основном с помощью ЦПОС и ПЛИС. Значительное увеличением ёмкости и быстродействия микросхем програм мируемой логики облегчает реализа цию алгоритмов БПФ. Предлагаемая статья содержит описание модуля быстрого преобразования Фурье, на писанного на языке Verilog и предна значенного для ПЛИС семейства Xilinx Spartan 6. Отладка проекта проводи лась на тестовой плате SP605, все ис ПРОГРАММИРОВАНИЕ 62 WWW.SOEL.RU СОВРЕМЕННАЯ ЭЛЕКТРОНИКА ◆ № 7 2012 ходные коды проекта содержатся в ар хиве fft_sopc.zip (www.soel.ru) . Т ЕОРЕТИЧЕСКИЕ ОСНОВЫ БПФ Как упоминалось выше, БПФ – это алгоритм вычисления ДПФ, которое является методомразложения дискрет ного периодического сигнала в ряд тригонометрическихфункций. Теория метода была разработана французс ким физиком и математиком Жаном БатистомФурье, который доказал, что любой дискретный периодический сигнал может быть представлен ком бинацией простейших тригонометри ческих функций (синусов и косину сов). Математическая часть преобра зования Фурье достаточно сложна и будет рассмотрена в статье только в объёме, минимально необходимом для реализации БПФ. Более подробно с теорией метода можно ознакомиться в [1, 2]. Существует два типа преобразова ния Фурье – действительное ДПФ и комплексное ДПФ. Для реализации БПФ необходимо использовать ком плексное ДПФ. Предположим, на входе имеется дискретный сигнал X ( k ), со стоящий из N отсчётов. Его ДПФ будет выглядеть следующим образом: ( k = 0, 1, …, N – 1), , ( k = 0, 1, …, N – 1). Комплексный компонент уравнения W N в англоязычной литературе часто называется twiddle factor (поворачи вающий коэффициент) и также может быть выражен комбинацией синусов и косинусов: W N = cos(2 π / N ) – j sin(2 π / N ). Количество отсчётов входного сиг нала N , как правило, равно степени 2, хотя существуют методы вычисления БПФ для произвольного числа вход ных отсчётов. При малой величине N время вычисления ДПФпрямыммето дом и методом БПФ сравнимы. Однако с увеличением размерности входно го сигнала преимущества БПФ по ско рости вычисления могут достигать со тен раз. Рассмотрим более подробно реа лизацию БПФ методом Кули–Тьюки для входного сигнала с размерностью 128 отсчётов. А ЛГОРИТМ БПФ Суть БПФ заключается в том, что входной сигнал большой размернос ти N , в данном случае 128, разбивается на N сигналов единичной размернос ти. Затем для каждого единичного сиг нала вычисляется спектр, т.е. проис ходит переход из временной области в частотную. На последнем этапе N единичных спектров объединяются в один общий спектр. Первый этап разделения входного сигнала называется декомпозицией. На нём применяется т.н. бит реверс ная адресация. Допустим, отсчёты входного сигнала нумеруются в пря мой последовательности 0, 1, 2, 3 и т.д. Для формирования бит реверсной последовательности необходимо еди ницы адреса отсчёта в двоичной фор ме переставить в обратном порядке, как показано в таблице. Для адресации 128 отсчётов требуется семь адресных битов. В таблице приведены первые девять отсчётов, для всех остальных отсчётов бит реверсный адрес вычис ляется аналогично. После бит реверс ной сортировки входные отсчёты бу Бит реверсная адресация Модуль быстрого преобразования Фурье Алексей Гребенников (Московская обл.) Статья содержит описание модуля быстрого преобразования Фурье, написанного на языке Verilog и реализованного для ПЛИС семейства Xilinx Spartan 6. Отсчёты исходной последовательности Отсчёты после бит реверсной сортировки десятичный адрес отсчёта двоичный адрес отсчёта десятичный адрес отсчёта двоичный адрес отсчёта 0 0000000 0 0000000 1 0000001 64 1000000 2 0000010 32 0100000 3 0000011 96 1100000 4 0000100 16 0010000 5 0000101 80 1010000 6 0000110 48 0110000 7 0000111 112 1110000 8 0001000 8 0001000 ' СТА - ПРЕСС