∑x(n)W+∑x(n)W n=0 n=0 n为偶数 n为奇数 N N ∑x(2r)+∑x(2r+1)W+ ∑x(+W∑x()W=X1(k)+WkX2(k) 式中,X1(k)和X2(k)分别是x(m)和x2(m)的N2的DFT。 另外,式中k的取值范围是:0,1,…,N2-1
11 − = + − = = + + 1 2 0 (2 1) 1 2 0 2 (2 ) (2 1) N r r k N N r r k x r WN x r W − = − = = + 1 2 0 2 2 1 2 0 2 1 ( ) ( ) N r r k N k N N r r k x r WN W x r W ( ) ( ) 1 2 X k W X k k = + N − = − = = + 1 0 1 0 ( ) ( ) N n n n k N N n n n k x n WN x n W 为偶数 为奇数 式中，X1 (k)和X2 (k)分别是x1 (n)和x2 (n)的N/2的DFT。 另外，式中k的取值范围是：0，1，…，N/2－1
因此,X(k)=X(k)+WX2(k)只能计算出X(k)的前一半值。 后一半X(k)值,N/2,N/2+1,…,N? 利用 W r(N/2+k)= w rk N/2 N/2 可得到 X(+k)=∑x)形2=∑x(W=X1(k) 同理可得 X2(+k)=X2(k) 12
12 因此， X k X k W X k ( ) ( ) ( ) = + 1 2 N k 只能计算出X(k)的前一半值。 后一半X(k) 值， N/2 ， N/2 ＋1， …，N ？ rk WN 2 ( 2 ) 2 r N k WN + = 利用 可得到 1 ( ) 2 N X k + = 2 1 ( 2 ) 1 2 0 ( ) N r N k N r x r W − + = = 2 1 1 2 0 ( ) N rk N r x r W − = = ( ) 1 X k 同理可得 2 2 ( ) ( ) 2 N X k X k + =
考虑到 (N/2+k) 2 N WN2·W=-W 及前半部分X(k) X(k)=X,(k)+WNX,(k) k=0,1 N2-1 因此可得后半部分X(k) X(k+o)=X,(+)+wkN2Y,h+N 2 =X1(k)-W2(k) k=0,1,∴,N2-1 13
13 考虑到 k N k N N N N k WN =W W = −W ( 2+ ) 2 因此可得后半部分X(k) ) 2 ) ( 2 ) ( 2 ( 2 2 1 N W X k N X k N X k k N + = + + N + + 1 2 ( ) ( ) ( ) k X k X k W X k = + N 及前半部分X(k) ( ) ( ) 1 2 X k W X k k = − N k=0，1， …，N/2－1 k=0，1， …，N/2－1
蝶形运算 X(k)=X(k)+WNx,(k) 蝶形运算式 X(K)=X(K)-WNX,(K) x(k) XI(H+WNX(h) 蝶形运算信 x2(k)w 号流图符号 A Xi(-Wkx,(k) 因此,只要求出2个N2点的DFT,即X(k)和X2(k),再 经过蝶形运算就可求出全部X(k)的值,运算量大大减少
14 蝶形运算 1 2 ( ) ( ) ( ) k X k X k W X k = + N 1 2 ( ) ( ) ( ) k X k X k W X k = − N 蝶形运算式 蝶形运算信 号流图符号 因此，只要求出2个N/2点的DFT，即X1 (k)和X2 (k)，再 经过蝶形运算就可求出全部X(k)的值，运算量大大减少
以8点为例第一次按奇偶分解 x1(0) x1(0)=x(0) X(0) 点x(1) 以N=8为例, x1(1)=x(2) X(1) 分解为2个4点 x1(2)=x(4) DFT Xi(2) X(2) 的DFT,然后 x1(3) x1(3)=x(6) Y(3) 做8/2=4次蝶形 x2(0) 运算即可求出 x2(0)=x(1)● X(4) N 所有8点X(k)的 点x x2(1)=x(3) 2 X(5) 值 x2(2)=x(5) DFT X2 (2) Y(6) (3) x2(3)=x(7) X(7) W 15
15 以8点为例第一次按奇偶分解 0 WN 1 WN 2 WN 3 WN 以N=8为例， 分解为2个4点 的DFT，然后 做8/2=4次蝶形 运算即可求出 所有8点X(k)的 值