第8章 FFT设计 8.1 FFT的原理 8.2 FFT与蝶形运算 8.3 使用DSP Builder设计FFT 8.4 在DSP Builder中使用FFT IP Core

8.1 FFT的原理 8.1.1 快速傅立叶变换FFT 对于一个N点有限长序列，其DFT变换可表示为 其中：k=0，1，…，N－1；

假如、都为复数，计算N点序列的DFT共需要次复数乘法和次复数加法，在N较大时，计算量不可想象。 可以发现， 存在下列对称性和周期性： 其中 是 的共轭。

利用上述对称性和周期性，可以大大简化DFT的运算。同时，可以把较多点的DFT分解为多个较少点的DFT运算。由于DFT的运算量与成正比，减少DFT的点数可以大大减少DFT的总运算量。不断地继续分解得到的DFT，可以加快DFT的运算过程，这种DFT的快速计算方法，我们称为FFT。若分解是对输入序列进行处理，称为时间抽取DIT(Decimation In Time)；反之，若分解是对输出序列进行处理，则称为频率抽取FIT(Decimation In Frequency)。

用DIT方法，N点的DFT可以用下式计算： 其中k=0，1，2，…，(N/2)－1。 可用图8-1来描述其运算的信号流图。由于该运算 状似蝶形，故被称为蝶形运算。

图8-1 DIT蝶形运算信号流图

对于，可以一直分解到2点DFT。这样，离散傅立叶变换的运算量就大大减少了，这种DFT的快速算法就是FFT。 图8-2显示了当N=8时DIT FFT的信号流图。

图8-2 N=8时FFT算法的信号流图

8.1.2 快速傅立叶反变换IFFT DFT是时域到频域的变换，同样也存在频域到时域的变换，即DFT的逆变换IDFT。对于频域上的抽样序列，其IDFT变换可表示为 其中： ；n=0，1，…，N－1。 可以看到IDFT的运算可由DFT运算得到。 对应与IDFT，也存在快速算法IFFT，这是由FFT来实现的。

8.2 FFT与蝶形运算 仔细观察图8-2可以发现，对于N是2的幂次的FFT运算有大量的形如图8-3的运算，即FFT由蝶形运算构成，实现了蝶形运算，FFT就可以实现了。 图8-3 蝶形运算

由于蝶形运算涉及复数运算，较为复杂，DSP Builder为能实现FFT模型的建构，专门引入了蝶形算子模块Butterfly，如图8-4。

Butterfly模块可以完成复数有符号数的蝶形运算。对于输入信号(复数) a=x+jX b=y+jY 蝶形运算系数： 蝶形运算：

8.3 使用DSP Builder设计FFT 由于FFT的算法过于复杂，在以往的数字信号处理器上实现一个高速信号的FFT变换是不可想象的。数字信号处理器固有的串行(顺序)执行结构，对一个高速(与该处理器的主频相当)的信号序列进行FFT，是很难实现的。然而，在FPGA上实现时，可以采用并行分布式结构，实现一个实时FFT的难度就比较小了。

8.3.1 8点DIT FFT模型的建立 在本节将介绍如何实现一个N=8的时间抽取FFT模型。 按照第3章的流程，在Simulink中建立一个新模型。参照图8-2的结构，调用DSP Builder模块完成DIT8FFT模型的绘制。模型如图8-5所示。

图8-5 DIT8FFT模型

DIT8FFT模型中各个模块的参数设置如下： X模块：(Altbus) 库：Altera DSP Builder中Bus Manipulation库 参数“Bus Type”设为“signed Integer” 参数“[number of bits].[]”设为“8”   XR、XR1、XR2、XR3、XR4、XR5、XR6、XR7模块：(Altbus) 参数“[number of bits].[]”设为“16”

XI、XI1、XI2、XI3、XI4、XI5、XI6、XI7模块：(Altbus) 库：Altera DSP Builder中Bus Manipulation库 参数“Bus Type”设为“signed Integer” 参数“[number of bits].[]”设为“16”   Shift Taps模块：(Shift Taps) 库：Altera DSP Builder中Storage库 参数“Number of Taps”设为“8” 参数“Distance Between Taps”设为“1”

