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

第四章 快速付里叶变换,FFT: Fast Fourier Transform,复习,什么是FFT？ 直接计算DFT的工作量有多大？ 的性质和特殊点？ 周期性、对称性、可约性。 时域抽取法基2FFT基本原理？ 时间抽取法基2FFT具体的运算步骤？,基2FFT具体的运算步骤,实现上式运算的流图称作蝶形运算,X1(k):偶中偶,X2(k):偶中奇,进行N/4点的DFT,得到,X3(k):偶中偶,X4(k):偶中奇,X5(k):奇中偶,X6(k):奇中奇,因此,8点DFT的FFT的运算流图,时间抽取基2FFT流图绘制,N个输入，N个输出； 输入为倒序码，输出为顺序码； N2M，表示运算共M级数，取值为0M1； 蝶形运算两节点的距离: 2m，其中m表示第m级 每一级都有N/2个蝶形单元，可以分成若干组； 第m级的组数为： 每一组具有相同的结构，相同的 因子分布；,0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7,自然顺序n 二进制n n n 倒位序二进制n n n 倒位顺序n,2 1 0 0 1 2,4.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),0nN/2-1; 后半子序列x(n+N/2),0nN/2-1;,例：N=8时，前半序列为：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 仍为偶数，所以可以将N/2 点DFT 的输出X(k) 再分为偶数组和奇数组，这样就将一个N/2 点的DFT 分成两个N/4 点DFT 的输入，也是将N/2 点的DFT 的输入上、下对半分后通过蝶形运算而形成，直至最后为2 点DFT 。,蝶形流图的另一种形式,-1,例子：求 N=23=8点DIF （1）先按N=8N/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),X(4),X(6)由x1(n)给出 X(1),X(3),X(5),X(7),由x2(n)给出,4点 DFT,x(0) x(1) x(2) x(3),4点 DFT,x(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,-1,(2)N/2(4点)N/4(2点)FFT (a)先将4点分解成2点的DIF：,（b）一个2点的DIF蝶形流图,(c)另一个2点的DIF蝶形流图,2点DFT,2点DFT,x2(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,最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x3(0)、x3(1)为例。,(b)2个1点的DFT蝶形流图,1点DFT,x3(0),1点DFT,x3(1),进一步简化为蝶形流图：,X(0) X(4),x3(0),x3(1),(4)一个完整N=8的按频率抽取FFT的运算流图,x(0) x(1) x(2) x(3) x(4) x(5) x(6) x(7),X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7),m=0,m=1,m=2,N=8时DIFFFT流图的另一种形式：,(5)DIF与DIT比较,1.相同点 (1)进行原位运算； (2)运算量相同,均为（N/2) Log2N次复乘,N Log2N次复加。 2.不同点 (1)DIT输入为倒位序,输出为自然顺序； DIF正好与此相反。 (2)DIF与DIT根本区别：在于蝶形结不同。 DIT的复数相乘出现在减法之前。 DIF的复数相乘出现在减法之后。,4.2.6 IDFT的高效算法,以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义出发，可以导出下列二种利用FFT来计算FFT的方法。,一、利用FFT计算IFFT的思路1,将下列两式进行比较,二、利用FFT计算IFFT的思路2,利用FFT计算IFFT时在命名上应注意： (1)把FFT的时间抽取法，用于IDFT运算时，由于输入变量由时间序列x(n)改成频率序列X(k),原来按x(n)的奇、偶次序分组的时间抽取法FFT，现在就变成了按X(k)的奇偶次序抽取了。 (2)同样，频率抽取的FFT运算用于IDFT运算时，也应改变为时间抽取的IFFT。,三、改变FFT流图系数的方法 1.思路,在IFFT的运算中，常常把1/N分解为(1/2)m，并且在M级运算中每一级运算都分别乘以1/2因子，就可得到IFFT的两种基本蝶形运算结构。,2.IFFT的基本蝶形运算,四.不改(FFT)的程序直接实现IFFT,这就是说,先将X(k)取共轭,即将X(k)的 虚部乘-1，直接利用FFT程序计算DFT；然后 再取一次共轭；最后再乘1/N,即得 (n)。所 以FFT,IFFT可用一个子程序。,五、FFT的应用,凡是利用付里叶变换来进行分析、综合、变换的地方，都可以利用FFT算法来减少其计算量。 FFT主要应用在 （1）快速卷积 （2）快速相关 （3）频谱分析,1、线性卷积的FFT算法,一.线性卷积的长度 设一离散线性移不变系统的冲激响 应为 ,其输入信号为 .其输出 为 .并且 的长度为L点, 的 长度为M点,则：,二、利用圆周卷积代替线卷积,用圆周卷积（FFT）代替线卷积的必要条件：x(n)、h(n)补零加长至L=N+M