海明碼及碼距

2024年3月31日發(fā)(作者：個(gè)體名詞)

海明碼及碼距

一、碼距

一個(gè)編碼系統(tǒng)中任意兩個(gè)合法編碼（碼字）之間不同的二進(jìn)數(shù)位（bit）數(shù)叫這兩個(gè)碼字的

碼距，而整個(gè)編碼系統(tǒng)中任意兩個(gè)碼字的的最小距離就是該編碼系統(tǒng)的碼距。

如圖1所示的一個(gè)編碼系統(tǒng)，用三個(gè)bit來表示八個(gè)不同信息中。在這個(gè)系統(tǒng)中，兩個(gè)碼字

之間不同的bit數(shù)從1到3不等，但最小值為1，故這個(gè)系統(tǒng)的碼距為1。如果任何碼字中

一位或多位被顛倒了，結(jié)果這個(gè)碼字就不能與其它有效信息區(qū)分開。例如，如果傳送信息

001，而被誤收為011，因011仍是表中的合法碼字，接收機(jī)仍將認(rèn)為011是正確的信息。

然而，如果用四個(gè)二進(jìn)數(shù)字來編8個(gè)碼字，那么在碼字間的最小距離可以增加到2，如圖2

的表中所示。

信息序號(hào)

二進(jìn)碼字

a2 a1 a0

0 0 0 0

1 0 0 1

2 0 1 0

3 0 1 1

4 1 0 0

5 1 0 1

6 1 1 0

7 1 1 1

圖 1

信息序號(hào)

二進(jìn)碼字

a3 a2 a1 a0

0 0 0 0 0

1 1 0 0 1

2 1 0 1 0

3 0 0 1 1

4 1 1 0 0

5 0 1 0 1

6 0 1 1 0

7 1 1 1 1

圖 2

注意，圖8-2的8個(gè)碼字相互間最少有兩bit的差異。因此，如果任何信息的一個(gè)數(shù)位被顛

倒，就成為一個(gè)不用的碼字，接收機(jī)能檢查出來。例如信息是1001，誤收為1011，接收機(jī)

知道發(fā)生了一個(gè)差錯(cuò)，因?yàn)?011不是一個(gè)碼字（表中沒有）。然而，差錯(cuò)不能被糾正。假定

只有一個(gè)數(shù)位是錯(cuò)的，正確碼字可以是1001，1111，0011或1010。接收者不能確定原來到

底是這4個(gè)碼字中的那一個(gè)。也可看到， 在這個(gè)系統(tǒng)中，偶數(shù)個(gè)（2或4）差錯(cuò)也無法發(fā)現(xiàn)。

為了使一個(gè)系統(tǒng)能檢查和糾正一個(gè)差錯(cuò)，碼間最小距離必須至少是“3”。最小距離為3時(shí)，

或能糾正一個(gè)錯(cuò)，或能檢二個(gè)錯(cuò)，但不能同時(shí)糾一個(gè)錯(cuò)和檢二個(gè)錯(cuò)。編碼信息糾錯(cuò)和檢錯(cuò)能

力的進(jìn)一步提高需要進(jìn)一步增加碼字間的最小距離。圖8-3的表概括了最小距離為1至7的

碼的糾錯(cuò)和檢錯(cuò)能力。

碼距

碼 能 力

檢錯(cuò) 糾錯(cuò)

1 0 0

2 1 0

3 2 或 1

4 2 加 1

5 2 加 2

6 3 加 2

7 3 加 3

圖3

碼距越大，糾錯(cuò)能力越強(qiáng)，但數(shù)據(jù)冗余也越大，即編碼效率低了。所以，選擇碼距要取決于

特定系統(tǒng)的參數(shù)。數(shù)字系統(tǒng)的設(shè)計(jì)者必須考慮信息發(fā)生差錯(cuò)的概率和該系統(tǒng)能容許的最小差

錯(cuò)率等因素。要有專門的研究來解決這些問題。

二、奇偶校驗(yàn)

奇偶校驗(yàn)碼是一種增加二進(jìn)制傳輸系統(tǒng)最小距離的簡(jiǎn)單和廣泛采用的方法。例如，單個(gè)的奇

偶校驗(yàn)將使碼的最小距離由一增加到二。

一個(gè)二進(jìn)制碼字，如果它的碼元有奇數(shù)個(gè)1，就稱為具有奇性。例如，碼字“10110101”有

五個(gè)1，因此，這個(gè)碼字具有奇性。同樣，偶性碼字具有偶數(shù)個(gè)1。注意奇性檢測(cè)等效于所

有碼元的模二加，并能夠由所有碼元的異或運(yùn)算來確定。對(duì)于一個(gè)n位字，奇性由下式給出：

