快速付里叶变换.pptVIP

进行原位运算；运算量相同,均为（N/2)Log2N次复乘,NLog2N次复加。DIT输入为倒位序,输出为自然顺序；DIF正好与此相反。DIF与DIT根本区别：在于蝶形结不同。DIT的复数相乘出现在减法之前。DIF的复数相乘出现在减法之后。相同点不同点(5)DIF与DIT比较4.2.6IDFT的高效算法以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义出发，可以导出下列二种利用FFT来计算FFT的方法。一、利用FFT计算IFFT的思路1将下列两式进行比较第四章快速付里叶变换FFT:FastFourierTransform复习什么是FFT？直接计算DFT的工作量有多大？的性质和特殊点？周期性、对称性、可约性。时域抽取法基2FFT基本原理？时间抽取法基2FFT具体的运算步骤？基2FFT具体的运算步骤X1(k)X2(k)实现上式运算的流图称作蝶形运算X1(k):偶中偶X2(k):偶中奇X3(k):偶中偶X5(k):奇中偶X4(k):偶中奇X6(k):奇中奇进行N/4点的DFT,得到2点DFT2点DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)2点DFT2点DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)因此,8点DFT的FFT的运算流图(0)(4)(2)(6)(1)(5)(3)(7)WN0WN0WN0W0N-1-1-1-1X(0)X(1)X(0)X(1)X(0)X(1)X(0)X(1)33445566WN0WN2WN0WN2-1-1-1-1X(0)X(1)X(2)X(3)X(0)X(1)X(2)X(3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)N个输入，N个输出；输入为倒序码，输出为顺序码；N＝2M，表示运算共M级数，取值为0～M－1；蝶形运算两节点的距离:2m，其中m表示第m级每一级都有N/2个蝶形单元，可以分成若干组；第m级的组数为：每一组具有相同的结构，相同的因子分布；时间抽取基2FFT流图绘制0000000010011004201001023011110641000011510110156110011371111117自然顺序n二进制nnn倒位序二进制nnn倒位顺序n^2100124.2.5频域抽取法FFT(DIF-FFT)一、算法原理设输入序列长度为N=2M(M为正整数，将该序列的频域的输出序列X(k)（也是M点序列）按其频域顺序的奇偶分解为越来越短的子序列，称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。二、算法步骤1.分组已经证明频域上X(k)按k的奇偶分为两组，在时域上x(n)按n的顺序分前后两部分。现将输入x(n)按n的顺序分前后两部分:前半子序列x(n),0≤n≤N/2-1;后半子序列x(n+N/2),0≤n≤N/2-1;例：N=8时，前半序列为：x(0),x(1),x(2),x(3);后半序列为：x(4),x(5),x(6),x(7);2.代入DFT中因此X(k)可表为即