Bài giảng môn Xử lý số tín hiệu - 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ố