基于FPGA流水线结构并行FFT的设计与实现

 离散傅里叶变换DFT在通信、控制、信号处理、图像处理、生物信息学、计算物理、应用数学等领域中有着广泛的应用。FFT算法是作为DFT快速算法提出的，它将长序列的DFT分解为短序列的DFT，大大减少了运算量。FFT的FPGA实现同时具有软件编程的灵活性和ASIC电路的快速性等优点，成为快速实时实现FFT的一种重要手段。文章意在设计一种高速率高吞吐率的FFT处理器，以满足实时处理要求。

1 数学模型

FFT的基本思想是利用旋转因子的周期性、对称性和可约性将一个长度为N的序列的DFT逐次分解为较短的DFT来计算，而总的运算次数比直接DFT运算要少得多，达到提高速度的目的。根据旋转因子的周期性、对称性和可约性，我们可以得到如式(1)的一系列有用结果。

2 结构说明

2.1 流水线结构

硬件结构实现FFT的常用形式有4种：递归结构，流水线结构，并行迭代结构和全并行结构。设计采用流水线结构，流水线结构一般在FFT实现的每一级均采用一个运算单元，前一级算结果直接用于下一级运算而无需等到本级运算全部完成，因此，可提高运算速度。递归结构的运算的时间较长，并行迭代结构对数据存取带宽要求很高，全并行结构资源消耗过大，均不适用。

2.2 并行处理

FFT作为时域和频域转换的基本运算，是数字频谱分析的必要前提，超级的运算能力在雷达处理、观测、跟踪、定时定位处理、高速图像处理、保密无线通讯和数字通信、滤波等的应用上极为强烈，而实时系统对FFT的运算速度要求更高。提高FFT速度的一种有效解决方法是并行运算，如采用多个蝶形运算单元并行处理。

综上，设计选取流水结构，4路并行处理结构。

3 硬件设计

3.1 逻辑设计

FFT逻辑框架如图1，为了构造高速率高吞吐量的FFT，设计4路并行输入输出，采用基4与基2混合FFT，FFT512采用基4蝶形算法，其余则采用基2蝶形算法。

流水结构的FFT处理器的基本结构如图2所示。实际设计由3个部分组成：运算单元、数据交换单元和重排单元。

运算单元完成蝶形运算，是处理器的核心，其运算速度直接决定整个FFT处理器的速度。由于4组输入数据同时进入蝶形运算，所以处理速度为串行的4倍。其中，每个蝶形单元均采用流水线技术设计。运算单元启动后，每个周期处理4组数据，完成4输入4输出的FFT。

数据交换单元是处理器的关键，实现对前一级蝶形运算单元输出数据的交换，以满足下一级蝶形运算的配对需求。实现方法为每一级的输入均采用顺序输入，内部用FIFO缓存数据，按照逆序形式配对数据，等待数据到来，将加法结果输出，减法结果存至FIFO中，待加法结果输出完毕，继续输出减法结果，如此输出结果即为顺序输出。

数据重排单元负责对最终计算结果进行重新排序，以实现自然序数输出。512点基4框架图如图3所示，在512基4运算完成后，输出数据的顺序并不是所需顺序，需要进行调整，由输入数据与输入数据的地址特点发现，倒序RAM的读地址即完成顺序输出。

3.2 时序设计

流水示意图如图4所示，详细说明如下：

FFT64模块的5级流水：第1级，前64组输入数据的实部、虚部均寄存在FIFO中，当第65组数据到来时，与FIFO中寄存的第一组数据做蝶形运算，将相减的结果继续存在FIFO中待用，相加运算将在第二级进行;第2级，前64个周期，做蝶形加法，结果记为add，第65个周期起，从FIFO中读数给add;第3级，前64个周期，add赋给第一级缓存寄存器，第65个周期起，把add赋给乘法器的输入端;第4级，前64个周期，把第一级缓存寄存器赋值给第二级缓存寄存器，第65个周期起，做乘法运算;第5级，前64个周期，把第二级缓存寄存器的值赋给输出端，第65个周期起，把乘法器输出累加的结果赋给输出端;

FFT512模块的6级流水：第1级，当输入有效信号拉高时，将第一组输入数据放入第一级缓存器中，寄存第二至四组数据，待接乘法器输入端。同时，从rom中读取旋转因子;第2级，第一路缓存至第二级缓存中，其余三路做乘法运算;第3级，第一路缓存至第三级缓存中，其余三路做复数乘法的加法运算;第4级，四路数据均做缓存;第5级，做如图3中的第一个蝶形运算。其中，乘以-j运算可以用颠倒相加来完成，如此可以节省乘法器资源;第6级，做如图3中的第二个蝶形运算，同时将输出有效信号拉高。

FFT32、FFT16、FFT8、FFT4、FFT2、FFT1与FFT_64流水原理一致，只是控制位数不同，其分别为32、16、8、4、2、1。

4 验证设计

Testbench是一种验证手段，通常包含3个部分，激励生成、待测设计、输出校验。针对设计搭建的testbench如图5所示，从文件中读取向量i_data_real、i_data_imag，经过FFT处理得到结果o_data_relal、o_data_imag，并根据end信号将向量写入相应文档中，与正确结果进行比对。

5 仿真结果

ISE仿真波形如图6所示，输出文件经与MATLAB对比验证正确。图(1)为整体仿真波形，输出有效信号拉高后，数据连续输出。图(2)为FFT 512模块局部仿真波形，输入有效信号拉高后，第6个周期输出有效，与分析的流水级数相吻合。

6 综合结果

综合后得到资源利用情况如表1，我们发现，并行处理带来面积的增大，如何在实际问题中平衡速度与面积尤为重要。

7 结束语

文章用FPGA实现了512点FFT处理器，采用Verilog硬件描述语言进行RTL级描述，并完成综合、布局布线。经过ISE仿真，结果与MATLAB仿真输出结果吻合。处理器先采用时域基2蝶形算法，后采用时域基4蝶形算法，并行处理4个蝶形运算单元，并同时采用流水线结构，大幅度提高了处理器速度，可进行实时FFT运算。在设计中用FIFO存储中间数据，并将旋转因子固定为乘法器IP的常数系数，以进一步提高处理器的速度。因为采用并行结构，所以FPGA硬件资源消耗较多，系统功耗也相应增大，如何根据系统实际需求找到速度与资源的平衡至关重要。