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

王英喆 ，杜 蓉

（1.北京大学 软件与微电子学院，北京 100871；2.中科院国家空间中心 北京 100190）

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

1 数学模型

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

一般情况下，长度为N的有限长序列x(n)的DFT为：

根据公式(1)(2)得到的基2与基4计算公式如下：

2 结构说明

2.1 流水线结构

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

2.2 并行处理

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

3 硬件设计

3.1 逻辑设计

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

图1 逻辑框图Fig.1 Logic diagram

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

图2 FFT流水线结构Fig.2 Pipelined architecture of FFT

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

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

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

3.2 时序设计

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

图3 FFT基4框架图Fig.3 Radix-4 framework of FFT

图4 流水设计Fig.4 Pipeline design

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_real、o_data_imag，并根据end信号将向量写入相应文档中，与正确结果进行比对。

图5 Testbench示意图Fig.5 Testbench diagram

5 仿真结果

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

图6 FFT仿真波形Fig.6 Simulation waveforms of FFT

6 综合结果

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

7 结束语

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

表1 FPGA资源利用表Tab.1 FPGA resource utilization table

[1]陆旦前，陈建平，陈晓勇.FFT算法的一种FPGA设计[J].现代电子技术，2007(6):178-187.LU Dan-qian,CHEN Jian-ping,CHEN Xiao-yong.A FPGA Design of FFT Algorithm [J].Modern ElectronicTechnique,2007(6):178-187.

[2]姚国珍.基于MegaCore的FFT模块在FPGA上的实现[J].山西电子技术，2008(2):53-56.YAO Guozhen.The Implementation of FFT Module in FPGA Based on MegaCore [J].Shanxi Electronic Technology,2008(2):53-56.

[3]高亚军.基于FPGA的数字信号处理[M].北京：电子工业出版社，2012.

[4]周景龙.基于高速FFT结构的频域抗干扰算法的FPGA实现[J].微电子学与计算机，2014.31(5):32-35.ZHOU Jing-long.A FPGA Implementation of frequency-domain anti-jamming algorithm based on a structure of highspeed FFT[J].Microelectronics&computer,2014,31(5):32-35.

[5]石长振，杨雪，王贞松.高性能并行FFT处理器的设计与实现[J].计算机工程，2012,38(2):242-247.SHI Chang-zhen,YANG Xue,WANG Zhen-song.Design and realization of high performance parallel FFT processor[J].Computer Engineering,2012,38(2):242-247.

[6]刘万明，王鲁平，杨卫平.基于FPGA的高速定点FFT处理器的设计[J].现代电子技术，2007(22):41-45.LIU Wan-ming,WANG Lu-ping,YANG Wei-ping.Design of high speed fixed-point FFT processor based on FPGA[J].Modern ElectronicTechnique,2007(22):41-45.