Signal & Systems - Lecture 9 - Trần Quang Việt

1Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
Ch-5: Lấy mẫu (Sampling)
Lecture-9 
5.1. Lý thuyết lấy mẫu
5.2. Biến đổi Fourier rời rạc (DFT)
5.3. Biến đổi Fourier nhanh (FFT)
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
5.1. Lý thuyết lấy mẫu
5.1.1. Lấy mẫu trong miền thời gian
5.1.2. Lấy mẫu trong miền tần số
2Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
5.1.1. Lấy mẫu trong miền thời gian
a) Lấy mẫu bằng chuỗi xung đơn vị - định lý lấy mẫu
b) Lấy mẫu bằng bộ giữ mẫu bậc không
c) Khôi phục tín hiệu – các phương trình nội suy
d) Khó khăn trong việc khôi phục tín hiệu thực tế
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
a) Lấy mẫu bằng chuỗi xung đơn vị - định lý lấy mẫu

 Trong miền thời gian: nhân tín hiệu cần lấy mẫu với chuỗi xung p(t)
sp(t) δ(t nT )
n
+∞
=−∞
= −∑f(t) f (t)
−
f (t)=f(t)p(t)
sf (t)=f(t) δ(t nT )
n
∞
=−∞
−∑ s sf (t) f(nT )δ(t nT )
n
∞
=−∞
= −∑

 Trong miền tần số: lặp lại phổ tín hiệu cần lấy mẫu
f(t) F(ω) (Band-limited to B Hz)↔
s s s s s
ns
2pip(t) P(ω) δ(ω nω ); F =1/T , ω =2piF
T
∞
=−∞
↔ = −∑
s
ns
1 1f (t) F(ω)= [F(ω) P(ω)] F(ω nω )
2pi T
∞
− −
=−∞
↔ ∗ = −∑
3Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
a) Lấy mẫu bằng chuỗi xung đơn vị - định lý lấy mẫu
sF 2B≥ s; F =2B Nyquist rate

 Định lý lấy mẫu: ĐL Nyquist, ĐL Shannon
Tín hiệu có phổ giới hạn là B Hz có thể khôi phục chính
xác từ các mẫu của nó có được khi lấy mẫu đều đặn với
tốc độ Fs≥2B mẫu/s. Nói cách khác tần số lấy mẫu nhỏ
nhất là Fs=2B Hz 
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
b) Lấy mẫu với bộ giữ mẫu bậc không
f(t)
0f (t)
sp(t)= δ(t nT )
n
+∞
=−∞
−∑

 Lấy mẫu với bộ giữ mẫu bậc không
f(t) 0f (t)
4Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
b) Lấy mẫu với bộ giữ mẫu bậc không

 Bộ khôi phục tín hiệu cho bộ giữ mẫu bậc không
sp(t)= δ(t nT )
n
+∞
=−∞
−∑
f(t) 0f (t) f (t)− f(t)
1H (ω ) s 2T H (ω)
r s 1 2H (ω)=T H (ω)H (ω)
r|H (ω)| rH (ω)∠
Không thực hiện được!!!
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
c) Khôi phục tín hiệu – các phương trình nội suy

 Nội suy lý tưởng dùng hàm sinc:
( )s
n=-
f(t)= f(nT )sinc 2piBt npi
+∞
∞
−∑
5Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
c) Khôi phục tín hiệu – các phương trình nội suy

 Nội suy với bộ giữ mẫu bậc không:
f (t)
−
0f (t)
0|H (ω)|
F( )ω
−
0|F (ω)|
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
d) Khó khăn trong việc khôi phục tín hiệu thực tế
Ideal Filter
Practical Filter
6Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
d) Khó khăn trong việc khôi phục tín hiệu thực tế
Aliasing effect
Giải pháp: Anti-aliasing Filter 
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
d) Khó khăn trong việc khôi phục tín hiệu thực tế
Anti-
aliasing 
Filter 
7Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
5.1.2. Lấy mẫu trong miền tần số
0
0
1 ( )nD F nT ω= ⇒ Phổ của fT0(t) chính là lấy mẫu phổ của f(t)
Điều kiện khôi phục tốc độ lấy mẫu R=1/F0≥τ
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
5.2. Biến đổi Fourier rời rạc DFT
( ) ( ) j tF f t e dtωω ∞ −
−∞
= ∫
1( ) ( )
2
j tf t F e dωω ω
pi
∞
−∞
= ∫
0
0
1
0
N
jr k
r k
k
F f e
−
− Ω
=
= ∑
0
0
1
0 0
1 N jr k
k r
r
f F e
N
−
Ω
=
= ∑0 0 / sN T T=
( )k s sf T f kT=
0 02 / NpiΩ =
N0 mẫu N0 mẫu
8Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
5.3. Biến đổi Fourier nhanh FFT
Giảm khối lượng tính toán: 20 0 0logN N N→
0
0
1
0
N
jr k
r k
k
F f e
−
− Ω
=
= ∑
0
0
1
0 0
1 N jr k
k r
r
f F e
N
−
Ω
=
= ∑ Nhân: N0
Cộng: N0-1
Tổng cộng cho các hệ số: N0N0 phép nhân và N0(N0-1) phép cộng
Đưa ra bởi Turkey and Cooley năm 1965, N0 phải là lũy thừa của 2

 Đặt: ( )0 0
