HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA QUỐC TẾ VÀ SAU ĐẠI HỌC

TIỂU LUẬN XỬ LÝ TÍN HIỆU SỐ NÂNG CAO
BIẾN ĐỔI FOURIER NHANH
Giảng viên: TS. Nguyễn Ngọc Minh
Nhóm 10 : 1. Nguyễn Xuân Đức
2. Vương Bảo Trung
3. Hà Minh Phú
4. Trần Bích Phương
Lớp : M12CQDT02-B
Hà Nội-Tháng 4/2013
1
MỤC LỤC
2
BIẾN ĐỔI FOURIER NHANH
1. Mở đầu
Lợi ích của xử lý số tín hiệu càng ngày càng được khẳng định rõ ràng. Nó được ứng
dụng ở nhiều dạng ngày càng khác nhau với những hiệu quả to lớn đặc biệt trong các lĩnh
vực thông tin, truyền dẫn, nhận dạng,… Ngày nay xử lý tín hiệu đã trở thành một ngành
khoa học chứ không phải là một môn học. Với mức độ phát triển ngày càng cao về cơ
bản, về các phương pháp và về khả năng ứng dụng nó đã lôi cuốn được các kỹ sư, các nhà
vật lý cũng như các nhà toán học dồn hết tâm lực để nghiên cứu nó.
Trong lĩnh vực xử lý số tín hiệu, biển đổi Fourier chiếm một vị trí hàng đầu nhờ sự tồn
tại các thuật toán hiệu quả biến đổi Fourier rời rạc đóng một vai trò rất quan trọng trong
xử lý số tín hiệu.
Từ khi Cooley phát hiện ra thuật toán tính nhanh biến đổi Fourier rời rạc vào năm
1965 (người ta quen gọi là biến đổi Fourier, tiếng Anh là Fast Fourier Transform viết tắt
là FFT), các thuật toán này càng ngày càng khẳng định vai trò của mình trong xử lý số tín
hiệu.
Tầm quan trọng của FFT là rất lớn vì những lý do sau đây:




2.1
3
1
0
1
( ) 0 1
0
( ) D [X(k)]=
N
kn
N
k
X k W n N
N
x n I FT
−
−
=
≤ ≤ −

∑

=



2.2

