Bài giảng Xử lý số tín hiệu: Chương 5 - TS. Đinh Đức Anh Vũ

Chia sẻ: Sơn Tùng | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

68
lượt xem 5
download

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

Bài giảng "Xử lý số tín hiệu - Chương 5: Biến đổi Fourier rời rạc" cung cấp cho người học các kiến thức: Giới thiệu về DFT, lấy mẫu miền tần số, biến đổi Fourier rời rạc, DFT - BĐ tuyến tính,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Xử lý số tín hiệu: Chương 5 - TS. Đinh Đức Anh Vũ

Chương 5 BIẾN ĐỔI FOURIER RỜI RẠC (DFT) T.S. Đinh Đức Anh Vũ Giới thiệu về DFT z 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 n = −∞ − jωn z 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π N k) 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 (ω ) ω = 2πk / N = X ( 2π N k) = ∑ x ( n )e n = −∞ − j 2πkn / N k = 0,1,..., N − 1 −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  ∞ N −1  − j 2π kn = ∑  ∑ x(n − lN ) e N Thay n bằng (n-lN) n = 0 l = −∞  N −1 ∞ ⇒ X ( k ) = ∑ x p ( n)e − j 2Nπ kn với x p ( n) = ∑ x(n − lN ) l = −∞ n =0 z 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 ck = N ∑x n=0 p (n)e − j 2πkn / N k = 0,1,..., N − 1 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 = X (k ) k = 0,1,K , N − 1 N 1 N −1 x p ( n) = ∑ X ( k )e N j 2 π kn n = 0,1,K , N − 1 N k =0 z Có thể phục hồi t/h xp(n) từ các mẫu của phổ X(ω)  x p ( n) 0 ≤ n ≤ N −1 x(n) x ( n) =  n 0 others 0 L N>L xp(n) n 0 L N N
Lấy mẫu miền tần số z Tóm tắt N −1 x(n) 1 ∑ X ( k )e j 2Nπ kn có chiều dài L≤N x ( n) = BĐ F N k =0 ∞ N −1 X (ω ) = ∑ x ( n )e n = −∞ − jωn X (ω ) = ∑ X (k ) P(ω − ωk ) k =0 N −1 1 P(ω ) = ∑e − jωn ω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ố z Ví dụ: x(n)=anu(n), 0
Biến đổi Fourier rời rạc (DFT) z Chuỗi không tuần hoàn, năng lượng hữu hạn x(n) z 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 z Nó đặc trưng cho chuỗi tuần hoàn, chu kỳ N xp(n) z 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 z 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)} z 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 2Nπ kn j 2π kn n =0 N k =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) z 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) 1 0 ≤ n ≤ L −1 ∞ L −1 x ( n) =  X (ω ) = ∑ x(n)e − jωn = ∑ e − jω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 2Nπ kn j 2π kn n =0 N k =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 kn N x(n) = ∑ X (k )WN− kn n =0 N 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 =    M  thời gian  M  tần số      x( N − 1)  X ( N − 1)  1 1 1 L 1     1 WN WN2 L WNN −1  WN =  Ma trận 1 WN2 WN4 L WN2 ( N −1)    BĐ tuyến tính  M M M M   1 WNN −1 WN2 ( N −1) L WN( N −1)( N −1)    z BĐ DFT N điểm X N = WN x N xN = WN−1 X N WN−1 = N1 WN* WN là ma trận xN = W X N 1 * WNW = NI N * đường chéo 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 z 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 2Nπ kn j 2 π kn k =0 N n =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 z 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 z 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(n) x(0) 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 ∞ z Chuỗi tuần hoàn chu kỳ N, mở rộng từ x(n) x p ( n) = ∑ x(n − lN ) n = −∞ ∞ z Chuỗi dịch xp(n) đi k mẫu x 'p (n) = x p ( n − k ) = ∑ x(n − lN − k ) l = −∞  x (n) 0 ≤ n ≤ N − 1 ' p z Chuỗi có chiều dài hữu hạn từ x’p(n) x ' ( n) =  0 otherwise z 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 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) x’(n) 2 4 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) 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 z 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ó z 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 z 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 z Đả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 z 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πNkn + xI (n) sin 2πNkn ] x  R ( n ) = ∑ [X R (k ) cos 2πNkn − X I (k ) sin 2πNkn ]  n =0  N k =0  N −1  N −1  X ( k ) = − [x ( n) sin 2πkn − x (n) cos 2πkn ]  x ( n) = 1  I ∑ n =0 R N I N  I ∑ [X R (k ) sin 2πNkn + X I (k ) cos 2πNkn ] N k =0 z Nếu x(n) thực: X(N-k) = X*(k) = X(-k) X ( N − k ) = X ( k ) và ∠X ( N − k ) = −∠X (k ) z 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 2πkn N x ( n) = ∑ X (k ) cos 2πkn N n =0 N k =0 z 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 2πkn N x ( n) = j ∑ X (k ) sin 2πkn N n =0 N k =0 z Nếu x(n) thuần ảo: x(n) = jxI(n) N −1 N −1 X R (k ) = ∑ xI (n) sin 2πkn N X I (k ) = ∑ xI (n) cos 2πNkn 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 z Tuần hoàn x(n) ← → X (k ) DFTN  x ( n) = x ( n + N ) ∀n ⇒  X (k ) = x(k + N ) ∀k z Tuyến tính  x1 (n) ← → X 1 (k ) DFTN   x2 (n) ← → X 2 (k ) DFTN ⇒ a1 x1 (n) + a2 x2 (n) ← → a1 X 1 (k ) + a2 X 2 (k ) DFTN z Tổng chập vòng  x1 (n) ← → X 1 (k ) DFTN   x2 (n) ← → X 2 (k ) DFTN ⇒ x1 (n) ⊗ N x2 ( n) ← DFTN → X 1 (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, K , N − 1 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  x1 ( n) ← → X 1 (k ) DFTN x ( m) = IDFT { X (k )}  1 N −1 ∑ X ( k )e j 2Nπ km  x2 (n) ←→ X 2 (k ) DFTN = N k =0 x(m) ← → X (k ) = X 1 (k ) X 2 (k ) DFTN N −1 1 ∑ X (k ) X j 2Nπ km = 1 2 ( k )e N k =0 N a =1  − j 2Nπ kn   − j 2Nπ kl  j 2Nπ km N −1 N −1 N −1 N −1  1 ∑ a = 1 − a k N = N ∑ ∑ 1 k =0  n =0 x ( n ) e  ∑ x1 (l )e   l =0 e  k =0  a ≠1  1− a 1 N −1 N −1 N −1 ∑ x (n)∑ x (l )∑ e j 2Nπ k ( m − n − l ) j 2Nπ ( m − n −l ) = Trong do a=e N n =0 1 l =0 2 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 N −1 N m − n − l = pN ⇔ l = ((m − n)) N ⇒ ∑ ak =  k =0 0 otherwise N −1 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 z Đảo theo thời gian x(n) ← → X (k ) DFTN ⇒ x((−n)) N = x( N − n) ← → X ((− k )) N = X ( N − k ) DFTN z Dịch vòng theo thời gian x(n) ← → X (k ) DFTN ⇒ x((n − l )) N ← → X (k )e − j 2πkl / N DFTN z Dịch vòng theo tần số x(n) ← → X (k ) DFTN ⇒ x(n)e j 2πnl / N ← → X ((k − l )) N DFTN z Liên hợp phức x(n) ← → X (k ) DFTN  x* (n) ← → X * ((−k )) N = X * ( N − k ) DFTN ⇒ *  x ((−n)) N = x* ( N − n) ← → X * (k ) DFTN 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 z Tương quan vòng x(n) ←→ X (k ) DFTN y (n) ← → Y (k ) DFTN ~ N −1 ~ ~ với r xy (l ) = ∑ x(n) y * ((n − l )) N ⇒ r xy (l ) ←→ R xy (k ) = X (k )Y (k ) DFTN * n =0 z Nhân 2 chuỗi  x1 (n) ← → X 1 ( k ) DFTN   x2 (n) ← → X 2 (k ) DFTN ⇒ x1 (n) x2 (n) ← → N1 X 1 (k ) ⊗ DFTN N X 2 (k ) z Định lý Parseval x(n) ←→ X (k ) DFTN y (n) ← → Y (k ) DFTN 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 z 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 z Lọc tuyến tính x(n) y(n) – Tín hiệu ngắn h(n) M −1 x(n) chiều dài = L (n=0,1,…,L-1) y ( n ) = ∑ h( k ) x ( n − k ) 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) 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) 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 z 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 – Overlap-Add T/h nhập x(n): được chia nhỏ thành từng block có chiều dài L >> M z 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 z 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 z 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 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 z PP Overlap-Add – Đệm thêm M-1 số không 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 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ố z T/h ngắn – Tính DFT từ x(n) z 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 xw(n) = x(n)w(n) chỉ phân biệt được w(n): hàm cửa sổ nếu các tần số cách nhau ít nhất một đoạn ∆ω = 2Lπ Cửa sổ chữ nhật Cửa sổ Hanning 1 0 ≤ n ≤ L −1  12 (1 − cos L2−π1 n) 0 ≤ n ≤ L − 1 w(n) =  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ố z Ví dụ 1 0 ≤ n ≤ L −1 x(n) = cos ω1n + cos ω 2 n w(n) =  0 otherwise ^ X (ω ) = 12 [W (ω − ω1 ) + W (ω − ω 2 ) + W (ω + ω1 ) + W (ω + ω 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ố