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

Chia sẻ: Le Ngoc Thin | Ngày: | Loại File: PDF | Số trang:30

Thêm vào BST

Báo xấu

145
lượt xem 31
download

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

Trong chương 4 này chúng ta sẽ nghiên cứu cách 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. THực chất của cách biến đổi này là lấy từng điểm rời rạc trên vòng tròn đơn vị trên mặt phẳng Z để biểu diễn.

Chủ đề:

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

Lưu

Nội dung Text: Xử lý tín hiệu số_Chương IV (Phần 2)

Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc DFT [ x 2 (n)] = X 2 (k ) DFT [ x 3 (n)] = X 3 (k ) thì X 3 (k ) = aX 1 (k ) + bX 2 (k ) (4.26) chuù yù raèng neáu chieàu daøi cuûa x1 (n) vaø x 2 (n) laø khaùc nhau thì L[ x1 (n)] = N 1 L[ x 2 (n)] = N 2 thì ta phaûi choïn chieàu daøi cuûa daõy x 3 (n) nhö sau : L[ x 3 (n)] = N 3 = max( N 1 , N 2 ) vaø taát caû caùc DFT[x1(n)], DFT[x2(n)] vaø DFT[x3(n)] ñeàu phaûi tính ñeán N3 maãu. Giaû söû neáu N1 < N2 thì daõy x1(n) phaûi ñöôïc keùo daøi theâm N2 – N1 maãu khoâng vaø DFT[x1(n)] phaûi ñöôïc tính treân N3 = N2 maãu vaø DFT[x2(n)] vaø DFT[x3(n)] cuõng ñöôïc tính treân N3 + N2 maãu. Cuï theå laø : N1 −1 X 1 (k ) = ∑ x (n)W n =0 1 kn N2 ≡ X 1 (k ) N 3 , 0 ≤ k ≤ N2 – 1 N 2 −1 X 2 (k ) = ∑x n =0 2 (n)W N 2 ≡ X 2 (k ) N 3 kn , 0 ≤ k ≤ N2 – 1 N 3 −1 X 3 (k ) = ∑x n =0 3 (n)W N 2 ≡ X 3 (k ) N 3 kn , 0 ≤ k ≤ N2 – 1 ñeå nhaán maïnh vaø chæ roõ chieàu daøi cuûa caùc daõy trong mieàn n vaø mieàn k ta ghi theâm chieàu daøi vaøo kyù hieäu daõy nhö laø ; x1 (n) N1 : Daõy coù chieàu daøi N1 x 2 (n) N 2 : Daõy coù chieàu daøi N2 x 3 (n) N 3 : Daõy coù chieàu daøi N3 X 1 (k ) N 3 : Daõy coù chieàu daøi N4 … b. Treã Voøng Tröôùc heát, chuùng ta nhìn laïi treã tuyeán tính vaø treã tuaàn hoaøn coù chu kyø N ñeå so saùnh vaø ruùt ra keát luaän cuûa treã voøng. Ñeå thaáy ñöôïc moät caùch tröïc quan ta coù ví duï sau : Ví duï 4.4 : Cho daõy x(n) sau : Xöû Lyù Tín Hieäu Soá 138
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc   1− n , 0≤n≤4 x (n ) x (n ) =  4 0  , n coøn laïi Haõy tìm treã tuyeán tính x(n - 2) vaø x(n + 2). Giaûi : n Chuùng ta giaûi baèng ñoà thò cho treân hình 4.12 Hình 4.12a Ví duï 4.5 : x (n − 2) Cho daõy tuaàn hoaøn chu kyø N = 4, ~ (n) 4 sau ñaây: x   1− n , 0≤n≤4 x (n ) =  4 0  , n coøn laïi n Haõy tìm ~ (n − 2) 4 vaø ~ (n + 2) 4 , sau ñoù laáy ra moät chu x x Hình 4.12b kyø cuûa hai daõy naøy. x (n + 2) Giaûi : Chuùng giaûi baèng ñoå thò cho treân hình 4.13. n x (n ) ~ ( n) x 4 Hình 4.12c n n Hình 4.13a Hình 4.13b ~ (n − 2) x 4 x ( n − 2) 4 n n Hình 4.13c Hình 4.13d Xöû Lyù Tín Hieäu Soá 139
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc ~ (n + 2) x x (n + 2) 4 4 n n Hình 4.13e Hình 4.13f Ñeå phaân bieät ñöôïc caùc loaïi treã ta coù theå kyù sau : x(n – n0) : Treã tuyeán tính. ~ (n − n ) : Treã tuaàn hoaøn chu kyø N x 0 N x(n – n0)N : Treã voøng vôùi chieàu daøi N Töø ví duï, ta thaáy neáu trích ra moät chu kyø töø (töø 0 ñeán N-1) cuûa treã tuaà hoaøn chu kyø N thì ta seõ coù treã voøng x(n ± n0)N, so saùnh vôùi treã tuyeán tính x(n ± n0), neáu noù vöôït ra khoûi (töø 0 ñeán N-1) thì noù seõ voøng laïi ñeå x(n)N xaùc ñònh trong khoaûng [0, N-1], thì luùc naøy treã voøng cuõng ñöôïc xaùc ñònh trong khoaûng [0, N-1]. Ta coù theå vieát nhö sau : x (n ) N = ~ (n ) N rect N (n ) x x (n ± n 0 ) N = ~ (n ± n 0 ) N rect N (n ) x (4.27) Hinh 4.14 seõ minh hoaï baûn chaát cuûa treã voøng. x (n ) ≡ x (n ) 4 x (n − 2) n n Hình 4.14a Hình 4.14b x ( n − 2) 4 = x ' ( n ) n Hình 4.14c Xöû Lyù Tín Hieäu Soá 140
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc x(1) x’(1) x(2) 2 0 x(0) x’(2 2 0 x’(0) 3 3 x(3) x’(3 Hình 4.14d x (n + 2) x (n + 2) 4 = x '' (n ) n n Hình 4.14e Hình 4.14f x(1) x’’(1) 1 3 x(2) 2 0 x(0) x’’ (2) 0 2 x’’(0) 3 1 x(3) x’’ (3) Hình 4.14g Neáu ta xeùt trong mieàn k, baûn chaát cuûa noù cuõ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) Xeùt tính chaát treã trong mieàn n, thì trong mieàn k : DFT[ x (n ) N ] = X(k ) N DFT[ x (n ± n 0 ) N ] = WN 0 X(n ) N kn (4.29) Chöùng minh : Döïa vaøo caùch chöùng minh trong tính chaát treã, ta coù : kn ~ DFT[~ (n ± n 0 ) N ] = WN 0 X(n ) N x Xöû Lyù Tín Hieäu Soá 141
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc Neáu laáy hai veá ra chu kyø [0, N-1], luùc naøy x (n − n 0 ) N = ~ (n − n 0 ) N rect N (n ) x ~ X(k ) N = X(k ) N rect N (n ) Vaäy ta coù ñöôïc : DFT[ x (n ± n 0 ) N ] = WN 0 X(n ) N kn Töông töï ta cuõng coù tính chaát treã trong mieàn k. Neáu coù : DFT[X(k ) N ] = x (n ) N thì − DFT[X(k − k 0 ) N ] = WN kn 0 x (n ) N (4.30) Nhaän xeùt : Neáu trích ra moät chu kyø (töø 0 ñeán N -1) cuûa daõy tuaàn hoaøn bieán ñaûo ~ (−n ) N thì x seõ ñöôïc daõy bieán ñaûo voøng chieåu daøi höõu haïn x (−n ) N , nghóa laø chieàu daøi höõu haïn seõ khoâng vöôït ra khoûi [0, N-1]. Ta coù theå vieát laïi x (−n ) N = ~ (− n ) N rect N (n ) x (4.31) Ta cuõng xeùt ñöôïc trong mieàn k: ~ X(− k ) N = X(−k ) N rect N (k ) (4.32) Do tính tuaàn hoaøn cuûa ~ (n ) , ta coù x ~(n ) = ~(n + N) x x ~ (− n ) = ~ (− n + N) = ~ ( N − n ) x x x Vaø ta cuõng coù : x (−n ) N = ~ (− n )rect N (n ) x vaø X( N − n ) N = ~ ( N − n )rect N (n ) x (4.33) Trong mieàn k X(−k ) N = X( N − k ) N (4.34) vaø DFT[ x (− n ) N ] = X(− k ) N (4.35) DFT[ x ( N − n ) N ] = X( N − k ) N (4.36) c. Tính Ñoái Xöùng Chuùng ta coù daõy chieàu daøi höõu haïn N x(n) N vaø DFT[ x (n ) N ] = X(k ) N thì ta coù : Xöû Lyù Tín Hieäu Soá 142
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc DFT[ x * (n ) N ] = X * (− k ) N Daáu * laø bieåu thò lieân hôïp phöùc. Chöùng minh : x * (n ) N = ~ * (n ) N rect N (n ) x ~ X * (−k ) N = X(− k )rect N (n ) nhö vaäy ta coù : ~ DFT [ x * (n) N ] = X * (−k ) N töông töï ta cuõng coù : DFT [ x * (−n) N ] = X * (k ) Caùc tính chaát ñoái xöùng cuûa DFT ñoái vôùi daõy coù chieàu daøi höõu haïn coù theå suy ra töø caùc tính chaát cuûa DFT ñoái vôùi daõy tuaàn hoaøn chu kyø N, hoaëc caùc tính chaát cuûa bieán ñoåi Fourier (FT) trong chöông 3. Baây giôø ta xeùt chi tieát tính ñoái xöùng ñoái vôùi daõy phöùc coù chieàu daøi höõu haïn N x(n)N. Daõy x(n)N coù theå ñöôïc bieåu dieãn döôùi daï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) vaø : x( n) N + x * ( n) N ] Re[ x(n) N ] = (4.39) 2 x ( n) N − x * ( n) N ] j Im[ x(n) N ] = (4.40) 2 Do vaäy ta coù theå vieát : N −1 1 DFT {Re[ x(n) N ]} = ∑ Re[ x(n) N ]W N = kn DFT [ x(n) N + x * (n) N ] n =0 2 1 = [ X (k ) N + X * (−k ) N ] = X e (k ) N 2 Xe(k)N laø phaàn ñoái xöùng lieân hôïp cuûa X(k)N. Trong thöïc teá thöôøng gaëp caùc daõy tín hieäu thöïc, vì vaäy ta haõy xeùt tröôøng hôïp rieâng khi x(n)N laø thöïc. Ta coù theå bieåu dieãn X(k)N döôùi daïng sau ñaâ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 ] * (4.42) 1 Re[ X (k ) N ] = [ X (k ) N + X * (k ) N ] (4.43) 2 1 j Im[ X (k ) N ] = [ X (k ) N − X * (k ) N ] (4.44) 2 Xöû Lyù Tín Hieäu Soá 143
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc vaø neáu x(n) laø thöïc thì ta coù : x(n)N = X*(n)N vaø DFT [ x(n) N ] = DFT [ x * (n) N ] Thöùc laø X (k ) N = X * (−k ) N (4.45) Laáy lieân hôïp phöùc hai veá ta coù : X * (k ) N = [ X * (−k ) N ]* = X (−k ) N (4.46) vôùi bieán ñaûo –k ta coù : 1 Re[ X (−k ) N ] = [ X (−k ) N + X * (−k ) N ] 2 theo (4.45) vaø (4.46) ta coù : 1 Re[ X (−k ) N ] = [ X * (k ) N + X (k ) N ] 2 Vaäy vôùi x(n) thöïc ta coù : Re[ X (k ) N ] = Re[ X (−k ) N ] (4.47) töông töï ta coù : Im[ X (k ) N ] = − Im[ X (− k ) N ] (4.48) Baây giôø ta xeùt module vaø Argument 1 1 X (−k ) N = [ X (k ) N X (k ) N ] = [ X (−k ) N X (−k ) N ] = X (−k ) N * 2 * 2 (4.49) töông töï Im[ X (k ) N ]  Im[ X (−k ) N ]  arg[ X (k ) N ] = arctg = arctg −  = − arg[ X (−k ) N ] (4.50) Re[ X (k ) N ]  Re[ X (−k ) N ]  d. Tích chaäp voøng Ñoái vôùi caùc daõy tuaàn hoaøn coù chu kyø N ta ñaõ coù quan heä sau : N −1 ~ (n) = ~ (n)( ~ ) x (n) = x3 x1 * N 2 N ∑ ~1 (m) ~2 (n − m) x x m =0 vaø trong mieàn k ta coù : ~ ~ ~ X 3 (k ) = X 1 (k ). X 2 (k ) Chuù yù : taát caû caùc daõy ôû quan heä treân ñeàu laø tuaàn hoaøn chu kyø N. Coøn ñoái vôùi daõy khoâng tuaàn hoaøn coù chieàu daøi höõu haïn N, chuùng ta coù theå coi chuùng töông öùng vôùi moät chu kyø cuûa caùc daõy tuaàn haoøn chu kyø N, vì vaäy chuùng ta cuõng coù ñònh nghóa vaø tính chaát töông töï nhö ñoái vôùi caùc daõy tuaàn hoaøn chu kyø N. Ñònh nghóa : Xöû Lyù Tín Hieäu Soá 144
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc Tích chaäp voøng cuûa hai daõy khoâng tuaàn hoaøn x1(n)N vaø x2(n)N coù chieàu daøi höõu haïn N laø moät daõy khoâng tuaàn hoaøn cuõng coù chieàu daøi höõu haïn N x3(n)N ñöôïc cho bôûi quan heä sau : N −1 x 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 laø tích chaäp voøng chieàu daøi N. Neáu trong mieàn n laø tích chaäp voøng thì trong mieàn k ta deã daøng chöùng minh ñöôïc tính chaát sau ñaây : X 3 (k ) N = X 1 (k ) N . X 2 (k ) N (4.53) ôû ñaây X 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í duï 4.6 : Cho hai daõy khoâng tuaàn hoaøn coù chieàu daøi höõu haïn N = 4 nhö sau : x1 (n) 4 = δ (n − 1)  n 1 − ,0 ≤ n ≤ 4 x 1 (n ) 4 =  4 0  , n coøn laïi Haõy tính tích chaäp voøng chieàu daøi N = 4 cuûa hai daõy naøy. Giaûi : 3 ~ x 3 ( n ) 4 = x1 ( n ) 4 ( * ) x 2 ( n ) 4 = ∑ x1 ( m ) x 2 ( n − m ) 4 m =0 3 x 3 (0) 4 = ∑ x1 (m) 4 x 2 (0 − m) 4 m =0 3 x 3 (1) 4 = ∑ x1 (m) 4 x 2 (1 − m) 4 m=0 3 x 3 (2) 4 = ∑ x1 (m) 4 x 2 (2 − m) 4 m =0 3 x 3 (3) 4 = ∑ x1 (m) 4 x 2 (3 − m) 4 m=0 ñeå thaáy roõ baûn chaát cuûa tích chaäp voøng, chuùng ta haõy xem quaù trình tính toaùn vaø keát quaû baèng ñoà thò cho treân hình 4.15. Xöû Lyù Tín Hieäu Soá 145
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc x 1 (n ) 4 = δ (n − 1) x 2 (n ) 4 x 2 (0 − m ) 4 n n m Hình 4.15a Hình 4.15b Hình 4.15c x 2 (1 − m) 4 x 2 ( 2 − m) 4 m m Hình 4.15d Hình 4.15e x 2 (3 − m) 4 x 3 (n ) 4 ≡ x 2 (n − 1) 4 m n Hình 4.15f Hình 4.15g Nhaän xeùt : Chuùng ta coù theå aùp duïng tính chaát cuûa bieåu thöùc (4.38) ñeå tính tích chaäp voøng, ñaây laø caùch tính giaùn tieáp thoâng qua DFT, nhöng cho ta hieäu quaû cao hôn. Ñeå thaáy roõ, chuùng ta haõy xeùt ví duï döôùi ñaây Ví duï 4.7 : Cho hai daõy coù chieàu daøi höõu haïn sau ñaây : x 1 (n ) N = x 2 (n ) N = rect N (n ) Haõy tính x 3 (n) N = x1 (n) N (*) x 2 (n) N thoâng qua DFT. Giaûi : N −1 X 1 ( k ) N = X 2 ( k ) N = ∑ WN kn n =0 N , k =0 = 0 , k coøn laïi Aùp duïng bieåu thöùc (4.53) ta coù : Xöû Lyù Tín Hieäu Soá 146
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc  N2 , k =0 X 3 (k ) N = X 1 (k ) N .X 2 (k ) N =  0 , k coøn laïi Ñeå tìm x3(n)N ta aùp duïng coâng thöùc cuûa IDFT. 1 N −1 x 3 (n ) N = ∑ X 3 (k ) N WNkn N k =0 − 1  X (0) W 0 , 0 ≤ n ≤ N −1 = n 3 N N  0  , n coøn laïi N , 0 ≤ n ≤ N −1 = 0 , n coøn laïi minh hoaï baèng ñoà thò cho treân hình 4.16 vôùi N = 4. x 1 (n ) 4 x 2 (n ) 4 n n -1 0 1 2 3 -1 0 1 2 3 Hình 4.16a Hình 4.16b X1 (k ) 4 = X 2 (k ) 4 X 3 (k ) 4 x 3 (n ) 4 16 4 4 k k n -1 0 1 2 3 -1 0 1 2 3 -1 0 1 2 3 Hình 4.16c Hình 4.16d Hình 4.16e 4.3.3 Tích chaäp nhanh (hay tích chaäp phaân ñoaïn) a. Toång quan Ñeå öùng duïng DFT vaøo vieäc tính tích chaäp khoâng tuaàn hoaøn, töùc laø tích chaäp tuyeán tính, tröôùc heát chuùng ta phaûi phaân bieät hai tröôøng hôïp. Tröôøng hôïp thöù nhaát khi caùc daõy chaäp vôùi nhau coù chieàu daøi gaàn baèng nhau vaø ngaén; tröôøng hôïp thöù hai khi caùc daõy chaäp vôùi nhau coù chieàu daøi khaùc nhau. Tröôøng hôïp thöù nhaát chính laø tröôøng hôïp chuùng ta ñaõ nghieân cöùu ôû caùc phaàn treân. Nhöng trong thöïc teá, chuùng ta thöôøng gaëp tröôøng hôïp thöù hai. Vieäc tính toaùn DFT cuûa Xöû Lyù Tín Hieäu Soá 147
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc daõy coù chieàu daøi quaù daøi seõ xaûy ra tröôøng hôïp vöôït quaù dung löôïng cuûa boä nhôù cuûa maùy tính vaø caàn phaûi coù thôøi gian tính toaùn quaù lôùn khoâng cho pheùp. Hôn nöõa ñeå coù ñöôïc maãu ñaàu tieân cuûa keát quaû ta phaûi ñôïi keát thuùc taát caû caùc tính toaùn. Ñeå giaûi quyeát caùc vaán ñeà treân, chuùng ta phaûi chia tính toaùn ra nhieàu giai ñoaïn. Chuùng ta coù hai phöông phaùp (Stockham nghieân cöùu phaùt trieån) noäi dung nhö sau : - Chia daõy thaønh nhieàu daõy con. - Chaäp töøng daõy con moät. - Toå hôïp caùc keát quaû thaønh phaàn. - Giaû söû daõy x(n) coù chieàu daøi N, daõy h(n) coù chieàu daøi M, vaø N raát lôùn so vôùi M(N>>M) vaø daõy y(n) = x(n)*h(n) coù chieàu daøi N + M – 1 seõ raát lôùn. Vaäy neáu ta duøng DFT thì DFT seõ ñöôïc tính vôùi chieàu daøi N + M – 1. Vaäy neáu muoán duøng DFT thì ta phaûi phaân daõy x(n) ra laøm nhieàu ñoaïn nhoû. b. Phöông Phaùp 1: coäng xeáp choàng Giaû söû ta caàn tính tích chaäp tuyeán tính y(n) = x(n)*h(n) L[x(n)] = N L[h(n)] = M N>>M Daõy x(n) ñöôïc xem nhö toång cuûa caùc daõy thaønh phaàn xi(n), maø L[xi(n)] = N1 Töùc ta coù : x ( n ) N = ∑ x i ( n ) N1 (4.54) i vôùi : x (n ) , iN 1 ≤ n ≤ (i + 1) N 1 − 1 x i (n ) N1 =  0 , n coøn laïi Ta bieát raèng : ∞ ∞ y( n ) = x ( n ) * h ( n ) = ∑ h ( m) x ( n − m) = ∑ h (m)[∑ x i ( n − m)] m = −∞ ∞ m = −∞ i (4.55) =∑ ∑ h ( m) x ( n − m) = ∑ h ( n ) i M * x i (n ) N = ∑ y i (n ) N + M −1 1 1 i m = −∞ i i y i (n) N1 + M −1 = h(n) M * x i (n) N1 goïi laø tích chaäp phaân ñoaïn, ñaây laø tích chaäp tuyeán tính, neáu duøng DFT thì moãi tích chaäp phaân ñoaïn naøy ta phaûi tính DFT vôùi chieàu daøi N1 + M – 1. Töùc laø ta phaûi tính tích chaäp voøng vôùi chieàu daøi N1 + M – 1: y i (n) N1 + M −1 = h(n) N1 + M −1 (*) x i (n) N1 + M −11 (4.56) Xöû Lyù Tín Hieäu Soá 148
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc nhö vaäy tích chaäp voøng naøy seõ baèng tích caäp tuyeán tính. Theá thì h(n)M seõ ñöôïc keùo daøi (N1 – 1) maãu khoâng vaø xi(n)N1 seõ ñöôïc keùo daøi M –1 maãu khoâng. Trong mieàn taàn soá rôøi raïc k ta coù : Yi (k ) N1 + M −1 = H (k ) N1 + M −1 (*) X i (k ) N1 + M −11 (4.57) sau ñoù duøng IDFT ñeå tính y i (n) N + M −1 1 y i (n ) N1 + M −1 = IDFT[Yi (k ) N1 + M −1 ]  1 N1 + M − 2  ∑ Yi (k) N1 + M −1 WN1nkM −1 =  N1 + M − 1 k =0 − + , iN 1 ≤ n ≤ (i + 1) N 1 + M − 2  0  , n coøn laïi hình 4.17 cho ta moät ví duï minh hoaï tích chaäp phaân ñoaïn theo phöông phaùp coäng xeáp choàng vôùi M = 4, N1 = 8 x (n ) n a) 0 h (n ) n b) 0 4 x 0 (n ) n c) 0 7 Xöû Lyù Tín Hieäu Soá 149
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc x 1 (n ) n d) 0 7 15 x 2 (n ) n e) 0 7 16 23 24 y 0 (n ) n f) 0 8 y1 (n ) n g) 0 8 y 2 (n ) n h) 0 8 15 Xöû Lyù Tín Hieäu Soá 150
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc y( n ) n i) 0 Hình 4.17 Nhaän xeùt : - Neáu n1 raát daøi thì ta coù lôïi laø soá löôïng caùc ñoaïn seõ ít ñi, nhöng vì N1 daøi neân thôøi gian tính toaùn cuûa moät ñoaïn seõ taêng leân. - Neáu n1 nhoû thì ta coù baát lôïi laø soá löôïng caùc ñoaïn seõ taêng leân, nhöng laïi coù lôïi laø thôøi gian tính toaùn cuûa moät ñoaïn seõ giaûm ñi. Vaäy trong thöïc teá, chuùng ta phaûi choïn giaù trò cuûa N1 toái öu so vôùi chieàu daøi M cuûa h(n). Giaù trò N1 toái öu ñöôïc choïn theo baûng 4.2, goïi laø baûng Helms. Baûng 4.2 Chieàu daøi cuûa h(n) _ M Chieàu daøi cuûa DFT _ N1 + M – 1 ≤ 10 32 11 – 17 64 18 – 29 128 30 – 52 256 53 – 49 512 95 – 171 1024 172 – 310 2048 311 – 575 4096 576 – 1050 8192 1051 – 2000 16.384 2001 – 3800 32.768 3801 – 7400 65.536 7401 – 14800 131.072 … … c. Phöông phaùp 2 : Ñaët keà nhau Chuùng ta coù moät phöông phaùp nöõa ñeå tính tích chaäp nhanh goïi laø phöông phaùp ñaët keà nhau, cuõng gioáng nhö phöông phaùp coäng xeáp choàng. Giaû söû ta coù : L[x(n)] = N L[h(n)] = M Xöû Lyù Tín Hieäu Soá 151
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc N>>M Ta caàn tính tích chaäp tuyeán tính cho y(n) = x(n)*h(n) Trong phöông phaùp naøy, x(n) ñöôïc xem nhö laø toång cuûa caùc daõy thaønh phaàn ñaët keà leân nhau M – 1 ñieåm, töùc laø M – 1 ñieåm ñaàu tieân cuûa daõy thaønh phaàn xi+1(n) seõ keà leân M – 1 ñieåm cuoái cuøng cuûa daõy thaønh phaàn xi(n). Coøn daõy thaønh phaàn ñaàu tieân x0(n) seõ ñöôïc boå sung m – 1 maãu khoâng ñaàu tieân. Chuùng ta goïi chieàu daøi cuûa caùc daõy thaønh phaàn xi(n) laø N1 : L[xi(n)] = N1 Sau ñoù ta phaûi choïn N1 > M. Ñeå öùng duïng bieán ñoåi Fourier rôøi raïc (DFT)tính tích chaäp phaân ñoaïn naøy, chuùng ta tính tích chaäp voøng cuûa xi(n)N1 vôùi h(n)M nhö sau : x i (n ) N1 (*) N1 h (n ) M = y i' (n ) N1 (4.58) Töùc ôû ñaây h(n)M ñöôïc keùo daøi theâm N1 – (M - 1) maãu khoâng vaø tích chaäp voøng ôû ñaây coù chieàu daøi N1. Chuyeån tích chaäp voøng 4.58 sang mieàn k ta coù : Yi ' (k ) N1 = X i (k ) N1 .H (k ) N1 (4.59) ôû ñaây :  N1 = ∑ i N1 N1  x (n ) W kn , 0 ≤ k ≤ N1 − 1 X i (k ) N1 n =0  0  , k coøn laïi  N1 = ∑  h (n ) M WN1 kn , 0 ≤ k ≤ N1 − 1 H(k ) N1 n =0  0  , k coøn laïi Sau ñoù duøng bieán ñoåi Fourier ngöôïc (IDFT) ñeå tìm y’(n)N1 nhö sau :  1 N1 ' =  N1 ∑ i −  Y (k ) N1 WN1kn , 0 ≤ n ≤ N1 − 1 y i' (n ) N1 k =0 (4.60)  0  , n coøn laïi Sau khi tính ñöôïc y’i(n)N chuùng ta phaûi boû ñi M – 1 ñieåm ñaàu tieân ñeå thu ñöôïc yi(n). Sau ñoù coäng caùc giaù trò yi(n) ta thu ñöôïc y(n) : y ( n) = ∑ y i ( n) i Hình 4.18 cho ta moät ví duï minh hoaï tích chaäp phaân ñoaïn theo phöông phaùp ñaët keà vôùi M = 4, N1 = 9. Cuõng gioáng nhö phöông phaùp coäng xeáp choàng, chieàu daøi cuûa DFT(N1) ñöôïc choïn töông öùng vôùi chieàu daøi M cuûa h(n)M sao cho thôøi gian tính toaùn laø toái öu nhaát. Trong thöïc teá ngöôøi ta choïn N1 theo baûng HEJMS baûng 4.2. Xöû Lyù Tín Hieäu Soá 152
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc x (n ) n a) 0 h (n ) n b) 0 x 0 (n ) n c) 0 8 9 x 1 (n ) n d) 0 7 16 23 24 x 2 (n ) n e) 0 7 16 23 24 Xöû Lyù Tín Hieäu Soá 153
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc y ' 0 (n ) 2,5 n f) 0 8 y '1 ( n ) 2,5 n g) 0 8 y ' 2 (n ) 2,5 n g) 0 8 y ' 0 (n ) 2,5 n h) 0 8 Hình 4.18 Xöû Lyù Tín Hieäu Soá 154
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc 4.4 Khoâi Phuïc Bieán Ñoåi Z Vaø Bieán Ñoåi Fourier Töø DFT a. Khoâi Phuïc Bieán Ñoåi Z Giaû söû coù moät daõy x(n)N coù chieàu daøi höõu haïn N. Vaäy ta coù : ∞ N −1 X ( z) = ∑ x ( n) N z − n = ∑ x ( n) N z − n n = −∞ n =0 Chuùng ta coù theå tìm X(z) theo haøm cuûa DFT[x(n)N]  N −1 DFT[ x (n ) N ] = X(k ) N = ∑  x ( n ) N WN kn , 0 ≤ k ≤ N −1 n =0  0  , k Coøn laïi  1 N −1 IDFT[X(k ) N ] = x (n ) N =  N ∑ −  X(k ) N WN kn , 0 ≤ n ≤ N −1 k =0 0  , n coøn laïi Ta coù ZT[x(n)N] nhö sau : N −1 1 N −1  1 N −1 N −1 X ( z) = ∑  ∑ X (k ) N W N− kn .z − n = N ∑ X (k ) N ∑ W N− kn z − n n=0  N k =0  k =0 n=0 1 N −1 N −1 1 N −1 1 − (W N k z −1 ) N − = N ∑ X (k ) N ∑ (W N−k z −1 ) n = k =0 n =0 N ∑ X (k ) N k =0 1 − W N k z −1 − nhöng −kN WN = 1 vaäy 1− z −N N −1 X (k ) N X ( z) = N ∑ 1−W k =0 −k z −1 (4.61) N Nhaän xeùt : Im[z] - Coù theå noùi raèng, chuùng ta coù theå nhaän ñöôïc bieán ñoåi z cuûa moät daõy coù chieàu daøi höõu haïn töø N giaù trò cuûa X(k)N. K= 0 - Caùc giaù trò (N giaù trò) cuûa X(k)N chính laø caùc maãu cuûa X(z) ñöôïc ñaùnh giaù treân voøng troøn 2π Re[z] ñôn vò taïi caùc ñieåm rôøi raïc k , vaäy treân N voøng troøn ñôn vò ta laáy maãu x(z) taïi caùc ñieåm nhö sau : 2π j k jωk − z=e =e N = WN k K= 7 vaø ta coù theå vieát : Hình 4.19 Xöû Lyù Tín Hieäu Soá 155
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc N −1 X ( z) − z =W N k = ∑ x ( n) N W N = X ( k ) N kn n =0 Ñeán ñaây ta coù theå noùi raèng bieåu thöùc (4.62) cho chuùng ta coâng thöùc bieán ñoåi z cuûa moät daõy coù chieàu daøi höõu haïn N töø N “maãu taàn soá” cuûa X(z) treân voøng troøn ñôn vò. Vò trí “caùc maãu taàn soá” treân voøng troøn ñôn vò trong maët phaúng z ñöôïc minh hoaï treân hình 4.19 vôùi N = 8. b. Khoâi Phuïc Bieán Ñoãi Fourier Chuùng ta coù theå nhaän ñöôïc bieán ñoåi Fourier töø bieán ñoåi z, neáu voøng troøn ñôn vò naèm trong mieàn hoäi tuï cuûa bieán ñoåi z. 1 − e − jωN N −1 X (k ) N X (e jω ) = X ( z ) z =e jω = N ∑ k =0 j 2π k 1− e e − jω N 1 − e − jωN N −1 X (k ) N = N ∑ k =0 j( 2π k −ω ) 1− e N ta bieát raèng : x  j2 x −j  x x  e − e 2  = 2e 2 sin x −j −j 1− e jx =e 2     2 vaäy : ωN N −1 sin  N −1 π  1 2 − j ω + k X (e jω )= N ∑ X (k ) N ω π e  2 N  (4.62) k =0 sin( − k) 2 N Bieåu thöùc (4.62) chính laø quan heä cho pheùp ta tìm bieán ñoåi Fourier baèng caùch noäi suy töø caùc giaù trò X(k)N. 4.5 Bieán Ñoåi Fourier Nhanh (FFT) Ñeå tieát kieäm thôøi gian tính toaùn trong bieán ñoåi Fourier rôøi raïc (DFT), ta söû duïng thuaät toaùn bieán ñoåi nhanh Fourier (FFT) baèng caùch chia nhoû soá ñieåm ñeå xöû lyù. 4.5.1 Thuaät Toaùn FFT Cô Soá 2 Chia Theo Thôøi Gian a. Tính ñoái xöùng W k ( N − n ) = ( W kn ) * (4.63) b. Tính tuaàn hoaøn W kn = W k ( n + N ) = W ( k + N ) n = W ( k + N )( n + N ) (4.64) Xeùt bieán ñoåi Fourier rôøi raïc N ñieåm cuûa chuoãi x(n) Xöû Lyù Tín Hieäu Soá 156
Chöông 4 - Bieåu Dieãn Tín Hieäu Vaø Heä Thoáng Rôøi Raïc Trong Mieàn Taàn Soá Rôøi Raïc N −1 X(k ) = ∑ x (n ) W kn vôùi k = 0, 1, 2, … , N-1 (4.65) n =0 ta taùch daõy x(n) ra nhöõng daõy chaün vaø daõy leû nhö sau : N −1 N −1 X(k ) = ∑ x (n )W kn + ∑ x (n)W kn n = chaün n = leû hoaëc thay theá bieán n = 2r ñoái vôùi n chaün vaø n = 2r + 1 ñoái vôùi n leû, ta coù : N N −1 −1 2 2 X(k ) = ∑ x (2r ) W 2 rk + ∑ x (2r + 1) W k ( 2 r +1) r =0 n = 0û maø W2 = WN/2 do W2 = e-j2(2π/N) = e-j2π(N/2) = WN/2 do ñoù ta coù theå vieát laïi bieåu thöùc nhö sau : N N −1 −1 2 2 X(k ) = ∑ x (2r ) WN / 2 + WN ∑ x (2r + 1) WN / 2 rk k rk r =0 n = 0û N −1 2 ñaët X 0 ( k ) = ∑ x ( 2 r ) WN / 2 rk vôùi (X0 töông öùng r chaün) r =0 N −1 2 vaø X 1 (k ) = ∑ x (2r + 1) WN / 2 rk vôùi (X1 töông öùng r leû) n = 0û nhö vaäy ta coù : X(k) = X0(k) + Wk. X1(k) Ví duï 4.8 : xeùt hình 4.20 , choïn N = 8, k = 4, ta coù : Giaûi : X(4) = X0(4) + WN4. X1(4) Do tính chaát tuaàn hoaøn neân X0(4) = X0(0) vaø X1(4) = X1(0) neân X(4) = X0(0) + WN4. X1(0) Ta coù theå laøm moät pheùp so saùnh nhö sau : - Moät DFT coù N ñieåm thì caàn N2 pheùp nhaân phöùc vaø khoaûng N2 pheùp coäng phöùc. - Neáu taùch thaønh 2 DFT coù N/2 ñieåm thì caàn 2(N/2)2 pheùp nhaân phöùc vaø khoaûng 2N(/2)2 pheùp coäng phöùc ñeå thöïc hieän X0(k) vaø X1(k) vaø maát theâm N pheùp nhaân phöùc giöõa W vaø X1(k) vaø theâm N pheùp coäng phöùc ñeå tính X(k) töø X0(k) vaø W.X1(k). Nhö vaäy, toång coäng ta caàn N + 2(N/2)2 = N + N2/2 pheùp nhaân phöùc vaø pheùp coäng phöùc ñeå tính taát caû caùc giaù trò cuûa X(k). Xöû Lyù Tín Hieäu Soá 157