校驗碼輔導講座

校驗碼輔導講座

老頑童（原創）

二進制數據經過傳送、存取等環節，會發生誤碼（1變成0或0變成1），這就有如何發現及糾正誤碼的問題。所有解決此類問題的方法就是在原始數據（數碼位）基礎上增加幾位校驗（冗余）位。

一、碼距

一個編碼系統中任意兩個合法編碼（碼字）之間不同的二進數位（bit）數叫這兩個碼字的碼距，而整個編碼系統中任意兩個碼字的的最小距離就是該編碼系統的碼距。

如圖1所示的一個編碼系統，用三個bit來表示八個不同信息中。在這個系統中，兩個碼字之間不同的bit數從1到3不等，但最小值為1，故這個系統的碼距為1。如果任何碼字中一位或多位被顛倒了，結果這個碼字就不能與其它有效信息區分開。例如，如果傳送信息001，而被誤收為011，因011仍是表中的合法碼字，接收機仍將認為011是正確的信息。

然而，如果用四個二進數字來編8個碼字，那麼在碼字間的最小距離可以增加到2，如圖2的表中所示。

信息序號

二進碼字 a₂ a₁ 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

信息序號

二進碼字 a₃ a₂ a₁ a₀ 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個碼字相互間最少有兩bit的差異。因此，如果任何信息的一個數位被顛倒，就成為一個不用的碼字，接收機能檢查出來。例如信息是1001，誤收為1011，接收機知道發生了一個差錯，因為1011不是一個碼字（表中沒有）。然而，差錯不能被糾正。假定只有一個數位是錯的，正確碼字可以是1001，1111，0011或1010。接收者不能確定原來到底是這4個碼字中的那一個。也可看到， 在這個系統中，偶數個（2或4）差錯也無法發現。

為了使一個系統能檢查和糾正一個差錯，碼間最小距離必須至少是“3”。最小距離為3時，或能糾正一個錯，或能檢二個錯，但不能同時糾一個錯和檢二個錯。編碼信息糾錯和檢錯能力的進一步提高需要進一步增加碼字間的最小距離。 圖8-3的表概括了最小距離為1至7的碼的糾錯和檢錯能力。

碼距

碼 能 力 檢錯  糾錯

1

2

3

4

5

6

7

0    0

1    0

2 或 1

2 加 1

2 加 2

3 加 2

3 加 3

圖3

碼距越大，糾錯能力越強，但數據冗余也越大，即編碼效率低了。所以，選擇碼距要取決於特定系統的參數。數字系統的設計者必須考慮信息發生差錯的概率和該系統能容許的最小差錯率等因素。要有專門的研究來解決這些問題。

二、奇偶校驗

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

一個二進制碼字，如果它的碼元有奇數個1，就稱為具有奇性。例如，碼字“10110101”有五個1，因此，這個碼字具有奇性。同樣，偶性碼字具有偶數個1。注意奇性檢測等效於所有碼元的模二加，並能夠由所有碼元的異或運算來確定。對於一個n位字，奇性由下式給出：

奇性=a₀⊕a₁⊕a₂⊕…⊕a_n 

奇偶校驗可描述為：給每一個碼字加一個校驗位，用它來構成奇性或偶性校驗。例如，在圖8-2中，就是這樣做的。可以看出，附加碼元d2，是簡單地用來使每個字成為偶性的。因此，若有一個碼元是錯的，就可以分辨得出，因為奇偶校驗將成為奇性。奇偶校驗編碼通過增加一位校驗位來使編碼中1個個數為奇數（奇校驗）或者為偶數（偶校驗），從而使碼距變為2。因為其利用的是編碼中1的個數的奇偶性作為依據，所以不能發現偶數位錯誤。

再以數字0的七位ASCII碼（0110000）為例，如果傳送後右邊第一位出錯，0變成1。接收端還認為是一個合法的代碼0110001（數字1的ASCII碼）。若在最左邊加一位奇校驗位，編碼變為10110000，如果傳送後右邊第一位出錯，則變成10110001，1的個數變成偶數，就不是合法的奇校驗碼了。但若有兩位（假設是第1、2位）出錯就變成10110011，1的個數為5，還是奇數。接收端還認為是一個合法的代碼（數字3的ASCII碼）。所以奇偶校驗不能發現。

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

偶校驗位 a_n =a₀⊕a₁⊕a₂⊕…⊕a_n-1， 奇校驗位 a_n =NOT（a₀⊕a₁⊕a₂⊕…⊕a_n-1）。