奇性=a0⊕a1⊕a2⊕…⊕an

奇偶校驗(yàn)可描述為：給每一個(gè)碼字加一個(gè)校驗(yàn)位，用它來構(gòu)成奇性或偶性校驗(yàn)。例如，在圖

8-2 中，就是這樣做的。可以看出，附加碼元d2，是簡(jiǎn)單地用來使每個(gè)字成為偶性的。因

此，若有一個(gè)碼元是錯(cuò)的，就可以分辨得出，因?yàn)槠媾夹ｒ?yàn)將成為奇性。奇偶校驗(yàn)編碼通過

增加一位校驗(yàn)位來使編碼中1個(gè)個(gè)數(shù)為奇數(shù)（奇校驗(yàn)）或者為偶數(shù)（偶校驗(yàn)），從而使碼距

變?yōu)?。因?yàn)槠淅玫氖蔷幋a中1的個(gè)數(shù)的奇偶性作為依據(jù)，所以不能發(fā)現(xiàn)偶數(shù)位錯(cuò)誤。

再以數(shù)字0的七位ASCII碼（0110000）為例，如果傳送后右邊第一位出錯(cuò)，0變成 1。接

收端還認(rèn)為是一個(gè)合法的代碼0110001（數(shù)字1的ASCII碼）。若在最左邊加一位奇校驗(yàn)位，

編碼變?yōu)?0110000，如果傳送后右邊第一位出錯(cuò)，則變成10110001，1的個(gè)數(shù)變成偶數(shù)，

就不是合法的奇校驗(yàn)碼了。但若有兩位（假設(shè)是第1、2位）出錯(cuò)就變成10110011，1的個(gè)

數(shù)為5，還是奇數(shù)。接收端還認(rèn)為是一個(gè)合法的代碼（數(shù)字3的ASCII碼）。所以奇偶校驗(yàn)

不能發(fā)現(xiàn)。

奇偶校驗(yàn)位可由硬件電路（異或門）或軟件產(chǎn)生：

偶校驗(yàn)位 an =a0⊕a1⊕a2⊕…⊕an-1， 奇校驗(yàn)位 an =NOT（a0⊕a1⊕a2⊕…⊕an-1）。

在一個(gè)典型系統(tǒng)里，在傳輸以前，由奇偶發(fā)生器把奇偶校驗(yàn)位加到每個(gè)字中。原有信息中的

數(shù)字在接收機(jī)中被檢測(cè)， 如果沒有出現(xiàn)正確的奇、偶性，這個(gè)信息標(biāo)定為錯(cuò)誤的，這個(gè)系

統(tǒng)將把錯(cuò)誤的字拋掉或者請(qǐng)求重發(fā)。

在實(shí)際工作中還經(jīng)常采用縱橫都加校驗(yàn)奇偶校驗(yàn)位的編碼系統(tǒng)--分組奇偶校驗(yàn)碼。

現(xiàn)在考慮一個(gè)系統(tǒng)， 它傳輸若干個(gè)長(zhǎng)度為m位的信息。如果把這些信息都編成每組n個(gè)信

息的分組，則在這些不同的信息間，也如對(duì)單個(gè)信息一樣，能夠作奇偶校驗(yàn)。圖4中n個(gè)信

息的一個(gè)分組排列成矩形式樣，并以橫向奇偶（HP）及縱向奇偶（VP）的形式編出奇偶校

驗(yàn)位。

m位數(shù)字

橫向奇偶位

n

個(gè)

碼

字

a1 a2 … am-1 am HP1

b1 b2 … bm-1 bm HP2

c1 c2 … cm-1 cm HP3

… … … … … …

n1 n2 … nm-1 nm HPn

VP1 VP2 … VPm-1 VPm HPn+1

縱向奇偶位

圖 4 用綜橫奇偶校驗(yàn)的分組奇偶校驗(yàn)碼

研究圖4可知：分組奇偶校驗(yàn)碼不僅能檢測(cè)許多形式的錯(cuò)誤。并且在給定的行或列中產(chǎn)生孤

立的錯(cuò)誤時(shí)，還可對(duì)該錯(cuò)誤進(jìn)行糾正。

在初級(jí)程序員試題中（早期也出現(xiàn)在程序員試題中），經(jīng)常有綜橫奇偶校驗(yàn)的題目。一般解

法應(yīng)該是這樣：先找一行或一列已知數(shù)據(jù)完整的，確定出該行（或列）是奇校驗(yàn)還是偶校驗(yàn)。

并假設(shè)行與列都采用同一種校驗(yàn)（這個(gè)假設(shè)是否正確，在全部做完后可以得到驗(yàn)證）。然后

