›
›

Bài giảng Xử lý tín hiệu số - Chương 5: Biến đổi Fourier rời rạc (DFT) - Đinh Đức Anh Vũ

pdf 32 trang ngocly 60
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Xử lý tín hiệu số - Chương 5: Biến đổi Fourier rời rạc (DFT) - Đinh Đức Anh Vũ", để 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:

  • pdfbai_giang_xu_ly_tin_hieu_so_chuong_5_bien_doi_fourier_roi_ra.pdf

Nội dung text: Bài giảng Xử lý tín hiệu số - Chương 5: Biến đổi Fourier rời rạc (DFT) - Đinh Đức Anh Vũ

  1. dce 2011 Chương 5 Biến đổi Fourier rời rạc (DFT) BK TP.HCM ©2011, TS. Đinh Đức Anh Vũ
  2. dce 2011 Giới thiệu về DFT • Biến đổi Fourier liên tục x(n) = 0.8nu(n) x(n) Miền thời gian F Miền tần số ∞ X (ω) = ∑ x(n)e− jωn n=−∞ • Vấn đề: X(ω) liên tục theo tần số ω → khơng thích hợp cho việc tính tốn trên máy tính DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 2
  3. dce 2011 Lấy mẫu miền tần số X(ω) Lấy mẫu N=10 N=10 2π X (k) ≡ X (ω = N k) DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 3
  4. dce 2011 Lấy mẫu miền tần số ∞ ω = 2π = − j2πkn/ N = − X ( ) ω =2πk / N X ( N k) ∑ x(n)e k 0,1, , N 1 n=−∞ −1 N −1 2N −1 − j 2π kn − j 2π kn − j 2π kn X (k) = + ∑ x(n)e N + ∑ x(n)e N + ∑ x(n)e N + n=−N n=0 n=N ∞ lN +N −1 − j 2π kn = ∑ ∑ x(n)e N l=−∞ n=lN N −1 ∞   − j 2π kn = ∑  ∑ x(n − lN)e N Thay n bằng (n-lN) n=0 l=−∞  N −1 ∞ − j 2π kn N x (n) = x(n − lN) ⇒ X (k) = ∑ x p (n)e với p ∑ n=0 l=−∞ • T/h xp(n) – lặp chu kỳ của x(n) mỗi N mẫu – t/h tuần hồn với chu kỳ cơ bản N N −1 j2πkn/ N x p (n) = ∑ck e n = 0,1, , N −1 k =0 N −1 1 − j2πkn/ N ck = ∑ x p (n)e k = 0,1, , N −1 N n=0 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 4
  5. dce 2011 Lấy mẫu miền tần số 1 c = X (k) k = 0,1,, N −1 k N N −1 2π 1 j N kn x p (n) = ∑ X (k)e n = 0,1,, N −1 N k =0 • Cĩ thể phục hồi t/h xp(n) từ các mẫu của phổ X(ω) x(n) x p (n) 0 ≤ n ≤ N −1 n x(n) =  0 L 0 others N>L xp(n) n 0 L N N<L xp(n) alias Khi N≥L, x(n) cĩ thể được khơi phục n từ các mẫu phổ tần số tại ωk=2πk/N 0 N DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 5
  6. dce 2011 Lấy mẫu miền tần số • Cĩ thể phục hồi X(ω) từ các mẫu X(k) với k = 0, 1, , N-1 – Giả sử N ≥ L → x(n) = xp(n) khi 0 ≤ n ≤ N-1 1 N −1 x(n) = ∑ X (k)e j2πkn/ N N k =0 ∞ N −1 N −1 − jωn  1 j2πkn/ N  − jωn X (ω) = ∑ x(n)e = ∑  ∑ X (k)e e n=−∞ n=0  N k =0  N −1 N −1  1 − j(ω −2πk / N )n  = ∑ X (k) ∑e  k =0  N n=0  1 N −1 1 1− e− jωN ω = − jωn = P( ) ∑e − jω N = N 1− e n 0 N −1 sin(ωN / 2) X (ω) = X (k)P(ω − 2π k) N ≥ L = e− jω (N −1)/ 2 ∑ N N sin(ω / 2) k =0 = 2π 1 k 0 P( N k) =  0 k =1,2,, N −1 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 6
  7. dce 2011 Lấy mẫu miền tần số N −1 1 j 2π kn x(n) x(n) = ∑ X (k)e N cĩ chiều dài L≤N N k =0 BĐ F ∞ N −1 − jωn X (ω) = ∑ x(n)e X (ω) = ∑ X (k)P(ω −ωk ) n=−∞ k =0 L N −1 ấy mẫu 1 − jωn ω = 2π P(ω) = ∑e k N k N k =0 N −1 − 2π j N kn X (k) = ∑ x(n)e Phục hồi Phục hồi n=0 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 7
  8. dce 2011 Lấy mẫu miền tần số • Ví dụ: x(n) = anu(n), 0<a<1 – Phổ t/h được lấy mẫu tại các tần số ωk = 2πk/N, k=0, 1, , N-1 ∞ 1 2πk 1 ω = n − jωn = X (k) = X ( ) = X ( ) ∑ a e − jω − j2πk / N n=0 1− ae N 1− ae ∞ x p (n) = ∑ x(n − lN) l=−∞ a=0.8 0 an = n−lN = ∑ a N l=−∞ 1− a DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 8
  9. dce 2011 Biến đổi Fourier rời rạc (DFT) • Chuỗi khơng tuần hồn, năng lượng hữu hạn x(n) • Các mẫu tần số X(2πk/N), k = 0, 1, , N-1 khơng đặc trưng cho x(n) khi x(n) cĩ chiều dài vơ hạn • Nĩ đặc trưng cho chuỗi tuần hồn, chu kỳ N xp(n) • xp(n) là lặp tuần hồn của x(n) nếu x(n) cĩ chiều dài hữu hạn L ≤ N • Do đĩ, các mẫu tần số X(2πk/N), k = 0, 1, , N-1 đặc trưng cho chuỗi chiều dài hữu hạn x(n); i.e. X(n) cĩ thể được phục hồi từ các mẫu tần số {X(2πk/N)} • x(n) = xp(n) trên một chu kỳ N (được đệm vào N-L zero). Mặc dù L mẫu của X(ω) cĩ thể tái tạo lại được X(ω), nhưng việc đệm vào N-L zero giúp việc tính tốn DFT N điểm của X(ω) đồng nhất hơn DFT IDFT N −1 N −1 − j 2π kn 1 j 2π kn X (k) = ∑ x(n)e N x(n) = ∑ X (k)e N n=0 N k =0 k = 0,1,, N −1 n = 0,1,, N −1 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 9
  10. dce 2011 Biến đổi Fourier rời rạc (DFT) • Ví dụ: xác định DFT N điểm của chuỗi x(n) cĩ độ dài L hữu hạn (N≥L) ∞ L−1 1 0 ≤ n ≤ L −1 − jωn − jωn x(n) =  X (ω) = ∑ x(n)e = ∑e 0 others n=−∞ n=0 1− e− jωL sin(ωL / 2) = = e− jω (L−1)/ 2 1− e− jω sin(ω / 2) DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 10
  11. dce 2011 Biến đổi Fourier rời rạc (DFT) DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 11
  12. dce 2011 DFT – BĐ tuyến tính DFT IDFT N −1 N −1 − j 2π kn 1 j 2π kn X (k) = ∑ x(n)e N x(n) = ∑ X (k)e N n=0 N k =0 k = 0,1,, N −1 n = 0,1,, N −1 − jN2/π WeN = Nghiệm thứ N của đơn vị N −1 N −1 kn 1 −kn X (k) = ∑ x(n)WN x(n) = ∑ X (k)WN n=0 N n=0 k = 0,1,, N −1 n = 0,1,, N −1 Tính DFT một điểm Tính DFT N điểm - Nhân phức: N - Nhân phức: N2 - Cộng phức: N-1 - Cộng phức: N(N-1) DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 12
  13. dce 2011 DFT – BĐ tuyến tính  x(0)   X (0)       x(1)  Các mẫu miền  X (1)  Các mẫu miền xN = X N =    thời gian    tần số     x(N −1) X (N −1)  1 1 1  1    2  N −1  1 WN WN WN  Ma trận W =  1 W 2 W 4  W 2(N −1)  N  N N N  BĐ tuyến tính        N −1 2(N −1) (N −1)(N −1)   1 WN WN  WN  • BĐ DFT N điểm X N = WN xN −1 −1 1 * xN = WN X N WN = WN N WN là ma trận = 1 * * xN N WN X N WNWN = NI N đường chéo DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 13
  14. dce 2011 DFT – BĐ tuyến tính • Ví dụ: xác định DFT 4 điểm của chuỗi x(n) = {0 1 2 3} k + N 2 = − k 0 0 0 0 WWNNW4 W4 W4 W4  1 1 1 1  1 1 1 1     1 2 1    W 0 W 1 W 2 W 3 1 W W −W 1 − j −1 j W =  4 4 4 4  =  4 4 4  =   4 W 0 W 2 W 4 W 6  1 W 2 −W 2 W 2  1 −1 1 −1  4 4 4 4   4 4 4    0 3 6 9 − 1 2 1 W4 W4 W4 W4  1 W4 W4 W4  1 j −1 − j 0  6      − 2 + 2 j 1   x = X 4 = W4 x4 = 4 2  − 2      3 − 2 − 2 j • Ví dụ: tính DFT 4 điểm cho x(n) = {1 0 2 1} 3 − j 2π kn − π − j 3π k X (k) = ∑ x(n)e 4 =1+ 2e j k + e 2 n=0  4  X (0) =1+ 2 +1 = 4  j 3π  2e 4  j 3π   4 X = W x = X (1) =1− 2 + j = −1+ j = 2e 4 4 4    2  − j 3π  X (2) =1+ 2 −1 = 2 4   2e   − j 3π X (3) =1− 2 − j = −1− j = 2e 4 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 14
  15. dce 2011 DFT – Quan hệ với các phép BĐ khác • Với hệ số Fourier của chuỗi chu kỳ Chuỗi xp(n) tuần hồn chu kỳ N DFT N điểm của chuỗi x(n) − N −1 N 1 π j 2π kn 1 j 2 kn N x(n) = X (k)e N x p (n) = ∑ck e ∑ k =0 N n=0 − ∞ ≤ n ≤ ∞ n = 0,1,, N −1 X(k) = Nck N −1 N −1 1 − j 2π kn − j 2π kn = N = N ck ∑ x p (n)e DFT N điểm cho chính xác X (k) ∑ x(n)e N n=0 n=0 phổ vạch của chuỗi k = 0,1,, N −1 k = 0,1,, N −1 tuần hồn chu kỳ N • Với BĐ Fourier của chuỗi khơng chu kỳ – DFT N điểm cho phổ vạch của chuỗi khơng chu kỳ x(n) nếu x(n) hữu hạn cĩ độ dài L ≤ N DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 15
  16. dce 2011 DFT – Biểu diễn tín hiệu Dạng thẳng Dạng vịng Chiều dương Âm Dương n n=1 -2 -1 0 1 2 n=0 x(n) = {1 2 3 4} n=–1 Chiều âm x(n) x(1) 4 3 2 x(2) x(n) x(0) 1 n 0 1 2 3 x(3) DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 16
  17. dce 2011 DFT – Biểu diễn tín hiệu theo vịng ∞ • Chuỗi tuần hồn chu kỳ N, mở rộng từ x(n) x p (n) = ∑ x(n − lN) n=−∞ ∞ ' = − = − − • Chuỗi dịch xp(n) đi k mẫu xp (n) x p (n k) ∑ x(n lN k) l=−∞ ' x p (n) 0 ≤ n ≤ N −1 • Chuỗi cĩ chiều dài hữu hạn từ x’p(n) x'(n) =  0 otherwise • Quan hệ giữa x(n) và x’(n): dịch vịng x’(n) = x(n-k, MOD N) ≡ x((n-k))N x(n) 4 x (n) 4 4 4 x (n-2) 4 4 4 3 p 3 3 3 p 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 0 1 2 3 -4 -3 -2 -1 0 1 2 3 4 5 6 7 -2 -1 0 1 2 3 4 5 6 7 8 9 x(1) x’(1) 4 x’(n) 2 4 3 2 x(2) 3 x(n) 1 x(0) x’(2) 1 x’(n) 3 x’(0) 1 0 1 2 3 4 2 x(3) x’(3) DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 17
  18. dce 2011 DFT – Tính đối xứng vịng • Phép dịch vịng của một chuỗi N điểm tương đương với phép dịch tuyến tính của chuỗi mở rộng tuần hồn của nĩ • Chuỗi N điểm là chẵn theo vịng nếu nĩ đối xứng qua điểm 0 trên vịng trịn – i.e. x(N – n) = x(n), 0 ≤ n ≤ N – 1 • Chuỗi N điểm là lẻ theo vịng nếu nĩ phản đối xứng qua điểm 0 trên vịng trịn – i.e. x(N – n) = – x(n), 0 ≤ n ≤ N – 1 • Đảo theo thời gian của chuỗi N điểm: đảo các mẫu của chuỗi quanh điểm 0 trên vịng trịn – i.e. x((– n))N = x(N – n), 0 ≤ n ≤ N – 1 – Phép đảo được thực hiện bằng cách vẽ x(n) theo chiều kim đồng hồ DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 18
  19. dce 2011 DFT – Tính đối xứng vịng • Giả sử x(n) và BĐ DFT X(k) là t/h phức – x(n) = xR(n) + jxI(n), 0≤n≤N–1 – X(k) = X (k) + jX (k), 0≤k≤N–1 R I − N −1 N 1   1 π π = 2πkn + 2πkn x (n) = [X (k)cos 2 kn − X (k)sin 2 kn ] X R (k) ∑[xR (n)cos N xI (n)sin N ]  R ∑ R N I N  n=0  N k =0   N −1 1 N −1 X (k) = − [x (n)sin 2πkn − x (n)cos 2πkn ] x (n) = [X (k)sin 2πkn + X (k)cos 2πkn ]  I ∑ R N I N  I ∑ R N I N  n=0  N k =0 • Nếu x(n) thực: X(N-k) = X*(k) = X(–k) X (N − k) = X (k) và ∠X (N − k) = −∠X (k) • Nếu x(n) thực và chẵn: x(n) = x(N–n) → XI(k) = 0 N −1 1 N −1 = 2πkn = 2πkn X (k) ∑ x(n)cos N x(n) ∑ X (k)cos N n=0 N k =0 • Nếu x(n) thực và lẻ: x(n) = –x(N–n) → XR(k) = 0 N −1 1 N −1 = − 2πkn = 2πkn X (k) j∑ x(n)sin N x(n) j ∑ X (k)sin N n=0 N k =0 • Nếu x(n) thuần ảo: x(n) = jxI(n) N −1 N −1 = 2πkn = 2πkn X R (k) ∑ xI (n)sin N X I (k) ∑ xI (n)cos N n=0 n=0 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 19
  20. dce 2011 DFT – Tính chất • Tuần hồn DFT x(n)←N → X (k) x(n) = x(n + N) ∀n ⇒  X (k) = X (k + N) ∀k • Tuyến tính DFTN x1(n)←→ X1(k)  DFTN x2 (n)←→ X 2 (k) DFTN ⇒ a1x1(n) + a2 x2 (n)←→a1 X1(k) + a2 X 2 (k) • Tổng chập vịng DFTN x1(n)←→ X1(k)  DFTN x2 (n)←→ X 2 (k) DFTN ⇒ x1(n) ⊗N x2 (n)←→ X1(k)X 2 (k) N Tổng chập vịng N điểm N −1 x1(n) ⊗N x2 (n) = ∑ x1(k)x2 ((n − k))N n = 0,1,, N −1 k =0 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 20
  21. dce 2011 DFT – Tổng chập vịng DFTN = x1(n)←→ X1(k) x(m) IDFT{X (k)}  N −1 DFTN 2π x (n)←→ X (k) 1 j N km  2 2 = ∑ X (k)e DFTN N k=0 x(m)←→ X (k) = X1(k)X 2 (k) N −1 2π 1 j N km = ∑ X1(k)X 2 (k)e N a = N k=0 N −1  1 k  N −1 N −1 N −1 a = N 1  − j 2π kn  − j 2π kl  j 2π km ∑ 1− a = x (n)e N x (l)e N e N k=0  a ≠ 1 ∑ ∑ 1 ∑ 2   1− a N k=0 n=0  l=0  N −1 N −1 N −1 2π 2π j N (m−n−l) 1 j k (m−n−l) Trong đó a = e N = ∑ x1(n)∑ x2 (l)∑e N = = = a =1,khi : m − n − l = pN, p∈ Z n 0 l 0 k 0 a ≠ 1⇒ aN = e j2π (m−n−l) =1⇒1− aN = 0 N −1 N m − n − l = pN ⇔ l = ((m − n)) ⇒ ak = N ∑  N −1 k=0 0 otherwise x(m) = ∑ x1(n)x2 ((m − n))N m = 0,1,, N −1 n=0 N −1 x(n) = ∑ x1(k)x2 ((n − k))N n = 0,1,, N −1 k =0 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 21
  22. dce 2011 DFT – Tổng chập vịng • Ví dụ: cho x1(n) ={1^ 2 3 4} và x2(n) ={1^ 0 2 1}. Tính x(n) = x1(n) N x2(n) theo 2 cách – Dùng cơng thức định nghĩa – Dùng DFT và IDFT x2(0) = 1 2 Dùng định nghĩa x2(3) = 1 x2((1-n))4 x2(1) = 0 3 x1(n)x2((1-n))4 0 N −1 x(m) = x (n)x ((m − n)) m = 0,1,, N −1 ∑ 1 2 N x2(2) = 2 x(1) = 13 8 n=0 x1(1) = 2 x2(1) = 0 x2(1) = 0 0 x1(2) = 3 x1(n) x1(0) = 1 x2(2) = 2 x2(n) x2(0) = 1 x2(0) = 1 x2((2-n))4 x2(2) = 2 3 x1(n)x2((2-n))4 2 x1(3) = 4 x2(3) = 1 x2(3) = 1 x(2) = 9 4 x2(3) = 1 2 x2(2) = 2 4 x2(2) = 2 x2((-n))4 x2(0) = 1 6 x1(n)x2((-n))4 1 x2(1) = 0 x2((3-n))4 x2(3) = 1 0 x1(n)x2((3-n))4 1 x2(1) = 0 x(0) = 9 0 x2(0) = 1 x(3) = 9 4 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 22
  23. dce 2011 DFT – Tổng chập vịng Dùng DFT & IDFT X (k) = X1(k)X 2 (k) 3 − j 2π kn − j π k − π − j 3π k 4 2 j k 2 k = 0,1,2,3 X1(k) = ∑ x1(n)e =1+ 2e + 3e + 4e n=0 X (0) = 40 k = 0,1,2,3  X (1) = (−2 + 2 j)(−1+ j) = −4 j = + + + =  X1(0) 1 2 3 4 10 = −  X (2) 4 X1(1) =1+ (−2 j) + (−3) + (4 j) = −2 + 2 j   X (3) = 4 j = + − + + + − = − X1(2) 1 ( 2) ( 3) ( 4) 2 3 1 j 2π kn  x(n) = X (k)e 4 X1(3) =1+ (2 j) + (−3) + (−4 j) = −2 − 2 j ∑ 4 k =0 3 − j 2π kn − jπk − j 3π k π 3π 4 2 1 j 2 n jπn j 2 n X 2 (k) = ∑ x2 (n)e =1+ 2e + e = [40 − 4 je − 4e + 4 je ] n=0 4 k = 0,1,2,3 n = 0,1,2,3 X 2 (0) =1+ 2 +1 = 4 x(0) = 9   = X 2 (1) =1+ (−2) + ( j) = −1+ j x(1) 13   x(2) = 9 X 2 (2) =1+ 2 −1 = 2    = X 2 (3) =1+ (−2) + (− j) = −1− j x(3) 9 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 23
  24. dce 2011 DFT – Tính chất • Đảo vịng theo thời gian x(n)←DFTN → X (k) DFTN ⇒ x((−n))N = x(N − n)←→ X ((−k))N = X (N − k) • Dịch vịng theo thời gian x(n)←DFTN → X (k) DFTN − j2πkl / N ⇒ x((n − l))N ←→ X (k)e • Dịch vịng theo tần số x(n)←DFTN → X (k) j2πnl / N DFTN ⇒ x(n)e ←→ X ((k − l))N • Liên hợp phức x(n)←DFTN → X (k) x* (n)←DFTN → X * ((−k)) = X * (N − k) ⇒ N  * * DFT * x ((−n))N = x (N − n)←N → X (k) DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 24
  25. dce 2011 DFT – Tính chất • Tương quan vịng x(n)←DFTN → X (k) y(n)←DFTN →Y(k) ~ N −1 ~ ~ * DFTN * với r xy (l) = x(n)y ((n − l))N ⇒ xy ←→ xy = ∑ r (l) R (k) X (k)Y (k) n=0 • Nhân 2 chuỗi DFTN x1(n)←→ X1(k)  DFTN x2 (n)←→ X 2 (k) DFTN 1 ⇒ x1(n)x2 (n)←→ N X1(k) ⊗N X 2 (k) • Định lý Parseval x(n)←DFTN → X (k) y(n)←DFTN →Y (k) N −1 N −1 ⇒ ∑ x(n)y* (n) = ∑ X (k)Y * (k) n=0 k =0 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 25
  26. dce 2011 DFT – Lọc tuyến tính • Y(ω) = H(ω)X(ω) – Hàm liên tục theo tần số ω – Khĩ thực hiện trên các máy tính số → DFT: một cách tính hiệu qủa của tổng chập miền thời gian • Lọc tuyến tính M −1 x(n) y(n) = − – Tín hiệu ngắn h(n) y(n) ∑ h(k)x(n k) k =0 x(n) chiều dài = L (n=0,1, ,L-1) y(n) chiều dài N = M+L-1 h(n) chiều dài = M (n=0,1, ,M-1) Số mẫu phổ (tần số) cần thiết để biểu diễn duy nhất chuỗi y(n) ≥ L+M-1 Y(k) = H(k)X(k), k=0,1, ,N-1 H(k), X(k): DFT N điểm của h(n), x(n) (các số 0 được đệm vào để tăng kích thước chuỗi lên N) y(n) = IDFTN{Y(k)} • Tổng chập vịng N điểm của h(n) và x(n) tương đương với tổng chập tuyến tính của h(n) với x(n) • DFT cĩ thể được dùng để lọc tuyến tính (bằng cách đệm thêm các số 0 vào chuỗi tương ứng) DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 26
  27. dce 2011 DFT – Lọc tuyến tính • Tĩm tắt DFTN x(n) X(k) IDFT Y(k) = X(k)H(k) N y(n) DFTN x h(n) H(k) • Ví dụ: tính đáp ứng y(n) dùng DFT và IDFT – h(n) = {1^, 0, 1, 2} và x(n) = {1^, 0, 1} 7  − j2πkn/8 − jπk / 2 − j3πk / 4 H (k) = ∑ h(n)e =1+ e + 2e  = n 0 (k = 0,1, ,7)  7 X (k) = x(n)e− j2πkn/8 =1+ e− jπk / 2  ∑ Y (0) = 8  n=0  = − H (0) = 4 X (0) = 2 Y (1) 2(1 j)   Y (2) = 0 H (1) = (1− 2) − (1+ 2) j X (1) =1− j    = Y (3) = 2( 2 + j) H (2) = 2 j X (2) 0    Y (4) = 0 H (3) = (1+ 2) + (1− 2) j X (3) =1+ j    Y (5) = 2( 2 − j) H (4) = 0 X (4) = 2  Y(6) = 0  = + + − X (5) =1− j H (5) (1 2) ( 2 1) j   Y(7) = 2(− 2 + j) H (6) = −2 j X (6) = 0 7   j2πkn/8 H (7) = (1− 2) + (1+ 2) j X (7) =1+ j y(n) = ∑Y (k)e (n = 0,1, ,7) DSP – Biến đổi DFT k =0©2011, Đinh Đức Anh Vũ 27
  28. dce 2011 DFT – Lọc tuyến tính • Tín hiệu nhập dài: chia nhỏ x(n) thành từng block cĩ độ dài cố định – Overlap-Save – Overlap-Add • Giả thiết – Bộ lọc cĩ h(n): chiều dài M – T/h nhập x(n): được chia nhỏ thành từng block cĩ chiều dài L >> M DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 28
  29. dce 2011 Lọc tuyến tính – Overlap-Save • DFTN và IDFTN với N = L+M–1 • Mỗi block dữ liệu được xử lý bao gồm (M – 1) điểm của block trước và L điểm mới của t/h nhập – M-1 điểm của block đầu tiên được set bằng 0 • Đáp ứng xung của bộ lọc được đệm thêm (L – 1) số 0 để tăng chiều dài lên N – DFT của N điểm của h(n) được tính một lần duy nhất Input Add M-1 zeros M-1 L L L x1(n) M-1 L x2(n) M-1 L x3(n) M-1 L Output M-1 L M-1 L Discard M-1 L DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 29
  30. dce 2011 Lọc tuyến tính – Overlap-Add • Đệm thêm (M-1) số 0 vào mỗi block dữ liệu đầu vào Input x1(n) L M-1 zeros x2(n) L M-1 x3(n) L M-1 Output L M-1 + L M-1 + L M-1 Phương pháp hiệu quả hơn dùng để xác định bộ lọc tuyến tính được trình bày trong chương 6 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 30
  31. dce 2011 DFT – Phân tích tần số • T/h ngắn – Tính DFT từ x(n) • T/h dài – Cửa sổ hố x(n): t/h cần phân tích Giới hạn chiều dài chuỗi một khoảng L mẫu Hàm cửa sổ cĩ chiều dài L ⇔ Nhân chuỗi với cửa sổ chiều dài L chỉ phân biệt được nếu các tần số cách nhau xw(n) = x(n)w(n) ít nhất một đoạn w(n): hàm cửa sổ 2π ∆ω = L Cửa sổ chữ nhật Cửa sổ Hanning 1 2π 1 0 ≤ n ≤ L −1  (1− cos − n) 0 ≤ n ≤ L −1 w(n) =  w(n) =  2 L 1 0 otherwise 0 otherwise DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 31
  32. dce 2011 DFT – Phân tích tần số • Ví dụ 1 0 ≤ n ≤ L −1 x(n) = cosω1n + cosω2n w(n) =  0 otherwise ^ 1 X (ω) = 2 [W (ω −ω1) +W (ω −ω2 ) +W (ω +ω1) +W (ω +ω2 )] ω1 = 0.2π L=25 L=50 ω2 = 0.22π Rị rỉ cơng suất L=75 L=100 DSP – Biến đổi DFT ©2011, Đinh Đức Anh Vũ 32