Bài giảng Xử lý số - Chương 8: Biến đổi DFT và FFT

Xử lý số tín hiệu  
Chương 8: Biến đổi DFT và FFT 
Các phép biến đổi Fourier 
Miền thời gian	 Miền tần số 
Periodic (period T) 
Discrete 
Continuous 
FT 
Aperiodic 
FS 
Continuous 
Discrete 
Discrete 
DFS 
Periodic (period T) 
Continuous 
DTFT 
Aperiodic 
Discrete 
DFT 
Chuỗi Fourier (Fourier series-FS) 
Tín hiệu x(t) tuần hoàn, chu kỳ T p , tần số F 0 = 1/T p 
X(f) 
f 
-T p 
T p 
0 
x(t) 
τ 
t 
F 0 
-F 0 
Biến đổi Fourier (Fourier transform-FT) 
Tín hiệu x(t) không tuần hoàn 
X( ω ) 
ω 
2 π / τ 
-2 π / τ 
x(t) 
- τ /2 
t 
τ /2 
Biến đổi Fourier của một số tín hiệu cơ bản 
Biến đổi Fourier thời gian rời rạc Discrete – Time Fourier Transform (DTFT) 
Tín hiệu x(n) rời rạc, không tuần hoàn 
Chuỗi Fourier rời rạc Discrete Fourier Sequence (DFS) 
Tín hiệu x(n) rời rạc, tuần hoàn với chu kỳ N 
Biến đổi Fourier rời rạc  Discrete Fourier Transform (DFT) 
Tín hiệu x(n) rời rạc, không tuần hoàn, chiều dài L hữu hạn Biến đổi DTFT cho phổ liên tục X( ω ) 
0 
L-1 
n 
x(n) 
|X( ω )| 
ω 
- π 
π 
Biến đổi Fourier rời rạc  Discrete Fourier Transform (DFT) 
Lặp lại tín hiệu x(n) với chu kỳ N ≥ L Tín hiệu x p (n) tuần hoàn chu kỳ N 
0 
N 
x p (n) 
N-1 
n 
L-1 
n 
x p (n) tuần hoàn chu kỳ N Tính DFS của x p (n) X p (k) 
Biến đổi Fourier rời rạc  Discrete Fourier Transform (DFT) 
0 
N 
x p (n) 
N-1 
n 
L-1 
n 
|X p (k)| 
k 
0 
N 
-N 
X p (k) tuần hoàn chu kỳ N Đặt X(k) = X p (k), k = 0,..,N-1 
Biến đổi Fourier rời rạc  Discrete Fourier Transform (DFT) 
|X(k)| 
k 
0 
N-1 
0 
L-1 
n 
x(n) 
DFT 
Công thức biến đổi DFT N-điểm cho chuỗi chiều dài L: 
Biến đổi Fourier rời rạc  Discrete Fourier Transform (DFT) 
IDFT 
DFT 
Tính trực tiếp DFT N – điểm của x(n): 
 Tổng quát: X(k) và x(n) là số phức: 
Tính trực tiếp cần: 
 2N 2 phép tính hàm lượng giác 
4N 2 phép nhân thực 
4N(N-1) phép cộng thực 
Giải thuật biến đổi Fourier nhanh Fast Fourier Transform (FFT) 
Chi phí tính toán lớn 
Đặt 
Tính đối xứng: 
Tính tuần hoàn: 
Giải thuật biến đổi Fourier nhanh Fast Fourier Transform (FFT) 
Xét chuỗi x(n) = {x(0), x(1)} 
 FFT 2 điểm của x(n): 
(Lưu ý: W 2 = 1 ) 
Giải thuật biến đổi Fourier nhanh Fast Fourier Transform (FFT) 
x(0) 
x(1) 
X(0) 
X(1) 
-1 
1 Bướm 
(Butterfly) 
Xét chuỗi x(n) có chiều dài N = 2 K 
Đặt g(n) = x(2n) g(n) = {x(0), x(2),  } 
Đặt h(n) = x(2n + 1) h(n) = {x(1), x(3), } 
DFT N điểm của x(n): 
G(k), H(k) : DFT N/2 điểm của g(n), h(n) 
Giải thuật FFT phân chia theo thời gian (Decimation in time – DIT) 
Giải thuật FFT phân chia theo thời gian 
FFT N/2 điểm 
g(0) 
g(N/2 -1) 
g(1) 
G(0) 
G(N/2 -1) 
G(1) 
FFT N/2 điểm 
h(0) 
h(N/2 -1) 
h(1) 
H(0) 
H(N/2 -1) 
H(1) 
X(0) 
X(1) 
X(N/2-1) 
k =0 N/2 -1 
X(N/2) 
X(N/2 + 1) 
k = N/2 N - 1 
X(N – 1) 
Chi phí tính toán 
So với tính trực tiếp: chi phí tính toán thấp hơn 
DFT  N 2 
FFT  N log 2 N 
Ví dụ 
FFT 8 điểm phân chia theo thời gian 
Ví dụ 
FFT 8 điểm phân chia theo thời gian 
Ví dụ 
FFT 8 điểm phân chia theo thời gian 
Ví dụ 
FFT 8 điểm phân chia theo thời gian 
Ví dụ 
Thứ tự chuỗi x(n) trong pp Decimation – in - time 
Số thứ tự 
Dạng nhị phân 
Đảo bit 
n 
0 
000 
000 
0 
1 
001 
100 
4 
2 
010 
010 
2 
3 
011 
110 
6 
4 
100 
001 
1 
5 
101 
101 
5 
6 
110 
011 
3 
7 
111 
111 
7 
Số thứ tự 
Dạng nhị phân 
Đảo bit 
0 
000 
000 
1 
001 
100 
2 
010 
010 
3 
011 
110 
4 
100 
001 
5 
101 
101 
6 
110 
011 
7 
111 
111 
Số thứ tự 
Dạng nhị phân 
0 
000 
1 
001 
2 
010 
3 
011 
4 
100 
5 
101 
6 
110 
7 
111 
Số thứ tự 
0 
1 
2 
3 
4 
5 
6 
7 
Ví dụ 
FFT 8 điểm phân chia theo tần số (Decimation in freq) 
Ví dụ 
FFT 8 điểm phân chia theo tần số 
Ví dụ 
FFT 8 điểm phân chia theo tần số