Biến đổi fourier rời rạc (dft) - chương 5

Chia sẻ: Phan Quốc Hội | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

250
lượt xem 68
download

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

Tài liệu tham khảo - Biến đổi fourier rời rạc (dft)

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Biến đổi fourier rời rạc (dft) - chương 5

Chương 5 BIẾN ĐỔI FOURIER RỜI RẠC (DFT) T.S. Đinh Đức Anh Vũ 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(n)e X (ω) = − 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 toán trên máy tính Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 2 Bài Giảng Môn: Xử Lý Tín Hiệu Số
Lấy mẫu miền tần số X(ω) Lấy mẫ u N=10 N=10 X (k ) ≡ X (ω = 2π k) N Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 3 Bài Giảng Môn: Xử Lý Tín Hiệu Số Lấy mẫu miền tần số ∞ ∑ x ( n )e − j 2πkn / N X (ω ) ω = 2πk / N = X ( k) = k = 0,1,..., N − 1 2π N n = −∞ −1 N −1 2 N −1 ∑ x ( n )e + ∑ x ( n )e ∑ x ( n)e π π π − j 2N kn − j 2N kn − j 2N kn X (k ) = L + + +L n=− N n =0 n= N ∞ lN + N −1 ∑∑ π − j 2N kn = x ( n )e l = −∞ n =lN ∞  − j 2π kn N −1 = ∑  ∑ x(n − lN ) e N Thay n bằng (n-lN) n = 0 l = −∞  ∞ N −1 ∑ x(n − lN ) ⇒ X ( k ) = ∑ x p ( n)e π x p ( n) = − j 2N kn với l = −∞ n =0 T/h xp(n) – lặp chu kỳ của x(n) mỗi N mẫu – là t/h tuần hoàn với chu kỳ cơ bản N N −1 x p (n) = ∑ ck e j 2πkn / N n = 0,1,...N − 1 k =0 N −1 1 ∑x (n)e − j 2πkn / N ck = k = 0,1,..., N − 1 p N n=0 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 4 Bài Giảng Môn: Xử Lý Tín Hiệu Số
Lấy mẫu miền tần số 1 ck = k = 0,1,K , N − 1 X (k ) N 1 N −1 x p ( n) = ∑ X ( k )e N j 2 π kn n = 0,1,K , N − 1 N k =0 Có thể phục hồi t/h xp(n) từ các mẫu của phổ X(ω) 0 ≤ n ≤ N −1  x p ( n) x ( n) =  x(n) 0 others n 0 L xp(n) N>L n 0 LN xp(n) N
Lấy mẫu miền tần số Tóm tắt N −1 1 x(n) ∑ X ( k )e π j 2N kn x ( n) = có chiều dài L≤N N k =0 BĐ F ∞ N −1 ∑ x ( n )e X (ω ) = ∑ X (k ) P(ω − ωk ) − jωn X (ω ) = n = −∞ k =0 N −1 1 ∑e − jωn P(ω ) = ωk = 2π k Lấy mẫu N N k =0 N −1 X (k ) = ∑ x(n)e π − j 2N kn Phục hồi n =0 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 7 Bài Giảng Môn: Xử Lý Tín Hiệu Số Lấy mẫu miền tần số Ví dụ: x(n)=anu(n), 0
Biến đổi Fourier rời rạc (DFT) Chuỗi không tuần hoà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 hoàn, chu kỳ N xp(n) xp(n) là lặp tuần hoà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 toán DFT N điểm của X(ω) đồng nhất hơn DFT IDFT N −1 1 N −1 X ( k ) = ∑ x ( n )e x ( n) = ∑ X ( k )e N π j 2π kn − j 2N kn N k =0 n =0 k = 0,1,K , N − 1 n = 0,1,K , N − 1 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 9 Bài Giảng Môn: Xử Lý Tín Hiệu Số 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) 0 ≤ n ≤ L −1 ∞ L −1 1 X (ω ) = ∑ x(n)e − jωn = ∑ e − jωn x ( n) =  0 others n = −∞ n =0 1 − e − jωL sin(ωL / 2) − jω ( L −1) / 2 = = e 1 − e − jω sin(ω / 2) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 10 Bài Giảng Môn: Xử Lý Tín Hiệu Số
Biến đổi Fourier rời rạc (DFT) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 11 Bài Giảng Môn: Xử Lý Tín Hiệu Số DFT – BĐ tuyến tính DFT IDFT N −1 1 N −1 X ( k ) = ∑ x ( n )e x ( n) = ∑ X ( k )e N π j 2π kn − j 2N kn N k =0 n =0 k = 0,1,K , N − 1 n = 0,1,K , N − 1 WN = e− j 2π / N Nghiệm thứ N của đơn vị N −1 1 N −1 X (k ) = ∑ x(n)W x(n) = ∑ X (k )WN kn − kn N N n =0 n =0 k = 0,1, K, N − 1 n = 0,1, K , N − 1 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 12 Bài Giảng Môn: Xử Lý Tín Hiệu Số
DFT – BĐ tuyến tính  x(0)   X ( 0)   x(1)   X (1)  Các mẫu miền Các mẫu miền xN =   XN =   thời gian tần số M   M      x( N − 1)  X ( N − 1)   1 1 1 1 L   WNN −1  2 1 WN WN L  Ma trận WN =  WN ( N −1)  2 4 2 1 WN WN L BĐ tuyến tính   M M M M    ( N −1)( N −1)  WNN −1 WN ( N −1) 2 1 WN L   BĐ DFT N điểm X N = WN x N − x N = WN 1 X N − WN 1 = N WN * 1 WN là ma trận đường chéo WNW = NI N xN = W X N * * 1 N N N Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 13 Bài Giảng Môn: Xử Lý Tín Hiệu Số 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 hoàn chu kỳ N DFT N điểm của chuỗi x(n) N −1 1 N −1 x p ( n ) = ∑ ck e x ( n ) = ∑ X ( k )e N π j 2 π kn j 2N kn N n =0 k =0 −∞ ≤ n ≤ ∞ n = 0,1, K , N − 1 X(k) = Nck 1 N −1 N −1 ck = ∑ x p ( n ) e N X ( k ) = ∑ x ( n )e − j 2 π kn π − j 2N kn N n =0 DFT N điểm cho chính xác n =0 phổ vạch của chuỗi k = 0,1, K, N − 1 k = 0,1, K , N − 1 tuần hoà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 SV xem thêm mối quan hệ giữa DFT và BĐ Z; giữa DFT và hệ số Fourier của t/h LTTG Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 15 Bài Giảng Môn: Xử Lý Tín Hiệu Số
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 n=-1 Chiều âm x(n) = {1 2 3 4} x(n) x(1) 4 3 2 x(2) x(0) x(n) 1 n 0 1 2 3 x(3) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 16 Bài Giảng Môn: Xử Lý Tín Hiệu Số DFT – Biểu diễn tín hiệu theo vòng ∞ ∑ x(n − lN ) x p ( n) = Chuỗi tuần hoàn chu kỳ N, mở rộng từ x(n) n = −∞ ∞ ∑ x(n − lN − k ) x 'p (n) = x p ( n − k ) = Chuỗi dịch xp(n) đi k mẫu l = −∞   x ( n) 0 ≤ n ≤ N − 1 ' p x ' ( n) =  Chuỗi có chiều dài hữu hạn từ x’p(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 xp(n) 4 4 4 xp(n-2) 4 4 4 3 3 3 3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 1 1 1 0123 -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) x’(n) 2 4 4 3 x(n) x’(n) 2 x(2) 3 x’(2) 1 1 x(0) 3 x’(0) 1 4 2 0123 x(3) x’(3) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 17 Bài Giảng Môn: Xử Lý Tín Hiệu Số
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 hoà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ồ Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 18 Bài Giảng Môn: Xử Lý Tín Hiệu Số 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) = XR(k) + jXI(k), 0≤k≤N-1   N −1 1 N −1 X R (k ) = ∑ [xR (n) cos 2πkn + xI (n) sin 2πkn ] xR ( n) = ∑ [X R (k ) cos 2πkn − X I ( k ) sin 2πkn ]   N N N N   N k =0 n =0   N −1 N −1  x ( n) = 1  X ( k ) = − [x ( n) sin 2πkn − x (n) cos 2πkn ] ∑ [X R (k ) sin 2πNkn + X I (k ) cos 2πNkn ] ∑R I I I N N N k =0   n =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 N −1 1 X (k ) = ∑ x(n) cos ∑ X (k ) cos x ( n) = 2πkn 2πkn N N N n =0 k =0 Nếu x(n) thực và lẻ: x(n) = -x(N-n) → XR(k) = 0 N −1 N −1 1 X ( k ) = − j ∑ x( n) sin ∑ X (k ) sin x ( n) = j 2πkn 2πkn N N N n =0 k =0 Nếu x(n) thuần ảo: x(n) = jxI(n) N −1 N −1 X R (k ) = ∑ xI (n) sin X I (k ) = ∑ xI (n) cos 2πkn 2πkn N N n =0 n =0 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 19 Bài Giảng Môn: Xử Lý Tín Hiệu Số
DFT – Tính chất Tuần hoàn x(n) ← N → X (k )  DFT  x ( n) = x ( n + N ) ∀n ⇒  X (k ) = x(k + N ) ∀k   x1 (n) ← N → X 1 (k )  Tuyến tính DFT   x2 (n) ← N → X 2 (k )  DFT  ⇒ a1 x1 (n) + a2 x2 (n) ← N → a1 X 1 (k ) + a2 X 2 (k )  DFT  x1 (n) ← N → X 1 (k ) Tổng chập vòng  DFT    x2 (n) ← N → X 2 (k )  DFT  ⇒ x1 (n) ⊗ x2 (n) ← N → X 1 (k ) X 2 (k )  DFT N N Tổng chập vòng N điểm N −1 = ∑ x1 (k ) x2 ((n − k )) N x1 (n) ⊗ x2 (n) n = 0,1, K , N − 1 N k =0 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 20 Bài Giảng Môn: Xử Lý Tín Hiệu Số DFT – Tổng chập vòng = IDFT { X (k )} x ( m)  x1 ( n) ← N → X 1 (k )  DFT   N −1 1 ∑ X ( k )e π  x2 (n) ← → X 2 (k )  j 2N km DFTN =  N k =0 x(m) ← N → X (k ) = X 1 (k ) X 2 (k )  DFT N −1 1 ∑ X (k ) X π j 2N km = ( k )e 1 2 N k =0 a =1 N  − j 2 π kn   − j 2 π kl  j 2 π km N −1 N −1 N −1 1 N −1  ∑ ∑ x1 ( n)e N  ∑ x1 (l )e N  e N = ∑ a = 1 − a a ≠ 1 k N N k =0  n =0   l =0   k =0  1− a N −1 N −1 N −1 1 ∑ x (n)∑ x (l )∑ e π j 2N k ( m − n − l ) = π ( m − n −l ) j 2N a=e Trong do 1 2 N n =0 l =0 k =0 a = 1, khi : m − n − l = pN , p ∈ Z a ≠ 1 ⇒ a N = e j 2π ( m − n −l ) = 1 ⇒ 1 − a N = 0 m − n − l = pN ⇔ l = ((m − n)) N N N −1 ⇒ ∑ ak =  0 otherwise N −1 k =0 x(m) = ∑ x1 ( n) x2 ((m − n)) N m = 0,1, K , N − 1 n =0 N −1 x(n) = ∑ x1 (k ) x2 ((n − k )) N n = 0,1, K , N − 1 k =0 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 21 Bài Giảng Môn: Xử Lý Tín Hiệu Số
DFT – Tính chất Đảo theo thời gian x(n) ← N → X (k )  DFT ⇒ x((−n)) N = x( N − n) ← N → X ((− k )) N = X ( N − k )  DFT Dịch vòng theo thời gian x(n) ← N → X (k )  DFT ⇒ x((n − l )) N ← N → X (k )e − j 2πkl / N  DFT Dịch vòng theo tần số x(n) ← N → X (k )  DFT ⇒ x(n)e j 2πnl / N ← N → X ((k − l )) N  DFT Liên hợp phức x(n) ← N → X (k )  DFT  x* (n) ← N → X * ((−k )) N = X * ( N − k )  DFT  ⇒ *  x ((−n)) N = x* ( N − n) ← N → X * (k )  DFT  Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 24 Bài Giảng Môn: Xử Lý Tín Hiệu Số DFT – Tính chất Tương quan vòng x(n) ← N → X (k )  DFT y (n) ← N → Y (k )  DFT N −1 ~ r xy (l ) = ∑ x(n) y * ((n − l )) N với ~ ~ ⇒ r xy (l ) ← → R xy (k ) = X (k )Y (k ) DFTN * n =0 Nhân 2 chuỗi   x1 (n) ← N → X 1 ( k )  DFT   x2 (n) ← N → X 2 (k )  DFT  ⇒ x1 (n) x2 (n) ← N → N X 1 (k ) ⊗ X 2 (k ) 1 DFT N Định lý Parseval x(n) ← N → X (k )  DFT y (n) ← N → Y (k )  DFT N −1 N −1 ⇒ ∑ x(n) y (n) = ∑ X (k )Y * (k ) * n =0 k =0 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 25 Bài Giảng Môn: Xử Lý Tín Hiệu Số
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 quả của tổng chập miền thời gian Lọc tuyến tính x(n) y(n) h(n) – Tín hiệu ngắn M −1 y ( n ) = ∑ h( k ) x ( n − k ) x(n) chiều dài = L (n=0,1,…,L-1) h(n) chiều dài = M (n=0,1,…,M-1) k =0 y(n) chiều dài N = M+L-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) • Tổng chập vòng N điểm của h(n) và x(n) y(n) = IDFTN{Y(k)} 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) Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 26 Bài Giảng Môn: Xử Lý Tín Hiệu Số 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 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 – Overlap-Add có chiều dài L >> M PP 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 M-1 L x2(n) x3(n) M-1 L M-1 L Output M-1 L M-1 L Discard Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 29 Bài Giảng Môn: Xử Lý Tín Hiệu Số
DFT – Lọc tuyến tính PP Overlap-Add – Đệm thêm M-1 số không vào mỗi block dữ liệu đầu vào Input zeros x1(n) L M-1 L M-1 x2(n) x3(n) L M-1 L M-1 Output + 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 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 31 Bài Giảng Môn: Xử Lý Tín Hiệu Số 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ổ hoá 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 ⇔ Nhân chuỗi với cửa sổ chiều dài L Hàm cửa sổ có chiều dài L chỉ phân biệt được xw(n) = x(n)w(n) nếu các tần số cách nhau w(n): hàm cửa sổ ít nhất một đoạn ∆ω = 2L π Cửa sổ chữ nhật Cửa sổ Hanning  1 (1 − cos L −1 n) 0 ≤ n ≤ L − 1 2π 0 ≤ n ≤ L −1 1 w( n) =  2 w(n) =  0 otherwise 0 otherwise Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 32 Bài Giảng Môn: Xử Lý Tín Hiệu Số
DFT – Phân tích tần số 0 ≤ n ≤ L −1 1 Ví dụ x(n) = cos ω1n + cos ω 2 n w(n) =  0 otherwise ^ X (ω ) = 1 [W (ω − ω1 ) + W (ω − ω 2 ) + W (ω + ω1 ) + W (ω + ω 2 )] 2 L=25 L=50 ω1=0.2π ω2=0.22π Rò rỉ công suất L=75 L=100 Khoa Công Nghệ Thông Tin - Đại Học Bách Khoa Tp. HCM Side 33 Bài Giảng Môn: Xử Lý Tín Hiệu Số