找只有一個(gè)未知數(shù)的行或列，根據(jù)校驗(yàn)性質(zhì)確定該未知數(shù)，這樣不斷做下去，就能求出所有

未知數(shù)。

【例】2001年初級(jí)程序員試題

由 6 個(gè)字符的 7 位 ASCII 編碼排列，再加上水平垂直奇偶校驗(yàn)位構(gòu)成下列矩陣（最后一

列為水平奇偶校驗(yàn)位，最后一行為垂直奇偶校驗(yàn)位）:

字符 7 位 ASCII 碼 HP

3 0 X1 X2 0 0 1 1 0

Y1 1 0 0 1 0 0 X3 1

+ X4 1 0 1 0 1 1 0

Y2 0 1 X5 X6 1 1 1 1

D 1 0 0 X7 1 0 X8 0

= 0 X9 1 1 1 X10 1 1

VP 0 0 1 1 1 X11 1 X12

則 X1 X2 X3 X4 處的比特分別為 __(36)__ ；

X5 X6 X7 X8 處的比特分別為 ____ ；

X9 X10 XI1 X12 處的比特分別為 __(38)__ ；Y1 和 Y2 處的字符分別為 __(39)__ 和

__(40)__ 。

[解]

從ASCII碼左起第5列可知垂直為偶校驗(yàn)。則：

從第1列可知X4=0；從第3行可知水平也是偶校驗(yàn)。

從第2行可知X3=1；從第7列可知X8=0；從第8列可知X12=1；

從第7行可知X11=1；從第6列可知X10=0；從第6行可知X9=1；從第2列可知X1=1；

從第1行可知X2=1；從第3列可知X5=1；從第4行可知X6=0；

從第4列（或第5行）可知X7=0；整理一下：

(36) X1X2X3X4 = 1110

(37) X5X6X7X8 = 1000

(38) X9X10X11X12 = 1011

(39) 由字符Y1的ASCII碼1001001=49H知道，Y1即是“I”（由“D”的ASCII碼是

1000100=44H推得）

(40) 由字符Y2的ASCII碼0110111=37H知道，Y2即是“7”（由“3”的ASCII碼是0110011=33H

推得）

假如你能記住“0”的ASCII碼是0110000=30H；“A”的ASCII碼是1000001=41H，則解起

來就更方便了。

三、海明校驗(yàn)

我們?cè)谇懊嬷赋鲞^要能糾正信息字中的單個(gè)錯(cuò)誤，所需的最小距離為3。實(shí)現(xiàn)這種糾正的方

法之一是海明碼。

海明碼是一種多重(復(fù)式)奇偶檢錯(cuò)系統(tǒng)。它將信息用邏輯形式編碼，以便能夠檢錯(cuò)和糾錯(cuò)。

用在海明碼中的全部傳輸碼字是由原來的信息和附加的奇偶校驗(yàn)位組成的。每一個(gè)這種奇偶

位被編在傳輸碼字的特定位置上。實(shí)現(xiàn)得合適時(shí)，這個(gè)系統(tǒng)對(duì)于錯(cuò)誤的數(shù)位無論是原有信息

位中的，還是附加校驗(yàn)位中的都能把它分離出來。

推導(dǎo)并使用長(zhǎng)度為m位的碼字的海明碼，所需步驟如下：

1、確定最小的校驗(yàn)位數(shù)k，將它們記成D1、D2、…、Dk，每個(gè)校驗(yàn)位符合不同的奇偶測(cè)

試規(guī)定。

2、原有信息和k個(gè)校驗(yàn)位一起編成長(zhǎng)為m+k位的新碼字。選擇k校驗(yàn)位（0或1）以滿足

必要的奇偶條件。

3、對(duì)所接收的信息作所需的k個(gè)奇偶檢查。

4、如果所有的奇偶檢查結(jié)果均為正確的，則認(rèn)為信息無錯(cuò)誤。

如果發(fā)現(xiàn)有一個(gè)或多個(gè)錯(cuò)了，則錯(cuò)誤的位由這些檢查的結(jié)果來唯一地確定。

校驗(yàn)位數(shù)的位數(shù)

推求海明碼時(shí)的一項(xiàng)基本考慮是確定所需最少的校驗(yàn)位數(shù)k。考慮長(zhǎng)度為m位的信息，若附

加了k 個(gè)校驗(yàn)位，則所發(fā)送的總長(zhǎng)度為m+k。在接收器中要進(jìn)行k個(gè)奇偶檢查，每個(gè)檢查

結(jié)果或是真或是偽。這個(gè)奇偶檢查的結(jié)果可以表示成一個(gè)k位的二進(jìn)字，它可以確定最多

