资源描述：
《第4章 快速付立叶变换(FFT)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章FFT快速傅氏变换§4-5线性卷积的FFT算法§4-3DIF的FFT算法§4-4IFFT算法§4-2按时间抽取(DIT)的FFT算法§4-1引言目§4-1引言一.DFT的计算工作量两者的差别仅在指数的符号和因子1/N.DFT与IDFT运算特点复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)同理：IDFT运算量与DFT相同。实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)通常x(n)和都是复数,所以计
2、算一个X(k)的值需要N次复数乘法运算,和次复数加法运算.那么,所有的X(k)就要N2次复数乘法运算,N(N-1)次复数加法运算.当N很大时,运算量将是惊人的,如N=1024,则要完成1048576次(一百多万次)运算.这样,难以做到实时处理.一个X(k)的值的工作量,如X(1)二.改进的途径1.的对称性和周期性得:对称性:周期性:利用上述特性,可以将有些项合并,并将DFT分解为短序列,从而降低运算次数,提高运算速度.1965年,库利(cooley)和图基(Tukey)首先提出FFT算法.对于N点DFT,仅需(N/2)l
3、og2N次复数乘法运算.例如N=1024=210时，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%,速度提高20倍FFT算法分类:时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-Frequency§4-2按时间抽取(DIT)的FFT算法 —库利-图基算法一.算法原理(基2FFT)(一)N/2点DFT1.先将按n的奇偶分为两组作DFT,设N=2L,不足时,可补些零。这样有:n为偶数时:n为奇数时:因此，由于:所以,上式可
4、表示为:(n为偶数)(n为奇数)其中,2.两点结论:(1)X(k),X(k)均为N/2点的DFT。(2)X(k)=X(k)+WX(k)只能确定出X(k)的k=个；即前一半的结果。1212kN同理,这就是说,X1(k),X2(k)的后一半,分别等于其前一半的值。3.X(k)的后一半的确定由于（周期性）,所以:可见,X(k)的后一半，也完全由X1(k),X2(k)的前一半所确定。*N点的DFT可由两个N/2点的DFT来计算。又由于,所以实现上式运算的流图称作蝶形运算前一半4.蝶形运算后一半（N/2个蝶形)(前一半)(后一半)
5、1111-1由X1(k)、X2(k)表示X(k)的运算是一种特殊的运算-碟形运算5.分解后的运算量：复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计运算量减少了近一半例如N=8时的DFT,可以分解为两个N/2=4点的DFT.具体方法如下:(1)n为偶数时,即分别记作:(2)n为奇数时,分别记作:x1(0)=x(0)x1(1)=x(2)N/2点x1(2)=x(4)DFTx1(3)=x(6)x2(0)=x(1)x2(1)=x(3)
6、N/2点x2(2)=x(5)DFTx2(3)=x(7)12~~X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN2WN1WN0WN3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)(3)对X(k)和X(k)进行蝶形运算,前半部为X(0)X(3),后半部分为X(4)X(7)整个过程如下图所示:由于N=2L,所以N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。例如，n为偶数时的N/2点分解为:(二)N/4点DFT进行N/4
7、点的DFT,得到(偶中偶)(偶中奇)从而可得到前N/4的X1(k)后N/4的X1(k)为注意到(奇中偶)(奇中奇)同样对n为奇数时，N/2点分为两个N/4点的序列进行DFT，则有:例如,N=8时的DFT可分解为四个N/4的DFT,具体步骤如下:(1)将原序列x(n)的“偶中偶”部分:构成N/4点DFT，从而得到X3(0),X3(1)。(2)将原序列x(n)的“偶中奇”部分:构成N/4点DFT，从而得到X4(0),X4(1)。(3)将原序列x(n)的“奇中偶”部分:构成N/4点DFT，从而得到X5(0),X5(1)。(4)
8、将原序列x(n)的“奇中奇”部分:构成N/4点DFT，从而得到X6(0),X6(1)。（5）由X3(0),X3(1),X4(0),X4(1)进行碟形运算,得到X1(0),X1(1),X1(2),X1(3)。（6）由X5(0),X5(1),X6(0),X6(1)进行碟形运算,得到X2(0),X2(1),X2(2),X2
