FPGA(现场可编程门阵列)是一种具有大规模可编程门阵列的器件，不仅具有专用集成电路(ASIC)快速的特点，更具有很好的系统实现的灵活性。FPGA可通过开发工具实现在线编程。与CPLD(复杂可编程逻辑器件)相比，FPGA属寄存器丰富型结构，更加适合于完成时序逻辑控制。因此，FPGA为高速FFT算法的实现提供了一个很好的平台。
1 基4-FFT算法基本原理
在FFT各类算法中，基2-FFT算法是最简单的一种，但其运算量与基4-FFT算法相比则大得多，分裂基算法综合了基4和基2算法的特点，虽然具有最少的复乘运算量，但其L蝶形运算控制的复杂性也限制了其在硬件上的实现，因此，本设计采用了基4-FFT算法结构。
基4-FFT算法的基本运算是4点DFT。一个4点的DFT运算的表达式为：
式(1)对于输出变量进行了二进制倒序，便于在运算过程中进行同址运算，节省了运算过程中所需存储器单元的数量。
按DIT(时间抽取)的1 024点的基4-FFT共需5级蝶形运算，每级从RAM中读取的数据经过蝶形运算后原址存入存储单元准备下一级运算。算法的第1级为一组N=1 024点的基4蝶形运算，共256个蝶形，每个蝶形的距离为256点；第2级为4组N=256点的基4蝶形运算，每组64个蝶形，每个蝶形的距离为64点。后3级类推。这种算法每一级的运算具有相对独立性，每级运算都采用同址运算，因此，本设计只使用了2个1 k×16 bits的RAM单元。运算过程中所需的旋转因子的值经过查询预设的正弦与余弦ROM表得到。
2 1024点FFT算法模块的设计
本设计的总体框图如图1所示。整个模块的输入包括16位带符号实部和虚部数据输入、FFF启动信号，输出包括16位带符号实部和虚部数据输出、输出有效数据区间标志。内部结构包括2个1 k×16 bits的实部和虚部双口RAM存储单元、蝶形运算单元、旋转因子生成模块(包括正弦因子查询表、余弦因子查询表和象限转换模块)、RAM和ROM存储器地址控制单元、倒序模块以及时序总控制单元。
下面对主要单元进行分析。
2.1旋转因子产生模块
在整个FFT运算过程中，需要存储一组旋转因子表用于蝶形运算，如第1级运算需要的旋转因子有W01024，W11024，…，W10231024，根据旋转因子的可约性，后几级运算所需的旋转因子都可以在这一组数据中查到，因此无需另外存储。为了更节省存储资源，本设计只在ROM单元中存储了前256个旋转因子数据，即第1象限因子W01024，W11024，…，W2551024，。其余象限的因子通过象限转换后得到。这样便可以节省3／4的ROM存储单元的硬件资源。
2.2蝶形运算单元
2.2.1蝶形整体结构
蝶形运算单元包括输入输出寄存器、串／并转换、并／串转换和复数乘法器等。从基本的基4蝶形运算表达式可以看出，每一级的输出数据在进入下一级运算之前都要首先与旋转因子Wnk
