Bài giảng cung cấp cho người học các kiến thức: Biến đổi DFT và FFT, biến đổi Fourier, Biến đổi Fourier thời gian rời rạc Biến đổi Fourier thời gian rời rạc, giải thuật biến đổi Fourier nhanh,. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu. chi tiết nội dung tài liệu. | 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 -Tp Tp 0 x(t) τ t F0 -F0 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 xp(n) tuần hoàn chu kỳ N 0 N xp(n) N-1 n L-1 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) 0 N xp(n) N-1 n L-1 n |Xp(k)| k 0 N -N 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) |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: 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 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 N2 FFT N log2N 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ố
