為了保證通信過程中數(shù)據(jù)傳輸?shù)恼_性和完整性，并且在通信過程中，如果數(shù)據(jù)傳輸發(fā)生一位錯誤，能夠?qū)⑵涑C正過來，將信息數(shù)據(jù)進(jìn)行漢明編碼后再進(jìn)行數(shù)據(jù)傳輸。

漢明碼（Hamming Code）也叫海明碼，是Richard Hamming（貝爾實(shí)驗(yàn)室）于1950年發(fā)明的，漢明碼也是利用了奇偶校驗(yàn)位概念，通過在數(shù)據(jù)位后增加一些比特以驗(yàn)證數(shù)據(jù)的有效性，故漢明碼也屬于線性糾錯碼（可糾錯1-bit錯誤檢出2-bit錯誤）。漢明碼無法實(shí)現(xiàn)2位及2位以上糾錯。

漢明碼原理

漢明碼運(yùn)算需要構(gòu)造G生成矩***和H監(jiān)督矩***，關(guān)于構(gòu)造方法可參考相關(guān)計(jì)算機(jī)原理書籍，這里只需了解些簡單的概念即可。

設(shè)數(shù)據(jù)位數(shù)為m，校驗(yàn)位數(shù)為k，則總編碼位數(shù)為n，所以，n＝m+k，則，

有Hamming不等式：

2^k-1》=n

也可表示為：2^k》=m+k+1，該不等式用于對比運(yùn)算計(jì)算數(shù)據(jù)位數(shù)和檢驗(yàn)位數(shù)，舉個例子假設(shè)數(shù)據(jù)位為64，那么校驗(yàn)位則為（“2^k-k》=65” =》k=7）。

校驗(yàn)位數(shù)一般指最小值，因?yàn)閗越小總信息位會越小，傳輸開銷自然越小。

信息位數(shù)一般指最大值，但由于2^k-k只能在固定的離散值里取值，所以信息位也可能不是最大值，比如信息位為24，計(jì)算需要校驗(yàn)位5，但同樣可信息位為25時，校驗(yàn)位同樣是5。

校驗(yàn)位數(shù)VS信息位數(shù)關(guān)系如下表：

注：漢明碼的特性決定，一般不會做太多信息位的校驗(yàn)，信息位越長出現(xiàn)多余兩個錯誤的概率會越高，這將帶來糾錯的難度。

漢明碼編碼原理

設(shè)碼長為n，信息位長度為k，監(jiān)督位長度為r=n-k。如果需要糾正一位出錯，因?yàn)殚L度為n的序列上每一位都可能出錯，一共有n種情況，另外還有不出錯的情況，所以我們必須用長度為r的監(jiān)督碼表示出n+1種情況。而長度為r的監(jiān)督碼一共可以表示2^r種情況 。因此

2^r 》= n + 1， 即r 》= log（n+1）

我們以一個例子來說明漢明碼。假設(shè)k=4，需要糾正一位錯誤，則

2^r 》= n + 1 = k + r + 1 = 4 + r + 1

解得r 》= 3。我們?nèi)=3，則碼長為3+4=7。用a6，a5，。。.a0表示這7個碼元。用S1，S2，S3表示三個監(jiān)關(guān)系式中的校正子。我們作如下規(guī)定（這個規(guī)定是任意的）：

S1 S2 S3 錯碼的位置

0 0 1 a0

0 1 0 a1

1 0 0 a2

0 1 1 a3

1 0 1 a4

1 1 0 a5

1 1 1 a6

0 0 0 無錯

按照表中的規(guī)定可知，僅當(dāng)一個錯碼位置在a2，a4，a5或a6時校正子S1為1，否則S1為0。這就意味著a2，a4，a5，a6四個碼元構(gòu)成偶校驗(yàn)關(guān)系：

S1 = a6⊕a5⊕a4⊕a2 （1）式

同理，可以得到：

S2 = a6⊕a5⊕a3⊕a1 （2）式

S3 = a6⊕a4⊕a3⊕a0 （3）式

在發(fā)送信號時，信息位a6，a5，a4，a3的值取決于輸入信號，是隨機(jī)的。監(jiān)督為a2，a1，a0應(yīng)該根據(jù)信息位的取值按照監(jiān)督關(guān)系決定，即監(jiān)督位的取值應(yīng)該使上述（1）（2）（3）式中的S1，S2，S3為0，這表示初始情況下沒有錯碼。即

