FFT算法，全称为快速傅里叶变换（Fast Fourier Transform），是一种高效计算离散傅里叶变换（Discrete Fourier Transform，DFT）的算法。FFT算法最早由J.W. Cooley和J.W. Tukey于1965年提出，之后不断发展，其发展主要分为两大方向：一种是针对N等于2的整数次幂的算法，如基2算法、基4算法和分裂基算法等；另一种是N不等于2的整数次幂的算法，例如素因子算法、Winograd算法等。基2算法是目前最为常用的FFT算法，它将N点的序列分解为(N-1)/2点的子序列，最后分解为2点进行计算，以此消除大量重复运算。
FFT算法在时域或频域中对序列进行分解，存在时间抽取法（decimation in time，DIT）和频率抽取法（decimation in frequency，DIF）两种形式。时间抽取法需对输入数据进行重排序，而频率抽取法则需对输出数据进行重排序。FFT算法广泛应用于数字信号处理、图像处理、石油勘探和地震预测等多个领域。
为便于FFT算法在工程实践中的应用，各大FPGA厂商推出了相应的IP模块库。Xilinx公司推出的IP核Fast Fourier Transform v5.0提供了多种可选的计算参数、结构和数据流顺序，能够根据用户需求实现FFT算法。该IP核最高系统时钟频率为550MHz，数据吞吐量可达550MSPS，支持最高65536点FFT运算，最大输入数据和相位因子位宽为24bit。Xilinx FFT IP核支持所有主流Xilinx FPGA芯片，实现N点实数或复数形式的FFT变换及FFT逆变换（IFFT），N的取值范围为8到65536。
在实现FFT算法时，Xilinx IP核以硬件描述语言（HDL）设计文件为基础，这些验证的功能针对所有Xilinx FPGA器件的结构都能达到最优化。IP核还提供了硬件描述语言（VHDL，Verilog）的功能仿真模型，便于在标准EDA仿真工具中进行设计和调试。
Xilinx FFT IP核有四种结构可供选择，用户可以根据逻辑资源使用多少和转换时间的长短进行取舍。具体选择包括：流水线结构、基4 Burst I/O结构、Burst I/O结构和Streaming I/O结构。流水线结构允许连续的数据处理，使用最多的逻辑资源；基4 Burst I/O结构在数据导入、导出阶段和处理阶段使用分离的硬件资源；Burst I/O结构适合于数据点数不超过1024点的应用场景；Streaming I/O结构则适合于数据长度不确定的连续流数据处理，并能通过混合存储的方式，即部分使用Block RAM存储，其余使用Distributed RAM。
在FPGA平台上实现FFT算法需要进行数据和相位因子的位宽选择、二进制补码形式表示、以及数据重排序等操作。数据及相位因子和输出数据的缓存可以通过Block RAM或Distributed RAM存储，Block RAM适合存储任意点数的数据和相位因子，而Distributed RAM则适合于点数不超过1024的数据和相位因子存储。对于Burst I/O结构，分布式RAM只能存储点数不超过1024的数据和相位因子。在实际应用中，用户可根据实际需要和系统要求选择合适的存储方案，以达到最优的性能和资源使用效果。
