固定几何结构的FFT算法及其FPGA实现

．引言

2．算法介绍

为了说明问题的方便，下面以基2，八点FFT为例加以说明。传统的基2变几何结构算法如下（图一）：箭头上的数字代表旋转因子 中的k。图中输入采用的是按码位颠倒的顺序排放的。输出是自然顺序。这种结构的特点是每个蝶形的输出数据仍然放在原来的输入的数据存储单元内，这样只需要2N个存储单元（FFT中的数据是复数形式，每点需要两个单元存储）。其缺点是不同级的同一位置蝶形的输入数据的寻址不固定，难以实现循环控制。用FPGA编程时难以并行实现，数据处理速度慢。当FFT的点数增加时更是如此。通过观察传统结构的FFT算法可以发现，如果将第一级中间的两个蝶形交换，则可以得到如下结构（图二）：

对此结构进行进一步的变换，将第二级的输出不送回原处而是将其存储起来并按顺序存放，则第三级中间的两个蝶形跟着调换，并把输入按顺序排列，就变成了如下（图三）所示的固定结构的FFT了。在蝶形变换的同时，其旋转因子也跟着调换。

出数据的顺序是不变的，因此每级几何结构是固定的。用这种结构寻址方便，易于用FPGA编程，实现内部并行的FFT硬件结构，从而明显加快FFT的运算速度。

3．FPGA硬件实现

FPGA器件的特点是可用硬件描述语言对其进行灵活编程。利用FPGA厂商提供的软件可仿真硬件的功能。使硬件设计如同软件设计一样灵活方便。缩短了系统研发周期。利用JTAG接口可对其进行ISP(In System Programmable 在系统编程)提高了系统的灵活性。随着芯片集成度的提高，单片FPGA内不仅拥有大量的逻辑单元而且还能集成RAM,ROM,I/O及DSP块等。从而使SOC(System On_a_Chip 片上系统)成为现实。本文采用的是Altera公司的StraTIx系列芯片的EP1s25。用Altera公司的QuartusII2.0软件做硬件仿真和逻辑分析。并将输出结果与Matlab仿真结果进行了比较。系统框图如下（图四）：

代码用VHDL硬件描述语言实现。本系统的结构特点是：1。为提高数据精度，系统全部用16位宽。用data_array，write_array和fly_array三个数组实现了内核的并行处理，可在10个时钟周期内算完32点复FFT。时钟周期为25纳秒，因此32点FFT只需250纳秒。2。实现了数据的流水输入输出。在计算第i组数据的同时，第i-1组的数据FFT结果正在串行输出，第i+1组的数据则正在串行输入。因为内核计算是并行的，速度快，所以可以有很高的串行输入。本系统的A/D采样频率可达200MHz。仿真所用的信号是：

x(t)= (0.5*sin(2*n*pi/4.7)+0.5*sin(2*n*pi/16.3)+0.1*rand(1,32))*1000

输入数据为32点复数，系统仿真波形如下（局部）：

用FPGA输出的FFT的结果（图六）和用Matlab计算的FFT理论结果（图七）,其频谱如下：

此信号是由两个正弦波叠加一个随机函数构成的。信噪比为14db。为切合工程实际，仿真信号采用的是实信号，其频谱具有对称性，因此图中只取32点仿真结果的一半即16点便可。

4．结论

通过比较可以看出仿真结果与理论值吻合的很好。Altera公司采用传统结构的FFT算法其32点的运算时间大于1.0us。用DSP做的32点FFT时间也要1.0us以上。本系统的最大优势在于利用FPGA器件丰富的逻辑资源，内嵌的RAM,ROM块及其灵活的可编程特性采用固定几何结构的FFT算法使运算速度较传统方法有了很大提高。当然付出的代价是用这种并行的结构需求的硬件资源很多。随着芯片集成度的不断提高，用这种并行结构实现的FFT运算其优越性将越来越明显。而且用这种结构实现的FFT很容易扩展。只需要增加蝶形的个数和循环次数即可。详细说明见 VHDL源程序。