算2N点序列FFT的方法 掌握利用FFT计算IDFT的过程，以及IFFT实现
的原理
快速傅里叶变换(FFT)
重点：基2时间/频率抽取FFT算法的基本 原理，FFT蝶形运算流图
难点：由短序列的DFT表达相应长序列的 DFT的基本原理及方法
x[0], x[1],x[m],xN 1
N 1
W k
(
m
N 2
)
N
2
k 0
k 0
W W W W k
(
m
N 2
)
km
N 2
km
N
N
N
N
N
(WN2
e e
j
2 N/2
(
N
/
2
)
j 2
1)
旋转因子的周期性
2
2
2
2
2
W m
N 2
N

WNm
N
WN2
WNm
N
(WN2
e
j
2 N
(
N
/
2)
e j
x1[r] WN2rm WNm
x2[r] WN2rm
r 0
r 0
W ee W X [m]
x [k ] W W N
2
12 rm N
1 k 0

j
2 N
2rm
km
m

j
2 N /2
rmN2
rm N
N 2
1N2
N 2
1
旋转因x子2[的k可]约W 性 Nkm
1
X[6] N / 2个蝶形
N 2
X[7]
总计
N2 N
22
N2
当N很大时，运算量减少了近一半
复数加法
N 2
(
N 2
1)
N
(
N 2
1)
2
N
N2 2
N(N 1)
N点有限长序列的DFT
N 1
X [m]
x[k ] WNkm
k 0
m 0,1,, N 1
N/2点有限长序列的DFT
1)
旋转因子的对称性
X
[
N 2

m]

X1[m] WNm

X 2[m]
• 旋转因子
W e mk

j
2 N
km
N
W e e W 可约性
2km

j
2 N
2km

j
2 N/2
km
km
X1[0]
N/2点 X1[1] DFT X1[2]
X1[3]
X2[0]
N/2点 X2[1] DFT X2[2]
X2[3]
+
X[0] X[1] X[2] X[3] _ X[4] X[5] X[6] X[7]
X1[0]
N/2点 X1[1] DFT X1[2]
X1[3]
X2[0]
N/2点 X2[1] DFT X2[2]
X [m] x[0]WN0 x[1]WNm x[2]WN2m x[N 1]WNN1m
X [N 1] x[0]WN0 x[1]WNN1 x[2]WN2N1 x[N 1]WNN1N1
所有的X[m]就要N2次复数乘法运算， N(N-1)次复数加法运算。
X [m] x[k ] WNkm
DFT
k 0
IDFT
N 1
x[k ]
1 N
X [m] WNkm
m0
X[0], X[1],X[m],X N 1
WN
e
j
2 N
x[0], x[1],x[m],xN 1
DFT
X[0], X[1],X[m],X N 1
x1[0]
x1[1]
x1[k ] x[2r ]
x1[m]
x1[N/2-1]
r
1, 2,,
N 2
1
k
1, 2,,
N 2
1
N 2
1
N 2
1
X [m]
x[2r] WN2rm
x[2r 1] WN(2r 1)m
r 0
r 0
N 2
1
N 2
1
X [m]
离散傅里叶变换快速算法(FFT)
快速傅里叶变换(FFT)
问题的提出 基2时间抽取FFT算法 基2频率抽取FFT算法 IFFT算法的实际应用
快速傅里叶变换(FFT)
掌握基2时间抽取FFT算法的基本思想和方法 掌握基2频率抽取FFT算法的基本思想和方法 掌握实序列FFT计算，以及由N点序列FFT计
N 2
1
X [m]
x[k
]
W
k
N
m
2
k 0
m

0,1,,
N 2
1
x2[0]
x2[1]
x2[m]
x2[N/2-1]
x [k ] x[2r 1] 2
r
1, 2,,
N 2
1
k
1, 2,,
N 2
1
x[0] x[1] x[2]
x[3]
x[2r] x[2r+1]
x[N-2] x[N-1]
• 当N很大时，运算量将是惊人的，如N=1024， 则要完成1048576 次(一百多万次)运算。
1965年，库利(cooley)和图基(Tukey)首先在《机器 计算傅里叶级数的一种算法》文章中提出FFT算法。
Cooley, James W., and John W. Tukey, "An algorithm for the machine calculation of complex Fourier series," Math. Comput. 19, 297–301 (1965) /view/d5628524192e45361 066f549.html
加法次数N-1
X [1] x[0]WN0 x[1]WN1 x[2]WN2 x[N 1]WNN 1
乘法次数N
通常x[k]和WNkm都是复数，所以计算一 个 X[m]的值需要N次复数乘法运算和N-1次 复数加法运算。
X [0] x[0]WN0 x[1]WN0 x[2]WN0 x[N 1]WN0 X [1] x[0]WN0 x[1]WN1 x[2]WN2 x[N 1]WNN1
2
k 0
X [m] X 1X[m [m]] W k 0Nxm[k]XW2N2k[mm]
m范围
m

0,1,,
N 2
1
如何求？m
N 2
,
N 2
1,, N
1
X[m
N 2
]

N 2
1
x1[k ]
W k
(
m
N 2
)
N
2

W(
m
N 2
N
)

N 2
1
x2 [k ]
X2[3]
X[0]
+
X[1]
+
X[2]
+
X[3]
+
- X[4]
- X[5] - X[6]
- X[7]
将DFT长序列分解为短 X[0] 序列，降低运算次数。
N/2点 DFT
X[1]
复数乘法
X[2]
1个N2 点DFT
X[3]
(
N 2
)
2
X[4]
2个
N 2
点DFT
N2 2
N/2点 DFT
X[5]
1个蝶形