Xử Lý Tín Hiệu Số Chương IV (phần 2) - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (30 trang)

Trang chủ

Kỹ Thuật - Công Nghệ

Kĩ thuật Viễn thông

Xử lý tín hiệu số chương IV (phần 2)

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (280.29 KB, 30 trang )

Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcDFT [ x 2 (n)] = X 2 (k )DFT [ x 3 (n)] = X 3 (k )thì(4.26)X 3 (k ) = aX 1 (k ) + bX 2 (k )chú ý rằng nếu chiều dài của x1 (n) và x 2 (n) là khác nhau thìL[ x1 (n)] = N 1L[ x 2 (n)] = N 2thì ta phải chọn chiều dài của dãy x 3 (n) như sau :L[ x 3 (n)] = N 3 = max( N 1 , N 2 )và tất cả các DFT[x1(n)], DFT[x2(n)] và DFT[x3(n)] đều phải tính đến N3 mẫu. Giả sửnếu N1 < N2 thì dãy x1(n) phải được kéo dài thêm N2 – N1 mẫu không và DFT[x1(n)]phải được tính trên N3 = N2 mẫu và DFT[x2(n)] và DFT[x3(n)] cũng được tính trên N3 +N2 mẫu. Cụ thể là :X 1 (k ) =X 2 (k ) =X 3 (k ) =N1 −1∑ x (n)Wn =01N 2 −1∑xn =0n =0≡ X 1 (k ) N 3, 0 ≤ k ≤ N2 – 12(n)W Nkn2 ≡ X 2 (k ) N 3, 0 ≤ k ≤ N2 – 13(n)W Nkn2 ≡ X 3 (k ) N 3, 0 ≤ k ≤ N2 – 1N 3 −1∑xknN2để nhấn mạnh và chỉ rõ chiều dài của các dãy trong miền n và miền k ta ghi thêmchiều dài vào ký hiệu dãy như là ;x1 (n) N1 : Dãy có chiều dài N1x 2 (n) N 2 : Dãy có chiều dài N2x 3 (n) N 3 : Dãy có chiều dài N3X 1 (k ) N 3 : Dãy có chiều dài N4…b.Trễ VòngTrước hết, chúng ta nhìn lại trễ tuyến tính và trễ tuần hoàn có chu kỳ N để sosánh và rút ra kết luận của trễ vòng. Để thấy được một cách trực quan ta có ví dụ sau :Ví dụ 4.4 :Cho dãy x(n) sau :Xử Lý Tín Hiệu Số138Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạcn1−x (n ) = 40, 0≤n≤4x (n ), n còn lạiHãy tìm trễ tuyến tính x(n - 2) và x(n + 2).nGiải :Chúng ta giải bằng đồ thò cho trên hình 4.12Hình 4.12aVí dụ 4.5 :x (n − 2)Cho dãy tuần hoàn chu kỳ N = 4, ~x (n) 4 sau đây:n1−, 0≤n≤4x (n ) = 40, n còn lạinHãy tìm ~x (n − 2) 4 và ~x (n + 2) 4 , sau đó lấy ra một chukỳ của hai dãy này.Hình 4.12bx (n + 2)Giải :Chúng giải bằng đổ thò cho trên hình 4.13.n~x ( n) 4x (n )Hình 4.12cnnHình 4.13aHình 4.13b~x (n − 2) 4x ( n − 2) 4nnHình 4.13cXử Lý Tín Hiệu SốHình 4.13d139Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạc~x (n + 2) 4x (n + 2) 4nnHình 4.13eHình 4.13fĐể phân biệt được các loại trễ ta có thể ký sau :x(n – n0) : Trễ tuyến tính.~x (n − n 0 ) N : Trễ tuần hoàn chu kỳ Nx(n – n0)N : Trễ vòng với chiều dài NTừ ví dụ, ta thấy nếu trích ra một chu kỳ từ (từ 0 đến N-1) của trễ tuầ hoàn chukỳ N thì ta sẽ có trễ vòng x(n ± n0)N, so sánh với trễ tuyến tính x(n ± n0), nếu nó vượt rakhỏi (từ 0 đến N-1) thì nó sẽ vòng lại để x(n)N xác đònh trong khoảng [0, N-1], thì lúcnày trễ vòng cũng được xác đònh trong khoảng [0, N-1].Ta có thể viết như sau :x (n ) N = ~x (n ) N rect N (n )x (n ± n 0 ) N rect N (n )x (n ± n 0 ) N = ~(4.27)Hinh 4.14 sẽ minh hoạ bản chất của trễ vòng.x (n ) ≡ x (n ) 4x (n − 2)nnHình 4.14aHình 4.14bx ( n − 2) 4 = x ' ( n )nHình 4.14cXử Lý Tín Hiệu Số140Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạcx’(1)x(1)x(2)20x’(2x(0)2x’(0)033x(3)x’(3Hình 4.14dx (n + 2)x (n + 2) 4 = x '' (n )nnHình 4.14eHình 4.14fx’’(1)x(1)1x(2)230x’’ (2)x(0)2x’’(0)13x(3)0Hình 4.14gx’’ (3)Nếu ta xét trong miền k, bản chất của nó cũng tương tự :~X(k ) N = X(k ) N rect N (k )~X(k ± k 0 ) N = X(k ± k 0 ) N rect N (k )(4.28)Xét tính chất trễ trong miền n, thì trong miền k :DFT[ x (n ) N ] = X(k ) N(4.29)DFT[ x (n ± n 0 ) N ] = WNkn 0 X(n ) NChứng minh :Dựa vào cách chứng minh trong tính chất trễ, ta có :~DFT[~x (n ± n 0 ) N ] = WNkn 0 X(n ) NXử Lý Tín Hiệu Số141Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcNếu lấy hai vế ra chu kỳ [0, N-1], lúc nàyx (n − n 0 ) N = ~x (n − n 0 ) N rect N (n )~X(k ) N = X(k ) N rect N (n )Vậy ta có được :DFT[ x (n ± n 0 ) N ] = WNkn 0 X(n ) NTương tự ta cũng có tính chất trễ trong miền k.Nếu có :DFT[X(k ) N ] = x (n ) NthìDFT[X(k − k 0 ) N ] = WN− kn 0 x (n ) N(4.30)Nhận xét :Nếu trích ra một chu kỳ (từ 0 đến N -1) của dãy tuần hoàn biến đảo ~x (−n ) N thìsẽ được dãy biến đảo vòng chiểu dài hữu hạn x (−n ) N , nghóa là chiều dài hữu hạn sẽkhông vượt ra khỏi [0, N-1]. Ta có thể viết lạix (−n ) N = ~x (− n ) N rect N (n )(4.31)Ta cũng xét được trong miền k:~X(− k ) N = X(−k ) N rect N (k )(4.32)Do tính tuần hoàn của ~x (n ) , ta có~x (n ) = ~x (n + N)~x (−n ) = ~x (− n + N) = ~x(N − n)Và ta cũng có :x (−n ) N = ~x (− n )rect N (n )vàX( N − n ) N = ~x ( N − n )rect N (n )(4.33)X(−k ) N = X( N − k ) N(4.34)DFT[ x (− n ) N ] = X(− k ) N(4.35)DFT[ x ( N − n ) N ] = X( N − k ) N(4.36)Trong miền kvàc. Tính Đối XứngChúng ta có dãy chiều dài hữu hạn N x(n) N vàDFT[ x (n ) N ] = X(k ) Nthì ta có :Xử Lý Tín Hiệu Số142Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcDFT[ x * (n ) N ] = X * (− k ) NDấu * là biểu thò liên hợp phức.Chứng minh :x * (n ) N = ~x * (n ) N rect N (n )~X * (−k ) N = X(− k )rect N (n )như vậy ta có :~DFT [ x * (n) N ] = X * (−k ) Ntương tự ta cũng có :DFT [ x * (−n) N ] = X * (k )Các tính chất đối xứng của DFT đối với dãy có chiều dài hữu hạn có thể suy ratừ các tính chất của DFT đối với dãy tuần hoàn chu kỳ N, hoặc các tính chất của biếnđổi Fourier (FT) trong chương 3.Bây giờ ta xét chi tiết tính đối xứng đối với dãy phức có chiều dài hữu hạn Nx(n)N.Dãy x(n)N có thể được biểu diễn dưới dạng sau :x(n) N = Re[ x(n) N ] + j Im[ x(n) N ](4.37)x * (n) N = Re[ x(n) N ] − j Im[ x(n) N ](4.38)và :x( n) N + x * ( n) N ]Re[ x(n) N ] =2x ( n) N − x * ( n) N ]j Im[ x(n) N ] =2(4.39)(4.40)Do vậy ta có thể viết :N −1DFT {Re[ x(n) N ]} = ∑ Re[ x(n) N ]W Nkn =n =01DFT [ x(n) N + x * (n) N ]21= [ X (k ) N + X * (−k ) N ] = X e (k ) N2Xe(k)N là phần đối xứng liên hợp của X(k)N.Trong thực tế thường gặp các dãy tín hiệu thực, vì vậy ta hãy xét trường hợpriêng khi x(n)N là thực.Ta có thể biểu diễn X(k)N dưới dạng sau đây :X (k ) N = Re[ X (k ) N ] + j Im[ X (k ) N ](4.41)X (k ) N = Re[ X (k ) N ] − j Im[ X (k ) N ]1Re[ X (k ) N ] = [ X (k ) N + X * (k ) N ]21j Im[ X (k ) N ] = [ X (k ) N − X * (k ) N ]2(4.42)*Xử Lý Tín Hiệu Số143(4.43)(4.44)Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạcvà nếu x(n) là thực thì ta có : x(n)N = X*(n)NvàDFT [ x(n) N ] = DFT [ x * (n) N ]Thức là(4.45)X (k ) N = X * (−k ) NLấy liên hợp phức hai vế ta có :(4.46)X * (k ) N = [ X * (−k ) N ]* = X (−k ) Nvới biến đảo –k ta có :Re[ X (−k ) N ] =theo (4.45) và (4.46) ta có :Re[ X (−k ) N ] =Vậy với x(n) thực ta có :1[ X (−k ) N + X * (−k ) N ]21[ X * (k ) N + X (k ) N ]2(4.47)Re[ X (k ) N ] = Re[ X (−k ) N ]tương tự ta có :(4.48)Im[ X (k ) N ] = − Im[ X (− k ) N ]Bây giờ ta xét module và Argument1212X (−k ) N = [ X (k ) N X (k ) N ] = [ X (−k ) N X (−k ) N ] = X (−k ) N**(4.49)tương tựarg[ X (k ) N ] = arctgd. Im[ X (−k ) N ] Im[ X (k ) N ]= arctg − = − arg[ X (−k ) N ] (4.50)Re[ X (k ) N ]Re[X(−k)]N Tích chập vòngĐối với các dãy tuần hoàn có chu kỳ N ta đã có quan hệ sau :N −1~~x 3 ( n) = ~x1 (n)( * ) N x 2 (n) N = ∑ ~x1 ( m ) ~x 2 ( n − m)m =0và trong miền k ta có :~~~X 3 (k ) = X 1 (k ). X 2 (k )Chú ý : tất cả các dãy ở quan hệ trên đều là tuần hoàn chu kỳ N. Còn đối với dãykhông tuần hoàn có chiều dài hữu hạn N, chúng ta có thể coi chúng tương ứng với mộtchu kỳ của các dãy tuần haòn chu kỳ N, vì vậy chúng ta cũng có đònh nghóa và tính chấttương tự như đối với các dãy tuần hoàn chu kỳ N.Đònh nghóa :Xử Lý Tín Hiệu Số144Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcTích chập vòng của hai dãy không tuần hoàn x1(n)N và x2(n)N có chiều dài hữuhạn N là một dãy không tuần hoàn cũng có chiều dài hữu hạn N x3(n)N được cho bởiquan hệ sau :N −1x 3 ( n ) N = ∑ x1 ( m ) N x 2 ( n − m ) N(4.51)m=0~= x1 (n) N ( * ) x 2 (n) N(4.52)(*)N là tích chập vòng chiều dài N.Nếu trong miền n là tích chập vòng thì trong miền k ta dễ dàng chứng minh đượctính chất sau đây :(4.53)X 3 (k ) N = X 1 (k ) N . X 2 (k ) Nở đâyX 1 (k ) N = DFT [ x1 (n) N ]X 2 (k ) N = DFT [ x 2 (n) N ]X 3 (k ) N = DFT [ x 3 (n) N ]Ví dụ 4.6 :Cho hai dãy không tuần hoàn có chiều dài hữu hạn N = 4 như sau :x1 (n) 4 = δ (n − 1) n1−x 1 (n ) 4 =  4 0,0 ≤ n ≤ 4, n còn lạiHãy tính tích chập vòng chiều dài N = 4 của hai dãy này.Giải :3~x 3 ( n ) 4 = x1 ( n ) 4 ( * ) x 2 ( n ) 4 = ∑ x1 ( m ) x 2 ( n − m ) 4m =03x 3 (0) 4 = ∑ x1 (m) 4 x 2 (0 − m) 4m =03x 3 (1) 4 = ∑ x1 (m) 4 x 2 (1 − m) 4m=03x 3 (2) 4 = ∑ x1 (m) 4 x 2 (2 − m) 4m =03x 3 (3) 4 = ∑ x1 (m) 4 x 2 (3 − m) 4m=0để thấy rõ bản chất của tích chập vòng, chúng ta hãy xem quá trình tính toán và kếtquả bằng đồ thò cho trên hình 4.15.Xử Lý Tín Hiệu Số145Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạcx 1 (n ) 4 = δ (n − 1)x 2 (0 − m ) 4x 2 (n ) 4nmnHình 4.15aHình 4.15bHình 4.15cx 2 ( 2 − m) 4x 2 (1 − m) 4mmHình 4.15eHình 4.15dx 3 (n ) 4 ≡ x 2 (n − 1) 4x 2 (3 − m) 4mnHình 4.15fHình 4.15gNhận xét :Chúng ta có thể áp dụng tính chất của biểu thức (4.38) để tính tích chập vòng,đây là cách tính gián tiếp thông qua DFT, nhưng cho ta hiệu quả cao hơn. Để thấy rõ,chúng ta hãy xét ví dụ dưới đâyVí dụ 4.7 :Cho hai dãy có chiều dài hữu hạn sau đây :x 1 (n ) N = x 2 (n ) N = rect N (n )Hãy tính x 3 (n) N = x1 (n) N (*) x 2 (n) N thông qua DFT.Giải :N −1X 1 (k ) N = X 2 (k ) N = ∑ WNknn =0N=0, k =0, k còn lạip dụng biểu thức (4.53) ta có :Xử Lý Tín Hiệu Số146Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạc N2X 3 (k ) N = X 1 (k ) N .X 2 (k ) N = 0, k =0, k còn lạiĐể tìm x3(n)N ta áp dụng công thức của IDFT.x 3 (n ) N =1 N −1X 3 (k ) N WN− kn∑N k =0 1X (0) W 0= n 3 N N 0N=0, 0 ≤ n ≤ N −1, n còn lại, 0 ≤ n ≤ N −1, n còn lạiminh hoạ bằng đồ thò cho trên hình 4.16 với N = 4.x 1 (n ) 4x 2 (n ) 4nn-1 0 1 2 3-1 0 1 2 3Hình 4.16aHình 4.16bX1 (k ) 4 = X 2 (k ) 44X 3 (k ) 4164k-1 0 1 2 3Hình 4.16cx 3 (n ) 4nk-1 0 1 2 3Hình 4.16d-1 0 1 2 3Hình 4.16e4.3.3 Tích chập nhanh (hay tích chập phân đoạn)a.Tổng quanĐể ứng dụng DFT vào việc tính tích chập không tuần hoàn, tức là tích chậptuyến tính, trước hết chúng ta phải phân biệt hai trường hợp. Trường hợp thứ nhất khicác dãy chập với nhau có chiều dài gần bằng nhau và ngắn; trường hợp thứ hai khi cácdãy chập với nhau có chiều dài khác nhau.Trường hợp thứ nhất chính là trường hợp chúng ta đã nghiên cứu ở các phần trên.Nhưng trong thực tế, chúng ta thường gặp trường hợp thứ hai. Việc tính toán DFT củaXử Lý Tín Hiệu Số147Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạcdãy có chiều dài quá dài sẽ xảy ra trường hợp vượt quá dung lượng của bộ nhớ của máytính và cần phải có thời gian tính toán quá lớn không cho phép. Hơn nữa để có đượcmẫu đầu tiên của kết quả ta phải đợi kết thúc tất cả các tính toán.Để giải quyết các vấn đề trên, chúng ta phải chia tính toán ra nhiều giai đoạn.Chúng ta có hai phương pháp (Stockham nghiên cứu phát triển) nội dung như sau :-Chia dãy thành nhiều dãy con.-Chập từng dãy con một.-Tổ hợp các kết quả thành phần.-Giả sử dãy x(n) có chiều dài N, dãy h(n) có chiều dài M, và N rất lớn so vớiM(N>>M) và dãy y(n) = x(n)*h(n) có chiều dài N + M – 1 sẽ rất lớn. Vậy nếu tadùng DFT thì DFT sẽ được tính với chiều dài N + M – 1. Vậy nếu muốn dùng DFTthì ta phải phân dãy x(n) ra làm nhiều đoạn nhỏ.b.Phương Pháp 1: cộng xếp chồngGiả sử ta cần tính tích chập tuyến tínhy(n) = x(n)*h(n)L[x(n)] = NL[h(n)] = MN>>MDãy x(n) được xem như tổng của các dãy thành phần xi(n), mà L[xi(n)] = N1Tức ta có :x ( n ) N = ∑ x i ( n ) N1(4.54)ivới :x (n )x i (n ) N1 = 0, iN 1 ≤ n ≤ (i + 1) N 1 − 1, n còn lạiTa biết rằng :y( n ) = x ( n ) * h ( n ) =∞∑h ( m) x ( n − m) =m = −∞=∑i∞∑ h (m)[∑ xm = −∞∞∑ h ( m) x ( n − m) = ∑ h ( n )m = −∞i( n − m)]iiiM* x i (n ) N = ∑ y i (n ) N + M −11i(4.55)1y i (n) N1 + M −1 = h(n) M * x i (n) N1 gọi là tích chập phân đoạn, đây là tích chập tuyến tính, nếudùng DFT thì mỗi tích chập phân đoạn này ta phải tính DFT với chiều dài N1 + M – 1.Tức là ta phải tính tích chập vòng với chiều dài N1 + M – 1:y i (n) N1 + M −1 = h(n) N1 + M −1 (*) x i (n) N1 + M −11Xử Lý Tín Hiệu Số148(4.56)Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạcnhư vậy tích chập vòng này sẽ bằng tích cập tuyến tính. Thế thì h(n)M sẽ được kéo dài(N1 – 1) mẫu không và xi(n)N1 sẽ được kéo dài M –1 mẫu không.Trong miền tần số rời rạc k ta có :(4.57)Yi (k ) N1 + M −1 = H (k ) N1 + M −1 (*) X i (k ) N1 + M −11sau đó dùng IDFT để tính y i (n) N + M −11y i (n ) N1 + M −1 = IDFT[Yi (k ) N1 + M −1 ]N1 + M − 21Yi (k ) N1 + M −1 WN−1nk+ M −1∑=  N1 + M − 1 k =0 0, iN 1 ≤ n ≤ (i + 1) N 1 + M − 2, n còn lạihình 4.17 cho ta một ví dụ minh hoạ tích chập phân đoạn theo phương pháp cộng xếpchồng với M = 4, N1 = 8x (n )na) 0h (n )nb) 04x 0 (n )nc) 0Xử Lý Tín Hiệu Số7149Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạcx 1 (n )nd) 0715x 2 (n )ne) 071623 24y 0 (n )nf) 08y1 (n )ng) 08y 2 (n )nh) 0Xử Lý Tín Hiệu Số815150Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạcy( n )ni) 0Hình 4.17Nhận xét :- Nếu n1 rất dài thì ta có lợi là số lượng các đoạn sẽ ít đi, nhưng vì N1 dài nên thờigian tính toán của một đoạn sẽ tăng lên.Nếu n1 nhỏ thì ta có bất lợi là số lượng các đoạn sẽ tăng lên, nhưng lại có lợi là thờigian tính toán của một đoạn sẽ giảm đi.Vậy trong thực tế, chúng ta phải chọn giá trò của N1 tối ưu so với chiều dài M của h(n).Giá trò N1 tối ưu được chọn theo bảng 4.2, gọi là bảng Helms.Bảng 4.2Chiều dài của h(n) _ M≤ 1011 – 1718 – 2930 – 5253 – 4995 – 171172 – 310311 – 575576 – 10501051 – 20002001 – 38003801 – 74007401 – 14800…c.Chiều dài của DFT _ N1 + M – 13264128256512102420484096819216.38432.76865.536131.072…Phương pháp 2 : Đặt kề nhauChúng ta có một phương pháp nữa để tính tích chập nhanh gọi là phương phápđặt kề nhau, cũng giống như phương pháp cộng xếp chồng. Giả sử ta có :L[x(n)] = NL[h(n)] = MXử Lý Tín Hiệu Số151Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcN>>MTa cần tính tích chập tuyến tính choy(n) = x(n)*h(n)Trong phương pháp này, x(n) được xem như là tổng của các dãy thành phần đặtkề lên nhau M – 1 điểm, tức là M – 1 điểm đầu tiên của dãy thành phần xi+1(n) sẽ kềlên M – 1 điểm cuối cùng của dãy thành phần xi(n). Còn dãy thành phần đầu tiên x0(n)sẽ được bổ sung m – 1 mẫu không đầu tiên.Chúng ta gọi chiều dài của các dãy thành phần xi(n) là N1 :L[xi(n)] = N1Sau đó ta phải chọn N1 > M. Để ứng dụng biến đổi Fourier rời rạc (DFT)tính tíchchập phân đoạn này, chúng ta tính tích chập vòng của xi(n)N1 với h(n)M như sau :(4.58)x i (n ) N1 (*) N1 h (n ) M = y i' (n ) N1Tức ở đây h(n)M được kéo dài thêm N1 – (M - 1) mẫu không và tích chập vòng ởđây có chiều dài N1. Chuyển tích chập vòng 4.58 sang miền k ta có :(4.59)Yi ' (k ) N1 = X i (k ) N1 .H (k ) N1ở đây : N1 x i (n ) N1 WNkn1= ∑n =0 0X i (k ) N1H(k ) N1 N1 h (n ) M WNkn1= ∑n =0 0, 0 ≤ k ≤ N1 − 1, k còn lại, 0 ≤ k ≤ N1 − 1, k còn lạiSau đó dùng biến đổi Fourier ngược (IDFT) để tìm y’(n)N1 như sau :y i' (n ) N1 1 N1 'Yi (k ) N1 WN−1kn=  N1 ∑k =0 0, 0 ≤ n ≤ N1 − 1(4.60), n còn lạiSau khi tính được y’i(n)N chúng ta phải bỏ đi M – 1 điểm đầu tiên để thu được yi(n). Sauđó cộng các giá trò yi(n) ta thu được y(n) :y ( n) = ∑ y i ( n)iHình 4.18 cho ta một ví dụ minh hoạ tích chập phân đoạn theo phương pháp đặt kề vớiM = 4, N1 = 9.Cũng giống như phương pháp cộng xếp chồng, chiều dài của DFT(N1) được chọn tươngứng với chiều dài M của h(n)M sao cho thời gian tính toán là tối ưu nhất. Trong thực tếngười ta chọn N1 theo bảng HEJMS bảng 4.2.Xử Lý Tín Hiệu Số152Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạcx (n )na) 0h (n )nb) 0x 0 (n )nc) 08 9x 1 (n )nd) 071623 24x 2 (n )ne) 0Xử Lý Tín Hiệu Số71615323 24Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạcy ' 0 (n )2,5nf) 08y '1 ( n )2,5ng) 08y ' 2 (n )2,5ng) 08y ' 0 (n )2,5nh) 08Hình 4.18Xử Lý Tín Hiệu Số154Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạc4.4 Khôi Phục Biến Đổi Z Và Biến Đổi Fourier Từ DFTa. Khôi Phục Biến Đổi ZGiả sử có một dãy x(n)N có chiều dài hữu hạn N.Vậy ta có :∞N −1n = −∞n =0∑ x ( n) N z − n = ∑ x ( n) N z − nX ( z) =Chúng ta có thể tìm X(z) theo hàm của DFT[x(n)N] N −1 x (n ) N WNknDFT[ x (n ) N ] = X(k ) N = ∑n =0 0, 0 ≤ k ≤ N −1, k Còn lại 1 N −1X(k ) N WN− knIDFT[X(k ) N ] = x (n ) N =  N ∑k =0 0, 0 ≤ n ≤ N −1,n còn lạiTa có ZT[x(n)N] như sau :N −11X ( z) = ∑ n=0  N=1N1X (k ) N W N− kn .z − n =∑Nk =0N −1N −1N −1k =0n =0∑ X (k ) N ∑ (W N−k z −1 ) n =1NN −1N −1k =0n=0∑ X (k ) N ∑ W N− kn z − nN −11 − (W N− k z −1 ) Nk =01 − W N− k z −1∑ X (k ) NnhưngW N−kN = 1vậyX ( z) =1− z −NNN −1X (k ) N∑ 1−Wk =0−kN(4.61)z −1Nhận xét :- Có thể nói rằng, chúng ta có thể nhận đượcbiến đổi z của một dãy có chiều dài hữu hạntừ N giá trò của X(k)N.- Các giá trò (N giá trò) của X(k)N chính là cácmẫu của X(z) được đánh giá trên vòng tròn2πk , vậy trênđơn vò tại các điểm rời rạcIm[z]K= 0Re[z]Nvòng tròn đơn vò ta lấy mẫu x(z) tại các điểmnhư sau :z=ejωk=ej2πkN= W N− kK=7và ta có thể viết :Xử Lý Tín Hiệu SốHình 4.19155Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcN −1X ( z)z =W N− k= ∑ x(n) N W Nkn = X (k ) Nn =0Đến đây ta có thể nói rằng biểu thức (4.62) cho chúng ta công thức biến đổi zcủa một dãy có chiều dài hữu hạn N từ N “mẫu tần số” của X(z) trên vòng tròn đơn vò.Vò trí “các mẫu tần số” trên vòng tròn đơn vò trong mặt phẳng z được minh hoạ trênhình 4.19 với N = 8.b. Khôi Phục Biến Đỗi FourierChúng ta có thể nhận được biến đổi Fourier từ biến đổi z, nếu vòng tròn đơn vònằm trong miền hội tụ của biến đổi z.X (e jω ) = X ( z )z =ejω==1 − e − jωNN1 − e − jωNNN −1∑k =0N −1∑k =0X (k ) Nj2πkN1− ee − jωX (k ) N1− ej(2πk −ω )Nta biết rằng :1− ejx=e−jx2xx−j −j j 2x e − e 2  = 2e 2 sin x2vậy :X (ejω1)=NsinN −1∑ X (k )k =0Nsin(ω2ωN2−πNe N −1 π − j ω+ k2N (4.62)k)Biểu thức (4.62) chính là quan hệ cho phép ta tìm biến đổi Fourier bằng cách nội suy từcác giá trò X(k)N.4.5 Biến Đổi Fourier Nhanh (FFT)Để tiết kiệm thời gian tính toán trong biến đổi Fourier rời rạc (DFT), ta sử dụngthuật toán biến đổi nhanh Fourier (FFT) bằng cách chia nhỏ số điểm để xử lý.4.5.1 Thuật Toán FFT Cơ Số 2 Chia Theo Thời Giana.Tính đối xứng(4.63)W k ( N − n ) = ( W kn ) *b.Tính tuần hoànW kn = W k ( n + N ) = W ( k + N ) n = W ( k + N )( n + N )Xét biến đổi Fourier rời rạc N điểm của chuỗi x(n)Xử Lý Tín Hiệu Số156(4.64)Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcN −1X(k ) = ∑ x (n ) W knvớik = 0, 1, 2, … , N-1(4.65)n =0ta tách dãy x(n) ra những dãy chẵn và dãy lẻ như sau :X(k ) =N −1N −1n = chẵnn = lẻ∑ x (n )W kn + ∑ x (n)W knhoặc thay thế biến n = 2r đối với n chẵn và n = 2r + 1 đối với n lẻ, ta có :N−12N−12r =0n = 0ûX(k ) = ∑ x (2r ) W 2 rk + ∑ x (2r + 1) W k ( 2 r +1)mà W2 = WN/2 do W2 = e-j2(2π/N) = e-j2π(N/2) = WN/2do đó ta có thể viết lại biểu thức như sau :N−12N−12r =0n = 0ûX(k ) = ∑ x (2r ) WNrk/ 2 + WNk ∑ x (2r + 1) WNrk/ 2N−12X 0 (k ) = ∑ x (2r ) WNrk/ 2đặtvới(X0 tương ứng r chẵn)với(X1 tương ứng r lẻ)r =0N−12X 1 (k ) = ∑ x (2r + 1) WNrk/ 2vàn = 0ûnhư vậy ta có :X(k) = X0(k) + Wk. X1(k)Ví dụ 4.8 :xét hình 4.20 , chọn N = 8, k = 4, ta có :Giải :X(4) = X0(4) + WN4. X1(4)Do tính chất tuần hoàn nên X0(4) = X0(0) và X1(4) = X1(0) nênX(4) = X0(0) + WN4. X1(0)Ta có thể làm một phép so sánh như sau :- Một DFT có N điểm thì cần N2 phép nhân phức và khoảng N2 phép cộng phức.- Nếu tách thành 2 DFT có N/2 điểm thì cần 2(N/2)2 phép nhân phức và khoảng2N(/2)2 phép cộng phức để thực hiện X0(k) và X1(k) và mất thêm N phép nhânphức giữa W và X1(k) và thêm N phép cộng phức để tính X(k) từ X0(k) và W.X1(k).Như vậy, tổng cộng ta cần N + 2(N/2)2 = N + N2/2 phép nhân phức và phép cộngphức để tính tất cả các giá trò của X(k).Xử Lý Tín Hiệu Số157Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời Rạc-Nếu số điểm N có dạng N = 2M thì ta tiếp tục chia đôi sang M lần cho đến khi sốx(0)X0(0)DFTN/2điểmx(2)x(4)X0(1)X0(2)x(6)X0(3)X(0)W0W1W2X(1)X(2)X(3)W3x(1)X1(0)DFTN/2điểmx(3)x(5)X1(1)X1(2)x(7)X1(3)X(4)W4W5W6X(5)X(6)X(7)W7Hình 4.20điểm DFT là bằng 2, nên người ta còn gọi cách chia này là FFT cơ số 2 và cũng cóthể chi với FFT cơ số 4 nếu N = 4M … xem hình 4.20 , cụ thể ta có có thể tách X0(k)ra như sau :N−12N−12r =0n = 0ûX 0 (k ) = ∑ x (2r ) WNrk/ 2 = WNk ∑ g (r ) WNrk/ 2x(0)x(4)x(2)x(6)X0(0)DFTN/4điểmW0N/2W1N/2X0(2)DFTN/4điểmW2N/2Hình 4.21Xử Lý Tín Hiệu SốX0(1)158W3N/2X0(3)Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcNếu ta đặt l = 2r, ta tách thành hai dãy chẵn và lẻ.N−14N−14l =0l = 0ûX 0 (k ) = ∑ g (2l) WN2lk/ 2 + WNk ∑ g (2l + 1) WN( 2/l2+1) kN−14N−14l=0l = 0ûX 0 (k ) = ∑ g (2l) WN2lk/ 4 + WNk / 2 ∑ g (2l + 1) WNlk/ 4X 0 (k ) = X 00 (k ) + WNk / 2 X 01 (k )-X 00 (k ) : DFT của dãy g(r) có chỉ số chẵn.-X 01 (k ) : DFT của dãy g(r) có chỉ số lẻ. Hình 4.20x(0)X(0)DFTN/4điểmx(4)x(2)x(1)x(3)Hình 4.22X0(0)W0 N = 1X0(4)W2 = WN/2N = -1Hình 4.23Xử Lý Tín Hiệu SốW1W4W2W6W3X(3)W0W4W2W5X(5)X(6)DFTN/4điểmx(7)W2X(1)X(4)DFTN/4điểmx(5)W0X(2)DFTN/4điểmx(6)W0159W4W6W6W7X(7)Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcHình 4.22 là sau hai lần phân chiaX0(0)X0(0)W0W0X0(1)X0(4)-1W2W142X0(2)X0(2)WX0(6)-1WW3W6X0(1)WX0(4)0W4X0(5)X0(5)W2-1X0(3)W5X0(6)X0(3)WX0(7)4WX0(7)W7W6-16Hình 4.24Hình 4.23 : Lưu đồ tính cho hai điểm x(0) và x(4).Hình 4.24 : sau ba lần phân chia(N = 8)Theo bảng 4. , chúng ta thấy cách tính số phép toán.M = log2NNN2N.log2N1 2 3452 4 8 16324 16 64 256 10242 8 24 64 1606644096384712816384896825665536204895122621444608101024104857610240Trước tiên, chúng ta qui ước ký hiệu như sau :- Nút thứ i của tầng thứ m được ký hiệu là Xm(i). Mỗi tầng có N nút và có M = log2Ntầng. Để thuận tiện ta ký hiệu x(n) là tầng thứ 0.- Đối với tầng thứ (m + 1), ta có thể xem dãy Xm(i) như là dãy Xm+1(i) như là dãy ra.Đối với tầng đầu và khi N = 8 ta có :X0(0) = x(0) ;X0(4) = x(4)X0(1) = x(1) ;X0(5) = x(5)X0(2) = x(2) ;X0(6) = x(6)X0(3) = x(3) ;X0(7) = x(7)Xử Lý Tín Hiệu Số160Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcSử dụng ký hiệu này và từ sơ đồ, ta thấyphép tính cơ bản trong các tầng đều có Xm(p)Xm+1(p)dạng chung như sau :WrNXm+1(p) = Xm(p) + WNr. Xm(q) (*)Xm(q)Xm+1(q)Xm+1(q) = Xm(p) + WNr+N/2. Xm(q)rr+N/2= Xm(p) - WN . Xm(q)WN= - WNrBiểu diễn theo lưu đồ hình bướm hình 4.25Hình 4.25Cặp phép tính này, được biểu diễn trênhình 4.25 . Mỗi tầng đều có số hình bướm như nhau và bằng N/2 hình. Nhờ tính chất làWNr+N/2 = - WNr , nên ta có thể rút bớt số phép nhân đi một nửa, vì số hạng T = WNr.Xm(q) có thể chỉ cần tính một lần trong công thức (*) và N trong lưu đồ hình 4.25 .Ta có :Xm+1(p) = Xm(p) + TXm(p)Xm+1(p) = Xm(p) + T(*)Xm+1(q) = Xm(q) – T1Xm(q)Xm+1(q) = Xm(q) – TWrN-1Hình 4.26Kết hợp hình 4.24 và hình 4.26 ta có lưu đồ tính FFT phân chia theo thời gian với cáchình bướm đã được cải tiến hình 4.27 . Số phép nhân trong lưu đồ này đã giảm đi đượcmột nửa.X0(0)W0X0(0)X0(1)X0(4)W0-1X0(2)W1W0X0(6)W0-1W2X0(2)2-1W-1W3X0(3)X0(4)X0(1)X0(5)W0-1X0(3)W0X0(7)W0-1W2W4W1W5-1W2-1W3Hình 4.27Xử Lý Tín Hiệu SốW0161X0(5)X0(6)W6W7X0(7)Chương 4 - Biểu Diễn Tín Hiệu Và Hệ Thống Rời Rạc Trong Miền Tần Số Rời RạcSơ đồ hình 4.27 sau ba lần phân chia (N = 8).4.5.2 Thuật Toán FFT Cơ Số 2 Chia Theo Tần SốHình 4.24 phân chia theo tần số của DFT N điểm thành hai DFT N/2 điểm (N =8). giả thiết N = 2M , ta có thể chia dãy ra làm hai nửa.N−12X(k ) = ∑ x (n ) WNnk +n =0N−12∑ x (n ) Wn = N/2ûnkN(4.66)hoặcN−12N−12n =0n = 0ûX(k ) = ∑ x (n ) WNnk + WN( N / 2) k ∑ x (n + N / 2) WNnk(4.67)vớiWN( N / 2) = −1 rút gọn lại ta có :N−12X(k ) = ∑ [ x (n ) + (−1) k x (n + N / 2)]WNnkn =0xét k = 2r (k chẵn) và k = 2r + 1 (k lẻ), ta có :N−12X(2r ) = ∑ [ x (n ) + x (n + N / 2)]WN2 rnn =0với r = 0, 1, 2, … , (N/2 -1)do WN2 rn = WNrn/ 2 nên X(2r) là DFT N/2 điểm của dãy g(n) = x(n) + x(n + N/2) và X(2r +1) là DFT N/2 điểm của tích W với dãy h(n) = x(n) - x(n + N/2).Như vậy, sau khi có hai dãy h(n) và g(n), ta thực hiện h(n)Wn , sau đó lất DFTcủa hai dãy này ta sẽ có các điểm của X(k) chỉ số chẵn và chỉ số lẻ, Hình 4.24 tính vớiN = 8.Với mỗi DFT N/2 điểm, ta tiến hành tương tự và táchnthành N/4. Hình 4.25 chota thấy lưu đồ tổng quát của cách tính DFT theo phương pháp phân chia tần số. Nhưvậy, nếu có N/2 phép nhân thì ta có M = log2N tầng. Số phép nhân tổng cộng là (N/2).log2N, bằng với số phép nhân trong cách tính theo phương pháp phân chia theo thời gianvà số phép cộng cũng vậy.Xử Lý Tín Hiệu Số162

Tài liệu liên quan

Tài liệu ET4020 - Xử lý tín hiệu số Chương 4: Thiết kế bộ lọc số ppt
- 17
- 900
- 5
ET4020 - Xử lý tín hiệu số Chương 2: Các phép biến đổi Fourier pot
- 15
- 692
- 5
XỬ LÝ TÍN HIỆU SỐ (Chương 4+5) potx
- 37
- 565
- 0
Bài tập Xử lý tín hiệu số, Chương 5 potx
- 22
- 985
- 22
Bài tập Xử lý tín hiệu số, Chương 6 ppsx
- 28
- 919
- 14
Bài tập Xử lý tín hiệu số, Chương 7 ppsx
- 29
- 852
- 16
Xử lý tín hiệu số chương IV (phần 1)
- 17
- 399
- 0
Xử lý tín hiệu số chương IV (phần 2)
- 30
- 565
- 1
Bài tập xử lý tín hiệu số, chương 1 1
- 27
- 446
- 0
câu hỏi xử lý tín hiệu số chương 1
- 34
- 505
- 3