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

    1．引言
 
    DFT及其快速算法FFT是信号处理领域的核心组成部分。FFT算法多种多样，按数据组合方式不同一般分时域和频域，按数据抽取方式的不同又可分为基2，基4等。各算法的优缺点视不同的制约因素而不同。FFT的实现方法也多种多样，可以用软件实现，也可以用硬件实现，用软件在PC机或工作站上实现则计算速度很慢。一般多结合具体系统用硬件实现。例如用单片机或DSP实现。但是速度仍然很慢，难以与快速的A/D器件匹配。在雷达信号处理领域主要追求的目标是速度，即实时性的要求非常高。针对这种快速信号处理的要求及FPGA器件的特点，本文采用的是一种基2固定几何结构的FFT算法。采用的是Altera公司推出的最新器件Stratix来做硬件仿真。Stratix器件是一款采用高性能结构体系的PLD器件。它结合了强大内核性能，大存储带宽，数字信号处理（DSP）功能，高速I/O性能和模块化设计与一体的PLD。其内嵌的DSP模块具有很高的乘法运算速度。在用VHDL编程时可以用MegaWizard的方法指定用DSP模块生成乘法器，用这种乘法器来做蝶形，用多个蝶形来构成FFT运算级，通过循环即可实现FFT核心运算的并行化。用Altera公司的Quartus软件做逻辑分析和波形分析。Quartus软件具有很强的硬件仿真和逻辑分析功能，它可将用VHDL编写的硬件描述综合到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源程序。