序列，将计算量大大降低。
按时间下标的奇偶将N点x(n)分别抽取组成两个N/2点序列，分别记为x1(n)和x2(n)，将x(n)的DFT转化为x1(n)和x2(n)的DFT的计算。
x(2r) x1(r)
, x(2r 1) x(r) 2
nk
Xk xnW N
n 0N 1
r 0,1, ,
N
12
N 2
n 0,2,4...N 12
x n W
nkN
n 1,3,5...N 12
N 1
nk
x n WN
r 0,1N 12
2rk
x 2r WN
r 0,1N
12
x 2r 1 WN
2r 1 k
r 0,1
x r W
1
2rkN
r 0,1
x r W
2
2r 1 kN
nk
利用系数 WN的可约性，即
2rkW N e
2
2rk
N
j
e
N12r 0
2 rk2
rk
WN
rkk
X k x1 r WN WN x2 r WNrk
r 0
k X（ WNX（k）,0 k N 11k）2
N
12
用蝶形运算可表式为：
以此类推，还可以把x1(n)和x2(n)按n值得奇偶分为两个序列，这样就达到了降N得目的，从而减少了运算量。
FFT对DFT的数学运算量改进：
直接采用DFT进行计算，运算量为N^2次复数乘法和N*(N-1)次复数乘法。
第 9 页 共 23页