Bài giảng Xử lý tín hiệu số - Chương 5: Biến đổi fourier rời rạc (DFT) - Đinh Đức Anh Vũ

11DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
Biến đổi Fourier rời rạc (DFT)
12DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
DFT – BĐ tuyến tính
1,,1,0
)()(
1
0
-=
= å
-
=
Nk
WnxkX
N
n
kn
N
K 1,,1,0
)(1)(
1
0
-=
= å
-
=
-
Nn
WkX
N
nx
N
n
kn
N
K
DFT IDFT
1,,1,0
)()(
1
0
2
-=
= å
-
=
-
Nk
enxkX
N
n
knj N
K
p
1,,1,0
)(1)(
1
0
2
-=
= å
-
=
Nn
ekX
N
nx
N
k
knj N
K
p
Nghiệm thứ N của đơn vị
Nj
N eW
/2p-=
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)
13DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
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 MM
ú
ú
ú
ú
ú
ú
û
ù
ê
ê
ê
ê
ê
ê
ë
é
=
----
-
-
)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
L
MMMM
L
L
L
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ố
14DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
§ 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
§ SV xem thêm mối quan hệ giữa DFT và BĐ Z; giữa DFT và hệ số Fourier 
của t/h LTTG
DFT – Quan hệ với các phép BĐ khác
1,,1,0
)()(
1
0
2
-=
= å
-
=
-
Nk
enxkX
N
n
knj N
K
p
1,,1,0
)(1)(
1
0
2
-=
= å
-
=
Nn
ekX
N
nx
N
n
knj N
K
p
1,,1,0
)(1
1
0
2
-=
= å
-
=
-
Nk
enx
N
c
N
n
knj
pk
N
K
p
¥££¥-
= å
-
=
n
ecnx
N
k
knj
kp
N
1
0
2
)(
p
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
15DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
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)
16DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
§ 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
å
¥
-¥=
-=
n
p lNnxnx )()(
å
¥
-¥=
--=-=
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
17DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
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ồ
18DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
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
pp
pp [ ]
[ ]
ï
ï
î
ïï
í
ì
+=
-=
å
å
-
=
-
=
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
pp
pp
)()()()( kXkNXkXkNX -Ð=-Ð=-
å
-
=
=
1
0
2cos)()(
N
n
N
knnxkX p å
-
=
=
1
0
2cos)(1)(
N
k
N
knkX
N
nx p
å
-
=
-=
1
0
2sin)()(
N
n
N
knnxjkX p å
-
=
=
1
0
2sin)(1)(
N
k
N
knkX
N
jnx p
åå
-
=
-
=
==
1
0
2
1
0
2 cos)()(sin)()(
N
n
N
kn
II
N
n
N
kn
IR nxkXnxkX pp
19DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
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ích chập vòng N điểmN
1,,1,0))(()()()(
1
0
2121 -=-=Ä å
-
=
Nnknxkxnxnx
N
k
N KN
20DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
DFT – Tích 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
p
ppp
p
p
î
í
ì -=Û=--
=Þ
=-Þ==Þ¹
Î=--=
=
ïî
ï
í
ì
¹
-
-
=
=
å
å
-
=
--
--
-
=
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
p
p
1,,1,0))(()()(
1,,1,0))(()()(
1
0
21
1
0
21
-=-=
-=-=
å
å
-
=
-
=
Nnknxkxnx
Nmnmxnxmx
N
k
N
N
n
N
K
K
)()()()(
)()(
)()(
21
22
11
kXkXkXmx
kXnx
kXnx
N
N
N
DFT
DFT
DFT
=¾¾ ®¬
ïî
ï
í
ì
¾¾ ®¬
¾¾ ®¬
21DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
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)())((
)()(
p-¾¾ ®¬-Þ
¾¾ ®¬
N
DFTNnlj
DFT
lkXenx
kXnx
N
N
))(()(
)()(
/2 -¾¾ ®¬Þ
¾¾ ®¬
p
ïî
ï
í
ì
¾¾ ®¬-=-
-=-¾¾ ®¬
Þ
¾¾ ®¬
)()())((
)())(()(
)()(
***
***
kXnNxNnx
kNXkXnx
kXnx
N
N
N
DFT
N
DFT
DFT
22DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
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
23DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
§ 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
DFT – Lọc tuyến tính
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)
24DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
DFT – Lọc tuyến tính
Y(k) = X(k)H(k)
x(n)
DFTN X(k)
h(n)
DFTN
H(k)
x
IDFTN y(n)
§ Tóm tắt
§ 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
25DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
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
26DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
Lọc tuyến tính – Overlap-Add
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
§ Đệm thêm (M-1) số 0 vào mỗi block dữ liệu đầu 
vào
27DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
DFT – Phân tích tần số
§ 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
Ln
nw
0
101
)(
î
í
ì -££-
= -
otherwise
Lnn
nw L
0
10)cos1(
)( 1
2
2
1 p
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
pw 2=D
28DSP – Lecture 5, © 2007, Dr. Dinh-Duc Anh-Vu – CSE
DFT – Phân tích tần số
§ Ví dụ nnnx 21 coscos)( ww +=
[ ])()()()()( 212121
^
wwwwwwwww ++++-+-= 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