Bài giảng Xử lý tín hiệu số - Chương 4+5

42 trang huongle 3680

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 4+5", để 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:

bai_giang_xu_ly_tin_hieu_so_chuong_45.pdf

Nội dung text: Bài giảng Xử lý tín hiệu số - Chương 4+5

Chương IV Chương 4 PHÂN TÍCH TÍN HIỆU & HỆ THỐNG RỜI RẠC LTI TRONG MIỀN TẦN SỐ Trong chương III ta đã thấy phép biến đổi Z là một công cụ toán học hiệu quả trong việc phân tích hệ thống rời rạc LTI. Trong chương này, ta sẽ tìm hiểu một công cụ toán học quan trọng khác là phép biến đổi Fourier của tín hiệu rời rạc, gọi tắt là DTFT (DT-Fourier Transform). Phép biến đổi này áp dụng để phân tích cho cả tín hiệu và hệ thống. Nó được dùng trong trường hợp dãy rời rạc dài vô hạn và không tuần hoàn. Nội dung chính chương này bao gồm: - Biến đổi Fourier - Biến đổi Fourier ngược - Các tính chất của biến đổi Fourier - Phân tích tần số cho tín hiệu rời rạc (cách gọi thông dụng là phân tích phổ) - Phân tích tần số cho hệ thống rời rạc 4.1 PHÉP BIẾN ĐỔI FOURIER 4.1.1 Biểu thức tính biến đổi Fourier Ta đã biết rằng có thể biểu diễn tín hiệu rời rạc tạo ra bằng cách lấy mẫu tín hiệu tương tự dưới dạng sau đây: ∞ xs ()txkTtkT=−∑ ( )δ ( ) k =−∞ Bây giờ ta sẽ tính biến đổi Fourier cho tín hiệu này. Các bước như sau: 1. Tính biến đổi Fourier của δ ()tkT− . 2. Sử dụng nguyên lý xếp chồng, tìm biến đổi Fourier của xs (t ) . F ∞ − jnω T xts ()↔ ∑ xnTe ( ) n=−∞ Đặt x()nT= x [] n và thay biến Ω = ωT (xem lại chương I, lưu ý đơn vị củaΩ [rad] và ω [rad/s]), ta được: ∞ DTFT:Ω=Xxne ( )∑ [ ] − jnΩ n=−∞ Ta nhận xét thấy tuy tín hiệu rời rạc trong miền thời gian nhưng DTFT lại liên tục và tuần hoàn trong miền tần số. - 67 -
Chương IV DTFT chính là hàm phức theo biến tần số thực. Ta gọi DTFT là phổ phức (complex spectrum) hay ngắn gọn là phổ của tín hiệu rời rạc x[n ] 4.1.2 Sự hội tụ của phép biến đổi Fourier Không phải là tất cả DTFT đều tồn tại (hội tụ) vì DTFT chỉ hội tụ khi: ∞ ∑ x[n]e− jΩn 1? Ví dụ: Tìm Y (Ω ) với yn[ ]=− aun [ n ], ||>a 1. Nếu | a |<1? - 68 -
Chương IV Ví dụ: Cho p[nununN ]=−− [ ] [ ] . Tìm P (Ω ) . Hãy chứng tỏ rằng biến đổi Fourier này có pha tuyến tính (linear phase) Ví dụ: Tìm H (Ω ) của hệ LTI có đáp ứng xung sau hn[]=+δ [] n 2[δδδ n −+−+− 1]2[ n 2] [ n 3] Và chứng tỏ rằng hệ có pha tuyến tính 4.1.4 Quan hệ giữa biến đổi Z và biến đổi Fourier Biểu thức tính ZT là: ∞ X(z) = ∑x[n]z −n n=−∞ Giả sử ROC có chứa đường tròn đơn vị. Tính X(z) trên đường tròn đơn vị, ta được: ∞ X(z) = ∑x[n]e− jΩn = X(Ω) jΩ z=e n=−∞ Như vậy, biến đổi Fourier chính là biến đổi Z tính trên đường tròn đơn vị. Dựa vào đây, ta có thể phát biểu lại điều kiện tồn tại của DTFT như sau: - 69 -
Chương IV Biến đổi Fourier của một tín hiệu chỉ tồn tại khi ROC của biến đổi Z của tín hiệu đó có chứa đường tròn đơn vị. Ví dụ: Làm lại các ví dụ trên- Tìm biến đổi Fourier của: (a) x[naun ]= n [ ] , || a 1? (b) yn[ ]=− aun [ n ], ||>a 1. Nếu | a |<1? (c)p [nununN ]=−− [ ] [ ] (d) hn[ ]=+δ [ n ] 2δδδ [ n −+−+− 1] 2 [ n 2] [ n 3] 4.2 PHÉP BIẾN ĐỔI FOURIER NGƯỢC 4.2.1 Biểu thức tính biến đổi Fourier ngược Ta thấy X(Ω) là một hàm tuần hoàn với chu kỳ 2π, do e jΩ tuần hoàn với chu kỳ 2π : eejjΩ = (2)Ω+ππ==. eee jjj Ω 2 Ω Do đó dải tần số của tín hiệu rời rạc là một dải tần bất kỳ rộng 2π, thường chọn là:(−π,π) hay (0,2π) . Vậy ta có thể khai triển X(Ω) thành chỗi Fourier trong khoảng (−π,π) hay (0,2π) nếu điều kiện tồn tại X(Ω) thỏa mãn. Các hệ số Fourier là x[n], ta có thể tính được x[n] từ X(Ω) theo cách sau: 1 Nhân 2 vế của biểu thức tính DTFT với e jΩl rồi lấy tích phân trong khoảng (−π,π) ta có: 2π π π ∞ ∞ π 1 jΩl 1 ⎡ − jΩn ⎤ jΩl ⎡ 1 jΩ(l−n) ⎤ ∫ X(Ω)e dΩ = ∫ ⎢ ∑x[n]e ⎥e dΩ = ∑x[n]⎢ ∫e dΩ⎥ = x[l] 2π −π 2π −π⎣n=−∞ ⎦ n=−∞ ⎣2π −π ⎦ Thay l = n và thay cận tích phân, không nhất thiết phải là (−π,π ) mà chỉ cần khoảng cách giữa cận trên và dưới là 2π, ta được biểu thức tính biến đổi Fourier ngược (IDTFT) như sau: - 70 -
Chương IV 1 x[]nXed= (ΩΩ )jnΩ 2π ∫2π Ta có thể tính IDTFT bằng hai cách: một là tính trực tiếp tích phân trên, hai là chuyển về biến đổi Z rồi tính như tính biến đổi Z ngược. Tùy vào từng trường hợp cụ thể mà ta chọn phương pháp nào cho thuận tiện. 4.2.2 Một số ví dụ tính biến đổi Fourier ngược Ví dụ: Tìm x[n] nếu biết: ⎪⎧1, Ω ≤ Ωc X(Ω) = ⎨ ⎩⎪0, Ωc < Ω < π Ví dụ: Tìm x[n] nếu biết: X(Ω) = cos2 Ω - 71 -
Chương IV 4.3 CÁC TÍNH CHẤT CỦA PHÉP BIẾN ĐỔI FOURIER Sau đây ta sẽ xét một số tính chất quan trọng của DTFT, phần còn lại xem sách. 4.3.1 Tính tuyến tính ax12[] n+ bx [] n←→ aX 1 ( Ω ) + bX 2 ( Ω ) 4.3.2 Tính dịch thời gian xn[]←→Ω X ( ) −Ωjn0 xn[]− n0 ←→ e X () Ω Qua đây ta thấy sự dịch chuyển tín hiệu trong miền thời gian sẽ không ảnh hưởng đến biên độ của DTFT, tuy nhiên pha được cộng thêm một lượng. 4.3.3 Tính dịch tần số/ điều chế xn[]←→Ω X ( ) jΩ0n e x[n] ←→ X(Ω − Ω0 ) 1 1 cos(Ω n)x[n] ←→ X(Ω − Ω ) + X(Ω + Ω ) 0 2 0 2 0 Như vậy, việc điều chế tín hiệu gây ra sự dịch tần số. - 72 -
Chương IV 4.3.4 Tính chập thời gian Tương tự như biến đổi Z, với biến đổi Fourier ta cũng có: F xn12[]∗ xn []←→ X 12 ( Ω ) X ( Ω ) Ví dụ: n Cho hn[]=,||< aun [] a 1. Tìm hệ đảo của nó hni [ ] , nhưng không dùng biến đổi Z. 4.3.5 Tính nhân thời gian 1 x1[n].x 2 [n] ←→ X1 (λ)X 2 (Ω − λ)dλ 2π ∫2π 4.4 PHÂN TÍCH TẦN SỐ (PHỔ) CHO TÍN HIỆU RỜI RẠC 4.4.1 Ý nghĩa của phổ Trong miền tần số, mỗi tín hiệu đều có đặc điểm riêng của nó. Ví dụ như, tín hiệu sin chỉ có duy nhất một tần số đơn, trong khi nhiễu trắng chứa tất cả các thành phần tần số. Sự biến thiên chậm của tín hiệu là do tần số thấp, trong khi sự biến thiên nhanh và những sườn nhọn là do tần số cao. Như xung vuông chẳng hạn, nó chứa cả tần số thấp và cả tần số cao. Hình sau minh họa cho điều đó. Hình (a) là một sóng sin tần số thấp, các hình sau (b)-(c) cộng thêm dần các sóng sin tần số cao dần. Hình cuối cùng (e) là tổng của 7 sóng sin. Trong hình (e) ta thấy tổng của 7 sóng sin có dạng xấp xỉ với dạng của một xung vuông. Phổ của tín hiệu là mô tả chi tiết các thành phần tần số chứa bên trong tín hiệu. Ví dụ như với tín hiệu xung vuông vừa nói trên, phổ của nó chỉ ra tất cả các đỉnh nhọn của các sóng sin riêng có thể kết hợp lại với nhau tạo ra xung vuông. Thông tin này quan trọng vì nhiều lý do. Ví dụ như, thành phần tần số trong một mẩu nhạc chỉ cho ta biết các đặc trưng của loa, để từ đó khi sản xuất lại ta có thể cải tiến cho hay hơn. Một ví dụ khác, micro trong hệ thống nhận dạng tiếng nói phải có dải tần đủ rộng để có thể bắt được tất cả các tần số quan trọng trong tiếng nói đầu vào. Để dự đoán các ảnh hưởng của bộ lọc trên tín hiệu, cần phải biết không chỉ bản chất của bộ lọc mà còn phải biết cả phổ của tín hiệu nữa. - 73 -
Chương IV 4.4.2 Phổ biên độ và phổ pha Phổ của tín hiệu gồm có hai phần: phổ biên độ (magnitude spectrum) và phổ pha (phase spectrum). Phổ biên độ chỉ ra độ lớn của từng hành phần tần số. Phổ pha chỉ ra quan hệ pha giữa các thành phần tần số khác nhau. Trong phần này, ta xét tín hiệu rời rạc không tuần hoàn. Công cụ để tính phổ tín hiệu rời rạc không tuần hoàn là DTFT. Để tính phổ tín hiệu, ta qua hai bước: một là tính DTFT của tín hiệu- là X(Ω ) , hai là tính biên độ và pha của X(Ω) : X(Ω) = X(Ω) e jθ(Ω) ở đây | X(Ω) | là phổ biên độ và θ(Ω) là phổ pha. Ta dễ dàng chứng minh được rằng đối với tín hiệu thực, phổ biên độ là một hàm chẵn theo tần số Ω và phổ pha là một hàm lẻ theo Ω . Do đó, nếu biết phổ X(Ω) trong khoảng 0 đến π , ta có thể suy ra phổ trong toàn dải tần số. - 74 -
Chương IV Để dễ giải thích phổ, tần số số Ω từ 0 đến π thường được chuyển đổi thành tần số tương tự f từ 0 đến fS/2 nếu tần số lấy mẫu là fS. Ví dụ: Tìm phổ biên độ và phổ pha của tín hiệu chữ nhật: x[n] = u[n] - u[n-4] Ví dụ: Một mẩu nguyên âm tiếng nói “eee” được lấy mẫu ở tần số 8 kHz. Phổ biên độ của tín hiệu này như trên hình. Hỏi tần số cơ bản của tín hiệu này là bao nhiêu? - 75 -
Chương IV 4.4.3 Mật độ phổ năng lượng Năng lượng của tín hiệu x[n] được định nghĩa là: ∞ E = ∑| x[n] |2 n=−∞ Bây giờ ta biểu diễn năng lượng theo phổ: ∞ ∞ π * ⎡ 1 * − jΩn ⎤ E= ∑∑x[n]x [n] = x[n]⎢ ∫ X (Ω)e dΩ⎥ nn=−∞ =−∞ ⎣2π −π ⎦ Thay đổi thứ tự lấy tổng và tích phân, ta có: π ∞ π 1 * ⎡ − jΩn ⎤ 1 2 E = ∫ X (Ω)⎢ ∑ x[n]e ⎥dΩ = ∫ X(Ω) dΩ 2π −π ⎣n=−∞ ⎦ 2π −π Vậy quan hệ về năng lượng giữa x[n] và X(Ω ) là: ∞ π 1 2 E = ∑| x[n] |2 = ∫ X(Ω) dΩ (quan hệ Parseval) n=−∞ 2π −π 2 Đại lượng Sxx (Ω) = X(Ω) gọi là mật độ phổ năng lượng. Ví dụ: Xác định mật độ phổ năng lượng của tín hiệu sau: x[n] = an u[n] với -1 < a < 1 4.4.4 Băng thông Băng thông (bandwidth) là dải tần số tập trung hầu hết năng lượng (công suất) của tín hiệu. Giả sử 95% năng lượng của tín hiệu tập trung trong dải tần số F1 ≤ F ≤ F2 , ta nói băng thông 95% của tín hiệu là F2 − F1 . Ta có thể định nghĩa các băng thông 75%, băng thông 90%, băng thông 99% theo kiểu tương tự như băng thông 95% nói trên. Dựa vào băng thông của tín hiệu, ta có thể phân loại tín hiệu như sau: Nếu năng lượng tín hiệu tập trung quanh tần số 0 thì đó là tín hiệu tần số thấp (low-frequency signal). Nếu năng lượng tín hiệu tập trung ở miền tần số cao thì đó là tín hiệu cao tần (high- frequency signal). - 76 -
Chương IV Nếu năng lượng tín hiệu tập trung vào một dải tần số nào đó giữa tần số thấp và tần số cao thì đó là tín hiệu thông dải (bandpass signal) Trong trường hợp tín hiệu thông dải, khái niệm băng hẹp (narrowband) được dùng để chỉ tín hiệu có băng thông F2 − F1 rất nhỏ (khoảng 10% hoặc nhỏ hơn) so với tần số trung tâm (F1 + F2 ) / 2. Ngược lại, tín hiệu được gọi là băng rộng (wideband). Tín hiệu được gọi là có băng thông hữu hạn (bandlimited) nếu phổ của nó bằng 0 ở ngoài dải tần F ≥ B . Tín hiệu năng lượng x[n] được gọi là có băng thông hữu hạn nếu: X(Ω) = 0, Ω 0 < Ω < π 4.5 PHÂN TÍCH TẦN SỐ CHO HỆ THỐNG RỜI RẠC LTI Trong miền tần số, hệ thống rời rạc LTI được mô tả bằng một hàm theo tần số- gọi là đáp ứng tần số (frequency response)- là biến đổi Fourier của đáp ứng xung h[n]: Quan hệ giữa tín hiệu vào- ra và hệ thống trong miền tần số như sau: y[n] = x[n]∗ h[n] Y(Ω) = X(Ω).H(Ω) Đáp ứng tần số hoàn toàn đặc trưng cho hệ rời rạc LTI trong miền tần số. Nó cho phép ta: - xác định các đáp ứng của hệ thống với các đầu vào có dạng tổ hợp tuyến tính của tín hiệu sin hay hàm mũ phức. - xác định các đặc tính của hệ LTI là bộ lọc tần số. 4.5.1 Tính đáp ứng tần số 1. Tính từ đáp ứng xung Theo định nghĩa, đáp ứng tần số là H(Ω ) được tính như sau: ∞ H(Ω) = ∑h[n]e− jΩn n=−∞ 2. Tính từ phương trình sai phân tuyến tính hệ số hằng N M ∑ak y[n − k] =∑br x[n − r] k=0 r=0 Lấy DTFT 2 vế, sử dụng tính chất tuyến tính và dịch thời gian, ta được: N M − jΩk − jΩr ∑[a k e ]Y(Ω = ∑[b r e ]X(Ω) k=0 r=0 M − jΩr ∑ b r e Y(Ω) r=0 H(Ω) = = N X(Ω) − jΩk ∑a k e k=0 Ví dụ: Tìm đáp ứng tần số của hệ: y[[n]] + 0.1y[[n −1]] + 0.85y[n − 2] = x[n] − 0.3x[n −1] - 77 -
Chương IV 3. Tính từ hàm truyền đạt Theo quan hệ giữa phép biến đổi Z và phép biến đổi Fourier, ta có thể tính được đáp ứng tần số từ hàm truyền đạt bằng cách thay z= e jΩ (với điều kiện là ROC có chứa đường tròn đơn vị): H(Ω) = H(z) z=e jΩ 4.5.2 Đáp ứng biên độ và đáp ứng pha Do đáp ứng tần số H(Ω) là hàm theo biến phức Ω nên có thể biểu diễn như sau: H(Ω) = H(Ω) e jθ(Ω) |)H(Ω | được gọi là đáp ứng biên độ và θ(Ω ) được gọi là đáp ứng pha. Ví dụ: Cho đáp ứng tần số của hệ sau: 1 H(Ω) = 1− 0.4e − jΩ Tìm đáp ứng biên độ và pha. 4.5.3 Đáp ứng của hệ LTI đối với đầu vào là tổ hợp tuyến tính của các tín hiệu dạng sin hay hàm mũ phức 1. Đáp ứng trạng thái 0 đối với đầu vào dạng hàm mũ phức Từ chương II, ta đã biết đáp ứng của hệ (điều kiện đầu là 0) là: ∞ y[n] = ∑ h[k]x[n − k] k=−∞ Giả sử tín hiệu vào là tín hiệu hàm mũ phức sau: - 78 -
Chương IV x[n] = Ae jΩn , − ∞ < n < ∞ với A là biên độ và Ω là một tần số trong dải tần (−π,π) . Thay x[n] vào biểu thức y[n] ở trên, ta được: ∞ y[n] = ∑h[k]()Ae jΩ(n−k) k=−∞ ∞ ⎡ − jΩk ⎤ jΩn = A⎢ ∑ h[k]()e ⎥e ⎣k=−∞ ⎦ = (Ae jΩn )H(Ω) = x[n]H(Ω) Ta thấy đáp ứng của hệ có dạng giống dạng của đầu vào, tức là dạng hàm mũ phức với cùng tần số, chỉ khác nhau một hệ số nhân là H(Ω ) . Điều này cũng đúng trong trường hợp tín hiệu vào có dạng sin/cos. Ví dụ: Xác định đầu ra của hệ thống có đáp ứng xung là: h[n] = (1/ 2) n u[n] khi đầu vào có dạng: π j n ⎛ π ⎞ 1 2 0 (a) x[n] = Ae 2 , − ∞ < n < ∞ . Cho biết H = = e − j26.6 ⎜ ⎟ 1 ⎝ 2 ⎠ 1+ j 2 5 π (b) x[n] = 10 − 5sin n + 20cos πn, − ∞ < n < ∞ 2 - 79 -
Chương IV 2. Eigenfunction và eigenvalue Nếu ta có tín hiệu vào và tín hiệu ra có thể phân tích thành các hàm cơ sở là: x[]nan= ∑ kkφ [] k yn[]= ∑ akkψ [] n k Các hàm cơ sở này có cùng dạng là φk [n ], chỉ khác nhau một hệ số nhân (thực/ phức)bk : ψ kk[]nnhn= φ []∗ [] vàψ kkk []nb= φ [] n thì φk [n ] được gọi là một eigenfunction của hệ rời rạc LTI với eigenvalue là bk . Trong trường hợp này, tín hiệu vào có dạng hàm mũ phức như trên là eigenfunction và H(Ω) tính tại cùng tần số của tín hiệu vào là eigenvalue tương ứng. 3. Đáp ứng trạng thái bền và đáp ứng nhất thời Ta có thể phân tích đáp ứng của hệ thống thành hai thành phần. Thành phần thứ nhất không tiến tới 0 khi n tiến tới vô cùng, được gọi là đáp ứng trạng thái bền (steady-sate response) yss[n]. Thành phần này tồn tại trong cùng khoảng thời gian tồn tại của đầu vào. Thành phần kia tiến tới 0 khi n tiến tới vô cùng, được gọi là đáp ứng nhất thời (transient response) ytr[n] Trong nhiều ứng dụng thì đáp ứng nhất thời không quan trọng vì chỉ tồn tại trong một khoảng thời gian ngắn và do vậy mà nó thường được bỏ qua. Ví dụ: Cho tín hiệu x[n] = Ae jΩn , n ≥ 0 đi vào hệ thống y[n] − ay[n −1] = x[n] (|a| < 1) Cho điều kiện đầu là y[-1]. Tìm đáp ứng của hệ, đáp ứng trạng thái bền, đáp ứng nhất thời. Tín hiệu ra là: Aa n+1e− jΩ(n+1) A y[n] = a n+1y[−1] − e jΩn + e jΩn , n ≥ 0 1− ae− jΩ 1− ae− jΩ - 80 -
Chương IV Ta có đáp ứng trạng thái bền là: A jΩn yss [n] = lim y[n] = = AH(Ω)e n→∞ 1− ae− jΩ Hai số hạng đầu của y[n] giảm về 0 khi n tiến tới vô cùng. Đó là đáp ứng nhất thời: Aa n+1e − jΩ(n+1) y [n] = a n+1y[−1] − e jΩn , n ≥ 0 tr 1− ae− jΩ Tổng quát, khi tín hiệu vào là: M x[]nXz= n ∑ k=1 kk Bằng cách xếp chồng, ta tìm được đáp ứng trạng thái bền như sau: M yn[]= XHzz ( )n . sskkk∑ k=1 Ví dụ: 3 n Cho đầu vào xn[]= ()4 , và hn[]=. (5)[]n un Tìm đáp ứng trạng thái bền. n ⎛⎞⎛⎞33 ynss[]= H⎜⎟⎜⎟ ⎝⎠⎝⎠44 4.5.4 Hệ LTI là bộ lọc tần số Bộ lọc (filter) là một hệ thống xử lý tín hiệu bằng cách thay đổi các đặc trưng tần số của tín hiệu theo một điều kiện nào đó. Nói cách khác, bộ lọc thay đổi phổ của tín hiệu vào X(Ω ) theo đáp ứng tần số H(Ω)để tạo ra tín hiệu ra có phổ là: Y(Ω) = X(Ω)H(Ω ) . Đáp ứng tần số ở đây đóng vai trò là một hàm trọng số hay một hàm thay đổi dạng phổ đối với các thành phần tần số khác nhau trong tín hiệu vào. Khi xét theo quan điểm này thì bất kỳ một hệ LTI nào cũng có thể được xem là một bộ lọc tần số, ngay cả khi nó không ngăn một vài hay tất cả các thành phần tần số trong tín hiệu vào. Do vậy ta có thể đồng nhất hai khái niệm bộ lọc tần số và hệ LTI. Trong môn học này, ta dùng thuật ngữ “bộ lọc” là để chỉ các hệ LTI thực hiện chức năng chọn lọc tín hiệu theo tần số. Bộ lọc cho các thành phần tần số của tín hiệu trong một dải tần nào đó đi qua và ngăn không cho các thành phần tần số khác đi qua. Dải tần số cho qua gọi là dải thông (passband) và dải tần số không cho qua gọi là dải chắn (stopband/block-band). Tần số giới hạn giữa dải thông và dải chắn gọi là tần số cắt (cut-off frequency) - 81 -
Chương IV Cách mô tả bộ lọc đơn giản nhất là biểu diễn dạng của nó trong miền tần số. Đó chính là đáp ứng tần số, gồm đáp ứng biên độ và đáp ứng pha. Xét bộ lọc có dải thông là (Ω1 ,Ω 2 ) . Nếu đây là bộ lọc lý tưởng thì đáp ứng tần số có dạng như sau: ⎧Ce − jΩn0 , Ω < Ω < Ω H(Ω) = ⎨ 1 2 ⎩0, Ω ≠ ở đây C và n0 là hằng số. Tín hiệu ra bộ lọc lý tưởng có dạng: − jΩn0 Y(Ω) = X(Ω)H(Ω) = CX(Ω)e , Ω1 < Ω < Ω 2 y[n] = Cx[n − n 0 ] Ta thấy tín hiệu ra đơn giản chỉ là tín hiệu vào bị thay đổi một hệ số nhân và bị trễ đi một khoảng thời gian. Sự thay đổi biên độ và trễ này không làm méo tín hiệu. Vậy bộ lọc lý tưởng là bộ lọc có đáp ứng biên độ có dạng chữ nhật và đáp ứng pha là tuyến tính trong dải thông: | H(Ω) |= C, Ω < Ω < Ω 1 2 θ(Ω) = −Ωn 0 , Ω1 < Ω < Ω 2 Có rất nhiều loại bộ lọc khác nhau với rất nhiều ứng dụng khác nhau, trong đó thông dụng nhất là bộ lọc thông thấp, thông cao, thông dải và chắn dải. Hình sau vẽ các đáp ứng biên độ của 4 loại bộ lọc thông dụng. - 82 -
Chương IV Các đáp ứng biên độ trên không có dạng chữ nhật vì đây không phải là bộ lọc lý tưởng. Giữa dải thông và dải chắn có một dải chuyển tiếp (transition band). Độ lợi (gain) của bộ lọc tại một tần số nào đó là giá trị của đáp ứng biên độ tại tần số đó. Tần số cắt là tần số tại điểm mà độ lợi là 1/ 2 của giá trị lớn nhất. Bộ lọc càng tiến gần đến bộ lọc lý tưởng hơn khi độ dốc của bộ lọc càng lớn, dải chuyển tiếp càng nhỏ. Điều này yêu cầu bậc của bộ lọc phải lớn. Ta sẽ quay lại tìm hiểu kỹ hơn về bộ lọc và thiết kế bộ lọc sau này. - 83 -
Chương V Chương 5 PHÉP BIẾN ĐỔI FOURIER RỜI RẠC VÀ ỨNG DỤNG Từ chương trước, ta đã thấy ý nghĩa của việc phân tích tần số cho tín hiệu rời rạc. Công việc này thường được thực hiện trên các bộ xử lý tín hiệu số DSP. Để thực hiện phân tích tần số, ta phải chuyển tín hiệu trong miền thời gian thành biểu diễn tương đương trong miền tần số. Ta đã biết biểu diễn đó là biến đổi Fourier X(Ω) của tín hiệu x[n]. Tuy nhiên, X(Ω ) là một hàm liên tục theo tần số và do đó, nó không phù hợp cho tính toán thực tế. Hơn nữa, tín hiệu đưa vào tính DTFT là tín hiệu dài vô hạn, trong khi thực tế ta chỉ có tín hiệu dài hữu hạn, ví dụ như một bức ảnh, một đoạn tiếng nói Trong chương này, ta sẽ xét một phép biến đổi mới khắc phục được các khuyết điểm trên của DTFT. Đó là phép biến đổi Fourier rời rạc DFT (Discrete Fourier Transform). Đây là một công cụ tính toán rất mạnh để thực hiện phân tích tần số cho tín hiệu rời rạc trong thực tế. Nội dung chính chương này gồm: - DTFT của tín hiệu rời rạc tuần hoàn. Đây là phép biến đổi trung gian để dẫn dắt đến DFT - DFT thuận và ngược - Các tính chất của DFT - Một số ứng dụng của DFT - Thuật toán tính nhanh DFT, gọi là FFT 5.1 PHÉP BIẾN ĐỔI FOURIER CỦA TÍN HIỆU RỜI RẠC TUẦN HOÀN 5.1.1 Khai triển chuỗi Fourier cho tín hiệu rời rạc tuần hoàn Nhắc lại khai triển chuỗi Fourier cho tín hiệu liên tục tuần hoàn: ∞ jkω0 t xt( )= ∑ aek synthesis equation k =−∞ 1 − jkω0 t axtedtk = ( ) analysis equation T ∫T Tương tự, ta có khai triển chuỗi Fourier cho tín hiệu rời rạc tuần hoàn (còn được gọi là chuỗi Fourier rời rạc DFS- Discrete Fourier Serie) như sau: jkΩ0 n xn[ ]= ∑ aek synthesis equation kN∈ 1 −Ωjk0 n axnek = ∑ [ ] analysis equation N nN∈ Khác với khai triển chuỗi Fourier cho tín hiệu liên tục tuần hoàn, phép lấy tích phân bây giờ được thay bằng một tổng. Và có điểm khác quan trọng nữa là tổng ở đây là tổng hữu hạn, lấy trong một khoảng bằng một chu kỳ của tín hiệu. Lý do là: 2π 2π 2π jk n jk n j(k+N) n e jkΩ0n = e N = e N .e jk2πn = e N = e j(k+N)Ω0n - 88 -
Chương V 5.1.2 Biểu thức tính biến đổi Fourier của tín hiệu rời rạc tuần hoàn Ta có hai cách để xây dựng biểu thức tính biến dổi Fourier của tín hiệu rời rạc tuần hoàn như sau: 1. Cách thứ nhất: Ta bắt đầu từ tín hiệu liên tục tuần hoàn. Ta có: F jtω0 e ←→2(πδω − ω0 ) Nên: ∞ F ∞ jkω0t x[n] = ∑a k e ←→X(ω) = 2π ∑a k δ(ω − kω0 ) k=−∞ k=−∞ Vậy, phổ của tín hiệu tuần hoàn là phổ vạch (line spectrum), có vố số vạch phổ với chiều cao là 2πa k nằm cách đều nhau những khoảng là ω0 trên trục tần số ω Bây giờ chuyển sang tìm biến đổi Fourier của tín hiệu rời rạc tuần hoàn: Trước hết, ta tìm DTFT của e jnΩ0 . Ta có thể đoán là DTFT của e jnΩ0 cũng có dạng xung tương tự như DTFT của e jω0t , nhưng khác ở điểm DTFT này tuần hoàn với chu kỳ 2π: F ∞ jnΩ0 DT:←→Ω−Ω+ e2(π ∑ δπ0 2) l l=−∞ Ta có thể kiểm tra lại điều này bằng cách lấy DTFT ngược: 1 x[]nXed= (ΩΩ )jnΩ 2π ∫ =−∞ ∞ = 2()πδ∑ akk Ω− Ω0 (do ak tuần hoàn) k =−∞ - 89 -
Chương V 2π Với Ω=0 N , ta có: F ∞ 2π k xn[ ] periodic with period N↔Ω− 2πδ∑ ak ( ) k=−∞ N với ak là hệ số của chuỗi Fourier, tổng được lấy trong một chu kỳ của tín hiệu. 1 − jnkN2π / axnek = ∑ [] N nN∈ 1 nN0 +−1 = ∑ xne[]−/jnkN2π N nn= 0 Ví dụ: Tìm DTFT của dãy xung rời rạc sau: ∞ p[]nnkN= ∑ δ [−. ] k =−∞ Cuối cùng ta có: ∞∞22ππk pn[]=−↔Ω−=Ω∑∑δδ [ n kN ] ( ) P ( ) kk=−∞NN =−∞ 2π Như vậy, DTFT của dãy xung rời rạc là tập vô số xung rời rạc có chiều cao là và có N 2π khoảng cách giữa hai xung cạnh nhau là N - 90 -
Chương V 2. Cách thứ hai: Ta có thể rút ra kết quả DTFT của tín hiệu rời rạc tuần hoàn như trên nhưng bằng cách khác. Ta xét một chu kỳ của tín hiệu tuần hoàn x[]n , ký hiệu là: x0[]n : ⎧xn[], 0≤≤ n N − 1 xn0[]= ⎨ ⎩ 0otherwise, . Sau đó tính DTFT của x0[]n ∞−N 1 − jnΩ−Ω jn Xxnexne00(Ω= )∑∑ [] = 0 [] nn=−∞ =0 Viết lại x[n ] dưới dạng tổng của vô số chu kỳ x0[]n : ∞∞ ∞ x[]n=−=∗−=∗−∑∑ xnkN00 [ ] xn []δδ [ nkNxn ] 0 [] ∑ [ nkN ] kk=−∞ =−∞ k =−∞ Theo tính chất chập tuyến tính ta có: F xn[]=∗←→ΩΩ=Ω x00 [] n pn [] X ( ) P ( ) X ( ) Thay P()Ω vừa tìm được trong ví dụ trên vào biểu thức này, ta được: ⎛⎞22ππk XX()Ω=0 () Ω⎜⎟∑ δ ( Ω− ) ⎝⎠NNk 22π ππkk 2 =Ω−∑ X 0 ()(δ )(t/c nhân với một xung) NNk N 2π k ở đây X 0 ()N có N giá trị phân biệt, nghĩa là k = 0,1,2, , N − 1. Biểu thức tính DTFT ngược là: 112222π ππ∞ kk π x[]nXed=ΩΩ= ( )jnΩΩ [ X ( )(δ Ω−Ω )] ed jn ∫∫20π ∑ 0 22ππNNNk =−∞ ∞−N 1 12ππkk2π 2 12 π kjkn2π =Ω−Ω=X ()δ ( )edjnΩ X () eN ∑∑00∫0 NNkk=−∞ N NN =0 Nếu so sánh với công thức chuỗi Fourier ở trên, ta được: 1 ⎛ 2πk ⎞ a k = X 0 ⎜ ⎟ với k = 0,1,2, , N −1 N ⎝ N ⎠ - 91 -
Chương V Tóm lại, ta có: ∞ x[]nxn=∗0 []∑ δ [ nkN − ] k=−∞ N −1 − jnΩ Xxne00()Ω=∑ [] n=0 22π ∞ ππkk 2 XX()Ω=∑ 0 ( )(δ Ω− ) NNNk =−∞ N −1 jkn2π 12π k N x[]nXe= ∑ 0 ( ) NNk =0 12π k aX= () k NN0 Vậy, để tính DTFT X ()Ω của tín hiệu x[]n rời rạc tuần hoàn với chu kỳ N , ta tiến hành theo các bước sau đây: 1. Bắt đầu với một chu kỳ x0[]n của tín hiệu x[n ], lưu ý x0[]n không tuần hoàn 2. Tìm DTFT của tín hiệu không tuần hoàn trên: ∞ Xxne()Ω= []− jnΩ 00∑ n=−∞ 2π k 3. Tính X 0 ()Ω tại các giá trị Ω=N ,k N =01 , , , − 1 4. Từ đây có DTFT của tín hiệu tuần hoàn theo như công thức vừa tìm: 22π ∞ ππkk 2 XX()Ω=∑ 0 ( )(δ Ω− ) NNNk =−∞ Ví dụ: Cho xn[]= 1. Tìm X ()Ω - 92 -
Chương V Ví dụ: Cho xn0[]=+−+−δ [] nδδ [ n 1]2[ n 3]. Giả sử N = 4 . Tìm X 0 ()Ω và X ()Ω và xác định 4 giá 2π k trị phân biệt của X 0 ()N . Ví dụ: Cho tín hiệu tuần hoàn x [n ] với chu kỳ N = 3 và một chu kỳ là: xn0[]= δ [] n+− 2[δ n 2]. Tìm X 0 ()Ω và X ()Ω . Kiểm tra kết quả bằng cách tính DTFT ngược để khôi phục lại x[]n . - 93 -
Chương V Ví dụ: Cho tín hiệu tuần hoàn yn [ ] với chu kỳ N = 3 và một chu kỳ là: yn0[]= δ [] n+−+− 2[δδ n 1]3[ n 2]. Tìm Y0 ()Ω và Y()Ω . Kiểm tra kết quả bằng cách tính DTFT ngược để khôi phục lại yn[]. 5.2 PHÉP BIẾN ĐỔI FOURIER CỦA TÍN HIỆU RỜI RẠC DÀI HỮU HẠN 5.2.1 Biểu thức tính biến đổi Fourier rời rạc thuận của tín hiệu rời rạc tuần hoàn Trong mục trên, ta xét một chu kỳ x0[]n của tín hiệu tuần hoàn x[]n . Ta có thể xem phần chu kỳ này có được bằng cách lấy cửa số (windowing) tín hiệu dài vô hạn x[n ]: x0[]nxnwn= []R [] Với wnR [ ] là cửa số chữ nhật (ở đây nó còn được gọi là cửa sổ DFT): ⎧1011, nN=,,L , − wnR[]= ⎨ ⎩0otherwise, x0[]nxnwn= []R [] chỉ là các mẫu của x[]n nằm giữa n = 0 và nN= −.1 (không quan tâm đến các mẫu nằm ngoài cửa sổ). Ta có thể tính DTFT của x0[]n như sau: ∞∞N −1 − jnΩ−Ω−Ω jn jn Xxnxnexnwnexne000(Ω= ) DTFT([]) =∑∑ [] = []R [] = ∑ [] nn=−∞ =−∞ n =0 Vậy, NN−−11 − jnΩ−Ω jn Xxnexne00(Ω= )∑∑ [] = [] nn==00 Bây giờ ta tiến hành lấy mẫu X 0 ()Ω để lưu trữ trên máy tính. Do X 0 ()Ω liên tục và tuần hoàn với chu kỳ 2π nên chỉ cần các mẫu ở trong dải tần số cơ bản. Để thuận tiện, ta lấy N mẫu - 94 -
Chương V cách đều nhau trong đoạn [0, 2π ) : 0, 2π / N, 4π / N, K, (N −1)2π / N Nói cách khác, các điểm đó là: 2π k Ω =,=,,,−N k N01 1 Ta định nghĩa phép biến đổi Fourier rời rạc DFT (Discrete Fourier Transform) như sau: 2π k Xk[]= X ( ) với k = 0, 1, , N −1 0 N K X[k] được gọi là phổ rời rạc (discrete spectrum) của tín hiệu rời rạc. Lưu ý 1: X[k] là hàm phức theo biến nguyên, có thể được biểu diễn dưới dạng: X[k] =| X[k] | e jθ[k] ở đây |X[k]| là phổ biên độ và θ[k ] phổ pha. Lưu ý 2: 2π Độ phân giải (resolution) của phổ rời rạc là N vì ta đã lấy mẫu phổ liên tục tại các điểm 2π 2π cách nhau N trong miền tần số, nghĩa là: ∆Ω= N . Ta cũng có thể biểu diễn độ phân giải theo tần số tương tự f. Ta nhớ lại quan hệ: f F = f s Do đó: f ∆f = s N Lưu ý 3: 2π k Nếu ta xem xét các mẫu của X 0 ()Ω là N với k = −∞ đến ∞ thì ta sẽ thấy DFT chính là một chu kỳ của DFS, nhưng DFT hiệu quả hơn nhiều so với DFS bởi vì số mẫu của DFT là hữu hạn: - 95 -
Chương V 2π k Xk[]= X (Ω|Ω= ) , k = 01 ,, , N − 1 0 N L N −1 xne[]−Ωjn =|∑ Ω=2π k ,kN =01 , , , − 1 N L n=0 N −1 − j 2πkn =,=,,,−∑ xne[]N k 01L N 1 n=0 Để cho gọn, ta ký hiệu: 2π − j N WN = e Khi không cần để ý đến N, ta có thể viết đơn giản W thay cho WN Vậy, N −1 kn Xk[]= ∑ xnW []N ,=,,, k 01L N − 1 n=0 là DFT của dãy x0[]n . lấy cửa sổ từ x[n] Ví dụ: Tính DFT của x[n] = u[n] − u[n − N] NN−−11− jk2π ∑ ()eWN nkn= ∑ nn==00 Suy ra DFT của xn[ ]=, 1 n = 0 ,, 1L ,. 7 Ví dụ: ⎧10,=n Cho xn[]= ⎨ . Tìm X [kk ], =,,, 0 1 7 ⎩017,=,,n - 96 -
Chương V - 97 -
Chương V Ví dụ: Cho yn[ ]=−δ [ n 2] và N = 8 . Tìm Yk [ ] Ví dụ: 2π − pn − j N Cho xn[]=,=,,,− cWN n 01 N 1, với p là một số nguyên p N∈[0,, 1 , − 1] và WeN = Tìm DFT của x[n ]. 5.2.2 Biểu thức tính biến đổi Fourier rời rạc ngược Trong mục này, ta sẽ đi thiết lập công thức khôi phục x[n ] từ X[]k . Sự khôi phục này được gọi là tổng hợp hay DFT ngược (IDFT) Từ biểu thức tính DTFT ngược được thiết lập trong mục 5.2.1 và do tính tương hỗ giữa miền thời gian và tần số, ta có thể suy ra biểu thức tính IDFT như sau: N −1 1 −kn xn[]= ∑ X [] kWN ,=,,, n 01 N − 1 N k =0 - 98 -
Chương V Sau đây ta sẽ chứng minh điều này đúng: NN−−11 1 kl− kn xn[]= ∑∑ xlW [] NN W N kl==00 1 NN−−11 = xl[] Wkl()− n ∑∑N N lk==00 Ta có N −1 ⎧Nln, = kl()− n ∑WN = ⎨ k=0 ⎩ 0, ln≠ Thay kết quả này vào x[n] ta có được biểu thức tính IDFT trên là đúng 11NN−−11 N − 1 x[nxlWxlNnl ]==− []kl()− n []δ [ ] NN∑∑N ∑ lk==00 l = 0 1 ==([])[]Nx n x n N Ví dụ: Tìm IDFT của X[]kk=, 1 = 01 ,, , 7. Ví dụ: Cho xn[]=+δ [] n 2[δδδ n −+−+− 1]3[ n 2] [ n 3] và N = 4 , tìm X[]k . - 99 -
Chương V Ví dụ: Cho Xk[ ]=+− 2δ [ k ] 2δ [ k 2] và N = 4 , tìm x [n ]. 5.2.3 Chọn số mẫu tần số N Qua mục 5.2.1 ta thấy biểu thức tính DFT được thành lập từ việc lấy mẫu DTFT với số mẫu là N. Số mẫu N này cũng chính là số mẫu của tín hiệu rời rạc trong miền thời gian hay là độ dài của cửa sổ DFT, nói ngắn gọn là số mẫu tần số bằng số mẫu thời gian. Ví dụ: Cho tín hiệu x[n] như hình bên. Tính rồi vẽ hai loại phổ biên độ | X(Ω) | và |X[k]| trên đồ thị. Xem đồ thị ta thấy rõ ràng rằng: các mẫu |X[k]| bằng với | X(Ω) | tại cùng tần số. - 100 -
Chương V Việc chọn N ảnh hưởng đến độ phân giải của phổ rời rạc. Chọn N càng lớn, độ phân giải càng tốt, nghĩa là khoảng cách giữa hai vạch phổ cạnh nhau X[k] và X[k+1] càng nhỏ, nghĩa là đường bao của phổ rời rạc X[k] càng gần với hình ảnh của phổ liên tục | X(Ω) | . Để việc tăng N không làm ảnh hưởng đến kết quả, ta kéo dài tín hiệu trong miền thời gian ra bằng cách chèn thêm các mẫu bằng 0 (zero-padding) vào phía cuối của tín hiệu. Ví dụ: Cho xn[]=−− un [] un [ 5]. Tìm X[k] với N như sau: (a) N = 5. - 101 -
Chương V (b) N = 10 5.2.4 Các tính chất của biến đổi Fourier rời rạc Hầu hết các tính chất của DFT tương tự như các tính chất của DTFT, nhưng có vài điểm khác nhau. Điểm khác nhau đó là do DFT chính là một chu kỳ trích ra từ dãy DFS tuần hoàn với chu kỳ N. Bây giờ ta thay đổi ký hiệu, ký hiệu x%[]n là dãy tuần hoàn chu kỳ N, x [n ] là một chu kỳ trích ra từ x%[]n : ∞ x%[]nxn=∗ []∑ δ [ nkN − ] k=−∞ ∞ = ∑ x[n − kN] k=−∞ - 102 -
Chương V 1. Dịch vòng Nếu DFT x[]nXk↔ [] thì DFT 2π km − j N x[n − m]↔ W X[k] với WeN = Ví dụ: Dịch vòng đi m mẫu sẽ cho kết quả trùng với dich vòng đi (m mod N) mẫu. 2. Tổng chập vòng DFT, N x12[]nxn⊗↔ [] XkXk 12 [] [] ở đây: N −1 yn[]=⊗= xn12 [] xn []∑ xpxnp 12mod [ ] [ − ] N p=0 Dấu ⊗ là ký hiệu tổng chập vòng. Nhắc lại công thức tổng chập tuyến tính: ∞ yn[]=∗= x12 [] n x [] n∑ x 12 [ px ] [ n − p ] p=−∞ - 103 -
Chương V Thoạt nhìn, ta thấy biểu thức tính tổng chập vòng rất giống tổng chập tuyến tính. Tuy nhiên, hai phép chập đó khác nhau ở những điểm sau đây: - Phép chập vòng chỉ áp dụng cho hai dãy dài hữu hạn và bằng nhau, kết quả cũng là một dãy cùng chiều dài, nghĩa là x1[]n , x2[]n , and yn[] đều có chiều dài là N. Trong khi đó, phép chập tuyến tính áp dụng cho hai dãy có chiều dài bất kỳ: nếu x1[]n dài N , x []n dài N thì yn[]dài x1 2 x1 - Phép dịch trong tổng chập vòng là phép dịch vòng, khác với phép dịch trong tổng chập tuyến tính là phép dịch tuyến tính. Vì những điểm khác nhau trên nên kết quả của tổng chập vòng và tổng chập tuyến tính của cùng hai dãy có thể không trùng nhau. Tuy nhiên, ta có cách làm cho hai kết quả đó trùng nhau như sau: - Chuyển tổng chập tuyến tính sang miền tần số: Y(Ω) = X1 (Ω).X 2 (Ω) - Lấy mẫu Y(Ω) với số mẫu là N ≥ N = N + N − 1, ta được: y x1 x2 Y[k] = X[k].H[k] - Tính DFT ngược, ta được: y[n] = x[n] * h[n] ở đây chiều dài của y[n] , x[n] và h[n] là: N ≥ N = N + N −1 y x1 x2 Như vậy, bằng cách kéo dài các tín hiệu x1[n] và x2[n] ra đến chiều dài N ≥ N = N + N −1 rồi lấy chập vòng, ta được hai kết quả của tổng chập vòng và y x1 x2 chập tuyến tính là trùng nhau: y[n] = x1[n]∗ x 2 [n] = x1[n] ⊗ x 2 [n] Ví dụ: Tìm x12[]nxnzn⊗= [] [], với xn1[]= [1,2,0,0], xn2[ ]= [1,1,0,0] và N = 4. Kết quả này có trùng với tổng chập tuyến tính không? - 104 -
Chương V Ví dụ: Tìm yn[]=⊗ xn [] xn [], với xn[ ]= [1,0,1,1] trong hai trường hợp: (a) N = 4 (b) N = 8 N bằng bao nhiêu là đủ để tổng chập vòng trùng với tổng chập tuyến tính? 5.3 MỘT SỐ ỨNG DỤNG CỦA DFT Phần này sẽ giới thiệu sơ lược về một số ứng dụng của DFT trong thực tế 5.3.1 Phân tích phổ tín hiệu Trong chương trước, ta đã biết được ý nghĩa của phổ trong việc phân tích tín hiệu, từ phổ của tín hiệu ta biết được một số thông tin cần thiết. Để tìm phổ của tín hiệu (cả liên tục và rời rạc), ta cần phải biết giá trị của tín hiệu tại tất cả các thời điểm. Tuy nhiên trong thực tế, do ta chỉ quan sát được tín hiệu trong một khoảng thời gian hữu hạn nên phổ tính được chỉ là xấp xỉ của phổ chính xác. DFT được ứng dụng rất hiệu quả trong việc tính toán phổ xấp xỉ này. Trong thực tế, nếu tín hiệu cần phân tích là tín hiệu liên tục, trước hết ta cho tín hiệu đó đi qua một bộ lọc chống chồng phổ rồi lấy mẫu với tần số Fs ≥ 2B, với B là băng thông của tín hiệu sau khi lọc. Như vậy, tần số cao nhất chứa trong tín hiệu rời rạc là Fs/2. Sau đó, ta phải giới hạn chiều dài của tín hiệu trong khoảng thời gian T0 = LT, với L là số mẫu và T là khoảng cách giữa hai mẫu. Cuối cùng, ta tính DFT của tín hiệu rời rạc L mẫu. Như đã trình bày trên, muốn tăng độ phân giải của phổ rời rạc, ta tăng chiều dài của DFT bằng cách bù thêm số 0 vào cuối tín hiệu rời rạc trước khi tính DFT. Ví dụ sau đây minh họa một ứng dụng của DFT trong việc phân tích phổ tín hiệu điện tâm đồ (ECG): Hình vẽ (a) là đồ thị của 11 nhịp tim của một bệnh nhân. 11 nhịp tim này xuất hiện trong khoảng thời gian 9 giây, tương đương với 11/9 = 1.22 nhịp trong một giây, hay 73 nhịp trong một phút. Hình (b) là chi tiết nửa đầu của nhịp tim thứ tư. Hình (c) là một đoạn phổ biên độ DFT có được sau khi lấy mẫu đoạn 11 nhịp tim (a) với tần số lấy mẫu là 8 kHz. Nhìn (c) ta thấy có hai điểm biên độ cao nhất xuất hiện ở tần số 88 Hz - 105 -
Chương V và 235 Hz. Để tìm hiểu phổ kỹ hơn, ta tính DFT của tín hiệu ở hình (b)- phổ này thể hiện ở hình (d), ở đây ta thấy rõ hai điểm biên độ cao nhất ở tần số 88 Hz và 235 Hz bên trong mỗi nhịp tim. Tuy nhiên, ta không thấy tần số lặp lại nhịp tim là 1.22 Hz trong DFT hình (c). Hình (e) giải thích rõ hơn điều này. Nó là phiên bản mở rộng của các đỉnh nhọn trong dải tần từ 60 Hz đến 100 Hz. Trong khi tần số 1.22 Hz quá nhỏ nên không thấy rõ trong hình (c) thì trong hình (e) này, ta thấy rõ các hài của tần số 1.22 Hz và thấy rõ khoảng cách giữa hai đỉnh nhọn là 1.22 Hz. 5.3.2 Tính tín hiệu ra hệ thống rời rạc LTI Tín hiệu ra hệ thống rời rạc LTI được tính bằng cách chập tín hiệu vào với đáp ứng xung của hệ thống: y[n] = x[n]∗ h[n] Ta có hai cách để tính tổng chập này: một là tính trực tiếp, hai là tính thông qua tổng chập vòng như phân tích trong mục 5.2.4. Cách tính qua tổng chập vòng sẽ có lợi hơn về mặt thời gian. Lý do là tổng chập vòng có thể tính thông qua DFT, mà DFT có thể được tính nhanh nhờ thuật toán tính nhanh FFT. Để tính y[n], ta thực hiện theo các bước sau đây: - Kéo dài x[n] đến độ dài N = Nx + Nh - 1 - 106 -
Chương V - Kéo dài h[n] đến độ dài N = Nx + Nh - 1 - Tính DFT của x[n] N mẫu, ta được X[k] - Tính DFT của h[n] N mẫu, ta được H[k] - Nhân X[k] với H[k], ta được Y[k]: Y[k] = X[k].H[k] - Tính DFT ngược của Y[k], ta được y[n] Việc tính DFT và DFT ngược được thực hiện nhờ một thuật toán tính nhanh DFT, gọi là FFT (Fast Fourier Transform). Phần sau sẽ trình bày về thuật toán FFT. 5.4 TÍNH NHANH DFT BẰNG THUẬT TOÁN FFT DFT được ứng dụng rộng rãi trong xử lý tín hiệu rời rạc/ số nên nhiều nhà toán học, kỹ sư đã rất quan tâm đến việc rút ngắn thời gian tính toán. Năm 1965, Cooley và Tukey đã tìm ra thuật toán tính DFT một cách hiệu quả gọi là thuật toán FFT. Cần lưu ý FFT không phải là một phép biến đổi mà là một thuật toán tính DFT nhanh và gọn hơn. Để đánh giá hiệu quả của thuật toán, ta sử dụng số phép tính nhân và cộng phức. Số phép nhân và cộng phức liên quan trực tiếp đến tốc độ tính toán khi thuật toán được thực hiện trên các máy tính hay là các bộ xử lý chuyên dụng. 5.4.1 Hiệu quả tính toán của FFT Công thức tính DFT của dãy dài N: N −1 X[]kxnW= ∑ [] kn n=0 Qua đây ta thấy để tính mỗi giá trị DFT ta cần N phép nhân và cộng phức. Để tính toàn bộ DFT ta cần N 2 phép nhân và cộng phức. Tuy nhiên, nếu tính DFT nhờ thuật toán FFT thì số phép nhân và cộng phức giảm xuống chỉ N còn 2 log2 N . Ví dụ như N ==210 1024 thì nếu tính trực tiếp DFT cần N 2206==210 phép nhân và cộng N phức, trong khi tính qua FFT thì số phép nhân và cộng phức giảm xuống chỉ còn 2 log2 N = 5120. Số phép tính giảm đi gần 200 lần! Hình sau cho thấy rõ hiệu quả của thuật toán FFT: 10000 Number of Operations 8000 6000 4000 2000 0 0 20 40 60 80 100 N, Size of DFT or FFT - 107 -
Chương V Có nhiều thuật toán FFT khác nhau bao gồm FFT phân chia theo thời gian và FFT phân chia theo tần số. Trong phần này ta tập trung vào thuật toán FFT cơ số 2 ( Ni= 2i where is an integer ) phân chia theo thời gian. 5.4.2 Nguyên tắc của FFT Nguyên tắc cơ bản mà các thuật toán FFT đều dựa vào là phân chia DFT N mẫu thành các DFT nhỏ hơn một cách liên tục: i N Với N = 2 , đầu tiên ta phân chia DFT N mẫu thành các DFT 2 mẫu, sau đó phân chia DFT N N 2 mẫu thành DFT 4 mẫu và cứ tiếp tục như thế cho đến khi được các DFT dài N = 2. Việc tính DFT nhỏ hơn rõ ràng sẽ cần ít phép tính nhân và cộng phức hơn. Trước tiên, chia x[]n thành các dãy con chẵn và lẻ: X[]kxnWxnW=+∑ []kn∑ [] kn nneven odd Đặt nm= 2 với n chẵn và nm=+21 với n lẻ: NN 22−−11 Xk[]=++=∑∑ x [2] mW2(21)mk x [2 m 1] W k m+ mm==00 NN 22−−11 ∑∑xmW[2 ](22 )mk+ W k xm [2+= 1]( W ) mk mm==00 kk X[]kXkWXkGkWHk=+eo [] [] =+ [] [] N X e[]k và X o [k ] là DFT 2 mẫu. N Tiếp theo chia dãy con 2 mẫu là x[2m] làm đôi bằng cách đặt mp= 2 : NN 44−−11 42kp k 4 kp Xke[ ]=++=∑∑ xpW [4 ]( ) W xp [4 2]( W ) pp==00 Thực hiện tương tự như vậy cho dãy con x[2m+1] Ví dụ: N = 8 Quá trình phân chia DFT 8 mẫu thành các DFT nhỏ hơn được minh họa trên lưu đồ. Đầu tiên, chia x[n] thành 2 dãy con, dãy thứ nhất là dãy chẵn x[0], x[2], x[4], x[6] và dãy thứ hai là dãy lẻ x[1], x[3], x[5], x[7]. Tiếp theo, chia dãy chẵn thành 2 dãy con, dãy thứ nhất là x[0], x[4] và dãy thứ hai là x[2], x[6]. Tương tự, dãy lẻ được chia thành 2 dãy con, là dãy x[1], x[5] và dãy x[3], x[7]. Các DFT 2 mẫu được tính đơn giản như sau: 2π 1 − j G[k] = ∑g[n]W nk , 0 ≤ k ≤ 1, W = e 2 = −1 n=0 ⇒ G[0] = g[0]W 0.0 + g[1]W1.0 = g[0] + g[1] (chỉ cần phép cộng và trừ) G[1] = g[0]W 0.1 + g[1]W1.1 = g[0] − g[1] - 108 -
Chương V - 109 -
Chương V FFT cơ sở: A “Butterfly” 0 r WN (r + N/2) WN (r + N/2) N/2 r r r Lưu ý: WN = WN WN = -1 WN = - WN , do đó có thể vẽ lại lưu đồ FFT đơn giản như sau: - 110 -
Chương V Phụ lục 1 Summary: The Common Types of Fourier Transforms Continuous in Time x()t Discrete in Time x[]n = Aperiodic in Frequency = Periodic in Frequency Fourier Series (FS): Discrete Fourier Series (DFS) and Discrete Fourier Transform Periodic in (DFT): 1 − jkω0 t Time, axtedtk = () T ∫T N −1 kn ∞ Xk[]= xnW []N ,0≤≤ k N − 1 = Discrete jkω t ∑ 0 n=0 xt()= ∑ aek in k=−∞ Frequency N −1 1 −kn xn[]= ∑ X [] kWN ,0≤≤ n N − 1 N k =0 2π − j N where WeN = . Aperiodic Fourier Transform (FT): Discrete-Time Fourier in Time, ∞ Transform (DTFT): X ()ω = xte ()− jtω dt ∫−∞ ∞ −Ωjn = ∞ Xxne()Ω= [] x()tXedt= (ω ) − jtω ∑ Continuous ∫−∞ n=−∞ 1 in x[]nXed= (ΩΩ )jnΩ ∫2π Frequency 2π - 111 -
Chương V Phụ lục 2 Some Fourier Relationships The Fourier transform is the Laplace transform evaluated on the j∞ axis. ∞∞ XxtedtXsxtedt(ω )=== ()−−jtω ()⎡ () st ⎤ sj= ω ∫∫−∞⎣⎢ −∞ ⎦⎥s= jω The discrete-time Fourier transform is the z-transform evaluated around the unit circle. ∞∞⎡⎤ XxneXzxnx(Ω= ) []−Ωjn = () = [] − n ∑∑ze= jΩ ⎢⎥ nn=−∞⎣⎦ =−∞ ze= jΩ Discrete-time periodic signals can also be described by a Fourier Series expansion: jkΩ0 n xn[ ]= ∑ aek synthesis equation kN∈ and 1 −Ωjk0 n axnek = ∑ [ ] analysis equation N nN∈ then using the DTFT of the impulse train, P (Ω ) that we previously found, the DTFT of an arbitrary discrete-time periodic signal can be found from X 0 ()Ω the DTFT of one period x0[]n ⎛⎞22ππk XX()Ω=0 () Ω⎜⎟∑ δ ( Ω− ) ⎝⎠NNk 22π ππkk 2 =Ω−∑ X 0 ()(δ ) NNk N The DFT is simply a scaled version of the terms of one period of the discrete time Fourier transform for a periodic sequence: 2π k N −1 kn Xk[]== X0 ( )∑ xnW []N ,0 ≤≤− k N 1 N n=0 2π k for Ω=N ,k N =01 , , , − 1, i.e. only look at the N distinct sampled frequencies of X 0 ()Ω . Also important, the orthogonality of exponentials: N −1 kn ∑WNkN = δ[] n=0 2π − j N where WeN = . - 112 -