dsp电子教案(4-1)_快速傅立叶变换(本科2007)(精)

1、数字信号处理Digital Signal Processing第四章 快速傅里叶变换(一)ast ourier ransform引言按时间抽选的基-2FF I算法IT)按频率抽选的基-2FF I算法(D1I )IFFT算法Chirp-Z算法线形卷积和相关的FFT算法直接计算DFT的问题及改进途径N点冇限氏序列双DFT:N_X伙)=DFTx(n)=工心伙)n=0ID FT:x(n) = 1DFTX(k) = YX(QW、严Rg) N =郑州大学物理工程学院赵书俊直接计算DFT的问题及改进途径歼“I R彳ti ut* rwty直接计算DFT的问题及改进途径(a +jb)(c + jd) = (ac

2、 bd) + j (ad + cb)实数乘法实数加法|一次复乘42一次口加2一个 g）4N2N+2(N-1)=23-1)N个?C仗)(N点DF1) 4N22N(2N-1)直接计算DFT的问题及改进途径对称性(w/丁 = % =wN-n)k= WNk)IJW仁W严叭Nw严周期性= w,)k= WN+k)运算量奴数乘法tl数加法fMNN-lw,的特性可约性特殊宜接计算DFT的问题及改进途径T算法的基本思想：miDFT系数的特性，合并运算中的某些项， 把长序列DFT-短序列DFT,从Ifu减少其运算量。肿常法分类:时间抽选法DIT: Decimation1门Time频率抽选法DIF: Decimat

3、ion-In-Frequency按时间抽选的基2Frr算法二、按时间抽选的基-2FFT算法1、算法原理设序列点数N二25 L为整数。 若不满足，则补零N为2的整数泵的FFT算法称基-2FFT算法。将序列班“）按的奇偶分成两组:宜接计算DFT的问题及改进途径x(2r) = x,(r)x(2r+ 1) = x2(r)厂按时间抽选的基2FFT算法x仏戶工心肥伙二心）呼+工心）啜N/2-l=E ”2恥r=0N/2-1,八心-,=兀（广）（昭）+呛召（门（昭）r=0r=0JV/2-1AT/2-1=工MW爲+叱工J叱2r-0r=0按时间抽选的基2FFT算法再利用周期性求母&）的后半部分.X|（）,

4、X2（）是以N/2为周期的X丘+亍卜*2（“）kJV又7=比仁嗚=_wX伙）=X|伙）+VV（X伙）.I1E=0.1,N/2 lX伙+） =X|仗）wjx,、2则的D卜T:N7N-1n=0/!二0n=0n为偶数H为奇数N/E x（2厂+1）吻X】 ”+分x（）；K2丫仏）+讥W）按时间抽选的基2FFT算法丸IJ v- -a 严X|（A）- H=vi( (o) )-x( (o) )图4 J由两t VM点厂7组仃成 个M2点厂卩按时间抽选的基2Frr算法同理：x2(k) = x5(k)/2x()(k)NNAr = 0,1,., -1X2伙 +)=x5a)-v/2x6a)4其中：X”)= 和/)1

