Рассмотрим блок-схему вычислителя БПФ (рис . 1), реализующую алгоритм БПФ с замещением.
Рис.1 Блок-схема вычислителя БПФ
             Она состоит из памяти для хранения входных, промежуточных и выходных отсчетов; памяти для хранения коэффициентов преобразования Wk; элементарного вычислителя 2-точечного ДПФ, выполняющего базовую операцию БПФ, известную в литературе как «бабочка»; контроллер, управляющий работой вычислителя. На блок-схеме не показаны банки интерфейсной памяти, служащие для накопления входных отсчетов сигнала и выдачи выходных отсчетов спектра, ввиду непринципиальности их учета в данном случае.
             Реализация БПФ с применением алгоритма с замещением дает максимальную экономию внутрикристальной памяти ПЛИС. При этом чтение и запись промежуточных данных происходит в один и тот же блок памяти.
            Для алгоритма с замещением существуют 2 вида эквивалентных графов БПФ: граф с «прореживанием по частоте» и граф с «прореживанием по времени», между которыми нет принципиальной разности с позиции эффективной реализации. Для определенности в дальнейшем будем рассматривать БПФ с «прореживанием по частоте», «бабочка» для которого представлена на рис.2.
Рис. 2. «Бабочка» для БПФ с «прореживанием по частоте».
 Рассмотрим более подробно составные части вычислителя БПФ с «прореживанием по частоте».
             Контроллер (рис. 1) реализует граф БПФ путем генерации адресов для банков памяти, принимает управляющий сигнал о начале выполнения преобразования, выдает флаг готовности спектра и обеспечивает выдачу выходного массива спектра в двоично-инверсном порядке. Представляется целесообразным проектирование контроллера на языке HDL. Это дает возможность написания универсального контроллера, что позволяет строить контроллеры для вычислителей с различными базами БПФ путем изменения параметра в тексте программного кода контроллера и его последующей «перекомпиляции».
            Существенной проблемой, с которой неизбежно сталкивается разработчик схемы цифровой сигнальной обработки на ПЛИС, - это выбор оптимальной разрядности вычислителя, в нашем случае это операция «бабочка». Разрядность «бабочки» складывается из двух составляющих. Первая – это разрядность коэффициентов преобразования  Wk (разрядность представления комплексных синусоид). Вторая – разрядность промежуточных данных A и B (рис. 2)
рис.3 блок-схема аппаратной  реализации операции «бабочка»
            На рис.3 приведена одна из возможных блок-схем аппаратной  реализации операции «бабочка» (рис.2). Она содержит 4 умножителя, являющихся основными потребителями аппаратных ресурсов вычислителя. При этом достигается максимальная параллельность вычислений и соответственно предельная скорость вычисления БПФ при фиксированной тактовой частоте.
            Вычислитель «бабочки» производит арифметические операции над комплексными числами А и В, получая на своих выходах комплексные числа X и Y с той же разрядностью.  В ее составе: комплексный сумматор (adrer0); комплексный вычитатель (sub0); 4 умножителя (mul0…mul3); сумматор (adder1); и вычитатель (sub1), производящие комплексное умножение на коэффициент преобразования  (проворачивающий множитель) Wk.
            Устройства сдвига (shifter0…shifter4), производящие нормировку данных, показаны условно. В ПЛИС сдвиг осуществляется путем подключения со сдвигом по номерам битов входных и выходных шин элементов и не требует никаких аппаратных затрат.
           Построение вычислителя «бабочки» необходимо производить по схеме с промежуточным запоминанием данных в регистрах (pipeline). В силу специфики построения логических ячеек ПЛИС (slices) это не приводит к росту аппаратных затрат, но позволяет получать высокие тактовые частоты. При этом образуется вычислительный конвейер, задержки которого необходимо учитывать при построении контроллера. Для этой же цели служит FIFO-буфер(delay line), который позволяет получать одновременный выход преобразуемых отсчетов X и Y из вычислительного конвейера, несмотря на несимметричность ветвей «бабочки».
            Очень удобно использование двухпортовой внутрикристальной памяти ПЛИС для хранения промежуточных данных(рис. 1). Это дает возможность одновременно читать числа A, B и писать числа X, Y независимо от их взаимного расположения в памяти.
Список литературы:
  1. А. К. Пяткин, М. В. Никитин  Реализация на ПЛИС быстрого преобразования Фурье для алгоритмов ЦОС в многофункциональных РЛС. Цифровая обработка сигналов №3 2003г.
  2. А. К. Пяткин  Построение последовательно-параллельных вычислительных систем БПФ на ПЛИС. Цифровая обработка сигналов №1 2004г.
  3.  РабинерЛ., Гоулд Б. Теория и применение цифровой обработки сигналов. М.: Мир, 1978.