漢明碼原理和校驗(yàn)及實(shí)現(xiàn)

漢明碼原理介紹：

在計(jì)算機(jī)運(yùn)行過程中，由于種種原因?qū)е聰?shù)據(jù)在存儲(chǔ)過程中可能出現(xiàn)差錯(cuò)，為了能夠及時(shí)發(fā)現(xiàn)錯(cuò)誤并且將錯(cuò)誤糾正，通?？梢詫⒃瓟?shù)據(jù)配成漢明編碼。

漢明碼具有一位糾錯(cuò)能力。

奇偶校驗(yàn)是一種添加一個(gè)奇偶位用來指示之前的數(shù)據(jù)中包含有奇數(shù)還是偶數(shù)個(gè)1的檢驗(yàn)方式。如果在傳輸?shù)倪^程中，有奇數(shù)個(gè)位發(fā)生了改變，那么這個(gè)錯(cuò)誤將被檢測(cè)出來（注意奇偶位本身也可能改變）。一般來說，如果數(shù)據(jù)中包含有奇數(shù)個(gè)1的話，則將奇偶位設(shè)定為1；反之，如果數(shù)據(jù)中有偶數(shù)個(gè)1的話，則將奇偶位設(shè)定為0。換句話說，原始數(shù)據(jù)和奇偶位組成的新數(shù)據(jù)中，將總共包含偶數(shù)個(gè)1.

奇偶校驗(yàn)并不總是有效，如果數(shù)據(jù)中有偶數(shù)個(gè)位發(fā)生變化，則奇偶位仍將是正確的，因此不能檢測(cè)出錯(cuò)誤。而且，即使奇偶校驗(yàn)檢測(cè)出了錯(cuò)誤，它也不能指出哪一位出現(xiàn)了錯(cuò)誤，從而難以進(jìn)行更正。數(shù)據(jù)必須整體丟棄并且重新傳輸。在一個(gè)噪音較大的媒介中，成功傳輸數(shù)據(jù)可能需要很長時(shí)間甚至不可能完成。雖然奇偶校驗(yàn)的效果不佳，但是由于他只需要一位額外的空間開銷，因此這是開銷最小的檢測(cè)方式。并且，如果知道了發(fā)生錯(cuò)誤的位，奇偶校驗(yàn)還可以恢復(fù)數(shù)據(jù)。

如果一條信息中包含更多用于糾錯(cuò)的位，且通過妥善安排這些糾錯(cuò)位使得不同的出錯(cuò)位產(chǎn)生不同的錯(cuò)誤結(jié)果，那么我們就可以找出出錯(cuò)位了。在一個(gè)7位的信息中，單個(gè)數(shù)據(jù)位出錯(cuò)有7種可能，因此3個(gè)錯(cuò)誤控制位就足以確定是否出錯(cuò)及哪一位出錯(cuò)了。

漢明編碼方案通用算法

下列通用算法可以為任意位數(shù)字產(chǎn)生一個(gè)可以糾錯(cuò)一位的漢明碼。

一、1開始給數(shù)字的數(shù)據(jù)位（從左向右）標(biāo)上序號(hào)， 1，2，3，4，5.。。

二、將這些數(shù)據(jù)位的位置序號(hào)轉(zhuǎn)換為二進(jìn)制，1， 10， 11， 100， 101，等。

三、數(shù)據(jù)位的位置序號(hào)中所有為二的冪次方的位（編號(hào)1，2，4，8，等，即數(shù)據(jù)位位置序號(hào)的二進(jìn)制表示中只有一個(gè)1）是校驗(yàn)位

四、有其它位置的數(shù)據(jù)位（數(shù)據(jù)位位置序號(hào)的二進(jìn)制表示中至少2個(gè)是1）是數(shù)據(jù)位

五、每一位的數(shù)據(jù)包含在特定的兩個(gè)或兩個(gè)以上的校驗(yàn)位中，這些校驗(yàn)位取決于這些數(shù)據(jù)位的位置數(shù)值的二進(jìn)制表示

1.校驗(yàn)位1覆蓋了所有數(shù)據(jù)位位置序號(hào)的二進(jìn)制表示倒數(shù)第一位是1的數(shù)據(jù)：1（校驗(yàn)位自身，這里都是二進(jìn)制，下同），11，101，111，1001，等

2.校驗(yàn)位2覆蓋了所有數(shù)據(jù)位位置序號(hào)的二進(jìn)制表示倒數(shù)第二位是1的數(shù)據(jù)：10（校驗(yàn)位自身），11，110，111，1010，1011，等

