Xử lý số tín hiệu chương 8

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ỳ Tp , tần số F0 = 1/Tp

X(f)
f
F0
-F0
Biến đổi Fourier (Fourier transform-FT)
Tín hiệu x(t) không tuần hoàn
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(ω)
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 xp(n) tuần hoàn chu kỳ N
xp(n) tuần hoàn chu kỳ N  Tính DFS của xp(n)  Xp(k)
Biến đổi Fourier rời rạc
Discrete Fourier Transform (DFT)
Xp(k) tuần hoàn chu kỳ N  Đặt X(k) = Xp(k), k = 0,..,N-1
Biến đổi Fourier rời rạc
Discrete Fourier Transform (DFT)
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:
2N2 phép tính hàm lượng giác
4N2 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 ý: W2 = 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 = 2K
Đặ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
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
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
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ố