你看得懂的海明碼校驗和糾錯原理（一）

    以下内容摘自筆者即将出版的最新著作《深入了解計算機網絡》一書。本書将于12月底出版上市，敬請留意！！

     本書原始目錄參見此文：http://winda.blog.51cto.com/55153/1063878

    5.3.6 海明糾錯碼

    海明碼（Hamming Code）是一個可以有多個校驗位，具有檢測并糾正一位錯誤代碼的糾錯碼，是以它也僅用于信道特性比較好的環境中，如以太區域網路中，因為如果信道特性不好的情況下，出現的錯誤通常不是一位。

    海明碼的檢錯、糾錯基本思想是将有效資訊按某種規律分成若幹組，每組安排一個校驗位進行奇偶性測試，然後産生多位檢測資訊，并從中得出具體的出錯位置，最後通過對錯誤位取反（也是原來是1就變成0，原來是0就變成1）來将其糾正。

    要采用海明碼糾錯，需要按以下步驟來進行：計算校驗位數→确定校驗碼位置→确定校驗碼→實作校驗和糾錯。下面來具體介紹這幾個步驟。本文先介紹除最後一個步驟的其它幾個步驟。

1.    計算校驗位數

    要使用海明碼糾錯，首先就要确定發送的資料所需要要的校驗碼（也就是“海明碼”）位數（也稱“校驗碼長度”）。它是這樣的規定的：假設用N表示添加了校驗碼位後整個資訊的二進制位數，用K代表其中有效資訊位數，r表示添加的校驗碼位，它們之間的關系應滿足：N=K＋r≤2r－1。

    如K=5，則要求2r-r≥5+1=6，根據計算可以得知r的最小值為4，也就是要校驗5位資訊碼，則要插入4位校驗碼。如果資訊碼是8位，則要求2r-r≥8+1=9，根據計算可以得知r的最小值也為4。根據經驗總結，得出資訊碼和校驗碼位數之間的關系如表5-1所示。

表5-1   資訊碼位數與校驗碼位數之間的關系

資訊碼位數	1	2~4	5~11	12~26	27~57	58~120	121~247
校驗碼位數	2	3	4	5	6	7	8

2．确定校驗碼位置

    上一步我們确定了對應資訊中要插入的校驗碼位數，但這還不夠，因為這些校驗碼不是直接附加在資訊碼的前面、後面或中間的，而是分開插入到不同的位置。但不用擔心，校驗碼的位置很容易确定的，那就是校驗碼

必須

是在2n次方位置，如第1、2、4、8、16、32，……位（對應20、21、22、23、24、25，……，是從最左邊的位數起的），這樣一來就知道了資訊碼的分布位置，也就是非2n次方位置，如第3、5、6、7、9、10、11、12、13，……位（是從最左邊的位數起的）。

    舉一個例子，假設現有一個8位資訊碼，即b1、b2、b3、b4、b5、b6、b7、b8，由表5-1得知，它需要插入4位校驗碼，即p1、p2、p3、p4，也就是整個經過編碼後的資料碼（稱之為“碼字”）共有12位。根據以上介紹的校驗碼位置分布規則可以得出，這12位編碼後的資料就是p1、p2、b1、p3、b2、b3、b4、p4、b5、b6、b7、b8。

    現假設原來的8位資訊碼為10011101，因現在還沒有求出各位校驗碼值，現在這些校驗碼位都用“？”表示，最終的碼字為：？？

？

1101

。

3.    确定校驗碼

