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 //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. //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 ] //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 //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 ] //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] //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¶ //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 //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: //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] //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 //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 //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 //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 //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 //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] //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 //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 //www.ebook.edu.vn 18