ET402 0 - Xử lý tín hiệu số
Chương 3: Các thuật toán FFT và ứng dụng
TS. Đặng Quang Hiếu

Trường Đại học Bách Khoa Hà Nội
Viện Điện tử - Viễn thông
Năm học 2012 - 2013
Outline
Ứng dụng của DFT
Các thuật toán FFT
Thực hiện hệ thống FIR
Xét hệ thống LTI với đáp ứng xung h(n) có chiều dài hữu hạn P.
Khi đầu vào x(n) chiều dài L, ta có:
y(n) = x(n) ∗ h(n ) = x(n)
N
(∗)
M
h(n )
N
trong đó N ≥ L + P − 1, các dãy x(n)
N
, h(n)
N
được chèn thêm 0
vào cuối.
x(n)
h(n)
y (n)
DFT
DFT
IDFT

(P − 1) điểm 0
x
1
(n)
đầu ra
y
1
(n)
x
2
(n)
y
2
(n)
x
3
(n)
y
3
(n)
Bỏ
Phân tích phổ của tín hiệu thời gian thực
Nguyên lý: Chia tín hiệu thành các đoạn (thường là chồng lên
nhau), thực hiện biến đổi FFT trên từng đoạn, với các loại cửa sổ
khác nhau.
Các bước thực hiện trên một đoạn dữ liệu:
1. Rời rạc hóa tín hiệu x(t) → x(n), xét trên một đoạn N mẫu
2. Nhân với hàm cửa sổ x
d
(n) = x(n)w(n)

◮
N phép nhân phức (4N phép nhân thực và 2N phép cộng
thực)
◮
N − 1 phép cộng phức (2N − 2 phép cộng thực)
◮
2N phép tính giá trị các hàm sin, cos.
Độ phức tạp tính toán của DFT - N điểm: O(N
2
).
DIT Radix - 2 FFT (phân chia theo thời gian, cơ số 2)
Xét N = 2
v
, chia x(n) thành hai dãy chỉ số chẵn x(2m) và chỉ số
lẻ x(2m + 1):
X (k) =
N−1

n=0
x(n)W
kn
N
, k = 0, 1, · · · , (N − 1)
=
N/2−1

m=0
x(2m)W
k2m
N

2
(k)
DIT Radix - 2 FFT: Độ phức tạp tính toán
Nhận xét:
F
1
(k + N/2) = F
1
(k)
F
2
(k + N/2) = F
2
(k)
W
k+N/2
N
= −W
k
N
do vậy,
X (k +
N
2
) = F
1
(k) − W
k
N
F

x(6)
x(1)
x(3)
x(5)
x(7)
F
1
(0)
F
1
(1)
F
1
(2)
F
1
(3)
F
2
(0)
F
2
(1)
F
2
(2)
F
2
(3)
DFT

X (2)
X (3)
X (4)
X (5)
X (6)
X (7)
x(0)
x(2)
x(4)
x(6)
x(1)
x(3)
x(5)
x(7)
DFT
N/2 - điểm
DFT
N/2 - điểm
−1
W
0
N
−1
W
1
N
−1
W
2
N

W
0
N
−1
W
1
N
−1
W
2
N
−1
W
3
N
−1
−1
W
0
N
W
2
N
−1
−1
W
0
N
W
2

−1
W
3
N
−1
−1
W
0
N
W
2
N
−1
−1
W
0
N
W
2
N
−1
W
0
N
−1
W
0
N
−1
W

X
m−1
(p)
X
m−1
(q)
X
m
(p)
X
m
(q)
Hình: Sơ đồ cánh bướm rút gọn
Tính toán tại chỗ và đảo bit
X
m
(p) = X
m−1
(p) + W
r
N
X
m−1
(q)
X
m
(q) = X
m−1
(p) − W
r

(7) 111 111 x(7)
DIF Radix-2 FFT (phân chia theo tần số, cơ số 2)
X (k) =
N−1

n=0
x(n)W
kn
N
, k = 0, 1, · · · , (N − 1)
=
N/2−1

m=0
x(n)W
kn
N
+
N−1

n=N/2
x(n)W
kn
N
=
N/2−1

m=0
x(n)W
kn

N/2−1

m=0
[x(n) − x(n + N/2)]W
n
N
W
kn
N/2
Độ phức tạp tính toán: (N/2) log
2
N phép nhân phức và N log
2
N
phép cộng phức.
−1
W
r
N
X
m−1
(p)
X
m−1
(q)
X
m
(p)
X
m

N
−1
W
3
N
−1
−1
W
0
N
W
2
N
−1
−1
W
0
N
W
2
N
−1
W
0
N
−1
W
0
N
−1