經過前面的兩步，我們已經确定了所需的校驗碼位數和這些校驗碼的插入位置，但這還不夠，還得确定各個校驗碼值。這些校驗碼的值不是随意的，每個校驗位的值代表了代碼字中部分資料位的奇偶性（最終要根據是采用奇校驗，還是偶校驗來确定），其所在位置決定了要校驗的比特位序列。總的原則是：第i位校驗碼從目前位開始，每次連續校驗i（這裡是數值i，不是第i位，下同）位後再跳過i位，然後再連續校驗i位，再跳過i位，以此類推。最後根據所采用的是奇校驗，還是偶校驗即可得出第i位校驗碼的值。

    1）計算方法

    校驗碼的具體計算方法如下：

    p1（第1個校驗位，也是整個碼字的第1位）的校驗規則是：從目前位數起，校驗1位，然後跳過1位，再校驗1位，再跳過1位，……。這樣就可得出p1校驗碼位可以校驗的碼字位包括：第1位（也就是p1本身）、第3位、第5位、第7位、第9位、第11位、第13位、第15位，……。然後根據所采用的是奇校驗，還是偶校驗，最終可以确定該校驗位的值。

    p2（第2個校驗位，也是整個碼字的第2位）的校驗規則是：從目前位數起，連續校驗2位，然後跳過2位，再連續校驗2位，再跳過2位，……。這樣就可得出p2校驗碼位可以校驗的碼字位包括：第2位（也就是p2本身）、第3位，第6位、第7位，第10位、第11位，第14位、第15位，……。同樣根據所采用的是奇校驗，還是偶校驗，最終可以确定該校驗位的值。

    p3（第3個校驗位，也是整個碼字的第4位）的校驗規則是：從目前位數起，連續校驗4位，然後跳過4位，再連續校驗4位，再跳過4位，……。這樣就可得出p4校驗碼位可以校驗的碼字位包括：第4位（也就是p4本身）、第5位、第6位、第7位，第12位、第13位、第14位、第15位，第20位、第21位、第22位、第23位，……。同樣根據所采用的是奇校驗，還是偶校驗，最終可以确定該校驗位的值。

    p4（第4個校驗位，也是整個碼字的第8位）的校驗規則是：從目前位數起，連續校驗8位，然後跳過8位，再連續校驗8位，再跳過8位，……。這樣就可得出p4校驗碼位可以校驗的碼字位包括：第8位（也就是p4本身）、第9位、第10位、第11位、第12位、第13位、第14位、第15位，第24位、第25位、第26位、第27位、第28位、第29位、第30位、第31位，……。同樣根據所采用的是奇校驗，還是偶校驗，最終可以确定該校驗位的值。

……

    我們把以上這些校驗碼所校驗的位分成對應的組，它們在接收端的校驗結果（通過對各校驗位進行邏輯“異或運算”得出）對應表示為G1、G2、G3、G4，……，正常情況下均為0。

    2）校驗碼計算示例

    同樣舉上面的例子來說明，碼字為？？

    先求第1個“？”（也就是p1，第1位）的值，因為整個碼字長度為12（包括資訊碼長和校驗碼長），是以可以得出本示例中p1校驗碼校驗的位數是1、3、5、7、9、11共6位。這6位中除了第1位（也就是p1位）不能确定外，其餘5位的值都是已知的，分别為：1、0、1、1、0。現假設采用的是偶校驗（也就是要求整個被校驗的位中的“1”的個數為偶數），從已知的5位碼值可知，已有3個“1”，是以此時p1位校驗碼的值必須為“1”，得出p1=1。

    再求第2個“？”（也就是p2，第2位）的值，根據以上規則可以很快得出本示例中p2校驗碼校驗的位數是2、3、6、7、10、11，也是一共6位。這6位中除了第2位（也就是p2位）不能确定外，其餘5位的值都是已知的，分别為：1、0、1、1、0。現假設采用的是偶校驗，從已知的5位碼值可知，也已有3個“1”，是以此時p2位校驗碼的值必須為“1”，得出p2=1。

   再求第3個“？”（也就是p3，第4位）的值，根據以上規則可以很快得出本示例中p3校驗碼校驗的位數是4、5、6、7、12，一共5位。這5位中除了第4位（也就是p3位）不能确定外，其餘4位的值都是已知的，分别為：0、0、1、1。現假設采用的是偶校驗，從已知的4位碼值可知，也已有2個“1”，是以此時p2位校驗碼的值必須為“0”，得出p3=0。

   最後求第4個“？”（也就是p4，第8位）的值，根據以上規則可以很快得出本示例中p4校驗碼校驗的位數是8、9、10、11、12（本來是可以連續校驗8位的，但本示例的碼字後面的長度沒有這麼多位，是以隻校驗到第12位止），也是一共5位。這5位中除了第8位（也就是p4位）不能确定外，其餘4位的值都是已知的，分别為：1、1、0、1。現假設采用的是偶校驗，從已知的4位碼值可知，已有3個“1”，是以此時p2位校驗碼的值必須為“1”，得出p4=1。