校驗碼

2024年3月31日發(fā)(作者：迢迢牽牛星的詩意)

校驗碼

二進制數(shù)據(jù)經(jīng)過傳送、存取等環(huán)節(jié)，會發(fā)生誤碼（1變成0或0變成1），這就有如何發(fā)現(xiàn)及糾

正誤碼的問題。所有解決此類問題的方法就是在原始數(shù)據(jù)（數(shù)碼位）基礎(chǔ)上增加幾位校驗（冗余）

位。

一、碼距

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

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

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

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

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

被誤收為011，因011仍是表中的合法碼字，接收機仍將認為011是正確的信息。

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

2的表中所示。

二進碼字

信息序號

a

2

0

1

2

3

4

5

6

7

0

0

0

0

1

1

1

1

a

1

0

0

1

1

0

0

1

1

a0

0

1

0

1

0

1

0

1

0

1

2

3

4

5

6

7

信息序號

a

3

a

2

0

1

1

0

1

0

0

1

0

0

0

0

1

1

1

1

a

1

a

0

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

二進碼字

圖 1

圖 2

碼 能 力

碼距

檢錯 糾錯

1

2

3

4

5

6

7

0 0

1 0

2 或 1

2 加 1

2 加 2

3 加 2

3 加 3

注意，圖8-2的8個碼字相互間最少有兩bit的差異。因此，如果

任何信息的一個數(shù)位被顛倒，就成為一個不用的碼字，接收機能檢查出

來。例如信息是1001，誤收為1011，接收機知道發(fā)生了一個差錯，因

為1011不是一個碼字（表中沒有）。然而，差錯不能被糾正。假定只

有一個數(shù)位是錯的，正確碼字可以是1001，1111，0011或1010。接收

者不能確定原來到底是這4個碼字中的那一個。也可看到， 在這個系

統(tǒng)中，偶數(shù)個（2或4）差錯也無法發(fā)現(xiàn)。

為了使一個系統(tǒng)能檢查和糾正一個差錯，碼間最小距離必須至少

是“3”。最小距離為3時，或能糾正一個錯，或能檢二個錯，但不能同

時糾一個錯和檢二個錯。編碼信息糾錯和檢錯能力的進一步提高需要進

一步增加碼字間的最小距離。 圖8-3的表概括了最小距離為1至7的

碼的糾錯和檢錯能力。

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

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

率等因素。要有專門的研究來解決這些問題。

二、奇偶校驗

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

奇偶校驗將使碼的最小距離由一增加到二。

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

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

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

奇性=a

0

⊕a

1

⊕a

2

⊕…⊕a

n

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

圖8-2中，就是這樣做的。可以看出，附加碼元d2，是簡單地用來使每個字成為偶性的。因此，

若有一個碼元是錯的，就可以分辨得出，因為奇偶校驗將成為奇性。奇偶校驗編碼通過增加一位

校驗位來使編碼中1個個數(shù)為奇數(shù)（奇校驗）或者為偶數(shù)（偶校驗），從而使碼距變?yōu)?。因為

其利用的是編碼中1的個數(shù)的奇偶性作為依據(jù)，所以不能發(fā)現(xiàn)偶數(shù)位錯誤。

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

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

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

不是合法的奇校驗碼了。但若有兩位（假設是第1、2位）出錯就變成10110011，1的個數(shù)為5，

還是奇數(shù)。接收端還認為是一個合法的代碼（數(shù)字3的ASCII碼）。所以奇偶校驗不能發(fā)現(xiàn)。

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

偶校驗位 a

n

=a

0

⊕a

1

⊕a

2

⊕…⊕a

n-1

，

奇校驗位 a

n

=NOT（a

0

⊕a

1

⊕a

2

⊕…⊕a

n-1

）。

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

的數(shù)字在接收機中被檢測， 如果沒有出現(xiàn)正確的奇、偶性，這個信息標定為錯誤的，這個系統(tǒng)

將把錯誤的字拋掉或者請求重發(fā)。

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

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

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

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

圖3

m位數(shù)字

a

1

b

1

c

1

…

n

1

a

2

b

2

c

2

…

n

2

…

…

…

…

…

…

a

m-1

a

m

b

m-1

b

m

c

m-1

c

m

…

…

橫向奇偶位

HP

1

HP

2

HP

3

…

HP

n

HP

n+1

n

個

碼

字

縱向奇偶位

n

m-1

n

m

VP

m-1

VP

m

VP

1

VP

2

圖 4 用綜橫奇偶校驗的分組奇偶校驗碼