ECC糾錯算法

漢明碼實(shí)現(xiàn)原理

漢明碼（Hamming Code）是廣泛用于內(nèi)存糾錯的編碼。漢明碼不僅可檢錯，還可糾錯。（只能發(fā)現(xiàn)和糾正一位錯誤，對于兩位或者兩位以上的錯誤無法糾正）。

我們約定一串編碼里1的個數(shù)是偶數(shù)個，那么這串編碼里攜帶的信息就是對的，否則就是錯的。我們可以在開頭對這串編碼加一位校驗(yàn)碼實(shí)現(xiàn)奇偶校驗(yàn)。比如：

我們想傳輸10010這串碼，那么在傳輸?shù)臅r候，就傳010010，其中在開頭的0就是校驗(yàn)位。

我們想傳輸10000這串碼，那么在傳輸?shù)臅r候，就傳110000，其中在開頭的1就是校驗(yàn)位。

兩個例子的1的個數(shù)都是偶數(shù)。

首先漢明碼是采用奇偶校驗(yàn)的碼。它采用了一種非常巧妙的方式，把這串?dāng)?shù)字分了組，通過分組校驗(yàn)來確定哪一位出現(xiàn)了錯誤。

比如上圖，數(shù)據(jù)分成3組，P1組中有一個錯了，P2組沒錯，P3組沒錯。

P2組里誰都沒錯，可以排除2,4,5,7這幾個數(shù)據(jù)；

P3組里誰都沒錯，可以排除3,4,6,7這幾個數(shù)據(jù)；

很容易知道，是1這個數(shù)據(jù)有了錯誤。

因此，我們按照位置來分組，同時可以知道具體哪個位置數(shù)據(jù)比特錯誤，按照位置，

凡是位置符合這種形式的，XXX1，歸到P1；

凡是位置符合這種形式的，XX1X，歸到P2；

凡是位置符合這種形式的，X1XX，歸到P3；

凡是位置符合這種形式的，1XXX，歸到P4；

位置在1,3,5,7,9,11的數(shù)據(jù)進(jìn)到P1組。

位置在2,3,6,7,10,11的數(shù)據(jù)進(jìn)到P2組。

位置在4,5,6,7的數(shù)據(jù)進(jìn)到P3組。

位置在8,9,10,11的數(shù)據(jù)進(jìn)到P4組。

那么確定了分組，校驗(yàn)碼的值也就順便確定下來了。這樣整個串的碼就確定下來了。

那么顯然各個校驗(yàn)碼也被分到各個組里面去了，而且，每個組只有一個校驗(yàn)碼。（這個，太簡單我就不解釋了……）

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

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

1.1.1        校驗(yàn)碼的位置

這是規(guī)定，記住它，在采用漢明碼的一串?dāng)?shù)據(jù)中，2的i次方的位置上，我們放校驗(yàn)碼。

校驗(yàn)碼是1，或者是0，使得校驗(yàn)碼所在的組的1的個數(shù)是偶數(shù)。

如圖：

綠色的位置是放校驗(yàn)碼的地方，1,2,4,8,16……等等，2的i次方的地方。

1.1.2        漢明碼編碼實(shí)例

以10101編碼為例，創(chuàng)建一個漢明碼編碼的空間，并且把源碼填入編碼的對應(yīng)位置中，_ _ 1_010_1，并留出校驗(yàn)碼位(校驗(yàn)位先設(shè)為0)。(因?yàn)?^4 - 1>= 5 4 滿足，而 2^3-1>= 5 3所以需要4位校驗(yàn)碼)

• 計算校驗(yàn)碼第1位，1,3,5,7,9異或?yàn)?，所以漢明碼第2^(1-1)位為0，結(jié)果為：0_1_010_1

  
  

• 計算校驗(yàn)碼第2位，2,3,6,7異或?yàn)?，所以漢明碼第2^(2-1)位為0，結(jié)果為：001_010_1

  
  

• 計算校驗(yàn)碼第3位，4,5,6,7異或?yàn)?，所以漢明碼第2^(3-1)位為1，結(jié)果為：0011010_ 1

  
  

• 計算校驗(yàn)碼第4位，8, 9異或?yàn)?，所以漢明碼第2^(4-1)位為1，結(jié)果為：001101011

  
  

  所以最終編碼為001101011.

  
  

  
  

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

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

算法很簡單，我們只要在算漢明碼校驗(yàn)位的算法的上再算一遍，就得到了漢明碼的校驗(yàn)方法，比如計算001101001對應(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ī)則，編碼出錯的地方即在第8位，我們把第8位的0換成1，即可得原來的編碼001101011。

上述的例子是出現(xiàn)在2k的校驗(yàn)位上的，如果出現(xiàn)在非2k位上，得到的結(jié)果也是一樣的，比如：假設(shè)收到的編碼為001100011，即第6位出了錯誤，我們根據(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ī)則，編碼出錯的地方即在第6位，我們把第6位的0換成1，即可得原來的編碼001101011。

參考鏈接：

漢明碼（Hamming Code）原理及實(shí)現(xiàn)

https://blog.csdn.net/qq_38526635/article/details/82842383

說人話，漢明碼（海明碼、hamming code）通俗易懂的解釋，說人話

https://blog.csdn.net/Yonggie/article/details/83186280