蝶形运算量比较 点DFT的运算量 复数乘法次数:N 复数加法次数:MN-1) 分解一次后所需的运算量=2个N2的DFT N2蝶形: 复数乘法次数:2*(M2)2+M2=N2/2+M2 复数加法次数:2*(N2(N2-1)+2*N2=N2/2 因此通过一次分解后,运算工作量减少了差 不多一半 16
16 蝶形运算量比较 复数乘法次数： N2 复数加法次数： N(N－1) 复数乘法次数： 2*(N/2) 2+N/2=N2 /2+N/2 复数加法次数： 2*(N/2)(N/2－1)+2*N/2=N2 /2 ◼ N点DFT的运算量 ◼ 分解一次后所需的运算量＝2个N/2的DFT＋ N/2蝶形： ◼ 因此通过一次分解后，运算工作量减少了差 不多一半
进一步按奇偶分解 由于N=2,因而M2仍是偶数,可以进一步把每个M2点 子序列再按其奇偶部分分解为两个M4点的子序列。 以N2点序列x1(r)为例x(2)=x3( l=0. x(21+1)=x4( 则有 X(k)=∑x()W2=∑x1(2)W+∑x(21+1)W 1+1)k 1=0 ∑x(O)WM4+WM2∑x(O)W4 =0 =X(k)+N2X(k)=0.1 N 17
17 进一步按奇偶分解 由于N＝2 L，因而N/2仍是偶数 ，可以进一步把每个N/2点 子序列再按其奇偶部分分解为两个N/4点的子序列。 以N/2点序列x1 (r)为例 1 3 1 4 (2 ) ( ) 0,1, , 1 (2 1) ( ) 4 x l x l N l x l x l = = − + = 则有 rk N N r X k x r W 2 2 1 0 1 1 ( ) ( ) − = = l k N N l l k N N l x l W x l W (2 1) 2 4 1 0 1 2 2 4 1 0 1 (2 ) (2 1) + − = − = = + + lk N N l k N lk N N l x l W W x l W 4 4 1 0 4 2 4 4 1 0 3 ( ) ( ) − = − = = + ( ) ( ) 3 / 2 4 X k W X k k = + N k=0,1,…, 1 4 − N
且 N X+k|=X(k)-W2X(K)k=0,1,,4-1 4 由此可见,一个N2点DFT可分解成两个N4点DFT 同理,也可对x(m)进行同样的分解,求出X(k) 18
18 且 1 3 / 2 4 ( ) ( ) 4 k N N X k X k W X k + = − k=0,1,…, 1 4 − N 由此可见，一个N/2点DFT可分解成两个N/4点DFT。 同理，也可对x2 (n)进行同样的分解，求出X2 (k)