5、=DFTX2+1)/=0丄DhTDhTSO)7v(1)rr;_1宁点A*1)FT1)FT1 1IL 1SMI JL $x.i( 1 )=.vi(2)=.v(4Ai(0)X4( (I)= V!( (Iv4( 1 )X=XI(3)A:(6)-Vi(2) (3)生川上冬按时间抽选的基2FFT算法统系数：W/2- Wk建川J按时间抽选的基2FFT算法图4 4按时间抽选，将个、总DFTDFT分解为四个M4点DFT(X=8)按时间抽选的基2FFT算法这样逐级分解，直到2点DFTV5( (O)-X2( (O)-A( (1 ) DFTDFT 1子点DFTDFTxsxs1)f2(2)=A(5)tr 点DFTDF

6、T.IVs(0)/YAz(2)1弋/Y1朋VV(ll)V(1)xj(0)-xi(0)-x(0)X3(1)=VI(2)=V(4X(2)V(3)X(0)A5( (O).V4( (0)=x( I )-V4( (I )=xj(3)=x(6)A( 1)Y(5)-VA(0)=A-2(I)=A(3)V(6)X6( (I)*X2(3-V(7)按时间抽选的基2Frr算法当N=8时，即分解到兀(甸，X),兀做)，兀(怡), 怡二0, 1N/4-11X、(k)=工x3(/)C/4=工“叱為/=0/=0X3(0) = x3(0)W2 +W2x3(l) = x(0) + W；x(4)X3(l) =勺(0)叫 + %比(

7、1) = x(0)-y(4)N/4-1I/伙)=工寫=工W鳥41=0X4(0) =兀()耐 +W仏4(1)=兀(2) +比：k(6)X4() = x4(0)W2 +W；x4(l) = x(2)-W：兀(6)Jt=0,1k=0A1=0按时间抽选的基2Frr算法按时间抽选的基2Frr算法2、运算量当N二2匸吋，共有L级蝶形，每级N/2个蝶形,每个蝶形有1次复数乘法2次复数加法。N/V复数乘法： =- =2厶厶复数加法：aF= NL = Nlog2N比较DFTImr(DFT) _ N2_ 2N I g(FFT厂生吧J耐v( (0) )卞 v( (2)V(3)M4)A(5)V(6)-V(7ffl4-5

8、V-X按时间按时间抽选的基2Frr算法图4-6童接计仃7界法所匍象法次数的比较按时间抽选的基2FFT算法aXeogHUB3、算法特点1）原位计算X”) = XM)+ X./)WJX議力=X心伙) Xz(力昭加表示第加级迭代，k,丿表示数拯所在的行数A(A)=X,d (A)十上”I (/) “ I按时间抽选的基2Frr算法J(/)=,2）倒位序兀（八）no0n2000000000100410010102/20101103011001/41001015 /V1010113/、611011177111图4-7门然序n=（7M4）“ =（Wo）2倒位序按时间抽选的基2FFT算法按时间抽选的基2FFT算

9、法3）蝶形运算对N - 2匚点FFT,输入倒位序，输出自然序, 第加级运算每个蝶形的两节点距离为2i竽 级、云算j X”“）= X心伙）+X心伙+2心）W；刃加/I 貝：1*卫+2心）=X心伙）_ X心伙+2心）昭.(/)三Yi( A) Xm i (/)、r图臭 7 按时间抽选蝶形运算结构川JQuality 打储单元白然撷爪输入变址倒位庁X.SAXG(切+上“ (/) “丫4(1)1(3)1(2)，（1(5)“）v(0图49倒位序的W”4(7).v(7)按时间抽选的基2Frr算法的确定蝶形运算两节点的第一个节点为创直，表 示成L位二进制数，左移L-%位，把右 边空出的位置补零，结杲为厂的二进制

10、数。r = (k)2- 2Lm按时间抽选的基2FFT算法A(0) V(1) V(2)M3)-V(4) V(5)RM-5 W按时间抽选法J FT运算流图A(7)按时间抽选的基2FFT算法4)存储单元输入序列*3) ：N个存储单元系数叱门N/2个存储单元按时间抽选的基2FFT算法4、DIT算法的其他形式流图输入倒位序输出自然序 输入自然序输出倒位序输入输出均H然序相同几何形状输入倒位序输出自然序输入自然序输出倒位序按时间抽选的基2FFT算法输入倒位序输出自然序输入自然序输岀倒位序图4-10A(0)WW)A(5)A(6|x(4)A(7)按时间抽选，输入自然厲序，输出倒位序的F77图M2)按时间抽选的

11、基2FFT算法按时间抽选的基2FFT算法相同几何形状 M7）-1 ! 1图J 12按时间抽选，各级具有相同几何形 状，输入倒输入输出均自然序M0)x（0）-v(l)V(l)Ml)。V(2v(2V(3工 V-v(5)*(6)v(6)A(7)A(7)A(4)M4)出.1-I-IW4-I1按时M0)x(4)-V(l)M2)A(3)A(6)M4)v(lV(5)x(5)XA(3)v(7按时间抽选的基2FFT算法位序、输出自然顺序的FFT 谎图按时间抽选的基2FFT算法图4 1 J按时间抽选，各级具有相同几何形 状，输入自然顺序.输出倒位序的流图按频率抽选的基2FFT算法三.按频率抽选的基-2FFT算法1

12、、算法原理设序列点数N二25 L为整数。将X（Q按沧的奇偶分组询，先将输入x（）按的 顺序分成前后两半：x(1).v(4H*A5 v(6相同几何形状于V(0)A(4)A(2)X(1)-Y(5)M3)亠W) -111v(7按频率抽选的基2FFT算法A72-IX(幻=护=XXWN+ 工xS)W护二0W/2=-lAT/2-i=工X()+(-l)AZ 4-k=0丄，TV 1按频率抽选的基2FFT算法按沧的奇偶将X(旬分成两部分:N/21X(2r) = s x(/?) + xl /? + n=0N/2-I=工I X(n) + X/|=0N_N-1/r=0n=0N!2_N/2-=Z兀N/2IN=工x(川k

13、 =2r厂=0丄,N/2In=N/2N、.n+ k2)Nx n-Wnk按频率抽选的基2FFT算法X(2r + 1)=2j(N、x(n) - x=0按频率抽选的基2FFT算法X(n) =x(n)+xx2(/l) =x(n)-xNnH-2 J则X（2/）和AX2H-1）分别是乂（）和乂2（）的N/ 2点DFT,记为 甸和花（忌）x(佗)A*(w+y) ” V17 n乙图414按频率抽选蝶形运算流图符号按频率抽选的基2FFT算法按频率抽选的基2Frr算法N/2仍为偶数,进一步分解：N/2 N/4x“)= X|(n) +X(n 4- /V/4)n 0,1,., 1|x4(n) =乂|(兒)一斗(刃 +

14、7V/4)WJ/24w1fX.(k) = XS2k) = DFTx.(n)N =0丄,1X4(k) = X、(2k+ 1) =DFTx4(n)4KnEIKH按频率抽选的基2FFT算法址也JL萝按频率抽选的基2Frr算法同理：fx5(k) = X2(2k)= DFrx5(/2)k= 0,1,X6伙)=X2(2k+1) =DFTx6(n)9 9其中:x5(n) = x2(n) + x2(n + 2V/4)兄=o ix6(/?) =X2(H)-兀2(允 +N/4)叭/2按频率抽选的基2Frr算法M0)o/、/y八;餐v（o）V4)M2)X(6)W)V(5)Ml)2)Ml)M6)M7)j点DPT)点m

