獄中通信-海明碼new

獄中通信——什么是海明碼？1浙江工商大學(xué)鄒園萍故事發(fā)生在1947年初，在重慶郊區(qū)的深山里，國(guó)民黨某組織正在秘密研制一種大規(guī)模殺傷武器。34越獄！5放風(fēng)片段：6請(qǐng)大家仔細(xì)觀察青盲，猜猜他在做什么？為什么這么做？

答案：青盲給小貓發(fā)碼原消息含義原消息含義0000

——1000放風(fēng)0001

地道1001

小貓0010

青盲1010越獄0011土狗1011餐廳0100耗子1100體檢0101馬桶1101等待0110廚房1110地下室0111吃飯1111天花板7表１原消息內(nèi)容發(fā)哪條消息，最容易引起小貓的關(guān)注？考慮：發(fā)碼隨時(shí)可能會(huì)被干擾，引起錯(cuò)碼，因此要選用一種糾錯(cuò)碼，且監(jiān)督位不能太多，計(jì)算也要簡(jiǎn)單。

海明碼是一種高效的線性碼，不僅能檢錯(cuò)，還能糾正1位錯(cuò)碼，因此，青盲決定用海明碼來(lái)傳消息。海明碼的監(jiān)督位需要幾位？12如何根據(jù)原始消息生成海明碼？3海明碼在傳輸中出錯(cuò)，接收端如何糾正?海明碼的監(jiān)督位需要幾位？1一個(gè)（n,k）分組碼，n

為碼長(zhǎng)，k

為信息位位數(shù)，令監(jiān)督位位數(shù)為r，則有n-k=r，若要通過(guò)r個(gè)監(jiān)督位指示一位錯(cuò)碼的n

種可能位置，則k和r應(yīng)滿足什么關(guān)系？（１）已知k=4,青盲根據(jù)以上規(guī)則，很快就算出了

r

=3

2如何根據(jù)原始消息生成海明碼？碼位從最低位開始編號(hào)，從“1”開始，然后分別是2、3…等,其中第2n位（即1、2、4、...）是監(jiān)督位，其余是信息位。確定海明碼編碼格式a7a6a5a4

a3a2

a1(1)如果信息位有4位，則海明碼編碼格式為：其中的a7a6a5a3是已知的信息位1001(2)如何生成監(jiān)督位a1,a2,a4青盲知道，線性碼中信息位和監(jiān)督位滿足一組線性方程，線性方程即監(jiān)督關(guān)系式。若用S1,S2,S3表示監(jiān)督關(guān)系式的3個(gè)校正子，并且規(guī)定S1,S2,S3與錯(cuò)碼的位置關(guān)系為：S3S2S1錯(cuò)碼位置a1001a2010011a3a4100a5101a6110a7111表２校正子與錯(cuò)碼的位置關(guān)系觀察表2，當(dāng)一位錯(cuò)碼位置在a1,a3,a5和a7時(shí)，S1為１，否則為0。即a1,a3,a5和

a7存在偶數(shù)監(jiān)督關(guān)系。（2）（3）（4）在發(fā)端信息位是隨機(jī)的，監(jiān)督位根據(jù)信息位按監(jiān)督關(guān)系來(lái)確定，即監(jiān)督關(guān)系應(yīng)使（2）式～（4）式中的S1

，S2和S3的值為０，即同理（5）無(wú)錯(cuò)000(2)如何生成海明碼中的監(jiān)督位a1,a2,a4（5）將（5）式移項(xiàng)，可分別求出監(jiān)督位a1,a2,a4青盲根據(jù)要傳的信息位a7a6a5a3＝1001,按照(6)式，計(jì)算a1,a2,a4：（6）0011

0

0

a4

1

a2

a10013海明碼在傳輸中出錯(cuò)，接收端如何糾正?110010001

0

0

1

0

0

0S3S2S1錯(cuò)碼位置a30111

0

0

1

1

0

0奇跡即將發(fā)生！1

00

1

1

0

0數(shù)據(jù)發(fā)送順序0011x00小貓能得到正確的消息？a7a6a5a4

a3a2

a11001—小貓課后思考及習(xí)題14

1、青盲發(fā)海明碼時(shí)，被看守?fù)踝×耍参籥5