元 2兀 由于 2n n 2n W N/2 N/2 N/2-1 所以X(4)=∑x(r)形+W∑x(r)形2 r=0 0 N/2-1 N/2-1 ∑x1()M2+W∑x2()W2 r=0 X,(+WNX2(k k=0,1,…,-1k=0,1,,≌-1
所以 − = − = = + / 2 1 0 2 2 / 2 1 0 2 1 ( ) ( ) ( ) N r r k N k N N r r k X k x r WN W x r W 由于 n N n N n j N j n WN e e W / 2 / 2 2 2 2 2 = = = － － − = − = = + / 2 1 0 2 / 2 / 2 1 0 1 / 2 ( ) ( ) N r r k N k N N r r k x r WN W x r W ( ) ( ) X1 k W X2 k k = + N = 0,1, , 2 −1 N k = 0,1, , N −1 k ? = 0,1, , 2 −1 N k
X1(k)、X2k)只有N2个点,以N2为周期;而X(k) 却有N个点,以N为周期。要用X(k)、×2(k)表达全部的 X(k)值,还必须利用W系数的周期特性。 r(N/2+k) rk N/2 N/2 N/2-1 X(N/2+4)=∑x1(n)2211=∑x()WN2 0 0 X1(N/2+k)=X1(k) X2(N/2+k)=X2(k)
X1 (k)、X2 (k)只有N/2个点，以N/2为周期；而X(k) 却有N个点，以N为周期。要用X1 (k)、X2 (k)表达全部的 X (k) 值，还必须利用WN系数的周期特性。 r k N r N k WN W / 2 ( / 2 ) / 2 = + − = − = + + = = / 2 1 0 1 / 2 / 2 1 0 ( / 2 ) 1 1 / 2 ( / 2 ) ( ) ( ) N r r k N N r r N k X N k x r WN x r W + = + = ( / 2 ) ( ) ( / 2 ) ( ) 2 2 1 1 X N k X k X N k X k
又考虑到W的对称性: (N/2+k) N/2 N N kN 有: X(k)=X1(k)+WNX2(k)k=0,1,,M 前半部分 X(N/2+k)=X1(N/2+k)+W2+)X2(N/2+k) 后半部分 X1(k)-WX2(k)k=0,1,…,%-1
后半部分 前半部分 又考虑到 WN k 的对称性： k N k N N N N k WN ( / 2+ ) = W / 2 W = −W ( / 2 ) ( / 2 ) ( / 2 ) 2 ( / 2 ) X N k X1 N k W X N k N k + = + + N + + 有： ( ) = 1 ( ) + 2 ( ) = 0,1, , 2 −1 k N X k X k WN X k k = 1 ( ) − 2 ( ) = 0,1, , 2 −1 k N X k WN X k k
X(=X,()+WNX2(k) 前半部分 k=0,1,…,%-1 X(N/2+k)=X,()-WNX2(k) 后半部分 蝶形运算流图符号 说明 X1(k) (1)左边两路为输入 X,(k+WNX2(k) (2)右边两路为输出 W (3)中间以一个小圆表示加 X2(k) X(-WNX,(k) 减运算(右上路为相加 输出、右下路为相减输 出) 1个蝶形运算需要次复乘,2次复加
后半部分 前半部分 ( / 2 ) ( ) ( ) X N k X1 k W X2 k k + = − N ( ) ( ) ( ) X k X1 k W X2 k k = + N = 0,1, , 2 −1 N k ( ) 1 X k ( ) 2 X k k WN ( ) ( ) 1 2 X k W X k k + N ( ) ( ) 1 2 X k W X k k − N 蝶形运算流图符号 说明： (1) 左边两路为输入 (2) 右边两路为输出 (3) 中间以一个小圆表示加、 减运算（右上路为相加 输出、右下路为相减输 出) 1个蝶形运算需要1次复乘，2次复加
分解后的运算量: 复数乘法 复数加法 个N点DFT 2 N(N-1) 个N/2点DFT (N/2)2 N/2(N/2-1) 两个N/2点DFT N2/2 N(N/2-1 个蝶形 2 N/2个蝶形 N/2 N 总计 N2/2+N2 N(N21)+N ≈N2/2 ≈N2/2 运算量减少了近一半
复数乘法 复数加法 一个N 点DFT N 2 N (N–1) 一个N / 2点DFT (N / 2)2 N / 2 (N / 2 –1) 两个N / 2点DFT N 2 / 2 N (N / 2 –1) 一个蝶形 1 2 N / 2个蝶形 N / 2 N 总计 N2 /2 + N/2 ≈ N2 /2 N(N/2-1) + N ≈ N2 /2 运算量减少了近一半 ➢ 分解后的运算量：