2k（2的K次冪）種不同狀態(tài)。這些狀態(tài)中必有一個(gè)其所有奇偶測(cè)試試都是真的，它便是判

定信息正確的條件。于是剩下的（2k-1）種狀態(tài)，可以用來判定誤碼的位置。于是導(dǎo)出下一

關(guān)系：

2k-1≥m+k

碼字格式

從理論上講，校驗(yàn)位可放在任何位置，但習(xí)慣上校驗(yàn)位被安排在1、2、4、8、…的位置上。

圖5列出了m=4，k=3時(shí)，信息位和校驗(yàn)位的分布情況。

碼字位置 B1 B2 B3 B4 B5 B6 B7

校驗(yàn)位 x x x

信息位 x x x x

復(fù)合碼字 P1 P2 D1 P3 D2 D3 D4

圖5 海明碼中校驗(yàn)位和信息位的定位

校驗(yàn)位的確定

k個(gè)校驗(yàn)位是通過對(duì)m+k位復(fù)合碼字進(jìn)行奇偶校驗(yàn)而確定的。

其中：P1位負(fù)責(zé)校驗(yàn)海明碼的第1、3、5、7、…（P1、D1、D2、D4、…）位，（包括P1

自己）

P2負(fù)責(zé)校驗(yàn)海明碼的第2、3、6、7、…（P2、D1、D3、D4、…）位，（包括P2自己）

P3負(fù)責(zé)校驗(yàn)海明碼的第4、5、6、7、…（P3、D2、D3、D4、…）位，（包括P3自己）

對(duì)m=4，k=3，偶校驗(yàn)的例子，只要進(jìn)行三次偶性測(cè)試。這些測(cè)試（以A、B、C表示）在

圖6所示各位的位置上進(jìn)行。

奇偶條件

碼 字 位 置

1 2 3 4 5 6 7

A

B

C

x

x

x

x

x

x

x

x

x

x

x

x

圖6 奇偶校驗(yàn)位置

因此可得到三個(gè)校驗(yàn)方程及確定校驗(yàn)位的三個(gè)公式：

A=B1⊕B3⊕B5⊕B7=0 得P1=D1⊕D2⊕D4

B=B2⊕B3⊕B6⊕B7=0 得P2=D1⊕D3⊕D4

C=B4⊕B5⊕B6⊕B7=0 得P3=D2⊕D3⊕D4

若四位信息碼為1001，利用這三個(gè)公式可求得三個(gè)校驗(yàn)位P1、P2、P3值。和海明碼，如圖

7則表示了信息碼為1001時(shí)的海明碼編碼的全部情況。而圖8中則列出了全部16種信息

（D1D2D3D4=0000～1111）的海明碼。

碼字位置

B1

B2

B3

B4

B5

B6

B7

碼位類型

P1

P2

D1

P3

D2

D3

D4

信息碼

-

-

1

-

0

0

1

校驗(yàn)位

0

0

-

1

-

-

-

編碼后的海明碼

0

0

1

1

0

0

1

圖7 四位信息碼的海明編碼

P1 P2 D1 P3 D2 D3 D4

0 0 0 0 0 0 0

1 1 0 1 0 0 1

0 1 0 1 0 1 0

1 0 0 0 0 1 1

1 0 0 1 1 0 0

0 1 0 0 1 0 1

1 1 0 0 1 1 0

0 0 0 1 1 1 1

1 1 1 0 0 0 0

0 0 1 1 0 0 1

1 0 1 1 0 1 0

0 1 1 0 0 1 1

0 1 1 1 1 0 0

1 0 1 0 1 0 1

0 0 1 0 1 1 0

1 1 1 1 1 1 1

圖8 未編碼信息的海明碼

上面是發(fā)送方的處理

在接收方，也可根據(jù)這三個(gè)校驗(yàn)方程對(duì)接收到的信息進(jìn)行同樣的奇偶測(cè)試：

A=B1⊕B3⊕B5⊕B7=0；

B=B2⊕B3⊕B6⊕B7=0；

C=B4⊕B5⊕B5⊕B7=0。

若三個(gè)校驗(yàn)方程都成立,即方程式右邊都等于0，則說明沒有錯(cuò)。若不成立即方程式右邊不等

于 0，說明有錯(cuò)。從三個(gè)方程式右邊的值，可以判斷那一位出錯(cuò)。例如，如果第3位數(shù)字反

