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

EDA/PCB 时间:2016-10-16来源:网络

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

1 数学模型

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

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

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蝶形算法。

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

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

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

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

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

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

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信号将向量写入相应文档中,与正确结果进行比对。

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

5 仿真结果

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

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

6 综合结果

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

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

7 结束语

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

关键词: FFT FPGA 流水线 并行处理

加入微信
获取电子行业最新资讯
搜索微信公众号:电子产品世界

或用微信扫描左侧二维码

相关文章


用户评论

请文明上网,做现代文明人
验证码:
查看电脑版