2.4 校驗碼

為減少和避免數據傳輸錯誤，一方面從電路、電源和布線等方面采取措施，提高抗干擾能力。另一方面，在數據編碼上采用一些具有特征的編碼法，附加少量電路，能夠發現某些錯誤，甚至能確定錯誤的性質和出錯的位置，進而實現自動改錯。前者稱為檢錯，后者稱為糾錯。

糾錯的關鍵：如何快速、準確地發現錯誤。

常用技術：校驗碼技術。

常用校驗碼有三種：奇偶校驗碼、海明碼和循環冗余碼。

奇偶校驗碼

奇偶校驗碼：是在若干有效信息位上，增加一個校驗位，如果校驗位的取值使得整個校驗碼中“1”的個數是奇數，稱為奇校驗碼；如果校驗位的取值使得整個校驗碼中 “1”的個數是偶數，則稱為偶校驗碼。

形成校驗位、進行校驗的電路實現簡單。

以8位有效信息D(7)D(6)…D(1)D(0)為例，其奇偶校驗位的形成和校驗電路如下圖所示。其中：A輸出端為1，表明偶校驗碼出錯；B輸出端為1，表明奇校驗碼出錯。

注意：奇偶校驗位本身也可能出錯。

• 特點：

• 奇偶校驗方法簡單，電路容易實現，而且只需要一位額外的存儲空間，因此應用較多。

• 單向奇偶校驗只能檢測出校驗碼中有奇數個位出錯，不能發現偶數個錯誤，也不能確定哪位出錯。

• 交叉奇偶校驗：

• 大量字節的數據塊傳送時，經常將數據塊中的多個字節排列成矩陣，進行橫向和縱向同時進行校驗。

• 交叉校驗可以發現兩位同時出錯的情況。在一定程度上對單向的奇偶校驗是一種彌補。例如：

  
  假設第3個字節中的D(5)和D(2)位出錯，其橫向校驗碼中仍有奇數個1，單從橫向看不出錯誤。但是D(5)列和D(2)列的各有一個錯誤，從D(5)列和D(2)列的縱向奇校驗碼會發現該列出錯。

**合法代碼集合——**檢0位錯，糾0位錯

編碼的最小距離

海明校驗碼的組成

1. 漢明碼采用奇偶校驗

2. 漢明碼采用分組校驗

   

3. 漢明碼分組采用非劃分方式

   

海明校驗碼的組成

海明校驗碼的組成三要素

• 漢明碼的組成需增添？位檢測位
• 檢測位的位置？
• 檢測位的取值？

海明校驗碼

引言

奇偶校驗無法檢測出偶數個位出現錯誤，即使測出了錯誤，也不能指出哪一位出現了錯誤。

如果一條信息中包含多個用于糾錯的位，通過妥善安排這些糾錯位，使得不同位出錯產生不同的錯誤結果，這樣就可以找出出錯位了。

例如，在一個7位的信息中，單個數據位出錯有7種可能，用3個錯誤控制位可以確定是否出錯及哪一位出錯。

海明碼就是這種思想。其本質是多重奇偶校驗，可以用來自動糾正一位差錯。至今仍在廣泛使用。

編碼基本思想

若增加校驗位，也即增加了監督關系式和校正因子，就可以用來區分更多的情況。例如：有兩個校正因子S(1)、S(2)，其取值有4種情況00、01、10和11，就可以表達4種不同的情況。比如，00表示無差錯，01、10和11可以用來指出3種不同情況的差錯，從而可以進一步區分是哪一位出錯。

假設為k個數據位設置r個校驗位，則r個校驗位能表示2(r)個狀態，用其中的一個狀態表示整個k+r位的海明碼“沒有發生錯誤”，其余的2(r) -1個狀態指出有錯誤且不同的狀態值指明相應的位發生錯誤，包括k個數據位和r個校驗位。因此校驗位的位數應滿足如下關系：

循環冗余校驗碼

循環冗余校驗碼CRC（Cyclic Redundancy Check）是最著名的一種檢錯方式。

特點：檢錯能力極強，開銷小，易于用編碼器及檢測電路實現。其漏檢率低于0.0047%，在性能上和開銷上也遠遠優于奇偶校驗等方式。

在數據存儲和數據通訊領域，CRC無處不在，著名的通訊協議X.25的FCS(幀檢錯序列) 和磁盤驅動器的讀寫都采用了CRC作為檢錯手段。

循環冗余校驗碼CRC把任何一個二進制編碼都與一個系數為0或1的多項一一對應，因此循環冗余校驗碼CRC又稱為多項式碼。

模2除法：多位二進制模2除法與普通意義上多位二進制除法類似，只是每次的求余數時，采用的是模2減法，每一位的運算不影響其他位，即不向上一位借位，實際上就是異或。

模2除法

1. 余數的首位為1，且位數與除數相同，商就為1
2. 兩個數不比較大小，做異或運算得到結果