校驗(yàn)碼巧解之完整版

申冠豪

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

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

1.1 海明碼：（Hanming）

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

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

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

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

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

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

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

2 例子精講

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

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

【解析】

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

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

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

同理D5由P4、P2校驗(yàn)，D4由P4、P1校驗(yàn)，D3由P1、P2、P3校驗(yàn)，D2由P3、P2校驗(yàn)，D1由P1、P3校驗(yàn)，D0由P1、P2校驗(yàn)。

4）校驗(yàn)位的形成（按配偶原則）：

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

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

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

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

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

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

【解析】

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

故生成的CRC碼為1101001。

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

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

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

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

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

解析:

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

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

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

3 結(jié)論

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

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

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