N/2仍为偶数,进一步分解:N/2→)N/4 x(n)=x1(m)+x(n+N/4) x4(m)=[x1(n)-x(n+N/4)x2 0.1. 4 A X3(k)=X,(2k)=DFT[x, (n) k=0.1 X4(k)=X1(2k+1)=DF[x4(m) N4
N /2仍为偶数，进一步分解：N /2 N /4 3 1 1 4 1 1 / 2 ( ) ( ) ( / 4) ( ) [ ( ) ( / 4)] n N x n x n x n N x n x n x n N W 0,1,..., 1 4 N n 3 1 3 4 1 4 ( ) (2 ) [ ( )] ( ) (2 1) [ ( )] X k X k DFT x n X k X k DFT x n 0,1,..., 1 4 N k
x3(0 x3(O)=X1(0)=X(0) N4点 DET 1(1) X3(1)=X1(2)=X(4) 0 1(2) M2x4(0 x4(0=X1(1)=X(2) N4点 DET x1(3) WM2x4(1) X4(1)=X1(3)X(6)
x3(0) x3(1) -1-1 x4(0) x4(1) N/4点DFT N/4点 DFT x1(0) x1(1) x1(2) x1(3) X3(0)=X1(0)=X(0) X4(0)=X1(1)=X(2) X3(1)=X1(2)=X(4) X4(1)=X1(3)=X(6) 0 WN / 2 1 WN / 2