了，則C=0(此方程沒有B3），A=B=1（這兩個(gè)方程有B3）。可構(gòu)成二進(jìn)數(shù)CBA，以A為最

低有效位，則錯(cuò)誤位置就可簡(jiǎn)單地用二進(jìn)數(shù)CBA=011指出。

同樣，若三個(gè)方程式右邊的值為001，說明第1位出錯(cuò)。若三個(gè)方程式右邊的值為100，說

明第4位出錯(cuò)。

海明碼的碼距應(yīng)該是3，所以能糾正1位出錯(cuò)。而奇偶校驗(yàn)碼的碼距才是2，只能發(fā)現(xiàn)1位

出錯(cuò)，但不能糾正（不知道那一位錯(cuò)）。無校驗(yàn)的碼距是1，它出任何一位出錯(cuò)后還是合法

代碼，所以也就無法發(fā)現(xiàn)出錯(cuò)。

這是關(guān)于海明碼的經(jīng)典說法，即碼距為3，可以發(fā)現(xiàn)2位，或者糾正1位錯(cuò)。應(yīng)滿足2k-1

≥m+k。

但在清華的王愛英主編的《計(jì)算機(jī)組成與結(jié)構(gòu)》（該書已成為國內(nèi)的權(quán)威）中還提出了一種

碼距為4的海明碼，可以發(fā)現(xiàn)2位，并且糾正1位錯(cuò)。應(yīng)滿足2(k-1)≥m+k。

由于王愛英書上對(duì)這兩種概念沒有很仔細(xì)解釋（特別對(duì)碼距為3的海明碼），過渡很突然。

有些書簡(jiǎn)單抄襲時(shí)沒有仔細(xì)消化，所以出現(xiàn)一些概念錯(cuò)。對(duì)于一般碼距為3的海明碼，應(yīng)該

是“可以發(fā)現(xiàn)2位，或者糾正1位錯(cuò)”，而不是“可以發(fā)現(xiàn)2位，并且糾正1位錯(cuò)”。在試題

中出現(xiàn)過類似的錯(cuò)誤。

四、循環(huán)冗余校驗(yàn)碼

在串行傳送（磁盤、通訊）中，廣泛采用循環(huán)冗余校驗(yàn)碼（CRC）。CRC也是給信息碼加上

幾位校驗(yàn)碼，以增加整個(gè)編碼系統(tǒng)的碼距和查錯(cuò)糾錯(cuò)能力。

CRC的理論很復(fù)雜，一般書上只介紹已有生成多項(xiàng)式后計(jì)算校驗(yàn)碼的方法。檢錯(cuò)能力與生

成多項(xiàng)式有關(guān)，只能根據(jù)書上的結(jié)論死記。

循環(huán)冗余校驗(yàn)碼（CRC）的基本原理是：在K位信息碼后再拼接R位的校驗(yàn)碼，整個(gè)編碼

長(zhǎng)度為 N位，因此，這種編碼又叫（N，K）碼。對(duì)于一個(gè)給定的（N，K）碼，可以證明

存在一個(gè)最高次冪為N-K=R的多項(xiàng)式G(x)。根據(jù)G(x)可以生成K位信息的校驗(yàn)碼，而G(x)

叫做這個(gè)CRC碼的生成多項(xiàng)式。

校驗(yàn)碼的具體生成過程為：假設(shè)發(fā)送信息用信息多項(xiàng)式C(X)表示，將C(x)左移R位，則可

表示成C(x)*2R，這樣C(x)的右邊就會(huì)空出R位，這就是校驗(yàn)碼的位置。通過C(x)*2R除以

生成多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。

幾個(gè)基本概念

1、多項(xiàng)式與二進(jìn)制數(shù)碼

多項(xiàng)式和二進(jìn)制數(shù)有直接對(duì)應(yīng)關(guān)系：x的最高冪次對(duì)應(yīng)二進(jìn)制數(shù)的最高位，以下各位對(duì)應(yīng)多

項(xiàng)式的各冪次，有此冪次項(xiàng)對(duì)應(yīng)1，無此冪次項(xiàng)對(duì)應(yīng)0。可以看出：x的最高冪次為R，轉(zhuǎn)

換成對(duì)應(yīng)的二進(jìn)制數(shù)有R+1位。

多項(xiàng)式包括生成多項(xiàng)式G(x)和信息多項(xiàng)式C(x)。

如生成多項(xiàng)式為G(x)=x4+x3+x+1， 可轉(zhuǎn)換為二進(jìn)制數(shù)碼11011。

而發(fā)送信息位 1111，可轉(zhuǎn)換為數(shù)據(jù)多項(xiàng)式為C(x)=x3+x2+x+1。

2、生成多項(xiàng)式

是接受方和發(fā)送方的一個(gè)約定，也就是一個(gè)二進(jìn)制數(shù)，在整個(gè)傳輸過程中，這個(gè)數(shù)始終保持

不變。

在發(fā)送方,利用生成多項(xiàng)式對(duì)信息多項(xiàng)式做模2除生成校驗(yàn)碼。在接受方利用生成多項(xiàng)式對(duì)

收到的編碼多項(xiàng)式做模2除檢測(cè)和確定錯(cuò)誤位置。

應(yīng)滿足以下條件：

a、生成多項(xiàng)式的最高位和最低位必須為1。

b、當(dāng)被傳送信息（CRC碼）任何一位發(fā)生錯(cuò)誤時(shí)，被生成多項(xiàng)式做模2除后應(yīng)該使余數(shù)不

為0。

c、不同位發(fā)生錯(cuò)誤時(shí)，應(yīng)該使余數(shù)不同。

d、對(duì)余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán)。

