(k)=∑x(m)+∑x(m) ∑x(2r)W+∑x(2r+1)x =∑x(r)形2+W∑x1()W 由于 所以 X(k)=X1(k)+X2(k),k=01,2…,N-1 其中x(k)和x(k)分别是x()和x:()的点DF,即 X()=∑x()w=DT[x(r) x2(k)=23()W*=DFT[x2(r)I ·由于x()和x()均以为周期,且=-形,所以X(k)又可表示为 X(k)=X1(k)+WX2(k),k=0, Xk+2=X{(4)-X2(k),k=0.1 这样,就将N点DFT分解为两个点的DFT和(7式以及(8)式的运算 2、蝶形运算 为了形象直观地描述(7)和(8)式的运算,引入以下符号                1 1 2 2 2 2 1 0 0 1 1 2 2 2 2 1 2 0 0 2 2 1 kn kn N N n n N N kr kr N N r r N N kr k kr N N N r r X k x n W x n W x r W x r W x r W W x r W                         偶数 奇数 由于 2 2 2 2 2 2 j kr N j kr kr kr N W e e W N N        所以   1 2    , 0,1,2, , 1 k X k X k W X k k N     N  (4) 其中 X k 1   和 X k 2   分别是 x r 1   和 x r 2   的 2 N 点 DFT，即       1 2 1 1 1 0 2 N kr N r X k x r W DFT x r          (5)       1 2 2 2 2 0 2 N kr N r X k x r W DFT x r          (6)  由于 X k 1   和 X k 2   均以 2 N 为周期，且 2 N k k W W N N    ，所以 X k  又可表示为   1 2    , 0,1, , 1 2 k N N X k X k W X k k      (7) 1 2    , 0,1, , 1 2 2 k N N N X k X k W X k k             (8) 这样，就将 N 点 DFT 分解为两个 2 N 点的 DFT 和(7)式以及(8)式的运算。 2、蝶形运算 为了形象直观地描述(7)和(8)式的运算，引入以下符号 C A B A＋ BC A－BC