基于FPGA的FFT算法硬件实现

文章正文
发布时间:2024-10-02 06:22

FFT(快速傅里叶变换)是一种非常重要的算法,在信号处理、图像处理、生物信息学、计算物理、应用数学等方面都有着广泛的应用。在高速数字信号处理中,FFT的处理速度往往是整个系统设计性能的关键所在。FPGA(现场可编程门阵列)是一种具有大规模可编程门阵列的器件,不仅具有ASIC(专用集成电路)快速的特点,更具有很好的系统实现的灵活性。基于FPGA的设计可以满足实时数字信号处理的要求,在市
场竞争中具有很大的优势。因此,FPGA为高速FFT算法的实现提供了一个很好的平台。

1 FFT算法的硬件实现
1.1 系统框图

    本设计利用流水线技术来提高系统的性能,系统框图,如图1所示。其中,地址产生单元生成RAM读写地址,写使能信号以及相关模块的启动、控制信号,是系统的控制核心;4点蝶形运算单元的最后一级输出不是顺序的;旋转因子产生单元生成复乘运算中的旋转因子的角度数据;旋转因子ROM中预置了每一级运算中所需的旋转因子。


    在FPGA设计中,为提高系统的运行速度,而将指令分为几个子操作,每个子操作由不同的单元完成,这样,每一级的电路结构得到简化,从而减少输入到输出间的电路延时,在较小的时钟周期内就能够完成这一级的电路功能。在下一个时钟周期到来时,将前一级的结果锁存为该级电路的输入,这样逐级锁存,由最后一级完成最终结果的输出。也就是说,流水线技术是将待处理的任务分解为相互有关而又相互
独立、可以顺序执行的子任务来逐步实现。本设计中,4点蝶形运算单元、旋转因子复乘模块以及最后的精度截取模块采用流水线技术来处理。
1.2 基4蝶形运算算法原理   


    式(1)为基4蝶形运算单元的一般表达式,其中,

,N为FFT运算的点数,本设计中为1 024,p为旋转因子W的相位角,其规律将在1.4节讨论。X(0)、X(1)、X(2)、X(3)为原始数据,顺序输入RAM后蝶形倒序输出,与旋转因子复乘再进行4点蝶形运算,而X1(0)、X1(1)、X1(2)、X1(3)即为第1级蝶形运算的结果。此时RAM存储的原始数据已经清空,将第1级蝶形运算结果再存回RAM中,按照一定的地址输出后,与第2级的旋转因子复乘、4点蝶形运算,得到第2级蝶形运算结果,依此类推。由于蝶形运算为同址操作,所以第2级的RAM写地址即为第一级的RAM读地址,每一级的RAM读地址规律将在1.3节中讨论。
    1024点的基4-FFT共需要5级蝶形运算,每级需要计算256个蝶形,其传统实现框图如图2所示。

 


    考虑到第一级蝶形运算不需要旋转因子,所以第一级的旋转因子复乘模块可以省略,但本设计的硬件结构需要循环利用,一般情况下,可以对第一级数据进行×1运算,再进行4点蝶形运算。不过,考虑到我们并不关心每一级蝶形运算后的结果,本文提出了一种蝶形运算的新结构:即先进行前一级的4点蝶形运算,再进行本级的与旋转因子复乘运算,如图3所示。

可以看出,图3减少了一个旋转因子复乘模块,不但节约了一次乘法运算时间,也省略了第一级旋转因子,更好地利用了硬件结构。
    首先,在QuartusⅡ环境中对4点蝶形运算时序仿真,采用流水线设计,连续输入连续输出,仿真结果如图4所示。


    由图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Ⅱ环境中仿真结果的部分数据。

2 系统仿真结果
   
输入数据为s=1 024×cos(2π×f_in×t),其中f_in=50 M,Fs=80 MHz,n=40,t=0:1/Fs:(n-1)/Fs,利用QuartusⅡ软件对系统在100 MHz的时钟环境下进行了仿真,将仿真输出结果转换成tbl文件并利用Matlab软件读取后,得到如图7所示的频谱数据图(实部数据部分)。


    图8所示为Maflab自带FFT函数对于输入相同1 024点数据的FFT计算结果(同样为实部数据部分)。
    通过比较可以看到,本设计的仿真结果与Matlab的仿真结果基本一致,可以正确高效地计算出1 024点FFT数据。

3 结束语
   
本设计全部由Verilog HDL语言实现,采用自顶向下的设计方法,完成了一种基于FPGA的1 024点16位FFT算法,共需要5级运算,每级需要计算256个蝶形。提出了将蝶形运算先进行前一级的蝶形加减运算,再进行本级的与旋转因子复乘运算的结构。由前所述,平均每个蝶形运算需要4个时钟周期,所以理论上完成1 024点FFT的总时钟周期为N=256×4×5=5 120;假设使用的时钟为100MHz,那么将耗时T=5 120×(1/100)=51.2μs,这与仿真结果51.32μs基本一致。