將這些要求反映為數(shù)學(xué)關(guān)系是比較復(fù)雜的。但可以從有關(guān)資料查到常用的對(duì)應(yīng)于不同碼制的

生成多項(xiàng)式如圖9所示：

N K 碼距d G(x)多項(xiàng)式 G(x)

7 4 3 x3+x+1 1011

7 4 3 x3+x2+1 1101

7 3 4 x4+x3+x2+1 11101

7 3 4 x4+x2+x+1 10111

15 11 3 x4+x+1 10011

15 7 5 x8+x7+x6+x4+1 111010001

31 26 3 x5+x2+1 100101

31 21 5 x10+x9+x8+x6+x5+x3+1

63 57 3 x6+x+1 1000011

63 51 5 x12+x10+x5+x4+x2+1 1

1041 1024 x16+x15+x2+1 11101

圖9 常用的生成多項(xiàng)式

3、模2除（按位除）

模2除做法與算術(shù)除法類似，但每一位除（減）的結(jié)果不影響其它位，即不向上一位借位。

所以實(shí)際上就是異或。然后再移位移位做下一位的模2減。步驟如下：

a、用除數(shù)對(duì)被除數(shù)最高幾位做模2減，沒有借位。

b、除數(shù)右移一位，若余數(shù)最高位為1，商為1，并對(duì)余數(shù)做模2減。若余數(shù)最高位為0，商

為0，除數(shù)繼續(xù)右移一位。

c、一直做到余數(shù)的位數(shù)小于除數(shù)時(shí)，該余數(shù)就是最終余數(shù)。

【例】1111000除以1101：

1011———商

————

1111000-----被除數(shù)

1101———— 除數(shù)

————

010000

1101

————

01010

1101

————

111————余數(shù)

CRC碼的生成步驟

1、將x的最高冪次為R的生成多項(xiàng)式G(x)轉(zhuǎn)換成對(duì)應(yīng)的R+1位二進(jìn)制數(shù)。

2、將信息碼左移R位，相當(dāng)與對(duì)應(yīng)的信息多項(xiàng)式C(x)*2R

3、用生成多項(xiàng)式（二進(jìn)制數(shù)）對(duì)信息碼做模2除，得到R位的余數(shù)。

4、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼。

【例】假設(shè)使用的生成多項(xiàng)式是G(x)=x3+x+1。4位的原始報(bào)文為1010，求編碼后的報(bào)文。

解：

1、將生成多項(xiàng)式G(x)=x3+x+1轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制除數(shù)1011。

2、此題生成多項(xiàng)式有4位（R+1），要把原始報(bào)文C(x)左移3（R）位變成1010000

3、用生成多項(xiàng)式對(duì)應(yīng)的二進(jìn)制數(shù)對(duì)左移4位后的原始報(bào)文進(jìn)行模2除：

1001-------商

------------------------

1010000

1011----------除數(shù)

------------

1000

1011

------------

011-------余數(shù)（校驗(yàn)位）

5、編碼后的報(bào)文（CRC碼）：

1010000

+ 011

------------------

1010011

CRC的和糾錯(cuò)

在接收端收到了CRC碼后用生成多項(xiàng)式為G(x)去做模2除，若得到余數(shù)為0,則碼字無誤。

若如果有一位出錯(cuò)，則余數(shù)不為0，而且不同位出錯(cuò)，其余數(shù)也不同。可以證明，余數(shù)與出

錯(cuò)位的對(duì)應(yīng)關(guān)系只與碼制及生成多項(xiàng)式有關(guān)，而與待測(cè)碼字（信息位）無關(guān)。圖10給出了

G(x)＝1011，C(x)＝1010的出錯(cuò)模式，改變C(x)（碼字），只會(huì)改變表中碼字內(nèi)容，不改變

余數(shù)與出錯(cuò)位的對(duì)應(yīng)關(guān)系。

收到的CRC碼字

余數(shù) 出錯(cuò)位

碼位

A7 A6 A5 A4 A3 A2 A1

