第四章快速傅里叶变换课件

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