Bài tập lý thuyết thông tin có lời giải it4590 năm 2024

Nội dung Text: Bài tập và gợi ý giải môn học Lý thuyết thông tin

1. ®¸p ¸n Ngµnh ®µo t¹o: §iÖn tö – viÔn th«ng HÖ ®µo t¹o : §¹i häc M«n häc : Lý thuyÕt th«ng tin M· sè 411 LTT 340A Sè §VHT: 4 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 k = −1 I ( xk ) = − ln p ( xk ) (nat) 1 k=− I ( xk ) = − log 2 p ( xk ) (bÝt) ln 2 1 k=− I ( xk ) = − lg p ( xk ) (hart) 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 a2 ... as ⎞ A=⎜ ⎟ ⎝ p ( a1 ) p ( a 2 ) ... p ( a s ) ⎠ s 0 ≤ p (ai ) ≤ 1 ∑ p(a ) = 1 i =1 i s' H1 ( A ) = −∑ p ( a i ) log p ( a i ) (bÝt) i =1 http://www.ebook.edu.vn 1
2. 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 ⎞ H1 ( A ) (bits) A=⎜ 1 ⎟ ⎝ p 1− p⎠ H1 ( A )max = −plog p − (1 − p ) log (1 − p ) 1 1 Khi p = 1 − p = p 2 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
3. 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 ) Ta cã: H(A bj ) = H(A) 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 ) víi I ( a i ,b j ) = log p (ai ) http://www.ebook.edu.vn 3
4. s t p (ai b j ) I ( A,B ) = ∑∑ p ( a i b j ) log i =1 j=1 p (ai ) 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 Cho tèc ®é truyÒn tin cña kªnh vk = 1 T ps 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 ) ⎤ T A T A ⎣ ⎦ 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' = T A T C' C'max 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
5. 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 ) Víi p : x¸c suÊt nhËn c©u tr¶ lêi ″®óng ″ 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
6. 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 ) Víi p : x¸c suÊt nhËn c©u tr¶ lêi lµ ″®óng ″ 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
7. 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
8. 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 : ⎧ ai ⎫ ⎧ bj ⎫ ⎪ ⎪ A=⎨ ⎬ i = 1,0 B=⎨ ⎬ j = 1, t ⎩p ( a i ) ⎭ ⎪p ( b j )⎪ ⎩ ⎭ 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. A p ( b1 a2 ) = pd 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 ) a2 p ( b2 a1 ) = pd 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
9. ⎛ ai ⎞ ⎛ α ini ⎞ 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
10. 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. VÝ dô: αi7 = 0 1 1 0 1 0 0 α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 n i n j khi α in ≡ α n j + d (α ,α ) ≤ n n i n 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 +x +x3 ⎞ ⎛ 1 1 0 1 0 0 0 ⎞ ⎜ ⎟ ⎜ ⎟ ⎜x +x2 +x4 ⎟ ⎜ 0 1 1 0 1 0 0 ⎟ G= 2 = ⎜x +x3 + x5 ⎟ ⎜ 0 0 1 1 0 1 0 ⎟ ⎜ 3 ⎜x ⎟ ⎜ ⎟ ⎝ +x4 +x6 ⎟ ⎝ 0 0 0 1 1 0 1 ⎠ ⎠ 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
11. 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
12. 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 1 1+ x ( 7,6 ) 2 2 1 + x + x3 ( 7,4 ) 3 3 1 + x 2 + x3 ( 7,4 ) 3 4 1 + x + x2 + x4 ( 7,3) 4 5 1 + x2 + x3 + x 4 ( 7,3) 4 6 6 ( 7,1) 7 ∑x i=0 i 7 1 ( 7,7 ) 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… TT ai p (ai ) Tõ m· α ini ni 1 a1 14 0 0 2 2 a2 14 0 1 2 3 a3 18 1 0 0 3 4 a4 18 1 0 1 3 5 a5 18 1 1 0 3 6 a6 1 32 1 1 1 0 0 5 7 a7 1 32 1 1 1 0 1 5 8 a8 1 32 1 1 1 1 0 5 9 a9 1 64 1 1 1 1 1 0 6 10 a10 1 64 1 1 1 1 1 1 6 http://www.ebook.edu.vn 12
13. - §¸nh gi¸ hiÖu qu¶: 10 1 1 1 1 n = ∑ p ( a i ) n i = 2.2. + 3.3. + 3.5. + 2.6. i =1 4 8 32 64 9 15 6 25 =1+ + + = 2. dÊu 8 32 32 32 10 1 1 1 1 1 H1 ( A ) = ∑ p ( a i ) log = 2. .log 4 + 3. log8 + 3. log 32 + 2. log 64 i =1 p (ai ) 4 8 32 64 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
14. - 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 2 2 3 6 ↔ 0 111 0 0 1 (1 + x + x ) g ( x ) = 1 + x + x + x 2 4 6 ↔11 0 0 1 0 1 http://www.ebook.edu.vn 14
15. 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 i =0 i n ≤ 2n −k 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 n n t 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 VËy ®Ó söa ®−îc tÊt c¶ c¸c kiÓu sai cã träng sè ≤ t ta cã: ∑C i =0 i n ≤ 2n − k - §Þ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
16. TT §a thøc sinh M· (n,k) 1 g1 ( X ) (15,14) 2 g2 ( X ) (15,13) 3 g3 ( X ) (15,11) 4 g4 ( X ) (15,11) 5 g5 ( X ) (15,11) 6 g1.g 2 (15,12) 7 g1.g3 (15,10) 8 g1.g 4 (15,10) 9 g1.g5 (15,10) 10 g 2 .g 3 (15,9) 11 g 2 .( g 4 ) (15,9) 12 g 2 .g 5 (15,9) 13 g 3 .g 4 (15,7) 14 g 3 .g 5 (15,7) 15 g 4 .g 5 (15,7) 16 g1.g 2 .g 3 (15,8) 17 g1.g 2 .g 4 (15,8) 18 g1.g 2 .g 5 (15,8) 19 g 2 .g 3.g 4 (15,5) 20 g 2 .g 3 .g 5 (15,5) 21 g1.g 3 .g 4 (15,6) 22 g1.g 3.g 5 (15,6) 23 g1.g 4 .g 5 (15,6) 24 g 2 .g 4 .g 5 (15,5) 25 g 3 .g 4 .g 5 (15,3) 26 g1.g 2 .g 3 .g 4 (15,4) 27 g1.g 2 .g 3.g 5 (15,4) 28 g1.g 2 .g 4 .g 5 (15,4) 29 g 2 .g 3 .g 4 .g 5 (15,1) 30 g1.g 3 .g 4 .g 5 (15,2) 31 1 (15,15) http://www.ebook.edu.vn 16
17. 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 V1 1÷ 4 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
18. 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