在一個典型系統裡，在傳輸以前，由奇偶發生器把奇偶校驗位加到每個字中。原有信息中的數字在接收機中被檢測， 如果沒有出現正確的奇、偶性，這個信息標定為錯誤的，這個系統將把錯誤的字拋掉或者請求重發。

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

現在考慮一個系統， 它傳輸若干個長度為m位的信息。如果把這些信息都編成每組n個信息的分組，則在這些不同的信息間，也如對單個信息一樣，能夠作奇偶校驗。圖4中n個信息的一個分組排列成矩形式樣，並以橫向奇偶（HP）及縱向奇偶（VP）的形式編出奇偶校驗位。

m位數字

橫向奇偶位

n

個

碼

字

a₁ a₂ … a_m-1 a_m HP₁ b₁ b₂ … b_m-1 b_m HP₂ c₁ c₂ … c_m-1 c_m HP₃ … … … … … … n₁ n₂ … n_m-1 n_m HP_n VP₁ VP₂ … VP_m-1 VP_m HP_n+1

縱向奇偶位

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

研究圖4可知：分組奇偶校驗碼不僅能檢測許多形式的錯誤。並且在給定的行或列中產生孤立的錯誤時，還可對該錯誤進行糾正。

在初級程序員試題中（早期也出現在程序員試題中），經常有綜橫奇偶校驗的題目。一般解法應該是這樣：先找一行或一列已知數據完整的，確定出該行（或列）是奇校驗還是偶校驗。並假設行與列都采用同一種校驗（這個假設是否正確，在全部做完後可以得到驗證）。然後找只有一個未知數的行或列，根據校驗性質確定該未知數，這樣不斷做下去，就能求出所有未知數。

【例】2001年初級程序員試題

由 6 個字符的 7 位 ASCII 編碼排列，再加上水平垂直奇偶校驗位構成下列矩陣（最後一列為水平奇偶校驗位，最後一行為垂直奇偶校驗位）:

字符 7 位 ASCII 碼 HP 3 0 X₁ X₂ 0 0 1 1 0 Y₁ 1 0 0 1 0 0 X₃ 1 + X₄ 1 0 1 0 1 1 0 Y₂ 0 1 X₅ X₆ 1 1 1 1 D 1 0 0 X₇ 1 0 X₈ 0 = 0 X₉ 1 1 1 X₁₀ 1 1 VP 0 0 1 1 1 X₁₁ 1 X₁₂

則 X₁ X₂ X₃ X₄ 處的比特分別為 __(36)__ ；

   X₅ X₆ X₇ X₈ 處的比特分別為 ____ ；

   X₉ X₁₀ XI₁ X₁₂ 處的比特分別為 __(38)__ ；Y₁ 和 Y₂ 處的字符分別為 __(39)__ 和 __(40)__ 。

[解]

從ASCII碼左起第5列可知垂直為偶校驗。則：

從第1列可知X₄=0；從第3行可知水平也是偶校驗。

從第2行可知X₃=1；從第7列可知X₈=0；從第8列可知X₁₂=1；

從第7行可知X₁₁=1；從第6列可知X₁₀=0；從第6行可知X₉=1；從第2列可知X₁=1；

從第1行可知X₂=1；從第3列可知X₅=1；從第4行可知X₆=0；

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

(36) X₁X₂X₃X₄ = 1110

(37) X₅X₆X₇X₈ = 1000

(38) X₉X₁₀X₁₁X₁₂ = 1011

(39) 由字符Y₁的ASCII碼1001001=49H知道，Y₁即是“I”（由“D”的ASCII碼是1000100=44H推得）

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

假如你能記住“0”的ASCII碼是0110000=30H；“A”的ASCII碼是1000001=41H，則解起來就更方便了。

三、海明校驗

我們在前面指出過要能糾正信息字中的單個錯誤，所需的最小距離為3。實現這種糾正的方法之一是海明碼。

海明碼是一種多重(復式)奇偶檢錯系統。它將信息用邏輯形式編碼，以便能夠檢錯和糾錯。用在海明碼中的全部傳輸碼字是由原來的信息和附加的奇偶校驗位組成的。每一個這種奇偶位被編在傳輸碼字的特定位置上。實現得合適時，這個系統對於錯誤的數位無論是原有信息位中的，還是附加校驗位中的都能把它分離出來。

推導並使用長度為m位的碼字的海明碼，所需步驟如下：

1、確定最小的校驗位數k，將它們記成D1、D2、…、Dk，每個校驗位符合不同的奇偶測試規定。

