(3)对X1(k)和X4k)进行蝶形运算,前半部为 X(0)~X(3),后半部分为Ⅹ(4)X(7) 整个过程如下图所示 X1(0) x1(0=(0) X(0) x1(1)x(2)M2x(1) Ⅹ(1) x1(2)(4)DF7x(2 X(2 x1(3)x(6) X1(3 X(3 X2(0) x2(0)x(1) Ⅹ(4 (1) T(3 W2点 X2(1)W X(⑤5) (2)x(5 DFT X2(2) x2(3x(7 X(6) X2(3) Ⅹ(7)
x1(0)=x(0) x1(1)=x(2) N/2点 x1(2)=x(4) DFT x1(3)=x(6) x2(0)=x(1) x2(1)=x(3) N/2点 x2(2)=x(5) DFT x2(3)=x(7) 1 2 ~ ~ X1(0) X1(1) X1(2) X1(3) X2(0) X2(1) X2(2) X2(3) WN 2 WN 1 WN 0 WN 3 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) (3)对X (k)和X (k)进行蝶形运算,前半部为 X(0) X(3),后半部分为X(4) X(7) 整个过程如下图所示:
二)N/4点DFT 由于N=2L,所以N/2仍为偶数,可以进 步把每个N/2点的序列再按其奇偶部分 分解为两个N/4的子序列。例如,n为偶 数时的N/2点分解为: x1(2)=x(),0,1,…,4-1 x1(2+1)=x4(),0,,…,x-1 进行N/4点的DFT,得到 X3(k)=∑x(O)W4=∑x1(2)R(偶中偶) (k)=∑x(O)W4=x(21+1)x(偶中奇)
由于N=2 L ,所以 N/2仍为偶数,可以进 一步把每个N/2点的序列再按其奇偶部分 分解为两个N/4的子序列。例如，n为偶 数时的 N/2点分解为: (二) N/4点DFT (2 ) ( ), 0,1, , 1 1 3 4 N x l x l (2 1) ( ), 0,1, , 1 1 4 4 N x l x l 进行N/4点的DFT,得到 l k N l lk N l lk N l lk N l X k x l W x l W X k x l W x l W N N N N (2 1) /2 1 0 /4 1 1 0 4 4 2 /2 1 0 /4 1 1 0 3 3 ( ) ( ) (2 1) ( ) ( ) (2 ) 4 4 4 4 (偶中偶) (偶中奇)
从而可得到前N4的X/ x1(k)=X3(k)+WX4(k) k=0. 后N4的X为 x1( (y)xM-()x=(+N 4 k=0,1,4
( ) ( ) ( ) 1 3 4 2 X k X k W X k k N 0,1, , 1 4 N k 从而可得到前N/4的X1(k) ) ( ) ( ) 4 ( 1 3 4 2 k X k W X k N X k N 后N/4的X1(k)为 0,1, , 1 4 N k
同样对n为奇数时,M2点分为两个M4点 的序列进行DFT,则有: X5(k)=∑x2(21)W84=∑x5()W4(奇中偶) 6(k)=∑x2(2l+1)W 从4=∑x6()WM4(奇中奇) 由X5(k)、X6(k)进行碟形运算,得: 2(k)=X5(k)+WN2X6(k):k=0,1,…,-1 4 N 2(+k)=X5(k)-WN2X6(k);k=0,1
(奇中偶) 1 0 / 4 6 / 4 1 0 6 2 1 0 5 / 4 1 0 5 2 / 4 4 4 4 4 ( ) (2 1) ( ) ( ) (2 ) ( ) N N N N l lk N lk N l l lk N l lk N X k x l W x l W X k x l W x l W (奇中奇) 同样对n为奇数时，N/2点分为两个N/4点 的序列进行DFT，则有: 1 4 X (k) X (k) W X (k);k 0,1, , 6 k 2 5 N/2 N 1 4 k) X (k) W X (k);k 0,1, , 4 N X ( 6 k 2 5 N/2 N 由X 5 (k )、X 6 (k )进行碟形运算，得：
严例如,N=8时的DFT可分解为四个N/4的DFT, 具体步骤如下: (1)将原序列x(n)的“偶中偶”部分 x()=x1()=x(m) 3(0)=x1(0)=x(0) x(1)=x1(2)=x(4) 构成N4点DFT,从而得到X3(O,X3(1)
例如,N=8时的DFT可分解为四个N/4的DFT, 具体步骤如下: (1) (2) (4) (0) (0) (0) ( ) ( ) ( ) 3 1 3 1 3 1 x x x x x x x l x r x n (1) 将原序列x(n)的“偶中偶”部分: 构成N/4点DFT，从而得到X3(0), X3(1)