Bài tập Xử lý tín hiệu số, Chương 8

Chia sẻ: Minh Anh | Ngày: | Loại File: PDF | Số trang:26

0
406
lượt xem
209
download

Bài tập Xử lý tín hiệu số, Chương 8

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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, chiều dài L hữu hạn Biến đổi DTFT cho phổ liên tục X(ω). xp(n) tuần hoàn chu kỳ N Tính DFS của xp(n) Xp(k Công thức biến đổi DFT N-điểm cho chuỗi chiều dài L Giải thuật biến đổi Fourier nhanh Fast Fourier Transform (FFT)

Chủ đề:
Lưu

Nội dung Text: Bài tập Xử lý tín hiệu số, Chương 8

  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 2.5 Miền thời gian Miền tần số 2 1.5 1 T 1 Periodic c k    s(t)  e  j k ω t dt 0.5 FS Discrete 0 0 1 2 3 4 5 6 7 8 time, t T (period T) 0 2.5 Continuous  j2 π f t  S(f)   s(t)  e 2 1.5 1 Aperiodic FT Continuous  dt 0.5 0 0 2 4 6 8 10 12 time, t N1 2πkn j 2.5 ~ 1  N 2 ck s[n]  e Periodic DFS Discrete 1.5 1 N 0.5 n 0 0 0 1 2 3 time, tk 4 5 6 7 8 (period T)  Discrete S(f)   s[n]  e j 2 π f n DTFT Continuous n  2.5 2 Aperiodic 2πkn 1.5 N1 j 1 DFT ~ 1  s[n]  e 0.5 ck N Discrete 0 time, tk 0 2 4 6 8 10 12 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  x (t )  c k   k e j 2  kF 0 t 1 ck  Tp  Tp x ( t ) e  j 2  kF 0 t dt X(f) x(t) τ f 0 Tp t -F0 F0 -Tp
  4. Biến đổi Fourier (Fourier transform-FT)  Tín hiệu x(t) không tuần hoàn   X F e j 2  ft x (t )  df   X f   x t e  j 2  ft dt  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  e j n x(n)  d 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 x(n)  c k 0 k e j 2  kn / N N 1 1 ck   x n e  j 2  kn / N 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  j 2kn / N , k  0,1,2,..., N  1 n 0 N 1 1 IDFT xn    X k e j 2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: • 2N2 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)  j 2 / N  Đặt WN  e N 1  X k    x(n)WN nk n 0 kN /2  Tính đối xứng: W M  W k N kN  Tính tuần hoàn: W M W k N
  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): X (0)  x(0)W  x(1)W  x(0)  x(1) 2 0 2 0 X (1)  x(0)W  x(1)W  x(0)  x(1) 2 0 2 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 H ( k ) N k , k  0,1,...,  1 2 N N k N N X ( k )  G ( k  ) W N H ( k  ) 2 , k  ,..., N  1 2 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 WN k =0 FFT N/2  điểm N/2 -1 g(N/2 -1) G(N/2 -1) N / 2 1 X(N/2-1) W N h(0) H(0)  WN 0 X(N/2) h(1) H(1)  WN 1 X(N/2 + 1) k = N/2 FFT N/2  điểm N-1 h(N/2 -1) H(N/2 -1)  WNN / 21 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 Number of Operations 1500 DFT  N2 1000 FFT  N log2N 500 0 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
Đồng bộ tài khoản