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

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

——1000放風0001

地道1001

小貓0010

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

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

為碼長，k

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

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

r

=3

2如何根據(jù)原始消息生成海明碼？碼位從最低位開始編號，從“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)督關系式。若用S1,S2,S3表示監(jiān)督關系式的3個校正子，并且規(guī)定S1,S2,S3與錯碼的位置關系為：S3S2S1錯碼位置a1001a2010011a3a4100a5101a6110a7111表２校正子與錯碼的位置關系觀察表2，當一位錯碼位置在a1,a3,a5和a7時，S1為１，否則為0。即a1,a3,a5和

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

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

0

0

a4

1

a2

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

0

0

1

0

0

0S3S2S1錯碼位置a30111

0

0

1

1

0

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

00

1

1

0

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

a3a2

a11001—小貓課后思考及習題14

1、青盲發(fā)海明碼時，被看守擋住了２位a5