04数字信号处理3.

1、4.5 N 是组合数的 FFT 算法对 N 不是 2 的整数幕的情况，介绍两种处理方法。1、将兀）补零，使 N 成为 2 的整数幕。例 M=30,可以加 2 点，使 N=32=25；=1000,可以加 24 点，使N= 1024=2 W。2、如果要获得准确的 N 点 DFT,可以用任意基的 FFT 算法。其基本思路还是将大点 DFT 尽可能分解为小 点的DFT,充分利用小点 DFT 的周期性。4 5 1、N 是任意组合数的 FFT 算法设 gw%p.- 均为素数令q=P2P3 5N=p、q1、将 N 点 DFT 分解为 Pi个如点的 DFT用时间抽取法，将兀）分为“1 组，每组如个元素。N 点

2、 DFT 分解为內个如点的 DFT兀 E） 兀加+1）X（H）= IIlx（pp+pl）一般式 Xpp + /） x（&）=壬心）吟=22x（Pir）wNrk/i=0r=0（1）+ X（P/+1）W厂以+士 K（门厂+p _1）比丫5 一以r=0r=0（2）（Pi）共有i个工，对每个 M 直有厂 1 次复乘N_1/珂_1G_l咖=心）呼=乂（皿+对n=01=0r=0卩一1s-lPi-1T=E=工CL H/v+/）叱/=0r=0/=0r=（）（）P厂1 4 一 1= EEGS1=0r=05- v-z有” 1 次复乘其中 G他）=H/V + 0叱,是如点的 DFT。r=0厂=0 丄.,如

3、1计算量：个如点的 DFT 复数乘法有厂尸次；每一个 X 伙）值有（门1）次复乘，N 个 X 伙）值有 N（p）次复乘。总的合成 X 伙）的复乘次数mF=N（prl）+ （如）2（4.5-4）=N（P+q）N22、对如再分解令：q2=P3P4Pm，71=2 2每个。点 DFT 又可以分解为血个2 点的DFTO因为合成点的 DFT 及有血个2 点的 DFT,所以（如）2 次的复数乘法应为如（卩 21）+ P1 （2尸次，将此代入（4.5-4） 得到竹=M P1 -1)+ P1 q I ( P2-1)+Pl)2mF= N(prl)+piqi( p2-1 )4- p2)2= N(P|-l)+/?i

4、qp2-pi7i +PP2(qi)2= N(pil)+N(p2-l)+ PP2(2)2=N(PI+P22)+PIP2(02)23、一直分解到最后一个素数 p”最后总的计算量（类推）MF=N（PI+P2+.+P厂加）+P1P2 Pm（q$= N（7?+/?2+.+p 加加）+N=N（Pi+p2+g 加 +1）心 N(P+P产)N=P q/=0r=0计算效率:N，_ PP2P伙N( (p+血 +”厂力)P+P2 +”_加举例 N=18=332(l)x(n)分为三组，每组 6 点x(0), x(3), x(6), x(9), x(l 2), x(l 5) = v x(l x(4), x(7 x(l

5、0), x(l 3), x(l 6)x(2),x(5), x(8), x(l 1), x(l 4), x(l 7)1725mF-px如=36P =36=6o x(3r+l)x(3r + 2)厂=0丄.5一般式 x(3r + /)/ =0,1,2x(k) = 血)W篇=x(3r + /Xz/=0/=0r=0将兀分解为 Pi=3 组、如=6 点的 DFT,再利用 G/（Q 的 周期性将 3 个 6 点的 DFT 合成一个 18 点的 DFT。5其中 = x(3rKr=0=x(0)+x(3X +46X2A+X(9)U +X(1+X(15)町 J5GI()=Ex(3r+1Xdr=0F(1)+昭网 +

6、x(7)C + 兀(10)用+ x(l 3)C + x(l 6)用5G2（Q 二工如 2）叱r=O= H2）+x（5）叱+x（8）% +兀（11）叫严 +丸（14）叫严 +x（17）叫严/=0r=0合成时，G/伙）为 6 点，X 伙）为 18 点，所以仑 6,对 G/伙）有 G/（仗几（模运算）。而Go ()= H (0)+ H (0)4- H2(0)k=0X(0)= G(0) + G(0) + G2(0):k=11X(1) = G(1) + G(1 网+G2(1)吒ak=9111乂皿+5(9)昭+G2(9 卅=G。+G(3)昭+G2(3)WJk=7X (17)= G(5)+G(5) + G?

7、(5 瞬(2)如=32,可以进一步分为两组三点或三组两点 DFT。取三组两点 DFT,即对每个 G/(Q 再分。f x(3p)x(3r+ /)= Xj (r) = x(3p + 1) + 2)Gg = x(3r + /X*将厂=3/74-5 代入r=021=H9p + 3s + /)W 捫$=0p=0IIPi =3 P3 =2(0,1,2) (0,1)5=0,12= Epi =3 p2=3p.r=2 P3 Pl Pi =3(0,1,2)(0,1,2)( (0,1,2) ) ( (0,1) )而Go ()= H (0)+ H (0)4- H2(0)Go（l）=H（l）+耳（1 阀+笑（1 网=

8、H（1）+旦（1 図+笑（1 加G。=仏+耳（2）必皿 2（2）必二弘（0）+厲（0 皿+弘（0）5（3 卜（3）+也（3 网+弘（3 网=仏（1）+厲（1 网+姒 1）必8Hs伙)两点 DFTH (0)r(0)+兀(9)其中 /=() ,5=()/=() ,5=11=0 ,5=2Ho(l)=x(O)-x(9)H。(灯= x(O)+H9)验/i(R)= x(3)+ H12)必/2(Q = x(6)+ x(15)叱G（4）=仏（4）+厲（4 网+ 兄（4）図二仏（0）+耳（0 网 2 +兄（0）呛G。=/。（5）+乩（5 网+ 兄（5）叩= H（1）+H 伽？+禺（1 用这时输出为自然顺序，输入为广义“倒序”。若以 X（）表示广义倒序序列，兀（）表示实际输入序列, 则X()(6 / + 2 s +p)=I I IP =3 Pi =3 P3 =2(0,1,2)(0