固定几何结构的FFT算法及其FPGA实现.docx
3页
固定几何结构的FFT算法及其FPGA实现DFT及其快速算法FFT是信号处理领域的核心组成部分FFT算法多种多样，按数据组合 方式不同一般分时域和频域，按数据抽取方式的不同又可分为基2,基4等各算法的优缺 点视不同的制约因素而不同FFT的实现方法也多种多样，可以用软件实现，也可以用硬 件实现，用软件在PC机或工作站上实现则计算速度很慢一般多结合具体系统用硬件实现 例如用单片机或DSP实现但是速度仍然很慢，难以与快速的A/D器件匹配在雷达信号 处理领域主要追求的目标是速度，即实时性的要求非常高针对这种快速信号处理的要求及 FPGA器件的特点，本文采用的是一种基2固定几何结构的FFT算法采用的是Altera公 司推出的最新器件Strati来做硬件仿真Strati器件是一款采用高性能结构体系的PLD器 件它结合了强大内核性能，大存储带宽，数字信号处理（DSP）功能，高速I/O性能和模 块化设计与一体的PLD其内嵌的DSP模块具有很高的乘法运算速度在用VHDL编程时 可以用MegaWizard的方法指定用DSP模块生成乘法器，用这种乘法器来做蝶形，用多个 蝶形来构成FFT运算级，通过循环即可实现FFT核心运算的并行化。
用Altera公司的Qu artus软件做逻辑分析和波形分析Quartus软件具有很强的硬件仿真和逻辑分析功能，它 可将用VHDL编写的硬件描述综合到FPGA中2.算法介绍为了说明问题的方便，下面以基2，八点FFT为例加以说明传统的基2变几何结构算法 如下（图一）：箭头上的数字代表旋转因子中的k图中输入采用的是按码位颠倒的顺序 排放的输出是自然顺序这种结构的特点是每个蝶形的输出数据仍然放在原来的输入的数 据存储单元内，这样只需要2N个存储单元（FFT中的数据是复数形式，每点需要两个单元 存储）其缺点是不同级的同一位置蝶形的输入数据的寻址不固定，难以实现循环控制用FPGA编程时难以并行实现，数据处理速度慢当FFT的点数增加时更是如此通过观察传统结构的FFT算法可以发现，如果将第一级中间的两个蝶形交换，则可以得到如下结构 (图二)：对此结构进行进一步的变换，将第二级的输出不送回原处而是将其存储起来并按顺序存放， 则第三级中间的两个蝶形跟着调换，并把输入按顺序排列，就变成了如下(图三)所示的固 定结构的FFT 了在蝶形变换的同时，其旋转因子也跟着调换出数据的顺序是不变的，因此每级几何结构是固定的。
用这种结构寻址方便，易于用FPGA 编程，实现内部并行的FFT硬件结构，从而明显加快FFT的运算速度3. FPGA硬件实现FPGA器件的特点是可用硬件描述语言对其进行灵活编程利用FPGA厂商提供的软件可 仿真硬件的功能使硬件设计如同软件设计一样灵活方便缩短了系统研发周期利用JT AG接口可对其进行ISP(In System Programmable在系统编程)提高了系统的灵活性随 着芯片集成度的提高，单片FPGA内不仅拥有大量的逻辑单元而且还能集成RAM,ROM,I/ O及DSP块等从而使SOC(System On_a_Chip片上系统)成为现实本文采用的是Alt era公司的Stratix系列芯片的EP1s25用Altera公司的QuartusII2.0软件做硬件仿真和逻 辑分析并将输出结果与Matlab仿真结果进行了比较系统框图如下(图四)：代码用VHDL硬件描述语言实现本系统的结构特点是：1为提高数据精度，系统全部用 16位宽用data_array，write_array和fly_array三个数组实现了内核的并行处理，可在1 0个时钟周期内算完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算法其3 2点的运算时间大于1.0US用DSP做的32点FFT时间也要1.0us以上本系统的最大优 势在于利用FPGA器件丰富的逻辑资源，内嵌的RAM,ROM块及其灵活的可编程特性采用 固定几何结构的FFT算法使运算速度较传统方法有了很大提高。
当然付出的代价是用这种 并行的结构需求的硬件资源很多随着芯片集成度的不断提高，用这种并行结构实现的FF T运算其优越性将越来越明显而且用这种结构实现的FFT很容易扩展只需要增加蝶形 的个数和循环次数即可详细说明见VHDL源程序。
