›
›

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

ppt 26 trang phuongnguyen 4160
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Xử lý số tín hiệu - Chương 8: Biến đổi DFT và FFT", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_xu_ly_so_tin_hieu_chuong_8_bien_doi_dft_va_fft.ppt

Nội dung text: Bài giảng Xử lý số tín hiệu - Chương 8: Biến đổi DFT và FFT

  1. Xử lý số tín hiệu Chương 8: Biến đổi DFT và FFT
  2. Các phép biến đổi Fourier Miền thời gian Miền tần số 2.5 2 1.5 1 T 0.5 1 −jk ω t 0 0 1 2 3 4 5 6 7 8 Periodic ck =  s(t)e dt time, t FS Discrete T (period T) 0 2.5 Continuous −j2 π f t 2 + 1.5 Aperiodic FT Continuous S(f) = s(t) e dt 1 − 0.5 0 0 2 4 6 8 10 12 time, t 2.5 N−1 2πkn 2 j ~ 1 − 1.5 c = s[n] e N 1 k Periodic DFS Discrete N  0.5 n=0 0 0 1 2 3 4 5 6 7 8 (period T) time, tk + Discrete S(f) = s[n] e−j2π f n 2.5 DTFT Continuous 2 n=− 1.5 Aperiodic 1 2πkn 0.5 1 N−1 −j 0 ~ N 0 2 4 6 8 10 12 DFT ck = s[n] e time, tk Discrete N  n=0
  3. 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 + j2 kF0t x(t) = ck e k=− 1 c = x(t)e− j2 kF0t dt k T p Tp X(f) x(t) τ f t 0 T -F0 F0 -Tp p
  4. Biến đổi Fourier (Fourier transform-FT) ⚫ Tín hiệu x(t) không tuần hoàn + x(t) = X (F )e j2 ftdf − + X ( f ) = x(t)e− j2 ftdt − X(ω) x(t) ω -τ/2 τ/2 t -2π/τ 2π/τ
  5. Biến đổi Fourier của một số tín hiệu cơ bản
  6. 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 1 x(n) = X ()e jnd 2 2 + X () =  x(n)e jn n=−
  7. 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 N −1 j2 kn / N x(n) = ck e k =0 N −1 1 − j2 kn / N ck =  x(n)e N n=0
  8. 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(ω) |X(ω)| x(n) 0 L-1 n -π π ω
  9. 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) 0 L-1 N-1 N n n
  10. Biến đổi Fourier rời rạc Discrete Fourier Transform (DFT) ⚫ xp(n) tuần hoàn chu kỳ N ➔ Tính DFS của xp(n) → Xp(k) xp(n) 0 L-1 N-1 N n n |Xp(k)| -N 0 N k
  11. 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 x(n) 0 L-1 n |X(k)| DFT 0 N-1 k
  12. Biến đổi Fourier rời rạc Discrete Fourier Transform (DFT) Công thức biến đổi DFT N-điểm cho chuỗi chiều dài L: DFT L−1 X (k) =  x(n)e− j2 kn / N , k = 0,1,2, , N −1 n=0 1 N −1 IDFT x(n) =  X (k)e j2 kn / N , n = 0,1,2, , N −1 N k=0
  13. Giải thuật biến đổi Fourier nhanh Fast Fourier Transform (FFT) ⚫ 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: N −1 2 kn 2 kn X R (k) =  xR (n)cos + xI (n)sin n=0 N N N −1 2 kn 2 kn X I (k) = − xR (n)sin − xI (n)cos n=0 N N Tính trực tiếp cần: 2 • 2N phép tính hàm lượng giác Chi phí tính • 4N2 phép nhân thực toán lớn • 4N(N-1) phép cộng thực
  14. Giải thuật biến đổi Fourier nhanh Fast Fourier Transform (FFT) − j2 / N ⚫ Đặt WN = e N −1 nk ➔ X (k) =  x(n)WN n=0 k+N / 2 k ⚫ Tính đối xứng: WM = −WN ⚫ Tính tuần hoàn: k+N k WM = WN
  15. 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): 0 0 X (0) = x(0)W2 + x(1)W2 = x(0) + x(1) 0 1 X (1) = x(0)W2 + x(1)W2 = x(0) − x(1) = (Lưu ý: W2 1) x(0) X(0) 1 Bướm (Butterfly) x(1) X(1) -1
  16. Giải thuật FFT phân chia theo thời gian (Decimation in time – DIT) ⚫ 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): N X (k) = G(k) +W kH (k) , k = 0,1, , −1 N 2 N N k− N N X (k) = G(k − ) −W 2 H(k − ) , k = , , N −1 2 N 2 2 ⚫ G(k), H(k) : DFT N/2 điểm của g(n), h(n)
  17. Giải thuật FFT phân chia theo thời gian g(0) G(0) X(0) 0 g(1) G(1) W N X(1) 1 k =0 FFT N/2 WN → điểm N/2 -1 g(N/2 -1) G(N/2 -1) X(N/2-1) N / 2−1 WN h(0) H(0) −W 0 N X(N/2) h(1) H(1) −W 1 N X(N/2 + 1) k = N/2 FFT N/2 → điểm N - 1 h(N/2 -1) H(N/2 -1) −W N / 2−1 N X(N – 1)
  18. 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 2000 1500 DFT  N2 1000 FFT  N log2N 500 0 Number Number of Operations 0 10 20 30 40 Number of samples, N
  19. Ví dụ ⚫ FFT 8 điểm phân chia theo thời gian
  20. Ví dụ ⚫ FFT 8 điểm phân chia theo thời gian
  21. Ví dụ ⚫ FFT 8 điểm phân chia theo thời gian
  22. Ví dụ ⚫ FFT 8 điểm phân chia theo thời gian
  23. 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
  24. Ví dụ ⚫ FFT 8 điểm phân chia theo tần số (Decimation in freq)
  25. Ví dụ ⚫ FFT 8 điểm phân chia theo tần số
  26. Ví dụ ⚫ FFT 8 điểm phân chia theo tần số