基于FPGA的FFT算法硬件实现

由图4可以看出，输出比输入延时6个时钟，这在系统的控制核心地址产生单元的设计中需要考虑到。
1．3 地址产生与时序控制
对于1 024．点基4 FFT运算，需要5级蝶形运算，每一级运算都要有写地址和读地址，根据FFT同址运算的特点可知，当前的写地址即是上一级蝶形运算的读地址。因此完成FFT运算需要设计6级RAM地址。其中第1级的写地址即是数据输入的顺序地址，不予讨论。最后一级读地址为数据正序输出所需的地址。其余4级为1 024点数据对应的FFT蝶形运算。
第一级读取节点地址的顺序应该是：(0，256，512．768)，(1，257，513，769)，……，(255，511．767，1 023)。易观察其读地址的规律如下：设读取次序的二进制编码为bit[9：0]；则读地址的二进制编码为{bit[1：O]，bit[9：2]}，并且依次可以推出第2、3、4级的读地址二进制编码分别为{bit[9：8]，bit[1：0]，bit[7：2]}，{bit[9：6]，bit[1：0]，bit[5：2]}、{bit[9：4]，bit[1：0]，bit[3：2]}，而最后一级输出数据的地址二进制编码则为：{bit[1：0]，bit[3：2]，bit[5：4]，bit[7：6]，bit[9：8]}。图5给出了第1级读地址和第2级读地址的部分数据，也可以看出第2级的写地址即是第1级的读地址。

图1中的地址产生单元作为系统的控制核心，不仅要生成每一级的RAM读写地址，还要产生RAM写使能信号、输出有效信号以及4点蝶形运算单元和旋转因子产生单元的启动信号，由于时序电路还需要考虑器件延时，例如上文提到的4点蝶形运算输出比输入延时6个时钟，以及RAM存取数据输出比输入延时1个时钟，这些都需要在控制核心中考虑到。
1．4 旋转因子产生
对于1 024点FFT蝶形运算，需要1 024个旋转角度(即2π的1 024等份)，其中第一级不需要复乘运算，第6级只是将数据进行整序没有运算单元，其他4级都需要旋转因子。本设计采用将旋转因子预置于ROM中，通过查找表方法得出每一级运算的所需的旋转因子。根据旋转因子的可约性，后几级运算所需的旋转因子都可以在第一级运算的旋转因子中找到，因此无需另外存储。旋转因子在ROM中的存储规律是：旋转因子相位角p处存储旋转因子W=*****。定义一个10 bit的计数器count[9：0]，则第2、3、4、5级ROM的相位角规律按照Verilog语法可表示为

为了节省资源，本设计只在ROM单元中存储了前256个旋转因子数据，即第一象限因子其余象限的因子可通过象限转换后得到，这样就大大节省了存储单元的硬件资源。图6为旋转因子产生单元在QuartusⅡ环境中仿真结果的部分数据。