基于FPGA IP核的FFT实现

1 算法原理
FFT算法是基于离散傅里叶变换(DFT)，如式(1)和式(2)：

求和运算的嵌套分解以及复数乘法的对称性得以实现。其中一类FFT算法为库利一图基(Cooley-Tukey)基r按频率抽选(DIF)法，将输入序列循环分解为N／r个长度为r的序列，并需要logr N级运算。算法的核心操作是蝶型运算，蝶型运算的速度直接影响着整个设计的速度。
基4频域抽取FFT算法是指把输出序列X(k)按其除4的余数不同来分解为越来越短的序列，实现x(n)的DFT算法。FFT的每一级的运算都是有N／4个蝶形运算构成，第m级的一个蝶形运算的四节点分别为Xm(k)，Xm(k+N／4m)，Xm(k+2N／4m)以及Xm(k+3N／4m)，所以每一个蝶形运算结构完成以下基本迭代运算：

式(3)～式(6)中：m表示第m级蝶形算法；k为数据所在的行数；N为所要计算的数据的点数；WN为旋转因子。
将输入序列循环分解为4点序列的基4分解，使用4点FFT在乘法上更具优势，Altera的：FFT兆核选用的就是基4运算，若N是2的奇数幂的情况下，FFT IP核则自动在完成转换的最后使用基2运算。

2 FFT兆核(IP)函数
FFT Core支持4种I／O数据流结构：流(Stream-ing)、变量流(Variable Streaming)、缓冲突发(BufferedBurt)、突发(Burst)。流结构允许输入数据连续处理，并输出连续的复数据流，这个过程不需要停止FFT函数数据流的进出。变量流结构允许输入数据连续处理，并产生一个与流结构相似连续输出数据流。缓冲突发数据流结构的FFT需要的存储器资源比流动I／O数据流结构少，但平均模块吞吐量减少。突发数据流结构的执行过程和缓冲突发结构相同，不同的是，对于给定参数设置，突发结构在降低平均吞吐量的前提下需要更少的存储资源。

3 FFT处理器引擎结构
FFT兆核函数可以通过定制参数来使用两种不同的引擎结构：四输出(Quad-outlput)或单输出(Signal-output)引擎结构。为了增加FFT兆核函数的总吞吐量，也可以在一个FFT兆核函数变量中使用多个并行引擎。本文建立一个基于QuartusⅡ7.O计算24位512点FFT工程，采用四输出FFT引擎结构，如图1所示。

复取样数据X[k，m]从内部存储器并行读出并由变换开关(SW)重新排序，排序后的取样数据由基4处理器处理并得到复数输出G[k，m]，由于基4按频率抽选(DIF)分解方法固有的数字特点，在蝶形处理器输出上仅需要3个复数乘法器完成3次乘旋转因子(有一个因子为1，不需要乘)计算。这种实现结构在一个单时钟周期内计算所有四个基4蝶形复数输出。
同时，为了辨别取样数据的最大动态范围，四个输出由块浮点单元(BFPU)并行估计，丢弃适当的最低位(LSB)，在写入内部存储器之前对复数值进行四舍五入并行重新排序。对于要求转换时间尽量小的应用，四输出引擎结构是最佳的选择；对于要求资源尽量少的应用，单输出引擎结构比较合适。为了增加整个FFT吞吐量，可以采用多并行的结构。

4 系统验证
4．1 工程仿真
选择CycloneⅡ系列的EP2C70F896C8芯片来实现，先在QuartusⅡ软件下进行综合仿真，初始化参数设置FFT变换长度为512点，数据和旋转因子精度为24 b，选择缓冲突发的数据流结构，四输出引擎并行FFT引擎个数为4个，复数乘法器结构为“4／Mults／2Adders”。EP2C70F896C8芯片包括68 416个逻辑单元，31 112个寄存器单元，最大用户输入／输出引脚622个，总RAM达1 152 000 b，其布线资源由密布的可编程开关来实现相互间的连接，这种结构完全符合实现FFT电路的要求。
经综合和时序分析得知：其工作时钟频率
69．58 MHz(period=14．372 ns)，进行一次蝶形运算只需约14 ns，全部512点数据处理完成则需14．372×4×512=29．3μs满足时序要求。具体综合结果如图2所示，为Quartus软件环境下仿真得到。

图3则表明了FFT的综合逻辑结果，为编译成功后的RTL级电路描述。