Bài giảng Digital signal processing - Chương 5: Biến đổi Fourier rời rạc (DFT) - Đinh Đức Anh Vũ

BK
TP.HCM
2011
dce
Chương 5
Biến đổi Fourier rời rạc (DFT)
©2011, TS. Đinh Đức Anh Vũ
2011
dce
2DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Giới thiệu về DFT
∑
∞
−∞=
−=
n
njenxX ωω )()(
• Biến đổi Fourier liên tục
• Vấn đề: X(ω) liên tục theo tần số ω → không thích hợp cho việc tính toán trên máy
tính
x(n)
x(n) = 0.8nu(n)
Miền tần số
Miền thời gian
F
2011
dce
3DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Lấy mẫu miền tần số 
X(ω)
N=10 N=10
Lấy
mẫu
)()( 2 kXkX Nπω =≡
2011
dce
4DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Lấy mẫu miền tần số 
• T/h xp(n) – lặp chu kỳ của x(n) mỗi N mẫu – t/h tuần hoàn với chu kỳ cơ bản N
1,...,1,0)()()( /22
/2
−=== ∑
∞
−∞=
−
=
NkenxkXX
n
Nknj
NNk
ππ
πω
ω
∑
∑ ∑
∑ ∑
∑∑∑
−
=
−
−
=
−
∞
−∞=
∞
−∞=
−+
=
−
−
=
−
−
=
−
−
−=
−
=⇒






−=
=
++++=
1
0
1
0
1
121
0
1
2
2
2
222
)()(
)(
)(
)()()()(
N
n
knj
p
N
n
knj
l
l
NlN
lNn
knj
N
Nn
knj
N
n
knj
Nn
knj
N
N
N
NNN
enxkX
elNnx
enx
enxenxenxkX
π
π
π
πππ

∑
∞
−∞=
−=
l
p lNnxnx )()(với
Thay n bằng (n-lN)
1,...,1,0)(1
1,...,1,0)(
1
0
/2
1
0
/2
−==
−==
∑
∑
−
=
−
−
=
Nkenx
N
c
Nnecnx
N
n
Nknj
pk
N
k
Nknj
kp
π
π
2011
dce
5DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Lấy mẫu miền tần số 
• Có thể phục hồi t/h xp(n) từ các mẫu của phổ X(ω)
1,,1,0)(1)(
1,,1,0)(1
1
0
2
−==
−==
∑
−
=
NnekX
N
nx
NkkX
N
c
N
k
knj
p
k
N 

π
n
x(n)
0 L
n
xp(n)
0 NL
N>L
n
xp(n)
0 N
N<L alias


 −≤≤
=
others
Nnnx
nx p
0
10)(
)(
Khi N≥L, x(n) có thể được khôi phục
từ các mẫu phổ tần số tại ωk=2πk/N
2011
dce
6DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Lấy mẫu miền tần số 
• Có thể phục hồi X(ω) từ các mẫu X(k) với k = 0, 1,, N-1
– Giả sử N ≥ L → x(n) = xp(n) khi 0 ≤ n ≤ N-1
∑
−
=
=
1
0
/2)(1)(
N
k
NknjekX
N
nx π
∑ ∑
∑ ∑∑
−
=
−
=
−−
−
=
−
−
=
∞
−∞=
−






=






==
1
0
1
0
)/2(
1
0
1
0
/2
1)(
)(1)()(
N
k
N
n
nNkj
N
n
nj
N
k
Nknj
n
nj
e
N
kX
eekX
N
enxX
πω
ωπωω
2/)1(
1
0
)2/sin(
)2/sin(
1
111)(
−−
−
−−
=
−
=
−
−
== ∑
Nj
j
NjN
n
nj
e
N
N
e
e
N
e
N
P
ω
ω
ω
ω
ω
ω
ω



−=
=
=
1,,2,10
01
)( 2
Nk
k
kP N 
π
LNkPkXX
N
k
N ≥−=∑
−
=
1
0
2 )()()( πωω
2011
dce
7DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Lấy mẫu miền tần số 
∑
−
=
−=
1
0
2
)()(
N
n
knj NenxkX
π
∑
∞
−∞=
−=
n
njenxX ωω )()(
x(n)
có chiều dài L≤N
B
Đ
 F
Lấy m
ẫu
∑
−
=
=
1
0
2
)(1)(
N
k
knj NekX
N
nx
π
∑
−
=
−=
1
0
)()()(
N
k
kPkXX ωωω
∑
−
=
−=
1
0
1)(
N
k
nje
N
P ωω kNk πω 2=
Phục hồi Phục hồi
2011
dce
8DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Lấy mẫu miền tần số 
• Ví dụ: x(n) = anu(n), 0<a<1
– Phổ t/h được lấy mẫu tại các tần số ωk = 2πk/N, k=0, 1, , N-1
ω
ωω j
n
njn
ae
eaX −
∞
=
−
−
==∑ 1
1)(
0
NkjaeN
kXkX /21
1)2()( π
π
−−
==
N
n
l
lNn
l
p
a
aa
lNnxnx
−
==
−=
∑
∑
−∞=
−
∞
−∞=
1
)()(
0
a=0.8
2011
dce
9DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Biến đổi Fourier rời rạc (DFT)
• Chuỗi không tuần hoàn, năng lượng hữu hạn x(n)
• Các mẫu tần số X(2πk/N), k = 0, 1,, N-1 không đặc trưng cho x(n) khi 
x(n) có chiều dài vô hạn
• Nó đặc trưng cho chuỗi tuần hoàn, chu kỳ N xp(n)
• xp(n) là lặp tuần hoàn của x(n) nếu x(n) có chiều dài hữu hạn L ≤ N
• Do đó, các mẫu tần số X(2πk/N), k = 0, 1,, N-1 đặc trưng cho chuỗi 
chiều dài hữu hạn x(n); i.e. X(n) có thể được phục hồi từ các mẫu tần số
{X(2πk/N)}
• x(n) = xp(n) trên một chu kỳ N (được đệm vào N-L zero). Mặc dù L mẫu 
của X(ω) có thể tái tạo lại được X(ω), nhưng việc đệm vào N-L zero giúp
việc tính toán DFT N điểm của X(ω) đồng nhất hơn
1,,1,0
)()(
1
0
2
−=
=∑
−
=
−
Nk
enxkX
N
n
knj N

π
1,,1,0
)(1)(
1
0
2
−=
= ∑
−
=
Nn
ekX
N
nx
N
k
knj N

π
DFT IDFT
2011
dce
10DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Biến đổi Fourier rời rạc (DFT)
• Ví dụ: xác định DFT N điểm của chuỗi x(n) có độ dài L hữu hạn (N≥L)


 −≤≤
=
others
Ln
nx
0
101
)(
2/)1(
1
0
)2/sin(
)2/sin(
1
1
)()(
−−
−
−
−
=
−
∞
−∞=
−
=
−
−
=
== ∑∑
Lj
j
Lj
L
n
nj
n
nj
eL
e
e
eenxX
ω
ω
ω
ωω
ω
ω
ω
2011
dce
11DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Biến đổi Fourier rời rạc (DFT)
2011
dce
12DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
1,,1,0
)()(
1
0
2
−=
=∑
−
=
−
Nk
enxkX
N
n
knj N

π
1,,1,0
)(1)(
1
0
2
−=
= ∑
−
=
Nn
ekX
N
nx
N
k
knj N

π
DFT – BĐ tuyến tính
1,,1,0
)()(
1
0
−=
=∑
−
=
Nk
WnxkX
N
n
kn
N
 1,,1,0
)(1)(
1
0
−=
= ∑
−
=
−
Nn
WkX
N
nx
N
n
kn
N

DFT IDFT
Nghiệm thứ N của đơn vị2 /j NNW e
π−=
Tính DFT một điểm
- Nhân phức: N
- Cộng phức: N-1
Tính DFT N điểm
- Nhân phức: N2
- Cộng phức: N(N-1)
2011
dce
13DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – BĐ tuyến tính
• BĐ DFT N điểm












−
=












−
=
)1(
)1(
)0(
)1(
)1(
)0(
NX
X
X
X
Nx
x
x
x NN 
















=
−−−−
−
−
)1)(1()1(21
)1(242
12
1
1
1
1111
NN
N
N
N
N
N
N
NNN
N
NNN
N
WWW
WWW
WWW
W





Ma trận 
BĐ tuyến tính
NNN XWx
1−=
NNNN XWx
*1=
NNN
NNN
NIWW
WW
=
=−
*
*11
NNN xWX =
WN là ma trận 
đường chéo
Các mẫu miền
thời gian
Các mẫu miền
tần số
2011
dce
14DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – BĐ tuyến tính
• Ví dụ: xác định DFT 4 điểm của chuỗi x(n) = {0 1 2 3}
• Ví dụ: tính DFT 4 điểm cho x(n) = {1 0 2 1}
2
Nk k
N NW W
+ = −












−−
−−
−−
=












−
−
−
=














=
jj
jj
WWW
WWW
WWW
WWWW
WWWW
WWWW
WWWW
W
11
1111
11
1111
1
1
1
1111
1
4
2
4
1
4
2
4
2
4
2
4
1
4
2
4
1
4
9
4
6
4
3
4
0
4
6
4
4
4
2
4
0
4
3
4
2
4
1
4
0
4
0
4
0
4
0
4
0
4
4












−−
−
+−
==
j
j
xWX
22
2
22
6
444












=
3
2
1
0
4x







=−−=−−=
=−+=
=+−=+−=
=++=
++==
−
−−
=
−∑
4
3
4
3
2
3
4
2
2121)3(
2121)2(
2121)1(
4121)0(
21)()(
3
0
π
π
ππ π
j
j
kjkj
n
knj
ejjX
X
ejjX
X
eeenxkX












==
− 4
3
4
3
2
2
2
4
444
π
π
j
j
e
e
xWX
2011
dce
15DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Quan hệ với các phép BĐ khác
• Với hệ số Fourier của chuỗi chu kỳ
• Với BĐ Fourier của chuỗi không chu kỳ
– DFT N điểm cho phổ vạch của chuỗi không chu kỳ x(n) nếu x(n) hữu hạn có 
độ dài L ≤ N
1,,1,0
)()(
1
0
2
−=
=∑
−
=
−
Nk
enxkX
N
n
knj N

π
1,,1,0
)(1)(
1
0
2
−=
= ∑
−
=
Nn
ekX
N
nx
N
n
knj N

π
1,,1,0
)(1
1
0
2
−=
= ∑
−
=
−
Nk
enx
N
c
N
n
knj
pk
N

π
∞≤≤∞−
=∑
−
=
n
ecnx
N
k
knj
kp
N
1
0
2
)(
π
Chuỗi xp(n) tuần hoàn chu kỳ N DFT N điểm của chuỗi x(n)
DFT N điểm cho chính xác 
phổ vạch của chuỗi 
tuần hoàn chu kỳ N
X(k) = Nck
2011
dce
16DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Biểu diễn tín hiệu
x(n) = {1 2 3 4}
Dạng thẳng Dạng vòng
x(n) x(0)
x(1)
x(2)
x(3)
DươngÂm n
-2 -1 0 1 2
n=–1
n=1
Chiều dương
Chiều âm
n=0
0 1 2 3
n1
2
3
4
x(n)
2011
dce
17DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
∑
∞
−∞=
−=
n
p lNnxnx )()(• Chuỗi tuần hoàn chu kỳ N, mở rộng từ x(n)
• Chuỗi dịch xp(n) đi k mẫu
• Chuỗi có chiều dài hữu hạn từ x’p(n)
• Quan hệ giữa x(n) và x’(n): dịch vòng
∑
∞
−∞=
−−=−=
l
pp klNnxknxnx )()()(
'



 −≤≤
=
otherwise
Nnnx
nx p
0
10)(
)('
'
x’(n) = x(n-k, MOD N) ≡ x((n-k))N
0 1 2 3
4
1
2
3
0 1 2 3
4
1
2
3
4 5 6 7
4
1
2
3
-4 -3 -2 -1
4
1
2
3
81 2 3
4
1
2
3
4 5 6 7
4
1
2
3
-2 -1 0
4
1
2
3
90 1 2 3
4
1
2
3
x(n)
x(3)
x(0)
x(1)
x(2) 3
4
2
1 x’(n)
x’(3)
x’(0)
x’(1)
x’(2) 1
2
4
3
xp(n)x(n) xp(n-2)
x’(n)
DFT – Biểu diễn tín hiệu theo vòng
2011
dce
18DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Tính đối xứng vòng
• Phép dịch vòng của một chuỗi N điểm tương đương với phép
dịch tuyến tính của chuỗi mở rộng tuần hoàn của nó
• Chuỗi N điểm là chẵn theo vòng nếu nó đối xứng qua điểm 0 
trên vòng tròn
– i.e. x(N – n) = x(n), 0 ≤ n ≤ N – 1
• Chuỗi N điểm là lẻ theo vòng nếu nó phản đối xứng qua điểm
0 trên vòng tròn
– i.e. x(N – n) = – x(n), 0 ≤ n ≤ N – 1
• Đảo theo thời gian của chuỗi N điểm: đảo các mẫu của chuỗi
quanh điểm 0 trên vòng tròn
– i.e. x((– n))N = x(N – n), 0 ≤ n ≤ N – 1
– Phép đảo được thực hiện bằng cách vẽ x(n) theo chiều kim đồng hồ
2011
dce
19DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Tính đối xứng vòng
• Giả sử x(n) và BĐ DFT X(k) là t/h phức
– x(n) = xR(n) + jxI(n), 0≤n≤N–1
– X(k) = XR(k) + jXI(k), 0≤k≤N–1
• Nếu x(n) thực: X(N-k) = X*(k) = X(–k)
và
• Nếu x(n) thực và chẵn: x(n) = x(N–n) → XI(k) = 0
• Nếu x(n) thực và lẻ: x(n) = –x(N–n) → XR(k) = 0
• Nếu x(n) thuần ảo: x(n) = jxI(n)
[ ]
[ ]






−−=
+=
∑
∑
−
=
−
=
1
0
22
1
0
22
cos)(sin)()(
sin)(cos)()(
N
n
N
kn
IN
kn
RI
N
n
N
kn
IN
kn
RR
nxnxkX
nxnxkX
ππ
ππ [ ]
[ ]






+=
−=
∑
∑
−
=
−
=
1
0
22
1
0
22
cos)(sin)(1)(
sin)(cos)(1)(
N
k
N
kn
IN
kn
RI
N
k
N
kn
IN
kn
RR
kXkX
N
nx
kXkX
N
nx
ππ
ππ
)()()()( kXkNXkXkNX −∠=−∠=−
∑
−
=
=
1
0
2cos)()(
N
n
N
knnxkX π ∑
−
=
=
1
0
2cos)(1)(
N
k
N
knkX
N
nx π
∑
−
=
−=
1
0
2sin)()(
N
n
N
knnxjkX π ∑
−
=
=
1
0
2sin)(1)(
N
k
N
knkX
N
jnx π
∑∑
−
=
−
=
==
1
0
2
1
0
2 cos)()(sin)()(
N
n
N
kn
II
N
n
N
kn
IR nxkXnxkX ππ
2011
dce
20DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Tính chất
• Tuần hoàn
• Tuyến tính
• Tổng chập vòng



∀+=
∀+=
⇒
 →←
kNkXkX
nNnxnx
kXnx NDFT
)()(
)()(
)()(
)()()()(
)()(
)()(
22112211
22
11
kXakXanxanxa
kXnx
kXnx
N
N
N
DFT
DFT
DFT
+ →←+⇒




 →←
 →←
)()()()(
)()(
)()(
2121
22
11
kXkXnxnx
kXnx
kXnx
N
N
N
DFT
DFT
DFT
 →←⊗⇒




 →←
 →←
N
Tổng chập vòng N điểmN
1,,1,0))(()()()(
1
0
2121 −=−=⊗ ∑
−
=
Nnknxkxnxnx
N
k
N N
2011
dce
21DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Tổng chập vòng
∑∑ ∑
∑ ∑∑
∑
∑
−
=
−−
−
=
−
=
−
=
−
=
−
−
=
−
−
=
−
=
=












=
=
=
=
1
0
)(
1
0
1
0
21
1
0
1
0
2
1
0
1
1
0
21
1
0
2
222
2
2
)()(1
)()(1
)()(1
)(1
)}({)(
N
k
lnmkj
N
n
N
l
N
k
kmj
N
l
klj
N
n
knj
N
k
kmj
N
k
kmj
N
NNN
N
N
elxnx
N
eelxenx
N
ekXkX
N
ekX
N
kXIDFTmx
π
πππ
π
π


 −=⇔=−−
=⇒
=−⇒==⇒≠
∈=−−=
=




≠
−
−
=
=
∑
∑
−
=
−−
−−
−
=
otherwise
nmlpNlnmN
a
aeaa
ZppNlnmkhia
eañoùTrong
a
a
a
aN
a
N
N
k
k
NlnmjN
lnmj
N
N
k
k
N
0
))((
0111
,:,1
1
1
1
1
1
0
)(2
)(
1
0
2
π
π
1,,1,0))(()()(
1,,1,0))(()()(
1
0
21
1
0
21
−=−=
−=−=
∑
∑
−
=
−
=
Nnknxkxnx
Nmnmxnxmx
N
k
N
N
n
N


)()()()(
)()(
)()(
21
22
11
kXkXkXmx
kXnx
kXnx
N
N
N
DFT
DFT
DFT
= →←




 →←
 →←
2011
dce
22DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Tổng chập vòng
• Ví dụ: cho x1(n) ={1^ 2 3 4} và x2(n) ={1^ 0 2 1}. Tính x(n) = x1(n) x2(n) theo 2 
cách
– Dùng công thức định nghĩa
– Dùng DFT và IDFT
N
Dùng định nghĩa
x(1) = 13
x1(n)x2((1-n))4 0
2
3
8
x2((1-n))4 x2(1) = 0
x2(0) = 1
x2(3) = 1
x2(2) = 2
x2(n) x2(0) = 1
x2(1) = 0
x2(2) = 2
x2(3) = 1
x1(n) x1(0) = 1
x1(1) = 2
x1(2) = 3
x1(3) = 4
x(0) = 9
x1(n)x2((-n))4 1
2
6
0
x2((-n))4 x2(0) = 1
x2(3) = 1
x2(2) = 2
x2(1) = 0 x(3) = 9
x1(n)x2((3-n))4 1
4
0
4
x2((3-n))4 x2(3) = 1
x2(2) = 2
x2(1) = 0
x2(0) = 1
x(2) = 9
x1(n)x2((2-n))4 2
0
3
4
x2((2-n))4 x2(2) = 2
x2(1) = 0
x2(0) = 1
x2(3) = 1
1,,1,0))(()()(
1
0
21 −=−=∑
−
=
Nmnmxnxmx
N
n
N 
2011
dce
23DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Tổng chập vòng







−−=−+−++=
−=−+++−+=
+−=+−+−+=
=+++=
=
+++== −−−−
=
∑
jjjX
X
jjjX
X
k
eeeenxkX kjkjkjknj
n
22)4()3()2(1)3(
2)4()3()2(1)2(
22)4()3()2(1)1(
104321)0(
3,2,1,0
4321)()(
1
1
1
1
3
0
11
2
3
24
2 πππ π
Dùng DFT & IDFT







−−=−+−+=
=−+=
+−=+−+=
=++=
=
++== −−−
=
∑
jjX
X
jjX
X
k
eeenxkX kjkjknj
n
1)()2(1)3(
2121)2(
1)()2(1)1(
4121)0(
3,2,1,0
21)()(
2
2
2
2
3
0
22
2
3
4
2 ππ π







=
−=
−=+−+−=
=
=
=
jX
X
jjjX
X
k
kXkXkX
4)3(
4)2(
4)1)(22()1(
40)0(
3,2,1,0
)()()( 21
[ ]







=
=
=
=
=
+−−=
= ∑
=
9)3(
9)2(
13)1(
9)0(
3,2,1,0
44440
4
1
)(
4
1)(
2
3
2
4
2
3
0
x
x
x
x
n
jeeje
ekXnx
njnjnj
k
knj
ππ
π
π
2011
dce
24DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Tính chất
• Đảo vòng theo thời gian
• Dịch vòng theo thời gian
• Dịch vòng theo tần số
• Liên hợp phức
)())(()())((
)()(
kNXkXnNxnx
kXnx
N
DFT
N
DFT
N
N
−=− →←−=−⇒
 →←
NkljDFT
N
DFT
ekXlnx
kXnx
N
N
/2)())((
)()(
π− →←−⇒
 →←
N
DFTNnlj
DFT
lkXenx
kXnx
N
N
))(()(
)()(
/2 − →←⇒
 →←
π




 →←−=−
−=− →←
⇒
 →←
)()())((
)())(()(
)()(
***
***
kXnNxNnx
kNXkXnx
kXnx
N
N
N
DFT
N
DFT
DFT
2011
dce
25DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Tính chất
• Tương quan vòng
• Nhân 2 chuỗi
• Định lý Parseval
)()()()(
)()(
)()(
*
~~
kYkXkRlr
kYny
kXnx
xy
DFT
xy
DFT
DFT
N
N
N
= →←⇒
 →←
 →←
∑
−
=
−=
1
0
*
~
))(()()(
N
n
Nxy lnynxlr
)()()()(
)()(
)()(
21
1
21
22
11
kXkXnxnx
kXnx
kXnx
N
DFT
DFT
DFT
N
N
N
⊗ →←⇒




 →←
 →←
N
∑∑
−
=
−
=
=⇒
 →←
 →←
1
0
*
1
0
* )()()()(
)()(
)()(
N
k
N
n
DFT
DFT
kYkXnynx
kYny
kXnx
N
N
với
2011
dce
26DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Lọc tuyến tính
• Y(ω) = H(ω)X(ω)
– Hàm liên tục theo tần số ω
– Khó thực hiện trên các máy tính số
→ DFT: một cách tính hiệu qủa của tổng chập miền thời gian
• Lọc tuyến tính
– Tín hiệu ngắn h(n)
x(n) y(n)
x(n) chiều dài = L (n=0,1,,L-1)
h(n) chiều dài = M (n=0,1,,M-1)
∑
−
=
−=
1
0
)()()(
M
k
knxkhny
y(n) chiều dài N = M+L-1
Số mẫu phổ (tần số) cần thiết để biểu diễn duy nhất chuỗi y(n) ≥ L+M-1
Y(k) = H(k)X(k), k=0,1,,N-1
H(k), X(k): DFT N điểm của h(n), x(n)
(các số 0 được đệm vào để tăng kích thước chuỗi lên N)
y(n) = IDFTN{Y(k)} • Tổng chập vòng N điểm của h(n) và x(n) 
tương đương với tổng chập tuyến tính của h(n) với x(n)
• DFT có thể được dùng để lọc tuyến tính 
(bằng cách đệm thêm các số 0 vào chuỗi tương ứng)
2011
dce
27DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Lọc tuyến tính
• Tóm tắt
• Ví dụ: tính đáp ứng y(n) dùng DFT và IDFT 
– h(n) = {1^, 0, 1, 2} và x(n) = {1^, 0, 1}
Y(k) = X(k)H(k)
x(n)
DFTN X(k)
h(n)
DFTN H(k)
x IDFTN y(n)
)7,...,1,0(
1)()(
21)()(
2/
7
0
8/2
4/32/
7
0
8/2
=






+==
++==
−
=
−
−−
=
−
∑
∑
k
eenxkX
eeenhkH
kj
n
knj
kjkj
n
knj
ππ
πππ













+=
=
−=
=
+=
=
−=
=
jX
X
jX
X
jX
X
jX
X
1)7(
0)6(
1)5(
2)4(
1)3(
0)2(
1)1(
2)0(














++−=
−=
−++=
=
−++=
=
+−−=
=
jH
jH
jH
H
jH
jH
jH
H
)21()21()7(
2)6(
)12()21()5(
0)4(
)21()21()3(
2)2(
)21()21()1(
4)0(
)7,...,1,0()()(
7
0
8/2 ==∑
=
nekYny
k
knj π













+−=
=
−=
=
+=
=
−=
=
)2(2)7(
0)6(
)2(2)5(
0)4(
)2(2)3(
0)2(
)1(2)1(
8)0(
jY
Y
jY
Y
jY
Y
jY
Y
2011
dce
28DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Lọc tuyến tính
• Tín hiệu nhập dài: chia nhỏ x(n) thành từng 
block có độ dài cố định
– Overlap-Save
– Overlap-Add
• Giả thiết
– Bộ lọc có h(n): chiều dài M
– T/h nhập x(n): được chia nhỏ thành từng block có 
chiều dài L >> M
2011
dce
29DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Lọc tuyến tính – Overlap-Save
• DFTN và IDFTN với N = L+M–1 
• Mỗi block dữ liệu được xử lý bao gồm (M – 1) điểm của block trước và L 
điểm mới của t/h nhập
– M-1 điểm của block đầu tiên được set bằng 0
• Đáp ứng xung của bộ lọc được đệm thêm (L – 1) số 0 để tăng chiều dài 
lên N
– DFT của N điểm của h(n) được tính một lần duy nhất
Input
M-1
Add M-1 zeros
x1(n)
x2(n)
x3(n)
Output
LL
L
M-1 L
M-1 L
M-1 L
M-1 L
M-1 L
M-1 LDiscard
2011
dce
30DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
Lọc tuyến tính – Overlap-Add
• Đệm thêm (M-1) số 0 vào mỗi block dữ liệu đầu vào
Input
M-1x1(n)
x2(n)
x3(n)
Output
L
M-1L
M-1L
M-1L
M-1L
M-1L
+
+
zeros
Phương pháp hiệu quả hơn dùng để xác định bộ lọc tuyến tính 
được trình bày trong chương 6
2011
dce
31DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Phân tích tần số


 −≤≤
=
otherwise
Ln
nw
0
101
)(
• T/h ngắn
– Tính DFT từ x(n)
• T/h dài
– Cửa sổ hoá
Cửa sổ chữ nhật Cửa sổ Hanning


 −≤≤−
= −
otherwise
Lnn
nw L
0
10)cos1(
)( 1
2
2
1 π
x(n): t/h cần phân tích
Giới hạn chiều dài chuỗi một khoảng L mẫu 
⇔ Nhân chuỗi với cửa sổ chiều dài L
xw(n) = x(n)w(n)
w(n): hàm cửa sổ
Hàm cửa sổ có chiều dài L 
chỉ phân biệt được 
nếu các tần số cách nhau 
ít nhất một đoạn 
L
πω 2=∆
2011
dce
32DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ
DFT – Phân tích tần số
• Ví dụ
nnnx 21 coscos)( ωω +=
[ ])()()()()( 212121
^
ωωωωωωωωω ++++−+−= WWWWX
L=25
L=75
L=50
L=100
ω1 = 0.2π
ω2 = 0.22π


 −≤≤
=
otherwise
Ln
nw
0
101
)(
Rò rỉ công suất