2、原有信息和k個校驗位一起編成長為m+k位的新碼字。選擇k校驗位（0或1）以滿足必要的奇偶條件。

3、對所接收的信息作所需的k個奇偶檢查。

4、如果所有的奇偶檢查結果均為正確的，則認為信息無錯誤。

如果發現有一個或多個錯了，則錯誤的位由這些檢查的結果來唯一地確定。

校驗位數的位數

推求海明碼時的一項基本考慮是確定所需最少的校驗位數k。考慮長度為m位的信息，若附加了k個校驗位，則所發送的總長度為m+k。在接收器中要進行k個奇偶檢查，每個檢查結果或是真或是偽。這個奇偶檢查的結果可以表示成一個k位的二進字，它可以確定最多2k種不同狀態。 這些狀態中必有一個其所有奇偶測試試都是真的，它便是判定信息正確的條件。於是剩下的（2^k-1）種狀態，可以用來判定誤碼的位置。於是導出下一關系：

2^k-1≥m+k

碼字格式

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

圖5列出了m=4，k=3時，信息位和校驗位的分布情況。

碼字位置 B₁ B₂ B₃ B₄ B₅ B₆ B₇ 校驗位 x x 　 x 　 　 　 信息位 　 　 x 　 x x x 復合碼字 P₁ P₂ D₁ P₃ D₂ D₃ D₄

圖5 海明碼中校驗位和信息位的定位

校驗位的確定

k個校驗位是通過對m+k位復合碼字進行奇偶校驗而確定的。

其中：P₁位負責校驗海明碼的第1、3、5、7、…（P₁、D₁、D₂、D₄、…）位，（包括P₁自己）

P₂負責校驗海明碼的第2、3、6、7、…（P₂、D₁、D₃、D₄、…）位，（包括P₂自己）

P₃負責校驗海明碼的第4、5、6、7、…（P₃、D₂、D₃、D₄、…）位，（包括P₃自己）

對m=4，k=3，偶校驗的例子，只要進行式次偶性測試。這些測試（以A、B、C表示）在圖6所示各位的位置上進行。

奇偶條件

碼 字 位 置

1 2 3 4 5 6 7

A

B

C

x

　

　

　

x

x

x

　

　

　

x

x

　

x

　

x

x

x

x

x

圖6 奇偶校驗位置

因此可得到三個校驗方程及確定校驗位的三個公式：

A=B₁⊕B₃⊕B₅⊕B₇=0 得P₁=D₁⊕D₂⊕D₄

B=B₂⊕B₃⊕B₆⊕B₇=0 得P₂=D₁⊕D₃⊕D₄

C=B₄⊕B₅⊕B₆⊕B₇=0 得P₃=D₂⊕D₃⊕D₄

若四位信息碼為1001，利用這三個公式可求得三個校驗位P₁、P₂、P₃值。和海明碼，如圖7則表示了信息碼為1001時的海明碼編碼的全部情況。而圖8中則列出了全部16種信息（D₁D₂D₃D₄=0000～1111）的海明碼。

碼字位置

B₁

B₂

B₃

B₄

B₅

B₆

B₇

碼位類型

P₁

P₂

D₁

P₃

D₂

D₃

D₄

信息碼

-

-

1

-

0

0

1

校驗位

0

0

-

1

-

-

-

編碼後的海明碼

0

0

1

1

0

0

1

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

P₁ P₂ D₁ P₃ D₂ D₃ D₄ 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 未編碼信息的海明碼

上面是發送方的處理

在接收方，也可根據這三個校驗方程對接收到的信息進行同樣的奇偶測試：

A=B₁⊕B₃⊕B₅⊕B₇=0；

B=B₂⊕B₃⊕B₆⊕B₇=0；

C=B₄⊕B₅⊕B₅⊕B₇=0。

