FFT   算法是计算DFT的高效算法。算法最初由J.W.Cooley和J.W.Tukey于1965年提出，之后又有新的算法不断涌现，总的来说发展方向有两个：一是针对N等于2的整数次幂的算法，如基2算法、基4算法和分裂基算法等； 另一个是N不等于2 的整数次幂的算法，如素因子算法、Winograd算法等。其中基2算法是目前所常用的FFT算法，其核心思想是将N点的序列逐次分解为（N-1）/2点，最后分解为2点DFT进行计算，从而消除DFT中大量的重复运算。

FFT算法可从时域或频域对序列进行分解：

①时间抽取法（DIT），即直接将序列x（n）按奇、偶逐次分成奇数子序列和偶数子序列，然后通过计算子序列的DFT来实现整个序列的DFT；

② 频率抽取法（D     IF   ），即将频域X（k）的序号k按照奇、偶逐次分解成偶数点子序列和奇数点子序列，然后计算子序列的DFT，得到整个频域内的DFT。

时间抽取法和频率抽取法的计算复杂程度和所需要的计算量都是相同的，且由两种方法不同的分解形式可知：时间抽取法需要对输入数据序列x（n）进行重新排序，频率抽取法需要对输出数据序列X［k］进行进行排序。

目前FFT算法已经广泛应用于数字信号处理、图像处理、石油勘探和地震预测等众多领域。与此同时，为了便于FFT算法在工程实践中的应用，各大     FPGA   生产商也都纷纷推出了具有相关功能的IP模块库。其中由Xilinx公司研发的IP核Fast Fourier Transform V7.1提供了FFT算法多种可选的计算参数、结构、数据输入输出流的顺序方式，可以根据用户的需求方便地实现FFT算法。

2 Xilinx FFT IP核功能实现

Xilinx IP核功能是基于复杂系统功能的硬件描述语言（HDL）设计文件，这些验证的功能对于所有的Xilinx FPGA器件的结构都能够达到最优化，且提供硬件描述语言（VHDL，     Verilog   ）的功能仿真模型，可以在标准     EDA   仿真工具中进行设计和调试。

Xilinx FFT IP核V7.1是Xilinx公司配套其FPGA开发工具ISE14.1推出的，其最大的系统     时钟   频率达到了550MHz，最大的数据吞吐量达到550MSPS，最高可进行65536点的FFT运算，最大输入数据和相位因子位宽为34bit，支持所有的主流Xilinx FPGA芯片。同时，Xilinx FFT IP核V7.1可以实现变换长度为N点实数或复数形式的FFT变换及FFT逆变换（IFFT），N的取值范围是（8~65536）。输入数据实部和虚部都要以位宽为M bits的二进制补码形式表示，M取值范围是（8~34）；同样，相位因子位宽取值范围也是（8~34）。数据、相位因子以及输出数据重排序的缓存数据，在FFT实现的过程中，都可以用块     RAM   或者分布式RAM进行     存储   。对于Bu     rs   t     I/O   结构， 块RAM可以存储任意点数的数据和相位因子，而分布式RAM则只能存储点数不大于1024点的数据和相位因子；对于Strea     mi   ng I/O结构，可采用混合存储的方法，先选择使用块RAM     存储器   的阶数的数量，然后对剩余的采用分布式RAM。

Xilinx FFT IP核有四种结构可供选择，用户可以在逻辑资源使用的多少和转换时间的长短之间进行取舍，具体情况分别如下：

① 流水线，Streaming I/O结构：允许连续的数据处理，使用最多的逻辑资源。

② 基4，Burst I/O结构：提供数据导入/导出阶段和处理阶段，导入数据和处理数据时单独进行的。此结构拥有较小的结构，但是转换时间较长。

③ 基2，Burst I/O结构：使用较少的逻辑资源，同基4阶段，提供两阶段的过程。

④ 基2 Li     te   Burst I/O结构：这是一种基于基2结构的变体，采用了时分复用的方法使用了最少的逻辑资源，但是转换时间最长。

对于Burst I/O结构，使用DIT抽取法；流水线，Streaming I/O结构则使用DIF抽取法。

在实际硬件操作中，模块的执行速度是很重要的参数，因此本文进行的是基于流水线，Streaming I/O结构的仿真验证，进行连续的数据处理。流水线，Streaming I/O结构对一系列基2蝶形处理引擎采用流水线技术设计，且每个蝶形处理引擎都有自己独立的存储体对输入数据和中间数据进行存储。这种结构下，FFT IP核具有同时处理当前帧N点数据，载入下一帧N点数据，输出前一帧N点数据的能力。

Xilinx FFT IP核V5.0支持三种算法型：全精度无压缩、块浮点型和定点压缩（压缩比由用户自定义）。对于全精度无压缩结构，数据通道内任意一位有意义的整数都将被保留，在运算过程中产生的小数部分都被截断或者取整。此种结构，对于定点算法，经过多级乘法操作以后，数据位宽将加倍递增，其输出位宽为（输入位宽+log2（数据转换长度）+1）bits。对于块浮点型，对于一帧数据里面的任何一数据点有相同的压缩比，这个压缩比值由块指数（Block Exponent）作为输出值显示，而且只有在FFT IP核检测到将会产生数据溢出的时候，才会进行压缩运算。