正確

1 0 1 0 0 1 1

000 無

錯(cuò)

誤

1 0 1 0 0 1 0

1 0 1 0 0 0 1

1 0 1 0 1 1 1

1 0 1 1 0 1 1

1 0 0 0 0 1 1

1 1 1 0 0 1 1

0 0 1 0 0 1 1

001

010

100

011

110

111

101

1

2

3

4

5

6

7

圖10 （7，4）CRC碼的出錯(cuò)模式（G(x)＝1011）

如果循環(huán)碼有一位出錯(cuò)，用G(x)作模2除將得到一個(gè)不為0的余數(shù)。如果對(duì)余數(shù)補(bǔ)0繼續(xù)

除下去，我們將發(fā)現(xiàn)一個(gè)有趣的結(jié)果；各次余數(shù)將按圖10順序循環(huán)。例如第一位出錯(cuò)，余

數(shù)將為001，補(bǔ)0后再除（補(bǔ)0后若最高位為1，則用除數(shù)做模2減取余；若最高位為0，

則其最低3位就是余數(shù)），得到第二次余數(shù)為010。以后繼續(xù)補(bǔ)0作模2除，依次得到余數(shù)

為100，0ll…，反復(fù)循環(huán)，這就是“循環(huán)碼”名稱的由來。這是一個(gè)有價(jià)值的特點(diǎn)。如果我

們?cè)谇蟪鲇鄶?shù)不為0后，一邊對(duì)余數(shù)補(bǔ)0繼續(xù)做模2除，同時(shí)讓被檢測(cè)的校驗(yàn)碼字循環(huán)左移。

圖10說明，當(dāng)出現(xiàn)余數(shù) (101)時(shí)，出錯(cuò)位也移到A7位置。可通過異或門將它糾正后在下一

次移位時(shí)送回A1。這樣我們就不必像海明校驗(yàn)?zāi)菢佑米g碼電路對(duì)每一位提供糾正條件。當(dāng)

位數(shù)增多時(shí)，循環(huán)碼校驗(yàn)?zāi)苡行У亟档陀布鷥r(jià)，這是它得以廣泛應(yīng)用的主要原因。

【例】對(duì)圖10的CRC碼（G(x)＝1011，C(x)＝1010），若接收端收到的碼字為1010111，用

G(x)＝1011做模2除得到一個(gè)不為0的余數(shù)100，說明傳輸有錯(cuò)。將此余數(shù)繼續(xù)補(bǔ)0用G(x)

＝1011作模2除，同時(shí)讓碼字循環(huán)左移1010111。做了4次后，得到余數(shù)為101，這時(shí)碼字

也循環(huán)左移4位，變成1111010。說明出錯(cuò)位已移到最高位A7，將最高位1取反后變成

0111010。再將它循環(huán)左移3位，補(bǔ)足7次，出錯(cuò)位回到A3位，就成為一個(gè)正確的碼字1010011。

通信與網(wǎng)絡(luò)中常用的CRC

在數(shù)據(jù)通信與網(wǎng)絡(luò)中，通常k相當(dāng)大，由一千甚至數(shù)千數(shù)據(jù)位構(gòu)成一幀，而后采用CRC碼

產(chǎn)生r 位的校驗(yàn)位。它只能檢測(cè)出錯(cuò)誤，而不能糾正錯(cuò)誤。一般取r=16，標(biāo)準(zhǔn)的16位生成

多項(xiàng)式有CRC-16＝x16+x15+x2+1 和 CRC-CCITT＝x16+x15+x2+1。

一般情況下，r位生成多項(xiàng)式產(chǎn)生的CRC碼可檢測(cè)出所有的雙錯(cuò)、奇數(shù)位錯(cuò)和突發(fā)長(zhǎng)度小

于等于 r的突發(fā)錯(cuò)以及（1-2-(r-1)）的突發(fā)長(zhǎng)度為r+1的突發(fā)錯(cuò)和（1-2-r）的突發(fā)長(zhǎng)度大于

r+1的突發(fā)錯(cuò)。例如，對(duì)上述r=16的情況，就能檢測(cè)出所有突發(fā)長(zhǎng)度小于等于16的突發(fā)錯(cuò)

以及99．997%的突發(fā)長(zhǎng)度為17的突發(fā)錯(cuò)和99．998%的突發(fā)長(zhǎng)度大于17的突發(fā)錯(cuò)。所以

CRC碼的檢錯(cuò)能力還是很強(qiáng)的。這里，突發(fā)錯(cuò)誤是指幾乎是連續(xù)發(fā)生的一串錯(cuò)，突發(fā)長(zhǎng)度

