Bài giảng Tín hiệu và hệ thống: Chương 7 (Lecture 20) – Trần Quang Việt (2017)

404001 - Tín hi u và h th ng

Lecture-20
L y m u (Sampling)
Lý thuy t l y m u
Bi n i Fourier r i r c (DFT)
Bi n i Fourier nhanh (FFT)

Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/09-10

Bi n

i Fourier r i r c (DFT)

f (t ) =

1
2π

∞

∫−∞

F (ω )e jωt d ω

F (ω ) = ∫

−∞

fk =

1
N0

f (t )e − jωt dt

N0 m u

N0 m u

Ω0 = 2π / N 0
N 0 = T0 / T
f k = Tf (kT )

∞

N 0 −1

∑

r =0

Fr e jrΩ0 k Fr =

N 0 −1

∑

f k e − jrΩ0k

k =0

Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/09-10

1

Bi n

i Fourier nhanh (FFT)

ưa ra b i Turkey and Cooley năm 1965, N0 ph i là lũy th a c a 2
2
Gi m kh i lư ng tính toán: N 0 → N 0 log N 0

N −1

N −1

fk =

0
1 0
Fr e jrΩ0 k Fr = ∑ f k e − jrΩ0k
∑
N 0 r =0
k =0

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
− j 2π / N 0 )
t: WN 0 = e (
= e − jΩ0

Các bi u th c DFT ư c vi t l i:
N 0 −1

Fr =

∑

N −1

1 0
−
fk =
∑ FrWN 0kr
N 0 r =0

kr
f kWN 0

k =0

Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/09-10

Bi n

i Fourier nhanh (FFT)

Chia fk thành 2 chu i: ch n và l theo s th t :
f 0 , f 4 , f 6 ,..., f N 0 −2 f1 , f 3 , f5 ,..., f N 0 −1
sequence g k

sequence h k

Bi u th c DFT ư c vi t l i:
N0
2

Fr =

−1

∑

2
f 2 kWN 0kr +

k =0

N0
2

−1

∑

(2
f 2 k +1WN k +1) r
0

k =0

2
Ta có: W N0 = WN
0
2

⇒ Fr =

N0
2

−1

∑

k =0

kr

f 2 kW N 0
2

r
+ WN 0

N0
2

−1

∑

k =0

f 2 k +1W Nkr = G + W r H
0
2
r
N0 r

Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/09-10

2

Bi n

i Fourier nhanh (FFT)

⇒ Fr =

N0
2

−1

∑

kr

f 2 kW N 0
2

r
+ WN 0

k =0

N0
2

−1

∑

r
f 2 k +1W Nkr ⇒ Fr = Gr + WN 0 H r
0
2

k =0

(0 ≤ r ≤ N 0 − 1)
Do Gr và Hr là DFT N0/2 i m nên nó có tính tu n hoàn:

Gr + N20 = Gr & H r + N20 = H r
N0

N0

r
r
r
M t khác: W r + 2 = W 2 WN = e − jπ WN = −WN
N0
N0
0
0
0
N0

r
r
⇒ Fr + N0 = Gr + N0 + WN+ 2 H r + N0 ⇒ Fr + N0 = Gr − WN H r
2
2
2
0
0
2

r
Fr = Gr + WN 0 H r ; 0 ≤ r ≤

Fr +

N0
2

r
= Gr − WN 0 H r ;

N0
2

0≤r≤

Gr

−1
N0
2

Fr

⇔
−1
Hr

r
−W N 0

r
WN0

Fr + N20

Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/09-10

Bi n

i Fourier nhanh (FFT)

r
Fr = Gr + WN 0 H r ; 0 ≤ r ≤

Fr + N0
2

r
= Gr − WN 0 H r ;

N0
2

0≤r≤

Gr

−1
N0
2

Fr

⇔
−1
Hr

r
−W N 0

r
WN0

Fr + N20

Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/09-10

3

Bi n

i Fourier nhanh (FFT)

r
Fr = Gr + WN 0 H r ; 0 ≤ r ≤

Fr + N0
2

r
= Gr − WN 0 H r ;

N0
2

0≤r≤

Gr

−1
N0
2

Fr

⇔
−1
Hr

r
−W N 0

r
WN0

Fr + N20

Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/09-10

Bi n

i Fourier nhanh (FFT)

r
Fr = Gr + WN 0 H r ; 0 ≤ r ≤

Fr +

N0
2

r
= Gr − WN 0 H r ;

N0
2

0≤r≤

Gr

−1
N0
2

Fr

⇔
−1

S phép toán nhân và c ng dùng

Hr

r
−W N 0

r
WN0

Fr + N20

tính DFT dùng gi i thu t FFT:

S phép toán nhân: N 0 log 2 N 0
2
S phép toán c ng: N 0 log 2 N 0

Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/09-10

4

Bài t p
Bài 1. Tín hi u f(t)=sinc(200πt) ư c l y m u b i chu i xung ơn v
tu n hoàn v i các t c
l n lư t như sau: (a) 150Hz, (b) 200Hz, (c)
300Hz. V ph c a tín hi u ã ư c l y m u tương ng v i các
trư ng h p trên? Có th khôi ph c l i tín hi u g c f(t) t tín hi u
ư c l y m u không, gi i thích? Cho tín hi u ã ư c l y m u i
qua b l c thông th p lý tư ng có băng thông 100Hz, v ph c a tín
hi u ngõ ra b l c?
Bài 2. Tín hi u f(t)=sinc(200πt) ư c l y m u b i tín hi u xung tu n
hoàn pT(t) như hình v . Hãy tìm và v ph c a tín hi u ã ư c l y
m u? Cho tín hi u ã ư c l y m u i qua b l c thông th p lý tư ng
có băng thông b ng 100Hz, hãy xác nh tín hi u ngõ ra c a b l c?

Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/09-10

Bài t p

Bài 3. Tín hi u f(t)=5sinc2(5πt) ư c l y m u (t c
Nyquist) như hình v :

l n hơn t c

T/4

T

Hãy xác nh và v ph c a tín hi u ã ư c l y m u? T ó gi i
thích có th khôi ph c tín hi u g c t tín hi u này hay không?

Signal & Systems - Tran Quang Viet – FEEE, HCMUT – Semester: 02/09-10

5