Bài giảng Xử lý tín hiệu số - Chương 5: Phép biến đổi Fourier rời rạc và ứng dụng

Chuyển tổng chập tuyến tính sang miền tần số: 
)(X).(X)(Y 21 ΩΩ=Ω 
- Lấy mẫu )(Y Ω với số mẫu là 1NNNN
21 xxy
−+=≥ , ta được: 
]k[H].k[X]k[Y = 
- Tính DFT ngược, ta được: 
y[n] = x[n] * h[n] 
ở đây chiều dài của y[n] , x[n] và h[n] là: 
1NNNN
21 xxy
−+=≥ 
Như vậy, bằng cách kéo dài các tín hiệu x1[n] và x2[n] ra đến chiều dài 
1NNNN
21 xxy
−+=≥ rồi lấy chập vòng, ta được hai kết quả của tổng chập vòng và 
chập tuyến tính là trùng nhau: 
]n[x]n[x]n[x]n[x]n[y 2121 ⊗=∗= 
Ví dụ: 
Tìm 1 2[ ] [ ] [ ]x n x n z n⊗ = , với 1[ ] [1,2,0,0]x n = , 2[ ] [1,1,0,0]x n = và N = 4. 
Kết quả này có trùng với tổng chập tuyến tính không? 
Chương V 
- 105 - 
Ví dụ: 
Tìm [ ] [ ] [ ]y n x n x n= ⊗ , với [ ] [1,0,1,1]x n = trong hai trường hợp: 
(a) N = 4 
(b) N = 8 
N bằng bao nhiêu là đủ để tổng chập vòng trùng với tổng chập tuyến tính? 
5.3 MỘT SỐ ỨNG DỤNG CỦA DFT 
Phần này sẽ giới thiệu sơ lược về một số ứng dụng của DFT trong thực tế 
5.3.1 Phân tích phổ tín hiệu 
Trong chương trước, ta đã biết được ý nghĩa của phổ trong việc phân tích tín hiệu, từ phổ của 
tín hiệu ta biết được một số thông tin cần thiết. 
Để tìm phổ của tín hiệu (cả liên tục và rời rạc), ta cần phải biết giá trị của tín hiệu tại tất cả 
các thời điểm. Tuy nhiên trong thực tế, do ta chỉ quan sát được tín hiệu trong một khoảng 
thời gian hữu hạn nên phổ tính được chỉ là xấp xỉ của phổ chính xác. DFT được ứng dụng rất 
hiệu quả trong việc tính toán phổ xấp xỉ này. 
Trong thực tế, nếu tín hiệu cần phân tích là tín hiệu liên tục, trước hết ta cho tín hiệu đó đi 
qua một bộ lọc chống chồng phổ rồi lấy mẫu với tần số B2Fs ≥ , với B là băng thông của tín 
hiệu sau khi lọc. Như vậy, tần số cao nhất chứa trong tín hiệu rời rạc là Fs/2. Sau đó, ta phải 
giới hạn chiều dài của tín hiệu trong khoảng thời gian T0 = LT, với L là số mẫu và T là 
khoảng cách giữa hai mẫu. Cuối cùng, ta tính DFT của tín hiệu rời rạc L mẫu. Như đã trình 
bày trên, muốn tăng độ phân giải của phổ rời rạc, ta tăng chiều dài của DFT bằng cách bù 
thêm số 0 vào cuối tín hiệu rời rạc trước khi tính DFT. 
Ví dụ sau đây minh họa một ứng dụng của DFT trong việc phân tích phổ tín hiệu điện tâm đồ 
(ECG): 
Hình vẽ (a) là đồ thị của 11 nhịp tim của một bệnh nhân. 11 nhịp tim này xuất hiện trong 
khoảng thời gian 9 giây, tương đương với 11/9 = 1.22 nhịp trong một giây, hay 73 nhịp trong 
một phút. 
Hình (b) là chi tiết nửa đầu của nhịp tim thứ tư. 
Hình (c) là một đoạn phổ biên độ DFT có được sau khi lấy mẫu đoạn 11 nhịp tim (a) với tần 
số lấy mẫu là 8 kHz. Nhìn (c) ta thấy có hai điểm biên độ cao nhất xuất hiện ở tần số 88 Hz 
Chương V 
- 106 - 
và 235 Hz. 
Để tìm hiểu phổ kỹ hơn, ta tính DFT 
của tín hiệu ở hình (b)- phổ này thể 
hiện ở hình (d), ở đây ta thấy rõ hai 
điểm biên độ cao nhất ở tần số 88 
Hz và 235 Hz bên trong mỗi nhịp 
tim. Tuy nhiên, ta không thấy tần số 
lặp lại nhịp tim là 1.22 Hz trong 
DFT hình (c). 
Hình (e) giải thích rõ hơn điều này. 
Nó là phiên bản mở rộng của các đỉnh nhọn trong dải tần từ 60 Hz đến 100 Hz. Trong khi tần 
số 1.22 Hz quá nhỏ nên không thấy rõ trong hình (c) thì trong hình (e) này, ta thấy rõ các hài 
của tần số 1.22 Hz và thấy rõ khoảng cách giữa hai đỉnh nhọn là 1.22 Hz. 
5.3.2 Tính tín hiệu ra hệ thống rời rạc LTI 
Tín hiệu ra hệ thống rời rạc LTI được tính bằng cách chập tín hiệu vào với đáp ứng xung của 
hệ thống: 
]n[h]n[x]n[y ∗= 
Ta có hai cách để tính tổng chập này: một là tính trực tiếp, hai là tính thông qua tổng chập 
vòng như phân tích trong mục 5.2.4. Cách tính qua tổng chập vòng sẽ có lợi hơn về mặt thời 
gian. Lý do là tổng chập vòng có thể tính thông qua DFT, mà DFT có thể được tính nhanh 
nhờ thuật toán tính nhanh FFT. 
Để tính y[n], ta thực hiện theo các bước sau đây: 
- Kéo dài x[n] đến độ dài N = Nx + Nh - 1 
Chương V 
- 107 - 
- Kéo dài h[n] đến độ dài N = Nx + Nh - 1 
- Tính DFT của x[n] N mẫu, ta được X[k] 
- Tính DFT của h[n] N mẫu, ta được H[k] 
- Nhân X[k] với H[k], ta được Y[k]: 
Y[k] = X[k].H[k] 
- Tính DFT ngược của Y[k], ta được y[n] 
Việc tính DFT và DFT ngược được thực hiện nhờ một thuật toán tính nhanh DFT, gọi là FFT 
(Fast Fourier Transform). Phần sau sẽ trình bày về thuật toán FFT. 
5.4 TÍNH NHANH DFT BẰNG THUẬT TOÁN FFT 
DFT được ứng dụng rộng rãi trong xử lý tín hiệu rời rạc/ số nên nhiều nhà toán học, kỹ sư 
đã rất quan tâm đến việc rút ngắn thời gian tính toán. Năm 1965, Cooley và Tukey đã tìm ra 
thuật toán tính DFT một cách hiệu quả gọi là thuật toán FFT. Cần lưu ý FFT không phải là 
một phép biến đổi mà là một thuật toán tính DFT nhanh và gọn hơn. 
Để đánh giá hiệu quả của thuật toán, ta sử dụng số phép tính nhân và cộng phức. Số phép 
nhân và cộng phức liên quan trực tiếp đến tốc độ tính toán khi thuật toán được thực hiện trên 
các máy tính hay là các bộ xử lý chuyên dụng. 
5.4.1 Hiệu quả tính toán của FFT 
Công thức tính DFT của dãy dài N: 
1
0
[ ] [ ]
N
kn
n
X k x n W
−
=
=∑ 
Qua đây ta thấy để tính mỗi giá trị DFT ta cần N phép nhân và cộng phức. Để tính toàn bộ 
DFT ta cần 2N phép nhân và cộng phức. 
Tuy nhiên, nếu tính DFT nhờ thuật toán FFT thì số phép nhân và cộng phức giảm xuống chỉ 
còn 22 logN N . 
Ví dụ như 102 1024N = = thì nếu tính trực tiếp DFT cần 2 20 62 10N = = phép nhân và cộng 
phức, trong khi tính qua FFT thì số phép nhân và cộng phức giảm xuống chỉ còn 22 logN N = 
5120. Số phép tính giảm đi gần 200 lần! 
Hình sau cho thấy rõ hiệu quả của thuật toán FFT: 
0 20 40 60 80 100
0
2000
4000
6000
8000
10000 
N, Size of DFT or FFT
N
um
ber of O
perations
Chương V 
- 108 - 
Có nhiều thuật toán FFT khác nhau bao gồm FFT phân chia theo thời gian và FFT phân chia 
theo tần số. Trong phần này ta tập trung vào thuật toán FFT cơ số 2 
( 2 where is an integeriN i= ) phân chia theo thời gian. 
5.4.2 Nguyên tắc của FFT 
Nguyên tắc cơ bản mà các thuật toán FFT đều dựa vào là phân chia DFT N mẫu thành các 
DFT nhỏ hơn một cách liên tục: 
Với N = 2i, đầu tiên ta phân chia DFT N mẫu thành các DFT 2N mẫu, sau đó phân chia DFT 
2
N mẫu thành DFT 4N mẫu và cứ tiếp tục như thế cho đến khi được các DFT dài N = 2. Việc 
tính DFT nhỏ hơn rõ ràng sẽ cần ít phép tính nhân và cộng phức hơn. 
Trước tiên, chia [ ]x n thành các dãy con chẵn và lẻ: 
even odd
[ ] [ ] [ ]kn kn
n n
X k x n W x n W= +∑ ∑ 
Đặt 2n m= với n chẵn và 2 1n m= + với n lẻ: 
2 21 1
2 (2 1)
0 0
[ ] [2 ] [2 1]
N N
mk k m
m m
X k x m W x m W
− −
+
= =
= + + =∑ ∑ 
2 21 1
2 2
0 0
[2 ]( ) [2 1]( )
N N
mk k mk
m m
x m W W x m W
− −
= =
+ + =∑ ∑ 
[ ] [ ] [ ] [ ] [ ]k ke oX k X k W X k G k W H k= + = + 
[ ]eX k và [ ]oX k là DFT 2N mẫu. 
Tiếp theo chia dãy con 2N mẫu là x[2m] làm đôi bằng cách đặt 2m p= : 
4 41 1
4 2 4
0 0
[ ] [4 ]( ) [4 2]( )
N N
kp k kp
e
p p
X k x p W W x p W
− −
= =
= + + =∑ ∑ 
Thực hiện tương tự như vậy cho dãy con x[2m+1] 
Ví dụ: N = 8 
Quá trình phân chia DFT 8 mẫu thành các DFT nhỏ hơn được minh họa trên lưu đồ. 
Đầu tiên, chia x[n] thành 2 dãy con, dãy thứ nhất là dãy chẵn x[0], x[2], x[4], x[6] và dãy thứ 
hai là dãy lẻ x[1], x[3], x[5], x[7]. 
Tiếp theo, chia dãy chẵn thành 2 dãy con, dãy thứ nhất là x[0], x[4] và dãy thứ hai là x[2], 
x[6]. 
Tương tự, dãy lẻ được chia thành 2 dãy con, là dãy x[1], x[5] và dãy x[3], x[7]. 
Các DFT 2 mẫu được tính đơn giản như sau: 
]1[g]0[gW]1[gW]0[g]1[G
]1[g]0[gW]1[gW]0[g]0[G
1eW,1k0,W]n[g]k[G
1.11.0
0.10.0
2
2j1
0n
nk
−=+=
+=+=⇒
−==≤≤=
π−
=
∑
(chỉ cần phép cộng và trừ) 
Chương V 
- 109 - 
Chương V 
- 110 - 
FFT cơ sở: 
A “Butterfly” 
 0 
 WNr 
 WN(r + N/2) 
Lưu ý: WN(r + N/2) = WN N/2 WNr = -1 WNr = - WNr , do đó có thể vẽ lại lưu đồ FFT đơn 
giản như sau: 
Chương V 
- 111 - 
Phụ lục 1 
Summary: The Common Types of Fourier Transforms 
 Continuous in Time ( )x t 
= Aperiodic in Frequency 
Discrete in Time [ ]x n 
= Periodic in Frequency 
Periodic in 
Time, 
= Discrete 
in 
Frequency 
Fourier Series (FS): 
0
1 ( ) jk tk Ta x t e dtT
ω−= ∫ 
0( ) jk tk
k
x t a e ω
∞
=−∞
= ∑ 
Discrete Fourier Series (DFS) 
and Discrete Fourier Transform 
(DFT): 
1
0
[ ] [ ] ,0 1
N
kn
N
n
X k x n W k N
−
=
= ≤ ≤ −∑ 
1
0
1[ ] [ ] ,0 1
N
kn
N
k
x n X k W n N
N
− −
=
= ≤ ≤ −∑ 
where 
2
Nj
NW e
π−= . 
Aperiodic 
in Time, 
= 
Continuous 
in 
Frequency 
Fourier Transform (FT): 
( ) ( )
( ) ( )
j t
j t
X x t e dt
x t X e dt
ω
ω
ω
ω
∞ −
−∞
∞ −
−∞
=
=
∫
∫
Discrete-Time Fourier 
Transform (DTFT): 
( ) [ ] j n
n
X x n e
∞ − Ω
=−∞
Ω = ∑ 
2
1[ ] ( )
2
j nx n X e dππ
Ω= Ω Ω∫ 
Chương V 
- 112 - 
Phụ lục 2 
Some Fourier Relationships 
The Fourier transform is the Laplace transform evaluated on the j∞ axis. 
( ) ( ) ( ) ( )j t st
s j
s j
X x t e dt X s x t e dtω ω ω
ω ∞ ∞− −=−∞ −∞ =
⎡ ⎤= = = ⎢ ⎥⎣ ⎦∫ ∫ 
The discrete-time Fourier transform is the z-transform evaluated around the unit circle. 
( ) [ ] ( ) [ ]j
j
j n n
z e
n n z e
X x n e X z x n xΩ
Ω
∞ ∞− Ω −
==−∞ =−∞ =
⎡ ⎤Ω = = = ⎢ ⎥⎣ ⎦∑ ∑ 
Discrete-time periodic signals can also be described by a Fourier Series expansion: 
0[ ] synthesis equationjk nk
k N
x n a e Ω
∈
= ∑ 
and 
0
1 [ ] analysis equationjk nk
n N
a x n e
N
− Ω
∈
= ∑ 
then using the DTFT of the impulse train, ( )P Ω that we previously found, the DTFT of an 
arbitrary discrete-time periodic signal can be found from 0 ( )X Ω the DTFT of one 
period 0[ ]x n 
0
2 2( ) ( ) ( )
k
kX X
N N
π πδ⎛ ⎞Ω = Ω Ω−⎜ ⎟⎝ ⎠∑ 
0
2 2 2( ) ( )
k
k kX
N N N
π π πδ= Ω−∑ 
The DFT is simply a scaled version of the terms of one period of the discrete time Fourier 
transform for a periodic sequence: 
1
0
0
2[ ] ( ) [ ] ,0 1
N
kn
N
n
kX k X x n W k N
N
π −
=
= = ≤ ≤ −∑ 
for 2 0 1 1kN k  NπΩ = , = , , , − , i.e. only look at the N distinct sampled frequencies of 0 ( )X Ω . 
Also important, the orthogonality of exponentials: 
1
0
[ ]
N
kn
N
n
W N kδ−
=
=∑ 
where 
2
Nj
NW e
π−= .