校驗碼巧解之完整版

申冠豪

鄭州大學(xué)工學(xué)院，河南鄭州 450000

1 相關(guān)背景介紹

1.1 海明碼：（Hanming）

1）海明碼的用途：在計算機計算過程中，由于種種原因致使數(shù)據(jù)在存儲過程中出現(xiàn)差錯。為了能及時發(fā)現(xiàn)錯誤并及時糾正錯誤，通?？蓪⒃瓟?shù)據(jù)配成海明碼。

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

根據(jù)糾錯理論得：

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

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

1.2 循環(huán)冗余校驗碼：（Cyclic Redundancy Check）

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

2 例子精講

2.1 設(shè)置一個信息流的海明碼

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

【解析】

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

2）確定校驗位的位置：用位號（1-11）為2的權(quán)值的那些位，即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)步，如果按配奇原則，則只需將所得每個異或結(jié)果取反即可，具體過程如下：

從而得到相應(yīng)的海明碼是11010100111。

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

2.2 如何設(shè)置一個信息流的循環(huán)冗余校驗碼（CRC）及進(jìn)行糾錯

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

【解析】

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

故生成的CRC碼為1101001。

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

模2減:不考慮借位，當(dāng)兩個相同的數(shù)相減得0，當(dāng)兩個相異的數(shù)相減得1；

模2除:按模2減來計算，每上商一次使余數(shù)減少一位。上商的原則是：當(dāng)余數(shù)的首位是1時上1，當(dāng)余數(shù)的首位是0時上0，當(dāng)余數(shù)的位數(shù)小于除數(shù)時，預(yù)算結(jié)束。

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

用海明碼來發(fā)現(xiàn)并糾正一位錯。當(dāng)收到的海明碼位010011011100時，試問欲傳送的信息是什么？

解析:

首先，應(yīng)判斷接收到的海明碼是否出現(xiàn)錯誤。結(jié)合上面的海明碼編碼過程，校驗原理如下：

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

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

3 結(jié)論

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

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

[2]計算機專業(yè)基礎(chǔ)知識綜合復(fù)習(xí)指南.復(fù)旦大學(xué)出版社，2010，10.