42基2FF算法 其中X1(k)和×2(k)分别为x()和X2()的N2点DFT,目 X(K)=∑x(W2=DFT[x() (4.2.5) X,(k)=> x, (r)Wwn,=DFTIx, (r) (4.2.6) 由于X(k)和X2k)均以N2为周期,且W3=-W,所以 X(k)又可表示为 N X(k)=X1(k)+WNX2(k)k=0,1, (4.2.7) X(k+)=X1(k)-WX2(k)k=O,…4 (4.28
42基2FF算法 这样,N点DFT分解为两个N2点DFT,且所做运算可表示为 如下蝶形运算 A● AfBC B A-BC 图42.1蝶形运算符号
42基2FF算法 x1(0) X(0) N2点X1(1) X(1) X(2) (6) DFT X, (3) X(3) X,(0) X(4) M2点X2(1) XO (5) X(6) DET x2(3) (7)● 图42.2N点DFT的一次时域抽取分解图(N=8)
42基2FF算法 运算量分析: 口完成一次蝶形运算,需一次复数乘法和两次复数加法: 口经过一次分解后,1个N点DFT共需要计算两个N/2点DFT和 N/2个蝶形运算 口计算一个N2点DF需要N*N/4次复数乘法和N/2*N/2-1)次 复数加法。 所以总的运算量为 NNN(N+ N 乘法 十 运算量 2 减少近 半 加法 N 2N N
42基2FF算法 与第一次分解相同,将()按奇偶分解成两个N/4长的子 序列X3()和X4(),即 (D)=x2(2) l=0.1, ()=x(2+1) 4 那么,X1(k)又可表示为 N/4-L X1(k) x(2)W+∑x1(21+1W k(2/+1) (4.2.9) i=0 2w+n2 M4+W4 4(D)W N/4 x3(k)+W2X4(k,k=0.1,…N/2-1