《快速付里叶变换》PPT课件

《《快速付里叶变换》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章快速付里叶变换FFT:FastFourierTransform复习什么是FFT？直接计算DFT的工作量有多大？的性质和特殊点？周期性、对称性、可约性。时域抽取法基2FFT基本原理？时间抽取法基2FFT具体的运算步骤？基2FFT具体的运算步骤X1(k)X2(k)实现上式运算的流图称作蝶形运算X1(k):偶中偶X2(k):偶中奇进行N/4点的DFT,得到X3(k):偶中偶X4(k):偶中奇X5(k):奇中偶X6(k):奇中奇2点DFT2点DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(

2、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)(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

3、)X(2)X(3)X(4)X(5)X(6)X(7)因此,8点DFT的FFT的运算流图时间抽取基2FFT流图绘制N个输入，N个输出；输入为倒序码，输出为顺序码；N＝2M，表示运算共M级数，取值为0～M－1；蝶形运算两节点的距离:2m，其中m表示第m级每一级都有N/2个蝶形单元，可以分成若干组；第m级的组数为：每一组具有相同的结构，相同的因子分布；0000000010011004201001023011110641000011510110156110011371111117自然顺序n二进制nnn倒位序二进制nnn倒位

4、顺序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时，前

5、半序列为：x(0),x(1),x(2),x(3);后半序列为：x(4),x(5),x(6),x(7);2.代入DFT中由于因此X(k)可表为即：3.N点DFT按k的奇偶分组可分为两个N/2的DFT当k为偶数,即k=2r时,(-1)k=1；当k为奇数,即k=2r+1时(-1)k=-1。这时X(k)可分为两部分：k为偶数时：可见,上面两式均为N/2的DFT。k为奇数时：4.结论三、蝶形流图表示蝶形单元：时域中，前后半部表示式用蝶形结表示。x(n)x(n+N/2)与时间抽取法的推演过程一样，由于N=2M,N/2仍为偶数

6、，所以可以将N/2点DFT的输出X(k)再分为偶数组和奇数组，这样就将一个N/2点的DFT分成两个N/4点DFT的输入，也是将N/2点的DFT的输入上、下对半分后通过蝶形运算而形成，直至最后为2点DFT。蝶形流图的另一种形式-1例子：求N=23=8点DIF（1）先按N=8-->N/2=4，做4点的DIF：先将N=8DFT分解成2个4点DFT：可知：时域上：x(0),x(1),x(2),x(3)为前半序列x(4),x(5),x(6),x(7)为后半序列产生新的子序列：x1(n)、x2(n)频域上：X(0),X(2)

7、,X(4),X(6)由x1(n)给出X(1),X(3),X(5),X(7),由x2(n)给出4点DFTx(0)x(1)x(2)x(3)4点DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列x1(n)x2(n)X2(k)将N=8点分解成2个4点的DIF的信号流图N=8点分解成2个4点的另一种形式-1-1-1-1WWWWNNNN0123(2)N/2(4点)-->N/4(2点)FFT(a)先将4点分解成2点的DIF：（b）一个2点的D

8、IF蝶形流图2点DFT2点DFTx1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)(c)另一个2点的DIF蝶形流图2点DFT2点DFTx2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)X(1)X(5)X(3)X(7)(3)将N/4（2点）DFT再分解成2个1点的DFT最后剩下两点D