О. М. ШИШКИН
Московский инженерно-физический институт (государственный университет)
АППАРАТУРНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА БПФ
Предлагается схема выполнения быстрого преобразования Фурье (БПФ) с прореживанием по частоте, адаптированная для аппаратурной реализации на программируемой логической интегральной схеме (ПЛИС).
Дискретное преобразование Фурье находит широкое применение в цифровой обработке сигналов, но на практике применяют алгоритмы быстрого преобразования Фурье, обладающие меньшей вычислительной сложностью. Существуют различные алгоритмы БПФ и графы их выполнения. Выбор конкретного решения зависит как от условий самой задачи, так и от средств, предназначенных для ее реализации.
Постановка задачи: разработать предназначенную для реализации на ПЛИС Altera Stratix EP1S20 структуру, выполняющую 4096-точечное БПФ восьми действительных последовательностей. Отсчеты входных последовательностей поступают с АЦП в восьмибитном дополнительном коде с частотой дискретизации 45…60 МГц. Время выполнения преобразования не должно превышать трехкратного времени накопления отсчетов.
В данном случае применение одного из известных методов вычисления БПФ в чистом виде не позволяет уложится в заданные ограничения по времени и ресурсам. Для решения поставленной задачи был разработан алгоритм комбинирующий в себе метод выполнения БПФ с замещением и поточный метод, а также использующий свойство симметрии ДПФ действительной последовательности, которое позволяет осуществить преобразование двух действительных последовательностей в одном комплексном БПФ. Разработанный алгоритм выполняет БПФ с прореживанием по частоте, с прямым порядком входных отсчетов и с упорядочиванием спектральных отсчетов при их чтении. По этому алгоритму можно выполнять БПФ последовательностей длиной 
, 
.
Структурная схема, реализующая преобразование двух последовательностей, представлена на рис. 1.
Алгоритм построен так, что выборка двух операндов А и В для базовой операции БПФ всегда осуществляется из разных блоков памяти - ЗУ_А и ЗУ_В соответственно. Это позволяет использовать двух-, а не четырехпортовую память. Последовательность из двух конвейерных арифметических устройств (АУ1 и АУ2) и двух регистровых блоков (РБ1 и РБ2) позволяет совместить выполнение сразу двух этапов БПФ, почти вдвое уменьшая время выполнения всего преобразования. Арифметическое устройство АУ3 преобразует результат БПФ комплексной последовательности 
, составленной из двух действительных входных последовательностей. Выходные последовательности 
и 
являются спектральными отсчетами соответствующих входных последовательностей. Блок масштабирования отслеживает увеличение разрядности результатов вычислений на каждом этапе и в случае необходимости выполняет их масштабирование.
Рис. 1. Структурная схема для выполнения БПФ двух последовательностей
Полная схема, выполняющая БПФ восьми последовательностей, содержит четыре приведенных структуры с общим устройством управления, буфером для накопления входных отсчетов и памятью для хранения результатов.
Реализация данной схемы на ПЛИС Stratix EP1S20 использует следующие ресурсы:
- логические ячейки 5% от доступных);
- память 1431552 бит (85% от доступных);
- 9-ти битные DSP элементы% от доступных).
Тактовая частота приема исходных данных в буферную память – до 150 МГц; тактовая частота внутренних вычислений – до 160 МГц, тактовая частота выдачи результатов из буферной памяти результатов – до 200 МГц.
На процесс вычислений, включая перезапись данных из входного буфера FIFO в ЗУ и из ЗУ в память результатов, затрачивается примерно 18,5 тысяч тактов тактовой частоты внутренних вычислений, что при f = 160 МГц составляет 116 мкс.
Список литературы
1. Теория и применение цифровой обработки сигналов: М.: Мир. 1978.