15、r扌点DFT9 -V(7)址也JL萝按频率抽选的基2Frr算法图4 I6按頻牢抽选,将一个，、点7分解为4个,口点0 7（、=8）按频率抽选的基2FFT算法逐级分解，直到2点DFT当N= 8时，即分解到兀3()，x4(/z), x5(/),心力)，/=0,1A/4-l1兀伙)=X T(/)W寫=I3(/)W代Ar =0,11=01=0j X(0) =X3(0) = 6(0)吆 +昭心(1) = x3(0) + x3(l)|X(4)=X3(1) =X3()W20+ W,3(l) = x3()-x3(l)JW；N/4-11X4(Q= X七(/)W寫=工七(/)哗4 k=J7-0/=0乂=X4(0)

16、 = (0)W；+翻=亠(0) +兀(1)X(6)=X4(1) =X4(0)W+WX4(1) = X4(0)-X4(1)W按频率抽选的基2FFT算法-v(0)v(l) X(0)o A(4)hd4-17按频率抽选7虚W(A=K)按频率抽选的基2FFT算法2、算法特点1）原位计算L级蝶形运算，每级N/2个蝶形，每个蝶形结构:X”“)= X”L“)+ X,Q)Xm(j)=Xm_Sk)-X(J)K加表示第加级迭代，尿丿表示数据所在的行数if川JL彳CMMOWOIBwmwrwvy2）蝶形运算对N=2L点EFT,输入自然序，输出倒位序, 两节点距离：2匸二N/2，第加级运算：（N、X”）= X心伙）+X心k+ 上丿按频率抽选的基X按频率抽选的基2FFT算法X不卜X心伙）-X心卜+莎丿昭u-的确立蝶形运算两节点的第一个节点为怡值，表示成L位二进制数，左移1位，把右边空出的位置 补零，结果为卅J二进制数。r = (k按频率抽选的基2FFT算法3、DITjDIF的异同基本蝶形不同 DIT:先复乘后加减 DIF:先减后复乘运算量相同N、tnF=log2N aF= Nlog N按频率抽选的基2FFT算法都可原位运算 D/7羽IDE的基本蝶形互为转置IFFF算法比较:IDFT: