第3章 快速傅里叶变换FFT.ppt

* DIT-FFT算法的其他形式流图 根据流图的一些等效变换如转置等可得到其它形式的DIT-FFT算法，包括输入自然顺序，输出倒位序（书中图4-10）；输入输出均为自然顺序(图4-11)等结构 这些结构各有特点，但均完成的是FFT运算且运算量相当，有兴趣的同学可以证明一下各种DIT-FFT结构的等效性 结构特点： 输入输出均为自然顺序的结构免去了倒位序的处理（图4-11） 各级几何形状相同的结构便于模块化硬件实现（图4-12，图4-13） * 3.3 按频率抽选（DIF）的基-2 FFT（桑德-图基）算法 DIF-FFT，顾名思义，是对输出序列X(k)按其顺序的奇偶进行逐步分解，进而推导出的FFT算法 * DIF-FFT算法原理 设序列x(n)的点数N=2L，L为整数，故X(k)的长度也为N，将X(k)按照k的奇偶分组与将x(n)按照n的奇偶分组运算有所不同 算法： 上式是N点DFT的一种变换形式（由WNnk决定的N点DFT，而非N/2点的DFT） * DIF-FFT算法原理 而WNN/2k=(-1)k，故 下面按k的奇偶分组，k为偶数时，(-1)k=1，k为奇数时，(-1)k=-1，故由(4-10)可得 式(4-11)是序列x(n)的前一半和后一半之和的N/2点DFT运算 * DIF-FFT算法原理 令 则有 其中x1(n)、x2(n)对应的DFT X1(k)、X2(k)分别是X(k)的偶序列和奇序列 式(4-12)显然也可由蝶形运算流图(如下图)单元完成 -1 * DIF-FFT算法原理 综合(4-12), (4-13)式，可得经过一级分解后的DIF-FFT流图如右图(图8)(N=8) X(0) X(2) X(4) X(6) X(1) X(3) X(5) X(7) N/2点 DFT N/2点 DFT -1 -1 -1 -1 x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) WN0 WN1 WN2 WN3 x1(0) x1(1) x1(2) x1(3) x2(0) x2(1) x2(2) x3(3) * DIF-FFT算法原理 与DIT-FFT类似，由于N=2L，故可以对上图中的两个N/2点DFT再利用上述的分解方法进行分解，这种分解可以一直进行下去，共L级。如上图(图8a) (N=8) X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7) N/4点 DFT -1 -1 -1 -1 WN0 WN1 WN2 WN3 WN0 WN2 WN0 WN2 N/4点 DFT N/4点 DFT N/4点 DFT -1 -1 -1 -1 x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) x1(0) x1(1) x1(2) x1(3) x2(0) x2(1) x2(2) x3(3) x3(0) x3(1) x4(0) x4(1) x5(0) x5(1) x6(0) x6(1) * DIF-FFT算法原理 分解至第L级，实际上只剩下两点DFT运算了，这个两点DFT运算可用蝶形结构实现(如上图8b所示) X(0)=X3(0) X(4)=X3(1) X(2)=X4(0) X(6)=X4(1) X(1)=X5(0) X(5)=X5(1) X(3)=X6(0) X(7)=X6(1) -1 -1 -1 -1 WN0 WN1 WN2 WN3 WN0 WN2 WN0 WN2 -1 -1 -1 -1 x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7) x1(0) x1(1) x1(2) x1(3) x2(0) x2(1) x2(2) x3(3) x3(0) x3(1) x4(0) x4(1) x5(0) x5(1) x6(0) x6(1) WN0 WN0 WN0 WN0 －1 －1 －1 －1 * DIF-FFT算法原理 对于DIF-FFT运算，在实现时也存在与DIT-FFT运算一样的问题，即原位运算；蝶形运算两点之间的“距离”；WNr的计算和确定等 * DIF-FFT与DIT-FFT的比较 -1 1. 标准形式 DIF：标准形式为输入顺序，输出倒序 DIT：标准形式为输入倒序，输出顺序 2. 蝶形结构 DIT：先作复数乘法，再作加减法 DIF：复数乘法只出现在减法之后 -1 * 3.4 IDFT的FFT实现方法 1．比较IDFT和DFT的关系式 运算区别 可直接利用DFT的FFT结构实现IDFT，只需作两点变动 将FFT流图中的WNr换成WN-r 在流图的最后一级乘以1/N * 3.4 IDFT的FFT实现方法 2. 改进的实现结构 针对上述的两种变动，有一个问题，即在最后一级乘系数1/N，在N较大时，为了防止运算过程发生溢出，可将1