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

漢明碼原理介紹：

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

漢明碼具有一位糾錯能力。

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

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

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

漢明編碼方案通用算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

漢明碼的生成和檢驗

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

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

當k的位數(shù)確定后，便可根據(jù)承擔的檢測任務設定他們在傳送代碼中的位置和他們的取值。首先，將所要檢測的代碼分為Pn組，分多少個組，我們通過k的值來確定。下面我用一個例子來說明。

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

所以分組分為P1、P2、P4。原因則是第一組是20、第二組則是21 、同理第三組則是22 、依次列推分組應按照2k-1。同時以后根據(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ù)又是如何確定的呢？我們來看下面這個表格

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

其中C1、C2、C4是我們插入的檢測位

如果按照配偶原則來配置漢明碼，則C1應使1 3 5 7位中“1”的個數(shù)為偶數(shù)；C2應使2 3 6 7位中“1”的個數(shù)為偶數(shù)；C4應使4 5 6 7位中“1”的個數(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的漢明碼應為C1C2B4C4B3B2B1，即0100101

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

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

按配奇原則配置，則

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

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

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

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

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

漢明碼校驗錯誤實例

我們以上面的編碼為例，假設我們現(xiàn)在收到的編碼為001101001，我們可以發(fā)現(xiàn)漢明碼的第8位與原來的漢明碼001101011不同，那我們怎么找出這個第8位的錯誤編碼呢？

算法很簡單，我們只要在算漢明碼校驗位的算法的上再算一遍，就得到了漢明碼的校驗方法，比如計算001101001對應的2^k位。

1，3，5，7，9進行異或，得到0

2，3，6，7進行異或，得到0

4，5，6，7進行異或，得到0

8，9進行異或，得到1

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

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

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

1，3，5，7，9進行異或，得到0

2，3，6，7進行異或，得到1

4，5，6，7進行異或，得到1

8，9進行異或，得到0

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

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

通過原理，我們可以很簡單地實現(xià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++）

解碼與校驗：

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;

}

測試樣例：

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