3.校驗(yàn)位4覆蓋了所有數(shù)據(jù)位位置序號(hào)的二進(jìn)制表示倒數(shù)第三位是1的數(shù)據(jù)：100（校驗(yàn)位自身），101，110，111，1100，1101，1110，1111，等

4.校驗(yàn)位8覆蓋了所有數(shù)據(jù)位位置序號(hào)的二進(jìn)制表示倒數(shù)第四位是1的數(shù)據(jù)：1000（校驗(yàn)位自身），1001，1010，1011，1100，1101，1110，1111，等

5.簡而言之，所有校驗(yàn)位覆蓋了數(shù)據(jù)位置和該校驗(yàn)位位置的二進(jìn)制與的值不為0的數(shù)。 采用奇校驗(yàn)還是偶校驗(yàn)都是可行的。偶校驗(yàn)從數(shù)學(xué)的角度看更簡單一些，但在實(shí)踐中并沒有區(qū)別。

從編碼形式上，我們可以發(fā)現(xiàn)漢明碼是一個(gè)校驗(yàn)很嚴(yán)謹(jǐn)?shù)木幋a方式。在這個(gè)例子中，通過對(duì)4個(gè)數(shù)據(jù)位的3個(gè)位的3次組合檢測(cè)來達(dá)到具體碼位的校驗(yàn)與修正目的（不過只允許一個(gè)位出錯(cuò)，兩個(gè)出錯(cuò)就無法檢查出來了，這從下面的糾錯(cuò)例子中就能體現(xiàn)出來）。在校驗(yàn)時(shí)則把每個(gè)漢明碼與各自對(duì)應(yīng)的數(shù)據(jù)位值相加，如果結(jié)果為偶數(shù)（糾錯(cuò)代碼為0）就是正確，如果為奇數(shù)（糾錯(cuò)代碼為1）則說明當(dāng)前漢明碼所對(duì)應(yīng)的三個(gè)數(shù)據(jù)位中有錯(cuò)誤，此時(shí)再通過其他兩個(gè)漢明碼各自的運(yùn)算來確定具體是哪個(gè)位出了問題。

觀察上表可發(fā)現(xiàn)一個(gè)比較直觀的規(guī)律：第i個(gè)檢驗(yàn)位是第2i-1位，從該位開始，檢驗(yàn)2i-1位，跳過2i-1位……依次類推。例如上表中第3個(gè)檢驗(yàn)位p4從第23-1=4位開始，檢驗(yàn)4、5、6、7共4位，然后跳過8、9、10、11共4位，再檢驗(yàn)12、13、14、15共4位……

漢明碼的編碼規(guī)則如下：

在新的編碼的2^（k - 1）（ k 》= 0）位上填入0（即校驗(yàn)位）

把新的編碼的其余位把源碼按原順序填入

校驗(yàn)位的編碼方式為：第k位校驗(yàn)碼從則從新的編碼的第2^（k - 1）位開始，每計(jì)算2^（k - 1）位的異或，跳2^（k - 1）位，再計(jì)算下一組2^（k - 1）位的異或，填入2^（k - 1）位，比如：

第1位校驗(yàn)碼位于新的編碼的第1位（2 ^（1-1） == 1）（漢明碼從1位開始），計(jì)算1，3，5，7，9，11，13，15，。。。位的異或，填入新的編碼的第1位。

第2位校驗(yàn)碼位于新的編碼的第2位（2 ^（2-1） == 2），計(jì)算2，3，6，7，10，11，14，15，。。。位的異或，填入新的編碼的第2位。

第3位校驗(yàn)碼位于新的編碼的第4位（2 ^（3-1） == 4），計(jì)算4，5，6，7，12，13，14，15，20，21，22，23，。。。位的異或，填入新的編碼的第4位。

第4位校驗(yàn)碼位于新的編碼的第8位（2 ^（4-1） == 8），計(jì)算8-15，24-31，40-47，。。。位的異或，填入新的編碼的第8位。

第5位校驗(yàn)碼位于新的編碼的第16位（2 ^（5-1） == 16），計(jì)算16-31，48-63，80-95，。。。位的異或，填入新的編碼的第16位。

在數(shù)學(xué)方面，漢明碼是一種二元線性碼。對(duì)于每一個(gè)整數(shù)m》2，存在一個(gè)編碼，帶有m個(gè)奇偶校驗(yàn)位2m- m-1個(gè)數(shù)據(jù)位。

漢明碼的生成和檢驗(yàn)

設(shè)將要進(jìn)行檢測(cè)的二進(jìn)制代碼為n位，為使其具有糾錯(cuò)能力，需要再加上k位的檢測(cè)位，組成n+k位的代碼。那么，新增加的檢測(cè)位數(shù)k應(yīng)滿足：