就是指從出錯(cuò)的第一位到出錯(cuò)的最后一位的長(zhǎng)度(但是，中間并不一定每一位都錯(cuò))。

【例1】某循環(huán)冗余碼（CRC）的生成多項(xiàng)式 G(x)＝x3+x2+1，用此生成多項(xiàng)式產(chǎn)生的冗余

位，加在信息位后形成 CRC 碼。若發(fā)送信息位 1111 和 1100 則它的 CRC 碼分別為＿A

＿和＿B＿。由于某種原因，使接收端收到了按某種規(guī)律可判斷為出錯(cuò)的 CRC 碼，例如碼

字＿C＿、＿D＿、和＿E＿。（1998年試題11）

供選擇的答案

A：① lllll00 ② 1111101 ③ 1111110 ④ 1111111

B：① 1100100 ② 1100101 ③ 1100110 ④ 1100111

C～E：① 0000000 ② 0001100 ③ 0010111

⑤ 1000110 ⑥ 1001111 ⑦ 1010001 ⑧ 1011000

解：

A：G(x)＝1101，C(x)＝1111 C(x)*23÷G(x)＝1111000÷1101＝1011余111

得到的CRC碼為1111111

B：G(x)＝1101，C(x)＝1100 C(x)*23÷G(x)＝1100000÷1101＝1001余101

得到的CRC碼為1100101

C～E：

分別用G(x)＝1101對(duì)①～⑧ 作模2除: ① 0000000÷1101 余000 ② 1111101÷1101 余

001

③ 0010111÷1101 余000 ④ 0011010÷1101 余000 ⑤ 1000110÷1101 余000

⑥ 1001111÷1101 余100 ⑦ 1010001÷1101 余000 ⑧ 1011000÷1101 余100

所以＿C＿、＿D＿和＿E＿的答案是②、⑥、⑧

【例2】計(jì)算機(jī)中常用的一種檢錯(cuò)碼是CRC，即 _A_ 碼。在進(jìn)行編碼過程中要使用 _B_ 運(yùn)

算。假設(shè)使用的生成多項(xiàng)式是 G(X)=X4+X3+X+1， 原始報(bào)文為，則編碼后的

報(bào)文為 _C_ 。CRC碼 _D_ 的說法是正確的。

在無線電通信中常采用它規(guī)定碼字長(zhǎng)為7位．并且其中總有且僅有3個(gè)“1”。這種碼的編碼

效率為_E_。

供選擇的答案：

A：① 水平垂直奇偶校驗(yàn) ② 循環(huán)求和

③ 循環(huán)冗余 ④正比率

B：① 模2除法 ②定點(diǎn)二進(jìn)制除法 ③

二－十進(jìn)制除法 ④循環(huán)移位法

C：① 11 ② 111

③ 110 ④ 111

D：① 可糾正一位差錯(cuò) ②可檢測(cè)所

有偶數(shù)位錯(cuò)

③ 可檢測(cè)所有小于校驗(yàn)位長(zhǎng)度的突發(fā)錯(cuò) ④可檢測(cè)所有小于、等于校驗(yàn)

位長(zhǎng)度的突發(fā)錯(cuò)

E：① 3/7 ② 4/7 ③ log23/log27 ④ (log235)/7

解：從前面有關(guān)CRC的論述中可得出： A：③ 循環(huán)冗余 B：① 模2除法

C：G(x)＝11011，C(x)＝，C(x)*24÷G(x)＝110÷11011 余0011

得到的CRC碼為② 111

D：從前面有關(guān)通信與網(wǎng)絡(luò)中常用的CRC的論述中可得出：④ 可檢測(cè)所有小于、等于校驗(yàn)

位長(zhǎng)度的突發(fā)錯(cuò)

E：定比碼又叫定重碼，是奇偶校驗(yàn)的推廣。在定比碼中，奇數(shù)或偶數(shù)的性質(zhì)保持不變，然

而附加一種限制，每個(gè)字中1的總數(shù)是固定的。隨用途之不同，定比碼要求的附加校驗(yàn)位可

能多于一個(gè)，但較之單一的奇偶校驗(yàn)將增加更多的檢錯(cuò)能力。

所謂7中取3定比碼，就是整個(gè)碼字長(zhǎng)度為7位，其中1的位數(shù)固定為3。所有128個(gè)7位

代碼（0000000～1111111）中只有1的位數(shù)固定為3的才是其合法碼字。可以用求組合的公

式求出其合法碼字?jǐn)?shù)為：C73＝7!/(3!* (7-3)!)＝7*6*5/(1*2*3)＝35

編碼效率＝合法碼字所需位數(shù)/碼字總位數(shù)＝(log235)/7

極有貨 hm1c3m5k26