《第四章快速傅里叶变换课件.ppt》由会员分享，可在线阅读，更多相关《第四章快速傅里叶变换课件.ppt（37页珍藏版）》请在三一办公上搜索。
1、第四章快速傅里叶变换,1965年,库利-图基,计算数学(Mathematic of Computation),“机器计算傅里叶级数的一种算法”,揭开了FFT发展史上的第一页,1967年至1968年间,FFT的数字硬件制成,电子数字计算机,FFT算法迅速发展,DFT走向实用,一、直接计算DFT算法,存在的问题及改进途径,问题提出：,设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT运算，共需多大的运算工作量?,(一)存在的问题,1.比较DFT与IDFT之间的运算量,其中x(n)为复数，也为复数所以DFT与IDFT二者计算量相同。,2.DFT的复数运算量,计算一个X(k)(一个频率
2、成份)值，运算量为,例 k=1 则要进行,完成整个DFT运算，其计算量为：,N次复数乘法+(N-1)次复数加法,N*N次复数相乘+N*(N-1)次复数加法,3.一次复数运算量换算成实数运算量,4次复数乘法,2次实数加法,复数运算要比实数运算复杂，需要的运算时间长。,一个复数乘法包括4次实数乘法和2次实数加法。,(a+jb)(c+jd)=(ac-bd)+j(bc+ad),一个复数加法包括2次实数加法。,(a+jb)+(c+jd)=(a+c)+j(b+d),2次实数加法,4.计算DFT需要的实数运算量,由此看出：直接计算DFT时，乘法次数与加法次数都是和N2成比例的。当N很大时，所需工作量非常可观
3、。,4N2次实数相乘和2N(2N-1)次实数相加.,整个DFT实数运算量为：,N*N次复数乘+N*(N-1)次复数加,整个DFT的复数运算量转换为实数运算量：,2*N*N次实数加,4*N*N次实数乘,2*N*(N-1)次实数加,2N(2N-1)次实数加,例子,例1:当N=1024点时，直接计算DFT需要：,这对实时性很强的信号处理(如雷达信号处理它对计算速度有十分苛刻的要求)来讲，迫切需要改进DFT的计算方法，以减少总的运算次数。,4*N2=4194304 次实数乘,2N(2N-1)=4192256 次实数加,(二)改善DFT运算效率的基本途径,基本思路：,利用DFT运算的系数 的固有对称性和
4、周期性，,改善DFT的运算效率。,1.合并法：合并DFT运算中的某些项。2.分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。,1.利用DFT运算的系数 的固有对称性和周期性，改善DFT的运算效率,的共轭对称性：,的周期性：,2、将长序列DFT利用对称性和周期性分解,为短序列DFT,DFT的运算量与N2成正比,思路：,把N点数据分成二半：,其运算量为：,再分二半：,这样一直分下去，剩下两点的变换。,方法,结论,快速付里叶变换(FFT)就是在此特性基础上发展起来，并产生了多种FFT算法，其基本上可分成两大类：,按抽取方法分：时间抽取法(DIT);频率抽取法(DIF)按“基数”分：基-
5、2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：线性调频Z变换(CZT法),二、基-2按时间抽取的FFT算法(Coolkey-Tukey),（一）算法原理,设输入序列长度为N=2M(M为正整数），将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。,特别注意：,若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M,序列长度N必须满足 N=2M，M为整数.,(二)算法步骤,DFT变换：,1.分组，变量置换,先将x(n)按n的奇偶分为两 组，作变量置换:,当n=偶数时，令n=2r;当n=
6、奇数时，令n=2r+1;,得到：x(2r)=x1(r);x(2r+1)=x2(r);r=0N/2-1;,利用,得,2.分组序列的DFT中,生成两个子序列,X1(k):原序列偶数项的DFT,X2(k):原序列奇数项的DFT,3.结论1,再应用W系数的周期性，求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。,一个N点的DFT被分解为两个N/2点DFT。,X1(k),X2(k)这两个N/2点的DFT按照：,4.求出后半部的表示式,看出：后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。,5.结论2,频域中的N个点频率成分为：,只要
7、求出（0N/2-1）区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。,结论：,6.结论3,由于N=2M，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算。,（三）蝶形结,即蝶式计算结构,或蝶式信号流图。,X1(k),X2(k),作图要素：(1)左入右出(2)上加下减(3)系数标箭头,上面频域中前/后半部分表示式可以用蝶形信号流图表示如下。,例子,先将N=8DFT分解成2
8、个4点DFT：可知：时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上：X(0)X(3)，由X(k)给出 X(4)X(7),由X(k+N/2)给出,求 N=23=8点FFT变换,解：（1）先按N=8-N/2=4，做4点的DFT：,将N=8点分解成2个4点的DFT的信号流图,4点DFT,x(0)x(2)x(4)x(6),4点DFT,x(1)x(3)x(5)x(7),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),X2(3),偶数序
9、列,奇数序列,X(4)X(7)同学们自已写,x1(r),x2(r),(2)N/2(4点)-N/4(2点)FFT,因为4点DFT还是比较麻烦，所以再继续分解。若将N/2(4点)子序列按奇/偶分解成两个N/4点（2点）子序列。即将x1(r)和x2(r)分解成奇、偶两个N/4点（2点）点的子序列。,一个2点的DFT蝶形流图,2点DFT,2点DFT,x(0)x(4),x(2)x(6),X3(0),X3(1),X4(0),X4(1),X1(0)X1(1),X1(2)X1(3),另一个2点的DFT蝶形流图,2点DFT,2点DFT,x(1)x(5),x(3)x(7),X5(0),X5(1),X6(0),X6
10、(1),X2(0)X2(1),X2(2)X2(3),(3)将N/4（2点）DFT再分解成2个1点的DFT,最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。,2个1点的DFT蝶形流图,1点DFT,x(0),1点DFT,x(4),X3(0)X3(1),进一步简化为蝶形流图：,X3(0)X3(1),x(0),x(4),(4)一个完整N=8的按时间抽取FFT的运算流图,x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7),X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7),m=0,m=1
11、,m=2,三、基-2按频率抽取的FFT算法(DIF)(Sander-Tukey),(一)算法原理,设输入序列长度为N=2M(M为正整数，将该序列的频域的输出序列X(k)(也是M点序列)，按其频域顺序的奇偶分解为越来越短的子序列，称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。,基-2按时间抽取的FFT,时域：按奇偶划分 频域：按前后划分,基-2按频率抽取的FFT,时域：按前后划分 频域：按奇偶划分,例子,频域上：X(0),X(2),X(4),X(6)由x1(n)给出 X(1),X(3),X(5),X(7),由x2(n)给出,求 N=23=8点DIF,（1）先按N=8-N/2
12、=4，做4点的DIF：,将N=8点分解成2个4点的DIF的信号流图,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),(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,DIF与DIT比较,相同之处：（1）DIF与DIT两种算法均为原位运算。（2）DIF与DIT运算量相同。它们都需要,不同之处：（1）DIF与DIT两种算法结构倒过来。DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读”程序。DIT为输入乱序，输出顺序。先运行“二进制倒读”程序，再进行求DFT。（2）DIF与DIT根本区别：在于蝶形结不同。DIT的复数相乘出现在减法之前。DIF的复数相乘出现在减法之后。,
