第三章 离散付里叶变换（ DFT)
§ 3-1 离散付里叶变换
设离散时间信号 {x(k)} (k=0,1,2,3,……,N -1)
其 DFT,
IDFT,
1,,2,1,0)()(
1
0
??? ?
?
?
NpWkxpX
N
k
kp
N ?
12,1,0)(1)(
1
0
??? ?
?
?
? NkWpX
N
kx
N
p
kp
N ?
Matlab实现,
DFT矩阵,
将 X(p)及 x(k)写成列向量，则有,（ dft.m及 idft.m)
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
???
k
p
WW
WW
WW
N
N
N
N
N
NN
kp
NpkNN
2
)1(1
11
1,0
1
1
111
][
?
???
?
?
XW
N
x
xWX
N
N
*1
?
?
例 3.1,x(k)是一 4点序列
a.计算其付里叶变换 X(f);
b.计算 x(k)的 4点 DFT,
解,a.付里叶变换为 (ex31a.m)
?
?
? ??
?
其他,0
30,1
)(
k
kx
?
?
???
3
0
2)()(
k
tfkjekxfX ?
2/)2(3
2
)2(4
32222
]2/)2s in [ (
)]2(2s in [
1
1
1)(
tfj
tfj
tfj
tfjtfjtfj
e
tf
tf
e
e
eeefX
??
??
??
??????
?
?
?
?
?
?
????
?
?
?
???
?
?
]2/)2s i n [ (
)]2(2s i n [)(
tf
tffX
?
??
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
??
?
??
0
]2/)2(s i n [
)]2(s i n [ 2
,
2
)2(3
0
]2/)2(s i n [
)]2(s i n [ 2
,
2
)2(3
)(
tf
tftf
tf
tftf
fX
?
?
?
?
?
??
当
当
0 0, 2 0, 4 0, 6 0, 8 1 1, 2 1, 4 1, 6 1, 8 2
0
1
2
3
4
|
X
|
? μ ? × μ ? · ù ? è
0 0, 2 0, 4 0, 6 0, 8 1 1, 2 1, 4 1, 6 1, 8 2
- 2 0 0
- 1 0 0
0
100
200
ò ? p i ? a μ ￥ ? ? μ ? ? μ ? ê
?è
? μ ? × μ ? ? à ? ?
b.计算 x(k)的 4点 DFT,
jeW
pWkxpX
j
k
kp
???
??
?
?
?
4/2
4
3
0
4 3,2,1,0)()(
?
0 0, 5 1 1, 5 2 2, 5 3 3, 5 4
-1
0
1
2
3
4
5
|
X
(
k
)
|
D FT μ ? · ù ? è, N = 4
k
0 0, 5 1 1, 5 2 2, 5 3 3, 5 4
- 2 0 0
- 1 0 0
0
100
200
?è
D FT ? à ? ?, N = 4
k
例 3.2：上例中对 x(k)填 0，以得到更多点的 DFT。
解,
a.作 8点的 DFT,
填 4个 0，得 x(k)
x(k)={1,1,1,1,0,0,0,0}
作 8点 DFT,（ ex32a.m)
4/
8
7
0
8 7,1,0)()(
?j
k
kp
eW
pWkxpX
?
?
?
?? ? ?
0 1 2 3 4 5 6 7 8
-1
0
1
2
3
4
5
k
|
X
(
k
)
|
D FT μ ? · ù ? μ, N = 8
0 1 2 3 4 5 6 7 8
- 2 0 0
- 1 0 0
0
100
200
k
?è
D FT μ ? ? à ? ?, N = 8
b.作 16点的 DFT,
填 12个 0，得 x(k)
x(k)={1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0}
作 16点 DFT,（ ex32b.m)
8/
16
15
0
16 15,1,0)()(
?j
k
kp
eW
pWkxpX
?
?
?
?? ? ?
0 2 4 6 8 10 12 14 16
-1
0
1
2
3
4
5
k
|
X
(
k
)
|
D FT μ ? · ù ? μ, N = 1 6
0 2 4 6 8 10 12 14 16
- 2 0 0
- 1 0 0
0
100
200
k
?è
D FT μ ? ? à ? ?, N = 1 6
§ 3-2 快速付里叶变换（ FFT）
用 Matlab内部函数,
X=fft(x,N);
这是对离散时间信号 {x(k)}计算 N点 DFT。
注：①当 x的长度小于 N,则用 0使 x的长度等于 N;
② 缺省 N值为 x的长度；
③若 x为一矩阵，则计算 x中每列的 fft;
④ 采用的算法,N=2m → 基 2的算法，快；
N≠ 2m → 混合基算法，慢；
N为质数 → 用原始的 DFT算法。
逆变换,
x=ifft(X,N)
快速卷积
在 Matlab 中，当 N<50时，可以用 conv函数计算卷积；当 N较
大时，用 FFT法计算更有效。
))](())(([)()(
2121 kxf f tkxf f ti f f tkxkx ???
例 3.3对比 conv和用 FFT算卷积的时间 (ex33.m)
20 40 60 80 100 120 140 160
0
0, 0 0 5
0, 0 1
0, 0 1 5