傅立叶变换是时域-频域变换分析中最基本的方法之一，在数字处理领域应用的离散傅立叶变换（Discrete Fourier Transform，DFT）是许多数字信号处理方法的基础。FFT（Fast Fourier Transform，快速傅立叶变换）是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算法可从时域或频域对序列进行分解：
（1）时间抽取法（DIT），即直接将序列x（n）按奇、偶逐次分成奇数子序列和偶数子序列，然后通过计算子序列的DFT来实现整个序列的DFT。
（2）频率抽取法（DIF），即将频域X（k）的序号k按照奇、偶逐次分解成偶数点子序列和奇数点子序列，然后计算子序列的DFT，得到整个频域内的DFT。
时间抽取法和频率抽取法的计算复杂程度和所需要的计算量都是相同的，且由两种方法不同的分解形式可知：时间抽取法需要对输入数据序列x（n）进行重新排序，频率抽取法需要对输出数据序列X（k）进行排序。
目前FFT算法已经广泛应用于数字信号处理、图像处理、石油勘探和地震预测等众多领域。与此同时，为了便于FFT算法在工程实践中的应用，各大FPGA生产商也都纷纷推出了具有相关功能的IP模块库。其中由Xilinx公司研发的IP核Fast Fourier Transform V9.1提供了FFT算法多种可选的计算参数、结构、数据输入输出流的顺序方式，可以根据用户的需求方便地实现FFT算法。
XilinxIP核功能基于了复杂系统功能的硬件描述语言（HDL）设计文件，这些验证的功能对于所有的Xilinx FPGA器件的结构都能够达到最优化，且提供硬件描述语言（VHDL、Verilog）的功能仿真模型，可以在标准EDA仿真工具中进行设计和调试。
Xilinx FFT IP核V9.1是Xilinx公司配套其FPGA开发工具VIVADO推出的，其最大的系统时钟频率达到了550 MHz，最大的数据吞吐量达到550 Mb/s，最高可进行65 536点的FFT运算，最大输入数据和相位因子位宽为34 b，支持所有的主流Xilinx FPGA芯片。同时，Xilinx FFT IP核V9.1可以实现变换长度为N点实数或复数形式的FFT变换及FFT逆变换（IFFT），N的取值范围是8～65 536。输入数据实部和虚部都要以位宽为M的二进制补码形式表示，M取值范围是8～34。同样，相位因子位宽取值范围也是8～34。数据、相位因子以及输出数据重排序的缓存数据，在FFT实现的过程中，都可以用块RAM或者分布式RAM进行存储。对于Burst I/0结构，块RAM可以存储任意点数的数据和相位因子，而分布式RAM则只能存储点数不大于1 024点的数据和相位因子；对于Streaming I/0结构，可采用混合存储的方法。
Xilinx FFT IP核有4种结构可供选择，用户可以在逻辑资源使用的多少和转换时间的长短之间进行取舍，具体情况分别如下：(www.xing528.com)
（1）流水线、Streaming I/0结构：允许连续的数据处理，使用最多的逻辑资源。
（2）基4、Burst I/0结构：用于数据导入/导出阶段和处理阶段，导入数据和处理数据是单独进行的。此结构拥有较小的结构，但是转换时间较长。
（3）基2、Burst I/0结构：使用较少的逻辑资源，同基4结构，提供两阶段的过程。
（4）基2、Lite Burst I/0结构：这是一种基于基2结构的变体，采用了时分复用的方法，使用了最少的逻辑资源，但是转换时间最长。对于Burst I/0结构，使用DIT抽取法；对于Streaming I/0结构，则使用DIF抽取法。
在实际硬件操作中，模块的执行速度是很重要的参数，因此本文进行的是基于流水线、Streaming I/0结构的仿真验证，进行连续的数据处理。流水线，Streaming I/0结构对一系列基2蝶形处理引擎采用流水线技术设计，且每个蝶形处理引擎都有自己独立的存储体对输入数据和中间数据进行存储。这种结构下，FFT IP核具有同时处理当前帧N点数据，载入下一帧N点数据，输出前一帧N点数据的能力。
Xilinx FFT IP核V9.1支持三种算法型：全精度无压缩、块浮点型和定点压缩（压缩比由用户自定义）。对于全精度无压缩结构，数据通道内任意一位有意义的整数都将被保留，在运算过程中产生的小数部分都被截断或者取整。此种结构，对于定点算法，经过多级乘法操作以后，数据位宽将加倍递增，其输出位宽为[输入位宽+1og2（数据转换长度）+1]位。对于块浮点型结构，一帧数据里面的任何一数据点有相同的压缩比，这个压缩比值由块指数（Block Exponent）作为输出值显示，而且只有在FFT IP 核检测到将会产生数据溢出的时候，才会进行压缩运算。
本文所采用的是定点压缩结构。该结构相对于全精度无压缩结构，能够大大减少FPGA内部资源Xtreme DSP Slices和块RAM的使用，而相对于块浮点型，可灵活调节压缩比。定点压缩结构的压缩比例表（Scale _SCH）完全由用户自定义得到。压缩比例是按照1、2、4或者8对每一阶进行压缩，即对应于分别向右移位0、1、2或者3。如果压缩不充分，则蝶形输出结果会超出其动态范围，引起数据溢出。对于Burst I/0结构，Sca1e-SCH 的表示方法，对于每一阶的压缩比都由指定的一个2 b的数表示，零阶的2 b数为最低位，具体形式为[N4，N3，N2，N1，N0]，每一个2 b数分别对应着相应阶数的压缩比。例如，对于基4结构，数据转换长度N-1024，Scale-SCH-[01 10 001110]则表示对阶0右移位2，对阶1右移位3，对阶2右移位0，对阶3右移位2，对阶4右移位1。经验总结（可以防止产生数据溢出）：对于1 024点的基4、Burst I/0结构，Scale- SCH-[10 10 10 10 11]；而对于1 024点的基2结构，Scale-SCH-[01 0101 01 01 01 01 01 01 10]。
对于流水线、Streaming I/0结构，把邻近的一对基2阶组在一起，即阶0和阶1为组0，阶2和阶3为组1，等等。Scale.SCH的表示方法：对于每一组的压缩比都由指定的一个2 b的数表示，零组的2 b数为最低位，具体形式为[N4，N3，N2，N1，N0]，每一个2 b数分别对应着相应组的压缩比，表示同组内的两个基2阶有相同的压缩比。例如，数据长度N-1024，Sca1e-SCH-[1010 00 01 11]表示对组0（阶0和阶1）右移位3，对组1（阶2和阶3）右移位1，对组2（阶4和阶5）没有移位，对组3（阶6和阶7）右移位2，对组4（阶8和阶9）右移位2。若变换长度N不是4的幂次方的时候，最后一组只包含一个基2阶，只能用00或者01表示。经验总结（可以防止产生数据溢出）：N-512时，Scale.SCH-[0110 10 1011]；N-1024时，Scale-SCH-[10 10 10 10 11]。压缩比例Sca1e-SCH的位宽，对于流水线、Streaming I/O结构和基4、Burst I/O结构，为2*cei1（0.5*1og2（N））；对于基2、Burst I/O结构和基2、Lite Burst I/O结构，为2*1og2（N），其中N为转换数据长度。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