选择“Use Deicated Circuitry”   x0、x1、x2、x3、x4、x5、x6、x7模块：(Real=Imag to Complex) 库：Altera DSP Builder中Complex Signals库 参数“Bus Type”设为“Signed Integer” 参数“[number of bits].[]”设为“8”

Constant、Constant1、Constant2、Constant3、 Constant4、Constant5、Constant6、Constant7模块：(Constant) 库：Altera DSP Builder中Bus Manipulation库 参数“Bus Type”设为“signed Integer” 参数“[number of bits].[]”设为“8” 参数“Constant Value”设为“0” 参数“Sampling Period”设为“－1”

W0、W0_1、W0_2、W0_3模块：(Complex Constant) 库：Altera DSP Builder中Complex Signals库 参数“Bus Type”设为“signed Integer” 参数“[number of bits].[]”设为“8” 参数“[].[number of bits]”设为“0” 参数“Real Value”设为“127” 参数“Imaginary Value”设为“0”

butterfly000、butterfly001、butterfly002、butterfly003模块：(butterfly) 库：Altera DSP Builder中Complex Signals库 参数“Input bit width(a,b,W)”设为“8” 参数“Output bit width(A,B)”设为“16” 参数“Output lsb bit”设为“2”

W0_6、W2_5、W0_4、W2_7模块：(Complex Constant) 库：Altera DSP Builder中Complex Signals库 参数“Bus Type”设为“signed Integer” 参数“[number of bits].[]”设为“16” 参数“[].[number of bits]”设为“0” 对于W0_6、W2_5 参数“Real Value”设为“1” 参数“Imaginary Value”设为“0” z对于W0_4、W2_7

参数“Real Value”设为“0” 参数“Imaginary Value”设为“127”   butterfly010、butterfly020、butterfly030、butterfly040模块：(butterfly) 库：Altera DSP Builder中Complex Signals库 参数“Input bit width(a,b,W)”设为“16” 参数“Output bit width(A,B)”设为“16” 参数“Output lsb bit”设为“2”

W0_6、W2_5、W0_4、W2_7模块：(Complex Constant) 库：Altera DSP Builder中Complex Signals库 参数“Bus Type”设为“signed Integer” 参数“[number of bits].[]”设为“8” 参数“[].[number of bits]”设为“0” 对于W0_8 参数“Real Value”设为“127” 参数“Imaginary Value”设为“0” 对于W2_10

参数“Real Value”设为“0” 参数“Imaginary Value”设为“127” 对于W1_9、W3_11 参数“Real Value”设为“90” 参数“Imaginary Value”设为“90”   X0、X1、X2、X3、X4、X5、X6、X7模块：(Complex to Real-Imag) 库：Altera DSP Builder中Complex Signals库 参数“Bus Type”设为“Signed Integer” 参数“[number of bits].[]”设为“8”

在DIT8FFT模型中除了使用Butterfly模块进行蝶形运算外，还使用了有符号数到复数、复数到有符号数的转化，运算量是较大的。

8.3.2 8点DIT FFT模型的实现 通过SignalCompiler，把上面的FFT模型转换成VHDL，在Quartus II中进行编译下载。 图8-6显示了Synplify Pro的综合结果。

图8-6 综合结果(部分)

8.4 在DSP Builder中使用FFT IP Core 上面列举了一个8点FFT模型的例子。然而在实际应用中，8点的FFT是远远不够用的，往往需要N=512或者N=1024的情况。但是，若以以上的方法进行设计，8点FFT已经相当复杂了，再用DSP Builder模块来搭建N=1024的FFT是不可想象的，而且很难优化。 Altera提供了FFT IP Core帮助设计者绕过这个难题。 Altera的FFT IP Core称为FFT Compiler，也可以与DSP Builder完美地结合起来(见图8-7)。

图8-7 FFT Compiler模块

首先建立一个新的模型，调入FFT Compiler模块和SignalCompiler模块。双击FFT Compiler模块，进行FFT核的配置(见图8-8)。

图8-8 FFT核模块的配置

对于FFT Compiler而言，它同时支持FFT和FFT的反变换IFFT。在图8-8中，可以选择类型(Type)为FFT，然后选择相应的器件系列和输入序列数据位宽，选定FFT的点数。 点击“Next”，完成设置过程(如图8-9)。 然后，在DSP Builder中就可以像其它DSP模块一样使用FFT核了。

图8-9 完成FFT核设置