2k≥n+k+1或2k-1≥n+k

當(dāng)k的位數(shù)確定后，便可根據(jù)承擔(dān)的檢測(cè)任務(wù)設(shè)定他們?cè)趥魉痛a中的位置和他們的取值。首先，將所要檢測(cè)的代碼分為Pn組，分多少個(gè)組，我們通過k的值來確定。下面我用一個(gè)例子來說明。

假設(shè)將要進(jìn)行檢測(cè)的二進(jìn)制代碼為0101，位數(shù)n=4，根據(jù)公式2k≥n+k+1可以得出k的值是3，所以最終形成的漢明碼應(yīng)為n+k=7位。

所以分組分為P1、P2、P4。原因則是第一組是20、第二組則是21 、同理第三組則是22 、依次列推分組應(yīng)按照2k-1。同時(shí)以后根據(jù)分組產(chǎn)生的數(shù)插入的位置也是按照此規(guī)律插入，比如第一組插入20、即第1位，第二組插入21 、即第2位，以此類推。那么組分好了，他們每一組中包含的位則是：

p1包含（1，3，5，7，9，11，。。。位）

p2包含（2，3，6，7，10，11，14，15，。。。位）

p3包含（4，5，6，7，12，13，14，15，。。。位）

每一組中包含的數(shù)又是如何確定的呢？我們來看下面這個(gè)表格

將編號(hào)轉(zhuǎn)成二進(jìn)制從右向左，如果第一位是1，例如編號(hào)是1，3，5，7.。。。的就分入第一組，如果第二位是1的，例如編號(hào)2，3，6，7，10.。。的就分入第二組，以此類推將所有的編號(hào)分入相應(yīng)的組中。下面我么來看例子0101是如何產(chǎn)生漢明碼的（采用配偶原則），

其中C1、C2、C4是我們插入的檢測(cè)位

如果按照配偶原則來配置漢明碼，則C1應(yīng)使1 3 5 7位中“1”的個(gè)數(shù)為偶數(shù)；C2應(yīng)使2 3 6 7位中“1”的個(gè)數(shù)為偶數(shù)；C4應(yīng)使4 5 6 7位中“1”的個(gè)數(shù)為偶數(shù)。

按照上面我所說的則：

C1=③位+⑤位+⑦位，即C1=B4+B3+B1=0+1+1=0

C2=③位+⑥位+⑦位，即C2=B4+B2+B1=0+0+1=1

C4=⑤位+⑥位+⑦位，即C4=B3+B2+B1=1+0+1=0

所以0101的漢明碼應(yīng)為C1C2B4C4B3B2B1，即0100101

漢明碼還存在配奇原則，下面來講一講配奇原則。按照配奇原則配置1100101的漢明碼。

根據(jù)1100101可知n=7。根據(jù)公式我們可以求出需要添加k=4位檢測(cè)位，詳細(xì)情況如下表。

按配奇原則配置，則

C1=③位+⑤位+⑦位+⑨位+11位+1=1+1+0+1+1+1=1

C2=③位+⑥位+⑦位+10位+11位+1=1

C4=⑤位+⑥位+⑦位+1=0

C8=⑨位+10位+11位+1=1

所以按配奇原則新配置的漢明碼為11101001101

漢明碼校驗(yàn)錯(cuò)誤實(shí)例

我們以上面的編碼為例，假設(shè)我們現(xiàn)在收到的編碼為001101001，我們可以發(fā)現(xiàn)漢明碼的第8位與原來的漢明碼001101011不同，那我們?cè)趺凑页鲞@個(gè)第8位的錯(cuò)誤編碼呢？

算法很簡單，我們只要在算漢明碼校驗(yàn)位的算法的上再算一遍，就得到了漢明碼的校驗(yàn)方法，比如計(jì)算001101001對(duì)應(yīng)的2^k位。

1，3，5，7，9進(jìn)行異或，得到0

2，3，6，7進(jìn)行異或，得到0

4，5，6，7進(jìn)行異或，得到0

8，9進(jìn)行異或，得到1

我們把上述結(jié)果反著排列，得到1000，即十進(jìn)制的8，根據(jù)漢明碼的校驗(yàn)規(guī)則，編碼出錯(cuò)的地方即在第8位，我們把第8位的0換成1，即可得原來的編碼001101011。

上述的例子是出現(xiàn)在2^k的校驗(yàn)位上的，如果出現(xiàn)在非2^k位上，得到的結(jié)果也是一樣的，比如：

