校驗碼巧解之完整版

申冠豪

鄭州大學工學院，河南鄭州 450000

1 相關背景介紹

1.1 海明碼：（Hanming）

1）海明碼的用途：在計算機計算過程中，由于種種原因致使數據在存儲過程中出現差錯。為了能及時發現錯誤并及時糾正錯誤，通常可將原數據配成海明碼。

2）海明碼的引入：海明碼是由Richard Hanming 于1950年提出的，它具有一位糾錯能力。由糾錯編碼理論得知，任何一種編碼是否具有檢錯能力和糾錯能力，都與編碼的最小距離有關。所謂編碼最小距離，是指編碼系統中，任意兩組合法代碼之間的最小二進制位數的差異。

根據糾錯理論得：

L-1=D+C 且 D＞=C

即編碼的最小距離L越大，則其檢測錯誤的位數越多、糾正錯誤的位數也越多，且糾錯能力恒小于等于檢錯能力。

1.2 循環冗余校驗碼：（Cyclic Redundancy Check）

引入：磁表面存儲器由于磁介質表面的缺陷、塵埃等原因，致使出現許多個錯誤位，循環冗余檢驗碼可以發現和糾錯數據在存儲或傳送過程中出現的多位錯誤代碼，因此CRC碼在磁介質存儲器和計算機通信方面得到廣泛應用。

2 例子精講

2.1 設置一個信息流的海明碼

2.1.1 題目設計：分別按“配偶原則”和“配奇原則”設置信息碼1100101的海明校驗碼，要求能指出和糾正一位錯。

【解析】

1）確定海明碼的校驗位的位數：設r為校驗位的位數，則整個碼字的位數應滿足不等式：2r＞=k+r+1，其中k為信息位數，這里k=7，所以可計算出r＞=4，所以至少需要4位校驗位。

2）確定校驗位的位置：用位號（1-11）為2的權值的那些位，即20，21，22，23的位置作為校驗位，分別記作P1,P2,P3,P4,余下的位有效信息位。

3）分組：有4個校驗位，須將11位分成4組 ，第i位由校驗位序號之和等于i的那些校驗位所校驗，如第11位D6由P1 (序號為1)，P2 (序號為2)，P4 (序號為8)校驗，因為11=1+2+8。

同理D5由P4、P2校驗，D4由P4、P1校驗，D3由P1、P2、P3校驗，D2由P3、P2校驗，D1由P1、P3校驗，D0由P1、P2校驗。

4）校驗位的形成（按配偶原則）：

綜上題目中所給信息碼的能檢錯一位并糾錯一位的海明碼為11000101100。

【注】上面第(4)步，如果按配奇原則，則只需將所得每個異或結果取反即可，具體過程如下：

從而得到相應的海明碼是11010100111。

為了幫讀者方便確定校驗位的位數，以下給出了不同代碼長度n所需檢測位的位數k,如下表所示：

2.2 如何設置一個信息流的循環冗余校驗碼（CRC）及進行糾錯

題目設計：已知有效信息為1101。試用生成多項式G(X)=1011將其編成循環冗余校驗碼（CRC）；

【解析】

由于生成多項式為4位，故根據題意，最終的CRC碼由4位數據位加3位校驗位組成。校驗位的生成方式為：將數據位乘以2r（其中r的值由生成多項式的位數減1得到）,相當于將數據位右邊添加3個0，即1101000，模2除以G（X）,得到的三位余數即為校驗碼，模2除的過程如下：

故生成的CRC碼為1101001。

【注】題中用到了模2除和模2減，其運算規則如下：

模2減:不考慮借位，當兩個相同的數相減得0，當兩個相異的數相減得1；

模2除:按模2減來計算，每上商一次使余數減少一位。上商的原則是：當余數的首位是1時上1，當余數的首位是0時上0，當余數的位數小于除數時，預算結束。

2.3 已知給出接收到的海明碼，若何確定欲傳送的信息流

用海明碼來發現并糾正一位錯。當收到的海明碼位010011011100時，試問欲傳送的信息是什么？

解析:

首先，應判斷接收到的海明碼是否出現錯誤。結合上面的海明碼編碼過程，校驗原理如下：

在接收端分別求：G1,G2,G3,G4.

按配偶原則，通過觀察，G2和G3中特有的公共位D6出錯，將其取反變為1，并去掉校驗位便得到欲傳送的信息流位01001111。

3 結論

以上介紹了三大校驗碼的計算及相關解題過程，該解題思路是比較詳細的解題過程，對于考研學員及初學者能夠掌握該方法去解題，就已經夠用了。

[1]唐朔飛.計算機組成與原理.2版.高等教育出版社，2008，1.

[2]計算機專業基礎知識綜合復習指南.復旦大學出版社，2010，10.