Đáp án môn: Lý thuyết thông tin

Chia sẻ: Chao Hello | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

400
lượt xem 102
download

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

Lượng thông tin riêng là độ bất định tiềm năng chứa trong một biến cố ngẫu nhiên...

Chủ đề:

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

Lưu

Nội dung Text: Đáp án môn: Lý thuyết thông tin

®¸p ¸n Ngµnh ®µo t¹o: §iÖn tö – viÔn th«ng HÖ ®µo t¹o : §¹i häc Sè §VHT: 4 M«n häc : Lý thuyÕt th«ng tin M· sè 411 LTT 340A PhÇn 1: lý thuyÕt th«ng tin C©u 1: (1 ®iÓm): §Þnh nghÜa l−îng th«ng tin riªng (®é bÊt ®Þnh) cña mét biÕn ngÉu nhiªn. X¸c ®Þnh c¸c ®¬n vÞ ®o - §Þnh nghÜa l−îng th«ng tin riªng (®é bÊt ®Þnh) L−îng th«ng tin riªng lµ ®é bÊt ®Þnh tiÒm n¨ng chøa trong mét biÕn cè ngÉu nhiªn xk . Ký hiÖu I ( xk ) I ( xk ) = k ln p ( xk ) - C¸c ®¬n vÞ ®o I ( xk ) = − ln p ( xk ) (nat) k = −1 1 I ( xk ) = − log 2 p ( xk ) (bÝt) k=− ln 2 1 I ( xk ) = − lg p ( xk ) (hart) k=− ln10 1 nat = 1,443 bÝt 1 hart = 3,322 bÝt C©u 2: (1 ®iÓm) §Þnh nghÜa entropy cña nguån rêi r¹c Entropy cña nguån tin rêi r¹c A lµ trung b×nh thèng kª cña l−îng th«ng tin riªng cña c¸c tin thuéc A Ký hiÖu: H1 ( A ) Δ H1 ( A ) = M ⎡ I ( a i ) ⎤ ⎣ ⎦ ⎛ a1 as ⎞ a2 ... A=⎜ ⎟ ⎝ p ( a1 ) p ( a 2 ) ... p ( a s ) ⎠ s ∑ p(a ) = 1 0 ≤ p (ai ) ≤ 1 i i =1 s' H1 ( A ) = −∑ p ( a i ) log p ( a i ) (bÝt) i =1 http://www.ebook.edu.vn 1
C©u 3: (1 ®iÓm) Nªu c¸c tÝnh chÊt cña entropy cña nguån rêi r¹c C¸c tÝnh chÊt cña H1 ( A ) - Khi p ( a k ) = 1 , p ( a i ) = 0 víi ∀i ≠ k th× H1 ( A ) = H1 ( A )min = 0 - Mét nguån tin rêi r¹c gåm s dÊu ®ång x¸c suÊt cho entropy cùc ®¹i. Ta cã H1 ( A )max = logs - Entropy cña nguån rêi r¹c lµ mét ®¹i l−îng giíi néi 0 ≤ H1 ( a ) ≤ logs C©u 4: (1 ®iÓm) §Þnh nghÜa kh¶ n¨ng th«ng qua kªnh rêi r¹c, nªu c¸c tÝnh chÊt? - §Þnh nghÜa: Kh¶ n¨ng th«ng qua cña kªnh rêi r¹c lµ gi¸ trÞ cùc ®¹i cña l−îng th«ng tin chÐo trung b×nh truyÒn qua kªnh trong mét ®¬n vÞ thêi gian lÊy theo mäi kh¶ n¨ng cã thÓ cã cña nguån tin A. Δ C' = max I' ( A,B ) = v k max I ( A, B ) (bps) A A - C¸c tÝnh chÊt: + C' ≥ 0 C' = 0 khi A vµ B lµ ®éc lËp (kªnh bÞ ®øt) + C' ≤ v k logs C' = v k logs khi kªnh kh«ng nhiÔu C©u 5: (2 ®iÓm) Entropy cña nguån rêi r¹c nhÞ ph©n. ý nghÜa cña d¬n vÞ ®o bÝt? - Entropy cña nguån rêi r¹c nhÞ ph©n. ⎛a a2 ⎞ A=⎜ 1 ⎟ H1 ( A ) (bits) ⎝ p 1− p⎠ H1 ( A )max = −plog p − (1 − p ) log (1 − p ) 1 1 Khi p = 1 − p = 2 p H1 ( A ) = H1 ( A )max = 1bit 0,5 1 - ý nghÜa: 1 bÝt lµ l−îng th«ng tin riªng trung b×nh chøa trong mét biÕn cè cña mét nguån rêi r¹c 2 ph©n ®ång x¸c suÊt. http://www.ebook.edu.vn 2
C©u 6: (2 ®iÓm) X¸c ®Þnh hai tr¹ng th¸i cùc ®oan cña kªnh rêi r¹c. - Kªnh bÞ ®øt: C¸c nguån tin A vµ B ë hai ®Çu thu vµ ph¸t lµ ®éc lËp. p (ai b j ) = p(ai ) p ( b j ai ) = p (ai ) p (ai b j ) = p (ai ) p ( b j ) H(A bj ) = H(A) Ta cã: H ( A B) = H ( A ) NhËn xÐt: L−îng th«ng tin tæn hao trung b×nh ®óng b»ng entropy cña nguån. Kªnh kh«ng thÓ truyÒn tin ®−îc - Kªnh kh«ng nhiÔu: A≡B p ( a k bk ) = 1 H ( A bk ) = 0 H ( A B) = 0 NhËn xÐt: L−îng th«ng tin tæn hao trªn kªnh b»ng 0 C©u 7: (2 ®iÓm) Entropy cã ®iÒu kiÖn H ( A B ) : ®Þnh nghÜa vµ nªu c¸c tÝnh chÊt - §Þnh nghÜa: Entropy cã ®iÒu kiÖn vÒ 1 tr−êng tin A khi ®· râ tr−êng tin B ®−îc x¸c ®Þnh theo c«ng thøc sau: s t H ( A B ) = −∑∑ p ( a i b j ) log p ( a i b j ) i =1 j=1 - C¸c tÝnh chÊt: + H ( AB ) = H ( A ) + H ( B A ) = H ( B ) + H ( A B ) + 0 ≤ H ( A B) ≤ H ( A ) + H ( AB ) = H ( A ) + H ( B ) C©u 8: (2 ®iÓm) L−îng th«ng tin chÐo trung b×nh truyÒn qua kªnh rêi r¹c: ®Þnh nghÜa vµ tÝnh chÊt - §Þnh nghÜa: I ( A, B ) = M ⎡ I ( a i ,b j ) ⎤ Δ ⎣ ⎦ p (ai b j ) I ( a i ,b j ) = log víi p (ai ) http://www.ebook.edu.vn 3
p (ai b j ) s t I ( A,B ) = ∑∑ p ( a i b j ) log p (ai ) i =1 j=1 I ( A, B ) = H ( A ) − H ( A B ) = H ( B ) − H ( B A ) - TÝnh chÊt: + I ( A,B ) ≥ 0 + I ( A, B ) ≤ H ( A ) C©u 9: (3 ®iÓm) Cho kªnh ®èi xøng nhÞ ph©n sau p ( a1 ) = p A B p ( b1 a2 ) = pd p ( a2 ) = 1 − p a1 b1 p ( b1 a2 ) = p ( b2 a1 ) − ps = 1 − pd ps Cho tèc ®é truyÒn tin cña kªnh vk = 1 T ps a2 TÝnh kh¶ n¨ng th«ng qua C ' cña kªnh nµy. b2 p ( b2 a1 ) = pd Gi¶i: 1 1 Ta cã C' = max I ( A,B ) = max ⎡ H ( B ) − H ( B A ) ⎤ TA⎣ ⎦ TA Trong ®ã: 2 t H ( B A ) = −∑∑ p ( a i ) p ( b j a i ) log p ( b j a i ) i =1 j=1 = − p ( a1 ) ⎡ p ( b1 a1 ) log p ( b1 a1 ) + p ( b 2 a1 ) log p ( b 2 a1 ) ⎤ − ⎣ ⎦ − p ( a 2 ) ⎡ p ( b1 a 2 ) log p ( b1 a 2 ) + p ( b 2 a 2 ) log p ( b 2 a 2 ) ⎤ ⎣ ⎦ = − p ⎡(1 − ps ) log (1 − ps ) + ps log ps ⎤ − (1 − p ) ⎡ ps log ps + (1 − ps ) log (1 − ps ) ⎤ ⎣ ⎦ ⎣ ⎦ = − ⎡ ps log ps + (1 − ps ) log (1 − ps ) ⎤ ⎣ ⎦ Ta thÊy H ( B A ) kh«ng phô thuéc vµo x¸c suÊt tiªn nghiÖm cña c¸c tin thuéc nguån A. Do ®ã: 1 1 max H ( B ) − H ( B A ) C' = C' C'max TA T Ta cã max H ( B ) = H ( B )max = log 2 = 1bit A 1 1 C'max = khi ps = 0 (kªnh kh«ng nhiÔu) T C' ps = 1 + ps log ps + (1 − ps ) log (1 − ps ) 0,5 1 C'max http://www.ebook.edu.vn 4
C©u 10: (3 ®iÓm) A chän ngÉu nhiªn mét trong c¸c sè tõ 0 ®Õn 7. TÝnh sè c©u hái trung b×nh tèi thiÓu mµ B cÇn ®Æt cho A ®Ó x¸c ®Þnh ®−îc sè mµ A ®· chän. Nªu thuËt to¸n hái? Gi¶ sö A ®· chän sè 3, h·y ®Æt c¸c c©u hái cÇn thiÕt? §é bÊt ®Þnh cña sè ®−îc chän ngÉu nhiªn: 1 I ( a i ) = − log p ( a i ) = − log = 3bit 8 §Ó t×m ®−îc sè ®· chän cña A, B ph¶i ®Æt c¸c c©u hái cho A ®Ó thu ®−îc ®ñ mét l−îng th«ng tin cÇn thiÕt lµ 3 bÝt. Mçi c©u hái cña B (d¹ng lùa chän) cã thÓ xem lµ nguån rêi r¹c nhÞ ph©n, bëi vËy l−îng th«ng tin nhËn ®−îc sau mçi c©u tr¶ lêi t−¬ng øng lµ: H ( B ) = − plog p − (1 − p ) log (1 − p ) p : x¸c suÊt nhËn c©u tr¶ lêi ″®óng ″ Víi 1 − p : x¸c suÊt nhËn c©u tr¶ lêi ″sai″ I(ai ) VËy sè c©u hái cÇn thiÕt n lµ : n = H ( B) I (ai ) Sè c©u hái trung b×nh tèi thiÓu lµ: n min = H ( B )max 1 H ( B )max khi p = 1 − p = 2 3bit n min = = 3 lÇn hái 1bit Gi¶ sö A chän sè B. C¸c c©u hái b cã thÓ ®Æt cho A lµ: - C©u 1 - Sè A chän lín h¬n 3? Tr¶ lêi: Sai - C©u 2 - Sè A chän lín h¬n 1? Tr¶ lêi: §óng - C©u 3 - Sè A chän lín h¬n 2? Tr¶ lêi: Sai VËy sè A chän lµ 3 C©u 11: (4 ®iÓm) Mét thiÕt bÞ v« tuyÕn ®iÖn gåm 16 khèi cã ®é tin cËy nh− nhau vµ ®−îc m¾c nèi tiÕp. Ta sö dông mét thiÕt bÞ ®o ®Ó ®o tÝn hiÖu ra cña c¸c khèi. Gi¶ sö cã mét khèi nµo ®ã bÞ háng. H·y tÝnh sè lÇn ®o trung b×nh tèi thiÓu ®Ó t×m ®−îc khèi bÞ háng. Nªu thuËt to¸n ®o? Gi¶ sö khèi háng lµ khèi thø 6, t×m vÞ trÝ c¸c ®iÓm ®o cÇn thiÕt? Theo gi¶ thiÕt ®é bÊt ®Þnh cña khèi háng lµ: 1 I ( a i ) = − log p ( a i ) = − log = 4bit 16 L−îng th«ng tin nhËn ®−îc sau mçi phÐp ®o: H ( B ) = − plog p − (1 − p ) log (1 − p ) http://www.ebook.edu.vn 5
Víi p : x¸c suÊt cã tÝn hiÖu 1 − p : x¸c suÊt kh«ng cã tÝn hiÖu §Ó x¸c ®Þnh ®−îc khèi háng (khö hÕt ®é bÊt ®Þnh) sè phÐp ®o cÇn thiÕt n lµ: I (ai ) n min = H ( B )max 1 H ( B ) → max khi p = 1 − p = 2 H ( B )max = 1bit 4bit n min = = 4 lÇn ®o 1bit §Ó nmin thuËt to¸n ®o ph¶i ®¶m b¶o H ( B ) → max ⇒ Mçi lÇn ®o ph¶i ®o ë 1 ®iÓm gi÷a cña c¸c khèi cÇn x¸c ®Þnh nh»m ®¶m b¶o p = 1 − p = . 2 Gi¶ sö khèi háng lµ khèi 6. C¸c phÐp ®o cÇn thiÕt lµ: - LÇn 1: §o ë ®Çu ra khèi 8: Kh«ng cã tÝn hiÖu, khèi háng n»m trong c¸c khèi tõ 1 → 8. - LÇn 2: §o ë ®Çu ra khèi 4: Kh«ng cã tÝn hiÖu, khèi háng n»m trong c¸c khèi tõ 5 → 8. - LÇn 3: §o ë ®Çu ra khèi 6: Kh«ng cã tÝn hiÖu, khèi háng n»m trong khèi 5 hoÆc 6. - LÇn 4: §o ë ®Çu ra khèi 5: Cã tÝn hiÖu. VËy khèi háng lµ khèi 6 C©u 12: (4 ®iÓm) Trong bé tó l¬ kh¬ 52 qu©n (kh«ng kÓ f¨ng teo), A rót ra mét qu©n bµi bÊt kú. TÝnh sè c©u hái trung b×nh tèi tiÓu mµ B cÇn ®Æt cho A ®Ó x¸c ®Þnh ®−îc qu©n bµi mµ A ®· rót. Nªu thuËt to¸n hái? Gi¶ sö A rót ra 7 qu©n r«, h·y nªu c¸c c©u hái cÇn thiÕt? §é bÊt ®Þnh vÒ qu©n bµi mµ A ®· rót: 1 I ( a i ) = − log p ( a i ) = − log < 6bit 52 Gi¶ sö B ®Æt cho A c©u hái d¹ng lùa chän, khi ®ã l−îng th«ng tin nhËn ®−îc sau mçi c©u tr¶ lêi cña A lµ: H ( B ) = − plog p − (1 − p ) log (1 − p ) p : x¸c suÊt nhËn c©u tr¶ lêi lµ ″®óng ″ Víi 1 − p : x¸c suÊt nhËn c©u tr¶ lêi lµ ″sai″ I(ai ) Sè c©u hái cÇn thiÕt ®Ó x¸c ®Þnh ®−îc qu©n bµi A ®· rót lµ: n = H ( B) http://www.ebook.edu.vn 6
Ta thÊy n → min khi H ( B ) → max 1 H ( B ) = H ( B )max = 1bit khi p = 1 − p = 2 log52 bit Sè c©u hái trung b×nh tèi thiÓu lµ: n min = < 6 lÇn 1bit 1 ThuËt to¸n ph¶i ®¶m b¶o p = 1 − p = . 2 Gi¶ sö A rót ra 7 r«. C¸c c©u hái cÇn thiÕt cã thÓ nh− sau: - C©u 1: Qu©n A rót lµ qu©n ®á? §óng - C©u 2: Qu©n A rót lµ qu©n c¬? Sai - C©u 3: Qu©n A rót cã gi¸ trÞ ≤ 7? §óng (gi¶ sö J = 11, Q = 12, K = 13, At=1) - C©u 4: Qu©n A rót cã gi¸ trÞ ≤ 3? Sai - C©u 5: Qu©n A rót cã gi¸ trÞ ≤ 5? Sai - C©u 6: Qu©n A rót lµ 6 r«? Sai VËy qu©n A rót lµ 7 r« C©u 13 :(4 ®iÓm) Trong 27 ®ång xu cã 1 ®ång xu gi¶ nhÑ h¬n. §Ó t×m ®−îc ®ång xu gi¶ ng−êi ta sö dông mét c©n ®Üa th¨ng b»ng. H·y tÝnh sè lÇn c©n trung b×nh tèi thiÓu ®Ó x¸c ®Þnh ®−îc ®ång xu gi¶. Nªu thuËt to¸n c©n ? Theo gi¶ thiÕt ®é bÊt ®Þnh chøa trong sù kiÖn ®ång xu gi¶ lµ : I(xi) = - log p(xi) = - log 1/27 = log 27 bit Khi sö dông c©n ®Üa th¨ng b»ng, sau mçi lÇn c©n c¸c sù kiÖn cã thÓ cã lµ : - C©n th¨ng b»ng víi x¸c suÊt p - C©n lÖch tr¸i víi x¸c suÊt q - C©n lÖch ph¶i víi x¸c suÊt 1-p-q L−îng th«ng tin nhËn ®−îc sau mçi lÇn c©n : H(B) = -plog p – qlog q – (1-p-q)log (1-p-q) §Ó x¸c ®Þnh ®−îc ®ång xu gi¶ tæng l−îng th«ng tin nhËn ®−îc sau c¸c lÇn c©n ph¶i kh«ng nhá h¬n ®é bÊt ®Þnh cña ®«ng xu gi¶. Nh− vËy sè lÇn c©n cÇn thiÕt lµ : n = I(xi)/H(B) §Ó n cã gi¸ trÞ nhá nhÊt th× H(B) ph¶i ®¹t gi¸ trÞ cùc ®¹i. Ta cã H(B) = H(B)max= log 3 khi p = q = 1-p-q = 1/3. Khi ®ã nmin= I(xi)/H(B)max = log27/log 3 = 3 lÇn c©n. ThuËt to¸n c©n nh− sau( ®¶m b¶o p = q = 1-p-q ) - LÇn 1 : Chia 27 ®ång xu thµnh 3 phÇn, mçi phÇn cã 9 ®ång xu. LÊy 2 phÇn bÊt kú ®Æt lªn mçi bµn c©n 1 phÇn . NÕu c©n th¨ng b»ng th× ®ång xu gi¶ http://www.ebook.edu.vn 7
n»m trong 9 ®ång xu ch−a c©n. Ng−îc l¹i, tuú theo c©n lÖch tr¸i hay lÖch ph¶i ta còng x¸c ®Þnh ®−îc phÇn cã chøa ®ång xu gi¶. - LÇn 2 : Chia 9 ®ång cã chøa ®ång xu gi¶ thµnh 3 phÇn nh− nhau, mçi phÇn cã 3 ®ång xu. §Æt 2 phÇn bÊt kú lªn 2 bµn c©n. KÕt qu¶ cña phÐp c©n sÏ gióp ta x¸c ®Þnh ®−îc 3 ®ång xu cã chøa ®«ng xu gi¶. - LÇn 3 : LÊy 2 ®ång xu bÊt kú trong 3 ®ång xu cã chøa ®ång xu gi¶ ®Æt lªn 2 ®Üa c©n. Sau lÇn c©n nµy ta sÏ x¸c ®Þnh ®−îc ®ång xu gi¶. C©u 14 : (2 ®iÓm) TÝnh entropie cña tr−êng sù kiÖn ®ång thêi ? XÐt 2 tr−êng sù kiÖn A vµ B sau : ⎧ bj ⎫ ⎧ ai ⎫ ⎪ ⎪ A=⎨ ⎬ i = 1,0 B=⎨ ⎬ j = 1, t ⎪p ( b j )⎪ ⎩p ( a i ) ⎭ ⎩ ⎭ Khi ®ã, tr−êng sù kiÖn ®ång thêi C = A.B lµ : ⎧ aib j ⎫ ⎪ ⎪ C=⎨ ⎬ ∀i, j, i = 1,0, j = 1, t ⎪p ( a i ) p ( b j ) ⎪ ⎩ ⎭ Theo ®Þnh nghÜa, entropie cña tr−êng sù kiÖn ®ång thêi ®−îc x¸c ®Þnh nh− sau : s t H ( C ) = −∑∑ p ( a i b j ) log p ( a i b j ) i =1 j=1 C©u 15: (2 ®iÓm) Cho kªnh nhÞ ph©n ®èi xøng kh«ng nhí sau (h×nh vÏ). H·y tÝnh ph©n bè x¸c suÊt cña c¸c tin ë ®Çu ra? BiÕt r»ng p(a1)=p ; p(a2)=1-p. p ( b1 a2 ) = pd A B a1 b1 Theo c«ng thøc x¸c suÊt ®Çy ®ñ ta cã: p ( b1 ) = p ( a1 ) .p ( b1 a1 ) + p ( a 2 ) .p ( b1 a 2 ) pS p ( b 2 ) = p ( a1 ) .p ( b 2 a1 ) + p ( a 2 ) .p ( b 2 a 2 ) pS = 1 − p ( b1 ) p ( b2 a1 ) = pd a2 b2 PhÇn 2: lý thuyÕt m∙ ho¸ C©u 1: (1 ®iÓm): §Þnh nghÜa ®é dµi trung b×nh cña tõ m· ? Ph¸t biÓu ®Þnh lý m· ho¸ thø nhÊt cña Shannon? XÐt phÐp m· ho¸ c¸c tin rêi r¹c sau: a i → α ini http://www.ebook.edu.vn 8
⎛ α ini ⎞ ⎛ ai ⎞ A=⎜ ⎟→V=⎜⎜ p(a ) ⎟ ⎝ p (ai ) ⎠ ⎟ ⎝ i⎠ - §Þnh nghÜa: §é dµi trung b×nh cña tõ m· lµ kú väng cña ®¹i l−îng ngÉu nhiªn n i s n = ∑ p ( ai ) ni i =1 - §Þnh lý m· ho¸ thø nhÊt cña Shannon (®èi víi m· nhÞ ph©n) Lu«n lu«n cã thÓ x©y dùng ®−îc mét phÐp m· ho¸ c¸c tin rêi r¹c cã hiÖu qu¶ mµ ®é dµi trung b×nh cña tõ m· cã thÓ nhá tuú ý, nh−ng kh«ng nhá h¬n entropie x¸c ®Þnh bëi c¸c ®Æc tÝnh thèng kª cña nguån n ≥ H1 ( A ) C©u 2: (1 ®iÓm) Nªu nguyªn t¾c lËp m· tiÕt kiÖm? Tõ ®Þnh lý m· ho¸ thø 1 cña Shannon: s s n = ∑ p ( a i ) n i ≥ H1 ( A ) = −∑ p ( a i ) log p ( a i ) i =1 i =1 1 ta cã: n i ≥ log p (ai ) Nguyªn t¾c: C¸c tin cã x¸c suÊt xuÊt hiÖn lín ®−îc m· ho¸ b»ng c¸c tõ m· cã ®é dµi nhá vµ ng−îc l¹i c¸c tin cã x¸c suÊt xuÊt hiÖn nhá ®−îc m· ho¸ b»ng c¸c tõ m· cã ®é dµi lín. C©u3: (1 ®iÓm) Träng sè cña tõ m·: ®Þnh nghÜa vµ tÝnh chÊt? () - §Þnh nghÜa träng sè cña tõ m·: W αini Träng sè cña 1 tõ m· lµ sè c¸c dÊu m· kh¸c kh«ng chøa trong tõ m· - TÝnh chÊt: () + 0 ≤ W α ini ≤ 1 ( )( ) + W α in + α n = d α in , α n j j C©u 4: (1 ®iÓm) Nªu c¸c ®Þnh lý quy ®Þnh kh¶ n¨ng ph¸t hiÖn sai vµ kh¶ n¨ng söa sai cña mét bé m·? - §Þnh lý vÒ kh¶ n¨ng ph¸t hiÖn sai: M· ®Òu nhÞ ph©n cã ®é thõa víi kho¶ng c¸ch Hamming d 0 > 1 cã kh¶ n¨ng ph¸t hiÖn t sai tho¶ m·n ®iÒu kiÖn t ≤ d 0 − 1 . - §Þnh lý vÒ kh¶ n¨ng söa sai: http://www.ebook.edu.vn 9
M· ®Òu nhÞ ph©n cã ®é thõa víi kho¶ng c¸ch Hamming d 0 ≥ 3 cã kh¶ n¨ng ⎡ d − 1⎤ söa ®−îc t sai tho¶ m·n ®iÒu kiÖn: t ≤ ⎢ 0 ⎥ . Trong ®ã [ x ] ký hiÖu phÇn ⎣2⎦ nguyªn cña sè x. C©u 5: (2 ®iÓm) Kho¶ng c¸ch m·: ®Þnh nghÜa, tÝnh chÊt? §Þnh nghÜa kho¶ng c¸ch m· tèi thiÓu? - §Þnh nghÜa: Kho¶ng c¸ch gi÷a hai tõ m· αin vµ α n lµ sè c¸c dÊu m· kh¸c nhau vÒ gi¸ j trÞ tÝnh theo cïng mét thø tù gi÷a 2 tõ m· nµy. αi7 = 0 1 1 0 1 0 0 VÝ dô: α7 = 1 0 1 0 0 1 1 j ** *** ( ) d αi7 , α 7 = 5 j - TÝnh chÊt: ( ) + d α in , α n ≥ 0 j d (α ,α ) = 0 khi α in ≡ α n n n j i j d (α ,α ) ≤ n n n + i j ( )( )( ) + TÝnh chÊt tam gi¸c: d α in , α n + d α n , α n ≥ d α in , α n j j k k §Þnh nghÜa kho¶ng c¸ch m· tèi thiÓu: d0= min d( ain, ajn) víi mäi i,j C©u 6: (2 ®iÓm) Cho m· xyclic V - ( n - k ) cã ®a thøc sinh g ( x ) = 1+ x + x 3 ( n = 7, k = 4 ) . H·y thiÕt lËp ma trËn sinh vµ ma trËn kiÓm tra cña m· nµy? Cho ma trËn sinh G. ⎛1 +x3 ⎞ ⎛ 1 1 0 1 0 0 0 ⎞ +x ⎜ ⎟⎜ ⎟ +x2 +x4 ⎟ ⎜ 0 1 1 0 1 0 0 ⎟ ⎜x = G= 2 ⎜x + x5 ⎟ ⎜ 0 0 1 1 0 1 0 ⎟ +x3 ⎜3 ⎟⎜ ⎟ ⎜x +x6 ⎟ ⎝ 0 0 0 1 1 0 1 ⎠ +x4 ⎝ ⎠ Ma trËn kiÓm tra H : x7 + 1 Ta cã : h ( x ) = = x4 + x2 + x + 1 g(x) http://www.ebook.edu.vn 10
x7 + 1 x3 + x + 1 x7 + x5 + x 4 x 4 + x 2 + x + 1 x5 + x 4 + 1 x5 + x3 + x2 x 4 + x3 + x 2 + 1 x4 + x2 + x x3 + x + 1 x3 + x + 1 0 () h * ( X ) = X ( ) h X −1 = x 4 + x 3 + x 2 + 1 deg h x ⎛ h* ( x ) ⎞ ⎜ ⎟ x.h * ( x ) ⎟ H=⎜ ⎜ ........ ⎟ ⎜ r −1 * ⎜ x .h ( x ) ⎟ ⎟ ⎝ ⎠ ⎛ 1 + x + x + x 4 ⎞ ⎛ 1 0 1 110 0 ⎞ 2 3 ⎜ ⎟⎜ ⎟ H = ⎜ x + x 3 + x 4 + x 5 ⎟ = ⎜ 0 1 0 111 0 ⎟ ⎜ x 2 + x 4 + x 5 + x 6 ⎟ ⎜ 0 0 1 011 1 ⎟ ⎠⎝ ⎠ ⎝ Ta cã G.H T = 0 C©u 7: (2 ®iÓm) h·y thiÕt lËp tõ m· hÖ thèng cña bé m· xyclic (7,4) cã ®a thøc sinh g ( x ) = 1+ x + x 3 t−¬ng øng víi ®a thøc th«ng tin a ( x ) = x + x 3 . (Sö dông thuËt to¸n 4 b−íc). - B−íc 1: a ( x ) = x + x 3 ( ) - B−íc 2: N©ng bËc a ( x ) x n-k = x 3 + x x 7−4 = x 6 + x 4 - B−íc 3: Chia tÝnh d−: x6 + x 4 x 3 + x + 1 x6 + x 4 + x3 x3 + 1 x3 x3 + x + 1 r(x) = x +1 - B−íc 4: ThiÕt lËp tõ m· f(x) f ( x ) = a ( x ) x n −k + r ( x ) f (x) = x6 + x4 + x + 1 ↔ 1 1 0 0 1 0 1 x6 . . . . . . x6 http://www.ebook.edu.vn 11
C©u 8: (2 ®iÓm) Cho ph©n tÝch x 7 +1 nh− sau ( )( ) x 7 +1= ( 1+ x ) 1 + x + x 3 1 + x 2 + x 3 H·y nªu tÊt c¶ c¸c m· xyclic cã thÓ cã trªn vµnh Z2 [ x ] x 7 +1 . TT §a thøc sinh g(x) M· (n, k) d0 ( 7,6 ) 1 2 1+ x ( 7,4 ) 2 3 1 + x + x3 ( 7,4 ) 3 3 1 + x 2 + x3 ( 7,3) 4 4 1 + x + x2 + x4 ( 7,3) 5 4 1 + x2 + x3 + x 4 ( 7,1) 6 7 6 ∑x i i=0 ( 7,7 ) 7 1 1 C©u 9: (4 ®iÓm) H·y thùc hiÖn m· ho¸ Shannon – Fano cho nguån rêi r¹c A sau: ⎛ a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 ⎞ A=⎜ 1 1 1 1 1 1 1⎟ 1 1 1 ⎜ ⎟ ⎜ ⎟ ⎝ 4 4 8 8 8 32 32 32 64 64 ⎠ §¸nh gi¸ hiÖu qu¶ cña phÐp m· ho¸ nµy? H·y gi¶i m· cho d·y bÝt nhËn ®−îc cã d¹ng: 101100111010101… p (ai ) Tõ m· α ini TT ai ni 1 0 0 2 a1 14 2 0 1 2 a2 14 3 1 0 0 3 a3 18 4 1 0 1 3 a4 18 5 1 1 0 3 a5 18 6 1 1 1 0 0 5 a6 1 32 7 1 1 1 0 1 5 a7 1 32 8 1 1 1 1 0 5 a8 1 32 9 1 1 1 1 1 0 6 a9 1 64 10 1 1 1 1 1 1 6 a10 1 64 http://www.ebook.edu.vn 12
- §¸nh gi¸ hiÖu qu¶: 1 1 1 1 10 n = ∑ p ( a i ) n i = 2.2. + 3.3. + 3.5. + 2.6. 4 8 32 64 i =1 9 15 6 25 =1+ + + = 2. dÊu 8 32 32 32 1 1 1 1 1 10 H1 ( A ) = ∑ p ( a i ) log = 2. .log 4 + 3. log8 + 3. log 32 + 2. log 64 p (ai ) 4 8 32 64 i =1 25 = 2. bit 32 n = H1 ( A ) ⇒ phÐp m· ho¸ lµ tèi −u - Gi¶i m· cho d·y bÝt nhËn sau: 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 ... ↓ ↓ ↓ ↓ ↓ a4 a3 a8 a4 a2 C©u 10: (4 ®iÓm) Gi¶ sö tõ m· nhËn ®−îc cña m· xyclic (7,3) víi ®a thøc sinh g ( x ) = 1+ x + x 2 + x 4 cã d¹ng sau v ( x ) = x 6 + x 5 + x 4 + x 3 + x 2 . H·y sö dông thuËt to¸n chia dÞch vßng ®Ó t×m ®−îc tõ m· ®· ph¸t, biÕt r»ng m· (7, 3) nµy cã d0 = 4 . - B−íc 1: Chia v(x) cho g(x) x6 + x 5 + x 4 + x 3 + x 2 x 3 + x + 1 x6 + x 4 + x3 + x 2 x2 + x x5 x5 + x3 + x 2 + x r0 ( x ) = x 3 + x 2 + x ⎡ d − 1⎤ ⎡ 4 − 1⎤ - B−íc 2: W ( r0 ( x ) ) = 3 > t = ⎢ = = 1,5 ⎣2⎥ ⎢2⎥⎦⎣ ⎦ - B−íc 3: (lÇn 1) x.v ( x ) = x 6 + x 5 + x 4 + x 3 + 1 x6 + x 5 + x 4 + x 3 + 1 x 3 + x + 1 x6 + x 4 + x3 + x 2 x2 + x x5 + x 2 + 1 x5 + x3 + x 2 + x r1 ( x ) = x 3 + x + 1 W ( r1 ( x ) ) = 3 > t = 1 ⇒ B−íc 3 http://www.ebook.edu.vn 13
- B−íc 3: (lÇn 2): x 2 .v ( x ) = x 6 + x 5 + x 4 + x + 1 x6 + x 5 + x 4 + x + 1 x 3 + x + 1 x6 + x 4 + x3 + x 2 x2 + x x5 + x3 + x 2 + x + 1 x5 + x3 + x 2 + x r2 ( x ) = 1 W ( r2 ( x ) ) = 1 = t - B−íc 4: x 2 v ( x ) + r2 ( x ) x 6 + x 5 + x 4 + x ^ f (x) = = x2 x2 ^ f ( x ) = x 6 + x 4 + x 3 + x 2 ↔ 0011101 * Sai ë x 5 ®· ®−îc söa C©u 11: (3 ®iÓm) H·y x¸c ®Þnh tËp tÊt c¶ c¸c tõ m· cña bé m· xyclic (7, 3) cã ®a thøc sinh g ( x ) = 1+ x 2 + x 3 + x 4 . Cho m· xyclic (7, 3) cã g ( x ) = 1 + x 2 + x 3 + x 4 ma trËn sinh: ⎛ 1 + x 2 + x 3 + x 4 ⎞ ⎛ 1 0 1 110 0 ⎞ ⎜ ⎟ G = ⎜ x + x 3 + x 4 + x 5 ⎟ = ⎜ 0 1 0 111 0 ⎟ ⎜ ⎟ ⎜ x 2 + x 4 + x 5 + x 6 ⎟ ⎜ 0 0 1 011 1 ⎟ ⎠⎝ ⎠ ⎝ TËp 2 k = 23 = 8 tõ m·, trong ®ã 7 tõ m· kh¸c kh«ng lµ tËp c¸c tæ hîp tuyÕn tÝnh c¸c hµng cña ma trËn G g ( x ) = 1+ x 2 + x 3 + x 4 ↔ 1 0 1 1 1 0 0 xg ( x ) = x + x 3 + x 4 + x 5 ↔ 0 1 0 1 1 1 0 x 2g ( x ) = x 2 + x 4 + x 5 + x 6 ↔ 0 0 1 0 1 1 1 (1 + x ) g ( x ) = 1 + x + x 2 + x 5 ↔111 0 0 1 0 (1 + x 2 ) g ( x ) = 1 + x3 + x 5 + x 6 ↔1 0 0 1 0 11 (x + x )g(x) = x + x + x + x ↔ 0 111 0 0 1 2 2 3 6 (1 + x + x ) g ( x ) = 1 + x + x + x ↔11 0 0 1 0 1 2 4 6 http://www.ebook.edu.vn 14
C©u 12: (3 ®iÓm) Ph¸t biÓu vµ chøng minh giíi h¹n Hamming? §Þnh nghÜa m· hoµn thiÖn? - Giíi h¹n Hamming. Víi m· tuyÕn tÝnh (n, k), ®iÒu kiÖn cÇn ®Ó sö ®−îc t sai lµ: t ∑C ≤ 2n −k i n i =0 Chøng minh: Sè c¸c kiÓu sai cã träng sè i lµ Cin t Sè c¸c kiÓu sai cã träng sè ≤ t lµ: C0 + C1 + ... + Cn = ∑ Cin t n n i =0 Sè c¸c tr¹ng th¸i kh¸c nhau cña c¸c dÊu kiÓm tra lµ: 2r = 2n −k §Ó söa ®−îc sai, mçi tr¹ng th¸i cña c¸c dÊu kiÓm tra chØ ®−îc g¸n tèi ®a cho 1 kiÓu sai. t ∑C ≤ 2n − k VËy ®Ó söa ®−îc tÊt c¶ c¸c kiÓu sai cã träng sè ≤ t ta cã: i n i =0 - §Þnh nghÜa m· hoµn thiÖn. M· hoµn thiÖn lµ m· (n, k, d) ®¹t ®−îc giíi h¹n Hamming VÝ dô: M· (7, 4) cã d = 3 ⎡ d − 1⎤ Ta cã : t = ⎢ =1 ⎣2⎥ ⎦ C0 + C1 ≤ 27−4 = 23 = 8 7 7 1 + 7 =8 VËy m· (7, 4) lµ 1 m· hoµn thiÖn. C©u 13: (4 ®iÓm) Cho ph©n tÝch cña x15+1 nh− sau : X15+1=(1+x)(1+x+x2)(1+x+x4)(1+x3+x4)(1+x+x2+x3+x4) H·y nªu tÊt c¶ c¸c m· xyclic cã ®é dµi 15 trªn vµnh Z2[x]/x15+1? §Æt g1 ( X ) = 1 + X g2 ( X ) = 1 + X + X2 g3 ( X ) = 1 + X + X 4 g 4 ( X ) = 1 + X3 + X 4 http://www.ebook.edu.vn 15
TT §a thøc sinh M· (n,k) g1 ( X ) 1 (15,14) g2 ( X ) 2 (15,13) g3 ( X ) 3 (15,11) g4 ( X ) 4 (15,11) g5 ( X ) 5 (15,11) g1.g 2 6 (15,12) g1.g3 7 (15,10) g1.g 4 8 (15,10) g1.g5 9 (15,10) g 2 .g 3 10 (15,9) g 2 .( g 4 ) 11 (15,9) g 2 .g 5 12 (15,9) g 3 .g 4 13 (15,7) g 3 .g 5 14 (15,7) g 4 .g 5 15 (15,7) g1.g 2 .g 3 16 (15,8) g1.g 2 .g 4 17 (15,8) g1.g 2 .g 5 18 (15,8) g 2 .g 3.g 4 19 (15,5) g 2 .g 3 .g 5 20 (15,5) g1.g 3 .g 4 21 (15,6) g1.g 3.g 5 22 (15,6) g1.g 4 .g 5 23 (15,6) g 2 .g 4 .g 5 24 (15,5) g 3 .g 4 .g 5 25 (15,3) g1.g 2 .g 3 .g 4 26 (15,4) g1.g 2 .g 3.g 5 27 (15,4) g1.g 2 .g 4 .g 5 28 (15,4) g 2 .g 3 .g 4 .g 5 29 (15,1) g1.g 3 .g 4 .g 5 30 (15,2) 31 1 (15,15) http://www.ebook.edu.vn 16
C©u 14:(3 ®iÓm) M« t¶ s¬ ®å chøc n¨ng thiÕt bÞ m· ho¸ theo ph−¬ng ph¸p chia cho m· xyclic hÖ thèng (7,4) cã ®a thøc sinh g(x)=1+x+x3. T×m tõ m· ®Çu ra cña thiÕt bÞ nµy khi ®a thøc th«ng tin ®Çu vµo a(x)=1+x3. M· (7, 4) cã g ( X ) = 1 + X + X 3 1÷ 4 V1 Vµo 1 2 + 3 + RA 1÷ 7 5÷7 V2 a ( X ) = 1 + X3 a ( X ) .x n − k = X 6 + X3 Xung Tr¹ng th¸i c¸c « nhí Vµo Ra nhÞp 1 2 1 1 1 1 1 0 1 2 0 0 1 1 0 3 0 1 1 1 0 4 1 0 1 1 1 5 0 0 0 1 1 6 0 0 0 0 1 7 0 0 0 0 0 Tõ m· ra 0 1 1 1 0 0 1 ↔ X + X 2 + X3 + X 6 http://www.ebook.edu.vn 17
C©u 15: (2 ®iÓm) M« t¶ vµnh ®a thøc víi 2 phÐp to¸n céng vµ nh©n c¸c ®a thøc theo modulo xn+1 Z2 [ x ] Vµnh ®a thøc: αn + 1 n −1 f ( X ) = ∑ fi xi ; deg f ( X ) ≤ n − 1 ; fi ∈ GF ( 2 ) i =0 n −1 n −1 PhÐp céng: a ( X ) = ∑ a i xi ; b ( X ) = ∑ bi xi i =0 i =0 n −1 c ( X ) = a ( X ) + b ( X ) = ∑ ci xi trong ®ã ci = a i + bi mod 2 i =0 PhÐp nh©n: a ( X ) .b ( X ) = a ( X ) .b ( X ) mod X n + 1 Ta cã Xi .X j = Xi + jmod n http://www.ebook.edu.vn 18