若三個校驗方程都成立,即方程式右邊都等於0，則說明沒有錯。若不成立即方程式右邊不等於0，說明有錯。從三個方程式右邊的值，可以判斷那一位出錯。例如，如果第3位數字反了，則C=0(此方程沒有B₃），A=B=1（這兩個方程有B₃）。可構成二進數CBA，以A為最低有效位，則錯誤位置就可簡單地用二進數CBA=011指出。

同樣，若三個方程式右邊的值為001，說明第1位出錯。若三個方程式右邊的值為100，說明第4位出錯。

海明碼的碼距應該是3，所以能糾正1位出錯。而奇偶校驗碼的碼距才是2，只能發現1位出錯，但不能糾正（不知道那一位錯）。無校驗的碼距是1，它出任何一位出錯後還是合法代碼，所以也就無法發現出錯。

這是關於海明碼的經典說法，即碼距為3，可以發現2位，或者糾正1位錯。應滿足2^k-1≥m+k。

但在清華的王愛英主編的《計算機組成與結構》（該書已成為國內的權威）中還提出了一種碼距為4的海明碼，可以發現2位，並且糾正1位錯。應滿足2^(k-1)≥m+k。

由於王愛英書上對這兩種概念沒有很仔細解釋（特別對碼距為3的海明碼），過渡很突然。有些書簡單抄襲時沒有仔細消化，所以出現一些概念錯。對於一般碼距為3的海明碼，應該是“可以發現2位，或者糾正1位錯”，而不是“可以發現2位，並且糾正1位錯”。在試題中出現過類似的錯誤。

四、循環冗余校驗碼

在串行傳送（磁盤、通訊）中，廣泛采用循環冗余校驗碼（CRC）。CRC也是給信息碼加上幾位校驗碼，以增加整個編碼系統的碼距和查錯糾錯能力。

CRC的理論很復雜，一般書上只介紹已有生成多項式後計算校驗碼的方法。檢錯能力與生成多項式有關，只能根據書上的結論死記。

循環冗余校驗碼（CRC）的基本原理是：在K位信息碼後再拼接R位的校驗碼，整個編碼長度為N位，因此，這種編碼又叫（N，K）碼。對於一個給定的（N，K）碼，可以證明存在一個最高次冪為N-K=R的多項式G(x)。根據G(x)可以生成K位信息的校驗碼，而G(x)叫做這個CRC碼的生成多項式。

校驗碼的具體生成過程為：假設發送信息用信息多項式C(X)表示，將C(x)左移R位，則可表示成C(x)*2^R，這樣C(x)的右邊就會空出R位，這就是校驗碼的位置。通過C(x)*2^R除以生成多項式G(x)得到的余數就是校驗碼。

幾個基本概念

1、多項式與二進制數碼

多項式和二進制數有直接對應關系：x的最高冪次對應二進制數的最高位，以下各位對應多項式的各冪次，有此冪次項對應1，無此冪次項對應0。可以看出：x的最高冪次為R，轉換成對應的二進制數有R+1位。

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

如生成多項式為G(x)=x⁴+x³+x+1， 可轉換為二進制數碼11011。

而發送信息位 1111，可轉換為數據多項式為C(x)=x³+x²+x+1。

2、生成多項式

是接受方和發送方的一個約定，也就是一個二進制數，在整個傳輸過程中，這個數始終保持不變。

在發送方,利用生成多項式對信息多項式做模2除生成校驗碼。在接受方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。

應滿足以下條件：

a、生成多項式的最高位和最低位必須為1。

b、當被傳送信息（CRC碼）任何一位發生錯誤時，被生成多項式做模2除後應該使余數不為0。

c、不同位發生錯誤時，應該使余數不同。

d、對余數繼續做模2除，應使余數循環。

將這些要求反映為數學關系是比較復雜的。但可以從有關資料查到常用的對應於不同碼制的生成多項式如圖9所示：

N K 碼距d G(x)多項式 G(x) 7 4 3

x³+x+1

1011 7 4 3

x³+x²+1

1101 7 3 4

x⁴+x³+x²+1

11101 7 3 4

x⁴+x²+x+1

10111 15 11 3

x⁴+x+1

10011 15 7 5

x⁸+x⁷+x⁶+x⁴+1

111010001 31 26 3

x⁵+x²+1

100101 31 21 5

x¹⁰+x⁹+x⁸+x⁶+x⁵+x³+1

11101101001

63 57 3

x⁶+x+1

1000011

63 51 5

x¹²+x¹⁰+x⁵+x⁴+x²+1

1010000110101

1041 1024 　

x¹⁶+x¹⁵+x²+1

11000000000000101

圖9 常用的生成多項式

3、模2除（按位除）

模2除做法與算術除法類似，但每一位除（減）的結果不影響其它位，即不向上一位借位。所以實際上就是異或。然後再移位移位做下一位的模2減。步驟如下：

a、用除數對被除數最高幾位做模2減，沒有借位。

b、除數右移一位，若余數最高位為1，商為1，並對余數做模2減。若余數最高位為0，商為0，除數繼續右移一位。

c、一直做到余數的位數小於除數時，該余數就是最終余數。

【例】1111000除以1101：

1011———商

————

1111000-----被除數

1101———— 除數

————