假設(shè)收到的編碼為001100011，即第6位出了錯(cuò)誤，我們根據(jù)規(guī)則

1，3，5，7，9進(jìn)行異或，得到0

2，3，6，7進(jìn)行異或，得到1

4，5，6，7進(jìn)行異或，得到1

8，9進(jìn)行異或，得到0

我們把上述結(jié)果反著排列，得到0110，即十進(jìn)制的6，根據(jù)漢明碼的校驗(yàn)規(guī)則，編碼出錯(cuò)的地方即在第6位，我們把第6位的0換成1，即可得原來的編碼001101011。

漢明碼的編碼和校驗(yàn)的C++實(shí)現(xiàn)

通過原理，我們可以很簡單地實(shí)現(xiàn)漢明碼的編碼和校驗(yàn)代碼

auto cal（size_t sz）-》decltype（auto）

{

decltype（sz） k = 0;

decltype（sz） cur = 1;

while （cur - 1 《 sz + k ）

{

cur 《《= 1;

k++;

}

return k;

}

bool encode（const string &s， string &d）

{

d.clear（）;

auto k = cal（s.size（））;

d.resize（s.size（） + k）;

for （decltype（d.size（）） i = 0， j = 0， p = 0; i！= d.size（）;i++）

解碼與校驗(yàn)：

auto antiCal（size_t sz）-》decltype（auto）

{

decltype（sz） k = 0;

decltype（sz） cur = 1;

while （cur 《 sz）

{

cur 《《= 1;

k++;

}

return k;

}

auto decode（string &s， string &d）-》decltype（auto）

{

s.clear（）;

auto k = antiCal（d.size（））;

s.resize（d.size（） - k）;

decltype（d.size（）） sum = 0;

for （decltype（k） p = 0;p ！= k;p++）

{

int pAnti = 0;

decltype（k） index = 1 《《 p;

for （decltype（d.size（）） i = index - 1;i 《 d.size（）; i+=index）

{

for （auto j = 0; j 《 index && i 《 d.size（）; i++， j++）

pAnti ^= d［i］ - ‘0’;

}

sum += pAnti 《《 p;

}

if （sum ！= 0）

d［sum - 1］ = （1- （int）（d［sum - 1］ - ‘0’）） + ‘0’;

for （decltype（d.size（）） i = 0， p = 0，j = 0; i ！= d.size（）; i++）

{

if （（i + 1） == （1 《《 p） && p 《 k）

p++;

else

s［j++］ = d［i］;

}

return sum;

}

{

if （（i + 1） == pow（2，p） && p 《 k）

{

d［i］ = ‘0’;

p++;

}

else if （s［j］ == ‘0’ || s［j］ == ‘1’）

d［i］ = s［j++］;

else

return false;

}

for （auto i = 0; i ！= k;i++）

{

int count = 0 ，index = 1 《《 i;

for （auto j = index - 1; j 《 d.size（） ;j += index）

for （auto k = 0; k！= index && j 《 d.size（）; k++， j++）

count ^= d［j］ - ‘0’;

d［index - 1］ = ‘0’ + count;

}

return true;

}

測(cè)試樣例：

int main（）

{

string source， dest;

while （cin 》》 source）

{

if （encode（source，dest））

{

cout 《《 “Source： ” 《《source 《《 endl;

cout 《《 “Dest： ” 《《 dest 《《 endl;

}

size_t index;

cout 《《 “----input error index ： ”;

cin 》》 index;

auto k = dest.size（）;

if （index ！= 0 && index 《= dest.size（））

dest［index - 1］ = （1 - （int）（dest［index - 1］ - ‘0’）） + ‘0’;

cout 《《 “Code ” 《《 dest 《《endl;

auto ret = decode（source，dest）;

if （ret == 0）

{

cout 《《 “Source： ” 《《source 《《 endl;

cout 《《 “Dest： ” 《《dest 《《 endl;

}

else

{

cout 《《 “Error index ”《《 ret 《《 endl;

cout 《《 “Corret source： ” 《《source 《《 endl;

cout 《《 “Corret dest： ” 《《dest 《《 endl;

}

cout 《《 endl;

}

return 0;

}

Source： 10101

Dest： 001101011

----input error index ： 8

Code 001101001

Error index 8

Corret source： 10101

Corret dest： 001101011

Source： 1001010101010101010111111001101

Dest： 1111001101010100101010101111110101101

----input error index ： 20

Code 1111001101010100101110101111110101101

Error index 20

Corret source： 1001010101010101010111111001101

Corret dest： 1111001101010100101010101111110101101

Source： 1

Dest： 111

----input error index ： 0

Code 111

Source： 1

Dest： 111