海明碼原理說明

海明碼原理說明

海明碼：是由R·Hamming在1950年首次提出的，它也是一種可以糾正一位差錯(cuò)的編碼，但它的編碼效率要比正反碼高得多（當(dāng)信息位足夠長時(shí)）。基礎(chǔ)知識：二進(jìn)制數(shù)表示二進(jìn)制邏輯運(yùn)算數(shù)的表示方法奇偶校驗(yàn)奇偶校驗(yàn)碼；若信息的位數(shù)為k＝n－1位，可表示為an-1an-2…a1，加上一位偶校驗(yàn)位a0，構(gòu)成一個(gè)n位的碼字an-1an-2…a1a0

。在接收端校驗(yàn)時(shí)，可按下列關(guān)系式來計(jì)算：

S=an-1+an-2+…a1+a0（a0

用以湊成偶數(shù)個(gè)“1”）結(jié)果：若S＝0，則無錯(cuò)，若S＝1，則有錯(cuò)。上式可稱為監(jiān)督關(guān)系式，S稱為校正因子。在奇偶校驗(yàn)情況下，只有一個(gè)監(jiān)督關(guān)系式，一個(gè)校正因子，其取值只有兩種（0或l），分別代表了無錯(cuò)和有錯(cuò)兩種情況，而不能指出差錯(cuò)所在的位置?？梢栽黾尤哂辔?，就相應(yīng)地增加監(jiān)督關(guān)系式和校正因子，就能區(qū)分更多的情況。例如，若有兩個(gè)（2位）校正因子，則其取值就有4種可能：00、01、10或11，就能區(qū)分4種不同情況。若其中一種表示無錯(cuò)，另外三種不但可以用來指出有錯(cuò)，還可用來區(qū)分錯(cuò)誤的情況，如指出是哪一位錯(cuò)等。一般而言，信息位為k位，增加r位冗余位，構(gòu)成n＝k＋r位碼字。若希望用r個(gè)監(jiān)督關(guān)系式產(chǎn)生的r個(gè)校正因子來區(qū)分無錯(cuò)和在碼字中的n個(gè)不同位置的一位錯(cuò)，則要求：

2r≥n＋1或者2r≥k＋r＋1注:(n=k+r)如果用k＝4為例來說明，要滿足上述不等式，則r＞3。假設(shè)取r＝3則n＝k＋r＝7，即在4位信息位a6a5a4a3后面加上3位冗余位a2a1a0，構(gòu)成7位碼字a6a5a4a3a2a1a0

。a2、

a1和a0分別由4位信息位中某幾位半加得到。校驗(yàn)時(shí)，a2、

a1和a0

就分別和這些位半加構(gòu)成三個(gè)不同的監(jiān)督關(guān)系式。規(guī)定：無錯(cuò)時(shí)，這三個(gè)關(guān)系式的值S2、S1和S0全為“0”。若a2錯(cuò)，則S2＝1，而S1

＝S0＝0；若a1錯(cuò)，則S1＝1，而S2＝S0＝0；若a0錯(cuò)，則S0＝1，而S2＝S1＝0。S2S1S0這三個(gè)校正因子其它4種編碼值可用來區(qū)分a6a5a4a3一位錯(cuò)，該對應(yīng)關(guān)系可以規(guī)定如表1．3S2S1S0000

001

010100011101110111

錯(cuò)碼位置 無a0a1a2a3a4a5a6由表可見，a2、a4、a5或a6的一位錯(cuò)都應(yīng)使S2＝1，由此得到監(jiān)督關(guān)系式：S2

＝a2＋a4十a(chǎn)5十a(chǎn)6同理還有：

S1

＝a1＋a3十a(chǎn)5十a(chǎn)6S0

＝a0＋a3十a(chǎn)4十a(chǎn)6在發(fā)送端編碼時(shí)，信息位a6a5a4和a3的值取決于輸入信號，是隨機(jī)值。冗余位a2a1和a0的值應(yīng)根據(jù)信息位的取值按監(jiān)督關(guān)系式來決定，便上述三式中的S2S1

和S0

取值為零，即：

a2＋a4＋a5

＋a6

＝0 a1＋a3

＋a5

＋a6

＝0 a0

＋a3

＋a4

＋a6

＝0由此可求得：

a2＝a4十a(chǎn)5十a(chǎn)6 a1＝a3十a(chǎn)5十a(chǎn)6 a0＝a3十a(chǎn)4十a(chǎn)6已知信息位后，按此三式即可算出各冗余位。a6a5a4a3a2ala0a6a5a4a3a2ala00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111對于各種信息位算出的冗余位如表：在接收端收到每個(gè)碼字后，按監(jiān)督關(guān)系式算出S2、S1和S0，若全為“0”則認(rèn)為無錯(cuò)。若不全為“0”，在一位錯(cuò)的情況下，可查表來判定是哪一位錯(cuò)，從而糾正之。例如碼字0010101傳輸中發(fā)生一位錯(cuò)，在接收端收到的為0011101，代入監(jiān)督關(guān)系式：

S2

＝a2＋a4十a(chǎn)5十a(chǎn)6 S1

＝a1＋a3十a(chǎn)5十a(chǎn)6 S0

＝a0＋a3十a(chǎn)4十a(chǎn)6可算得S2＝0、S1＝1和S0

＝1，由表：S2S1S0000

001

010100011101110111

錯(cuò)碼位置 無a0a1a2a3a4a5a6可查得S2S1和S0

＝011對應(yīng)于a3錯(cuò)，因而可將0011101糾正為0010101。上述海明碼的編碼效率為4／7。若K＝7，按2r≥k十r＋1可算得r至少為4，此時(shí)編碼效率為7／11。結(jié)論：信息位長度越長時(shí)編碼效率越高。照例海明碼只能糾正一位錯(cuò)，若用下述方法排列可以糾正傳輸中出現(xiàn)的突發(fā)性錯(cuò)誤。將連續(xù)P個(gè)碼字排成一個(gè)矩陣，每行一個(gè)碼字，如圖所示 信息位冗余位

0001 011 1010 010 1011 001 0100 110 P個(gè)碼字組成矩陣

0100 110 每