0
2 /j N j
NW e e
pi−
− Ω
= =

 Các biểu thức DFT được viết lại: 
0
0
1
0
N
kr
r k N
k
F f W
−
=
= ∑
0
0
1
0 0
1 N kr
k r N
r
f F W
N
−
−
=
= ∑
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
5.3. Biến đổi Fourier nhanh FFT

 Chia fk thành 2 chuỗi: chẵn và lẻ theo số thứ tự:
0 0
k k
0 4 6 2 1 3 5 1
 g h
, , ,..., , , ,...,N N
sequence sequence
f f f f f f f f
− −



0 0
2 2
0 0
1 1 (2 1)2
2 2 1
0 0
N N
k rkr
r k N k N
k k
F f W f W
− −
+
+
= =
= +∑ ∑
Biểu thức DFT được viết lại:
0 0
2 2
0 0
02 2
1 1
2 2 1
0 0
N N
N N
kr r kr
r k N k
k k
F f W W f W
− −
+
= =
⇒ = +∑ ∑
Ta có: 0
02
2
N NW W=
0
r
r N rG W H= +
9Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
5.3. Biến đổi Fourier nhanh FFT

 Do Gr và Hr là DFT N0/2 điểm nên nó có tính tuần hoàn:
0 0
2 2
 &N Nr rr rG G H H+ += =
Mặt khác: 0 02 2
00 0
N N
r r
NN NW W W
+
=
0 0
j r r
N Ne W W
pi−
= = −
0 0
2 2
0 0
02 2
1 1
2 2 1
0 0
N N
N N
kr r kr
r k N k
k k
F f W W f W
− −
+
= =
⇒ = +∑ ∑ 0
r
r r N rF G W H= +
0
2
0 0 0
2 2 20
N
N N N
r
r r rNF G W H
+
+ + +⇒ = + 0 02N
r
r N rrF G W H+ = −
⇒
⇒
0(0 1)r N≤ ≤ −
0
0
0
0
02
2
2
; 0 1
; 0 1N
Nr
r r N r
Nr
r N rr
F G W H r
F G W H r+
= + ≤ ≤ −
= − ≤ ≤ −
rG rF
rH 02NrF +
0
r
NW
0
r
NW−
⇔
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
5.3. Biến đổi Fourier nhanh FFT
0
0
0
0
02
2
2
; 0 1
; 0 1N
Nr
r r N r
Nr
r N rr
F G W H r
F G W H r+
= + ≤ ≤ −
= − ≤ ≤ −
rG rF
rH 02NrF +
0
r
NW
0
r
NW−
⇔
10
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
5.3. Biến đổi Fourier nhanh FFT
0
0
0
0
02
2
2
; 0 1
; 0 1N
Nr
r r N r
Nr
r N rr
F G W H r
F G W H r+
= + ≤ ≤ −
= − ≤ ≤ −
rG rF
rH 02NrF +
0
r
NW
0
r
NW−
⇔
Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/10-11
5.3. Biến đổi Fourier nhanh FFT
 Số phép toán nhân và cộng dùng để tính DFT dùng giải thuật FFT: 
0
0
0
0
02
2
2
; 0 1
; 0 1N
Nr
r r N r
Nr
r N rr
F G W H r
F G W H r+
= + ≤ ≤ −
= − ≤ ≤ −
rG rF
rH 02NrF +
0
r
NW
0
r
NW−
⇔
 Số phép toán nhân: 0 2 0log2
N N
 Số phép toán cộng: 0 2 0logN N