Bài giảng Xử lý số tín hiệu (Digital Signal Processing ) - Chương 8: Biến đổi DFT và FFT

Xử lý số tín hiệuChương 8: Biến đổi DFT và FFTCác phép biến đổi FourierMiền thời gian Miền tần sốPeriodic (period T)Discrete ContinuousFTAperiodicFSContinuousDiscreteDiscreteDFSPeriodic (period T)ContinuousDTFTAperiodic DiscreteDFTChuỗi Fourier (Fourier series-FS)Tín hiệu x(t) tuần hoàn, chu kỳ Tp , tần số F0 = 1/TpX(f)f-TpTp0x(t)τtF0-F0Biến đổi Fourier (Fourier transform-FT)Tín hiệu x(t) không tuần hoànX(ω)ω2π/τ-2π/τx(t)-τ/2tτ/2Biến đổi Fourier của một số tín hiệu cơ bảnBiến đổi Fourier thời gian rời rạcDiscrete – Time Fourier Transform (DTFT)Tín hiệu x(n) rời rạc, không tuần hoànChuỗi Fourier rời rạcDiscrete Fourier Sequence (DFS)Tín hiệu x(n) rời rạc, tuần hoàn với chu kỳ NBiế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(ω)0L-1nx(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ỳ N0Nxp(n)N-1nL-1nxp(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)0Nxp(n)N-1nL-1n|Xp(k)|k0N-NXp(k) tuần hoàn chu kỳ N  Đặt X(k) = Xp(k), k = 0,..,N-1Biến đổi Fourier rời rạc Discrete Fourier Transform (DFT)|X(k)|k0N-10L-1nx(n)DFTCô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)IDFTDFTTí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ác4N2 phép nhân thực4N(N-1) phép cộng thựcGiải thuật biến đổi Fourier nhanhFast 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 nhanhFast 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 nhanhFast Fourier Transform (FFT)x(0)x(1)X(0)X(1)-11 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 gianFFT N/2 điểmg(0)g(N/2 -1)g(1)G(0)G(N/2 -1)G(1)FFT N/2 điểmh(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 -1X(N/2)X(N/2 + 1)k = N/2  N - 1X(N – 1)Chi phí tính toánSo với tính trực tiếp: chi phí tính toán thấp hơnDFT  N2FFT  N log2NVí 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 - timeSố thứ tựDạng nhị phânĐảo bitn0000000010011004201001023011110641000011510110156110011371111117Số thứ tựDạng nhị phânĐảo bit00000001001100201001030111104100001510110161100117111111Số thứ tựDạng nhị phân00001001201030114100510161107111Số thứ tự01234567Ví 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ố