3. 变量置换--2N/2?1NNnk'?X(2k')??[x(n)?x(n?)]WN/2k'?0,1,??122n?0x(n)前一半序列x(n)后一半序列NN设一个新序列：x1(n)?x(n)?x(n?),n?0,1,2??22N/2?1Nnk'则X(2k')??x1(n)]WN/2?X（k'?0,1,??11k')2n?0可见：x(n)的频域X(k)的偶数部分可以通过x1(n)序列的DFTX（1k)求得。N由于x1(n)序列只有点，所以其运算量降低一半。23. 变量置换--3同理：当k?奇数时，频率的奇数部分NkN?WN2??1,令k?2k'?1，k'?0,1,??12N/2?1NnkX(k)??[x(n)?x(n?)]WNk?1,3,5,7?N?12n?0令k?2k'?1代入N/2?1NNn（2k'?1）X(2k'?1)??[x(n)?x(n?)]WNk'?0,1,??122n?0又?W2nk'N?Wnk'N/2(?e2??j?2nk'N?e2??jnk'N/2?Wnk'N/2）3. 变量置换--4N/2?1N?nN?nk'?X(2k'?1)???x(n)?x(n?)?WN?WN/2k'?0,1,??12?2n?0?x(n)前一半序列x(n)后一半序列NNn设一个新序列：x2(n)?[x(n)?x(n?)]WN,n?0,1,2??122N/2?1Nnk'则X(2k'?1)??x2(n)WN/2?X（k'?0,1,??12k')2n?0可见：x(n)的频域X(k)的奇数部分可以通过x1(n)序列的DFTX（2k)求得。N由于x2(n)序列只有点，所以其运算量降低一半。24.结论1
?一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：
X(k)?X(2k')?X(2k'?1)???N点DFTN/2点N/2点即先求出X1(k')，X2(k')k'?0,1?N/2?1再用k?2k',k?2k'?1分别代入X(k)?X1(2k')?X2(2k'?1),k?0,1,?N?1又合成N点DFT可见：如此分解，直至分到2点的DFT为止。
4.结论2N/2?1X1(k')?N/2?1?x(n)]W1n?0nk'N/2??n?0Nnk'[x(n)?x(n?)]WN/22N/2?1n?0Nk'?0,1,??12Nk'?0,1,??12X2(k')?N/2?1?x2(n)]Wnk'N/2??n?0Nnnk'[x(n)?x(n?)]WNWN/22