资源描述：
《《快速傅立叶变换》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章(2)快速傅氏变换线性卷积的FFT算法DIF的FFT算法IFFT算法按时间抽取(DIT)的FFT算法引言点击进入目引言一.DFT的计算工作量两者的差别仅在指数的符号和因子1/N.通常x(n)和都是复数,所以计算一个X(k)的值需要N次复数乘法运算,和次复数加法运算.那么,所有的X(k)就要N2次复数乘法运算,N(N-1)次复数加法运算.当N很大时,运算量将是惊人的,如N=1024,则要完成1048576次(一百多万次)运算.这样,难以做到实时处理.一个X(k)的值的工作量,如X(1)二.改进的途径
2、1.的对称性和周期性得:对称性:周期性:利用上述特性,可以将有些项合并,并将DFT分解为短序列,从而降低运算次数,提高运算速度.1965年,库利(cooley)和图基(Tukey)首先提出FFT算法.对于N点DFT,仅需(N/2)log2N次复数乘法运算.例如N=1024=210时，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%,速度提高20倍按时间抽取(DIT)的FFT算法—库利-图基算法一.算法原理(基2FFT)(一)N/2点DFT1.先将按n的奇
3、偶分为两组作DFT,设N=2L,不足时,可补些零。这样有:n为偶数时:n为奇数时:因此，由于:所以,上式可表示为:(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
4、/2点的DFT来计算。又由于,所以实现上式运算的流图称作蝶形运算前一半4.蝶形运算后一半（N/2个蝶形)(前一半)(后一半)1111-1由X1(k)、X2(k)表示X(k)的运算是一种特殊的运算-碟形运算(1)N/2点的DFT运算量:复乘次数:复加次数:(2)两个N/2点的DFT运算量:复乘次数:复加次数:(3)N/2个蝶形运算的运算量:复乘次数:复加次数:5.计算工作量分析复乘:复加:总共运算量:按奇、偶分组后的计算量：*但是,N点DFT的复乘为N2;复加N(N-1);与分解后相比可知,计算工作点差不
5、多减少一半。例如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)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、(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点的DFT,得到(偶中偶)(偶中奇)从而可得到前N/4的X1(k)后N/4的X1(k)为(奇中偶)(奇中奇)同样对n为奇数时，N/2点分为两个N/4点的序列进行DFT，则有:例如,N=8时的DFT可分解为四个N/4
7、的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)将原序列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
8、)。（6）由X5(0),X5(1),X6(0),X6(1)进行碟形运算,得到X2(0),X2(1),X2(2),X2(3)。(0)=(0)=(0)N/4(1)=(2)=(4)DFT(0)=(1)=(2)N/4(1)=(3)=(6)DFT(0)=(0)=(1)N/4(1)=(2)=(5)DFT(0)=(1)=(3)N/4(1)=(3)=(7)DFT313141415252626202NN02NNWWWW0123NNNN-1-1-1-2-1-1