a6⊕a5⊕a4⊕a2 = 0

a6⊕a5⊕a3⊕a1 = 0

a6⊕a4⊕a3⊕a0 = 0

由上式進(jìn)行移項(xiàng)運(yùn)算，得到：

a2 = a6⊕a5⊕a4

a1 = a6⊕a5⊕a3

a0 = a6⊕a4⊕a3

已知信息位后，根據(jù)上式即可計(jì)算出a2，a1，a0三個監(jiān)督位的值。

接收端受到每個碼組后，先按照（1）~（3）式計(jì)算出S1，S2，S3，然后查表可知錯碼情況。

例如，若接收到的碼字為0000011，按照（1）~（3）計(jì)算得到：

S1 = 0， S2 = 1， S3 = 1

查表可得在a3位有一個錯碼。

這種編碼方法的最小漢明距離為d=3，所以這種編碼可以糾正一個錯碼或者檢測兩個錯碼。

漢明碼實(shí)例

下文示例為（30，24）漢明碼計(jì)算方法，用在MIPI DSI包頭部分（MIPI Alliance Specification for Display Serial Interface，Chapter 9），DSI包頭格式固定為24bits Data+8bits ECC，8bitsECC中預(yù)設(shè)P6=P7=0，所以實(shí)際n=30，m=24，k=6。

檢驗(yàn)位計(jì)算方法參考MIPI DSI table22生成矩***（Px vs ［DataBit0~DataBitx］），比如P5=D10^D11^.。。.D23，表示對應(yīng)DataBit23的P5列，只有這些DataBit位為1。

int main（） {

char res;

char in［20］={0};

char D0，D1，D2，D3，D4，D5，D6，D7，D8，D9，D10，D11，D12，D13，D14，D15，D16，D17，D18，D19，D20，D21，D22，D23;

char P0，P1，P2，P3，P4，P5，P6，P7;

cout《《“Checking Codes（eg.0x1234AF， \”-\“ for exit）： 0x”;

cin》》in;

if（in［0］==‘-’） {

return 0;

}

for（int i=0;i《6;i++）{

if（（in［i］》=‘0’） && （in［i］《=‘9’）） {

in［i］ = in［i］-0x30;

}else if（（in［i］》=‘A’） && （in［i］《=‘F’））{

in［i］ = in［i］-‘A’+10;

}else {

return 0;

}

}

D0=in［1］&0x01; D1=（in［1］&0x02）》》1;

D2=（in［1］&0x04）》》2; D3=（in［1］&0x08）》》3;

D4=in［0］&0x01; D5=（in［0］&0x02）》》1;

D6=（in［0］&0x04）》》2; D7=（in［0］&0x08）》》3;

D8=in［3］&0x01; D9=（in［3］&0x02）》》1;

D10=（in［3］&0x04）》》2; D11=（in［3］&0x08）》》3;

D12=in［2］&0x01; D13=（in［2］&0x02）》》1;

D14=（in［2］&0x04）》》2; D15=（in［2］&0x08）》》3;

D16=in［5］&0x01; D17=（in［5］&0x02）》》1;

D18=（in［5］&0x04）》》2; D19=（in［5］&0x08）》》3;

D20=in［4］&0x01; D21=（in［4］&0x02）》》1;

D22=（in［4］&0x04）》》2; D23=（in［4］&0x08）》》3;

P7=0;

P6=0;

P5=D10^D11^D12^D13^D14^D15^D16^D17^D18^D19^D21^D22^D23;

P4=D4^D5^D6^D7^D8^D9^D16^D17^D18^D19^D20^D22^D23;

P3=D1^D2^D3^D7^D8^D9^D13^D14^D15^D19^D20^D21^D23;

P2=D0^D2^D3^D5^D6^D9^D11^D12^D15^D18^D20^D21^D22;

P1=D0^D1^D3^D4^D6^D8^D10^D12^D14^D17^D20^D21^D22^D23;

P0=D0^D1^D2^D4^D5^D7^D10^D11^D13^D16^D20^D21^D22^D23;

res = （（P7&0x01）*8+（P6&0x01）*4+（P5&0x01）*2+（P4&0x01））*16+（P3&0x01）*8+（P2&0x01）*4+（P1&0x01）*2+（P0&0x01）;

printf（“Result:0x%02X\r\n”，res）;

return 0;

}