* *
0
. ( ) ( )
N
kn
N
k
N x n X k W
−
=
=
∑
2.4
So sánh hai biểu thức (1.1) và (1.3) thấy rằng chúng gần như giống nhau. Như thế
ta có thể thấy rằng các thuật toán FFT được sử dụng cho cả biến đổi Fourier rời rạc thuận.
Sau đây chúng ta tiến hành nghiên cứu hiệu quả của cách tính trực tiếp DFT thuận thông
qua việc tính số lượng phép nhân và cộng phức và thực.
- Tính toán số lượng phép nhân và cộng phức
Nhìn vào biểu thức (10.2.1.1) ta thấy ngay rằng đối với mỗi giá trị của k, cách tính
trực tiếp DFT phải thực hiện N phép nhân phức và N - 1 phép cộng phức. Nhưng k lấy N
giá trị từ 0 đến N – 1:
X(0), X(1),…,X(N-1)
Vậy cách tính trực tiếp DFT phải thực hiện: N
2
phép nhân phức và N(N-1) phép cộng
phức (khi
- Tính toán số lượng phép nhân và cộng số thực
Tổng quát ta thấy rằng x(n) là phức và là phức
Vậy ta có thể viết DFT như sau:
4

'' '' '' ''
' '' '' '' ''
( )
' *
1
( )
kn N k n N k n
N N N N
k n k n k n
N N N
W W W W
W W W
− −
−
= = =
= =
2.7
Nhận xét:
- Tất cả các thuật toán tính nhanh DFT đều dựa trên cùng một nguyên tắc là phân
việc tính toán DFT của một dãy có chiều dài N thành nhiều DFT có chiều dài nhỏ
hơn bằng cách khai thác các tính chất đối xứng và tính chất tuần hoàn của hàm mũ
phức .
- Việc đưa nguyên tắc này vào tính DFT sẽ dẫn đến một số phương pháp khác nhau
mà hiệu quả của các phương pháp đó có thể so sánh với nhau được.
5
3. Biến đổi Fourier nhanh phân thời gian (FFT)
3.1 Định nghĩa
Thuật toán tính nhanh biến đổi Fourier rời rạc dựa trên việc phân dãy x(n) thành
các dãy con có chiều dài ngắn hơn được gọi là thuật toán biến đổi Fourier nhanh phân
thời gian. Để minh họa thuật toán này trước hết chúng ta nghiên cứu trường hợp đặc biệt

Hoặc ta có thể viết:
2.11
Ở đây:
- là biến đổi Fourier rời rạc có chiều dài
- là biến đổi Fourier rời rạc có chiều dài
Và:
- là biến đổi Fourier rời rạc của các mẫu lẻ của x(n)
- là biến đổi Fourier rời rạc của các mẫu chẵn của x(n)
Nhận xét
+ Như vậy các phép toán được tiến hành với và chỉ trong khoảng , tức là:
7
2.12
+ Như thế thực chất ta đã phân một DFT có chiều dài N thành hai DFT có chiều dài . Để
thuận lợi cho việc theo dõi ta có ký hiệu sau đây:
(DFT)
N
: là biến đổi Fourier rời rạc có chiều dài N.
(DFT)
N
: là biến đổi Fourier rời rạc có chiều dài
Ví dụ 1
Giả sử cho chiều dài cửa DFT N = 8, hãy trình bày thuật toán FFT phân thời gian để phân
đôi DFT này. Sau đó dùng đồ hình có hướng để minh họa thuật toán này cho rõ ràng hơn.
Giải
Áp dụng biểu thức (2.10) trong trường hợp N = 8 chúng ta có thể viết:
8
Chú ý rằng nếu thay các giá trị của k từ 0 đến 7 vào biểu thức (2.10) ta sẽ thấy xuất
hiện các giá trị G(4)
4
, G(5)

. Chúng ta đã biết rằng để tính toán N mẫu của x(k)
N
đòi hỏi số lượng
các phép toán có N
2
phép tính phức (tức là có N
2
phép nhân phức và N
2
phép cộng
phức).Như vậy để tính chúng ta phải đòi hỏi phép nhân phức và phép cộng phức. Để tính
toán , tương tự chúng ta cũng phải đòi hỏi phép tính phức. Để kết hợp và , theo biểu thức
(10.3.2.1), chúng ta phải thực hiện phép toán nhân phức (k chạy từ 0 đến N-1), tức là
chúng ta cần phải thực hiện N phép nhân phức. Ngoài ra chúng ta còn cần phải thực hiện
phép toán: , tức là đòi hỏi N phép cộng phức. Tóm lại để tính toán x(k)
N
bằng cách phân
thành và , theo biểu thức (2.10) chúng ta cần số lượng các phép tính phức như sau:
- phép phân thức
- phép cộng phức
Cuối cùng ta có thể nói rằng để tính toán N mẫu của x(k)
N
thì số lượng phép tính phức cần
thực hiện là phép.
Ví dụ 2
Hãy tính hiệu quả của FFT với N = 8. Khi phân (DFT)
8
thành hai (DFT)
4.
Giải

8
bằng cách phân x(n)
8
thành hai dãy g(r)
4
và h(r)
4
.
Giải
Ta biết rằng: g(r) = x(2r)
h(r) = x(2r + 1)
11
Vậy từ hình 2 ta có dạng của g(r) và h(r) cho trên hình 3 như sau:
Hình 3:
Từ đây ta tính được được G(r)
4
và H(k)
4
như sau:
12
Từ đây ta tính được X(k)
8
như sau:
2.13
Vậy ta có giá trị của X(k)
8
như sau:
13
Đồ thị của ; , và được cho trên hình sau
14

, sau đó kết hợp để thành thủ tục tính X(k)
8
.
Giải
Thuật toán tính G(h)
4
và H(k)
4
được minh họa ở hình 5 thông qua graphe có hướng dạng
cánh bướm.
17
Hình 5:
Bằng cách tương tự chúng ta lại tiếp tục phân các dãy a(l)
N
; b(l)
N
; c(l)
N
và thànhcác dãy
có chiều dài là ,…, và quá trình cứ thế tiếp tục cho đến khi nào chỉ còn tính DFT hai
điểm.
Ví dụ 5
Chúng ta quay lại ví dụ 4 với DFT có chiều dài N = 8.
Hãy dùng graphe có hướng dạng cánh bướm để minh họa thuật toán tính A(k)
2
, B(k)
2
,
C(k)
2

và D(k)
2
rồi đến
G(k)
4
và H(k)
4
chúng ta thu được kết quả cuối cùng của toàn bộ thuật toán tính X(k)
8
được minh họa bằng graphe có hướng dạng cánh bướm được cho trên hình 6.
b. Tính toán hiệu quả
19
Trong phần trên chúng ta biết rằng nếu chúng ta tính toán trực tiếp dãy X(k)
N
theo định
nghĩa của DFT thì để tính toán tất cả N điểm của DFT chúng ta cần phải đòi hỏi số phép
tính cỡ N
2
. Còn nếu chúng ta thực hiện tính DFT gián tiếp theo thuật toán FFT thì chúng
ta sẽ thu được hiệu quả rất cao, cụ thể chúng ta sẽ đánh giá hiệu quả theo số phép tính cần
phải thực hiện để tính N điểm của X(k)
8
.
Bước đầu tiên chúng ta phân DFT
N
thành , khi đó số phép tính (nhân hoặc cộng) đòi hỏi
phải thực hiện là:
2.24
Bước thứ hai chúng ta phân mỗi thành hai , khi đó số phép tính đòi hỏi phải thực hiện là:
2.25

Giải
+ Tính trực tiếp: Số phép tính cần phải thực hiện là:
+ Tính gián tiếp qua thuật toán FFT:
- Giai đoạn thứ nhất: Số phép tính cần phải thực hiện là:
- Giai đoạn hai: số phép tính cần phải thực hiện là:
- Giai đoạn thứ ba: là giai đoạn cuối cùng nên khi phân DFT
2
thành hai DFT
1
, mà ta
lại không cần phải tính DFT
1
vậy số phép tính cần phải thực hiện là:
c. Cải thiện thuật toán
Chúng ta chú ý rằng theo thuật toán mà ta đã trình bày và nhất là theo hình 6 thì cứ
mỗi một giai đoạn tính toán chúng ta lại có cùng một thuật toán dạng cánh bướm. Giả sử
chúng ta có hai giai đoạn tính toán kế tiếp nhau i và (i+1), thuật toán cánh bướm của các
giai đoạn này được minh họa trên hình 8:
21
Hình 8:
Theo hình 6, ta thấy rằng giữa hai giai đoạn i và (i+1) chúng ta có thể viết như sau:
2.30
Nhưng ta có:
2.31
Vậy ta có thể viết lại biểu thức (10.3.2.9) dưới dạng khác sau đây:
2.32
Như vậy theo biểu thức (2.32) ở trên chúng ta có thể cải thiện thuật toán cánh bướm cho
trên hình 10.3.2.10 để mô tả hai giai đoạn tính toán kế tiếp nhau i và (i+1). Việc cải thiện
này được minh họa trên hình 8.
Nhận xét:

N
theo mã nhị phân đảo và dãy x(k)
N
theo
mã nhị phân bình thường trong trường hợp N = 8.
Giải
Vì N = 8 = 2
3
, vậy ta phải dùng 3 bit để mã hóa.
Bảng 10.3.2.1 sẽ mô tả mã nhị phân đảo và mã nhị phân bình thường dùng để sắp xếp thứ
tự của dãy x(n)
N
và x(k)
N
.
3.3. Các dạng khác của thuật toán
Sau đây chúng ta sẽ trình bày một số thuật toán là biến dạng của thuật toán FFT phân thời
gian.
a. Thuật toán Cooley
Ở đây Cooley đã sử các khái niệm đại số nhị phân để biểu diễn các dãy x(n)
N
và x(k)
N
.
Như vậy về mặt bản chất của thuật toán không khác gì thuật toán FFT phân thời gian đã
được trình bày ở mục trên.
Chúng ta cũng xét trường hợp . Vậy chúng ta có thể biểu diễn n và k theo mã nhị phân và
thập phân như sau:
Biểu diễn số n:
Biểu diễn số k:

Nếu thì chúng ta có thể phân dãy x(n)
N
thành B dãy có chiều dài là , tức là thành các dãy
như sau:
3.1
Vậy ta có thể viết x(n) dưới dạng sau đây:
3.2
và X(k)
N
có thể viết như sau:
24
3.3
3.4
Thay x
i
(n) vào và đổi biến số ta có:
Đặt:
3.5
Và trong miền k ta cũng đặt:
25