2.4 校驗(yàn)碼

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

糾錯的關(guān)鍵：如何快速、準(zhǔn)確地發(fā)現(xiàn)錯誤。

常用技術(shù)：校驗(yàn)碼技術(shù)。

常用校驗(yàn)碼有三種：奇偶校驗(yàn)碼、海明碼和循環(huán)冗余碼。

奇偶校驗(yàn)碼

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

形成校驗(yàn)位、進(jìn)行校驗(yàn)的電路實(shí)現(xiàn)簡單。

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

注意：奇偶校驗(yàn)位本身也可能出錯。

• 特點(diǎn)：

• 奇偶校驗(yàn)方法簡單，電路容易實(shí)現(xiàn)，而且只需要一位額外的存儲空間，因此應(yīng)用較多。

• 單向奇偶校驗(yàn)只能檢測出校驗(yàn)碼中有奇數(shù)個位出錯，不能發(fā)現(xiàn)偶數(shù)個錯誤，也不能確定哪位出錯。

• 交叉奇偶校驗(yàn)：

• 大量字節(jié)的數(shù)據(jù)塊傳送時，經(jīng)常將數(shù)據(jù)塊中的多個字節(jié)排列成矩陣，進(jìn)行橫向和縱向同時進(jìn)行校驗(yàn)。

• 交叉校驗(yàn)可以發(fā)現(xiàn)兩位同時出錯的情況。在一定程度上對單向的奇偶校驗(yàn)是一種彌補(bǔ)。例如：

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

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

編碼的最小距離

海明校驗(yàn)碼的組成

1. 漢明碼采用奇偶校驗(yàn)

2. 漢明碼采用分組校驗(yàn)

   

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

   

海明校驗(yàn)碼的組成

海明校驗(yàn)碼的組成三要素

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

海明校驗(yàn)碼

引言

奇偶校驗(yàn)無法檢測出偶數(shù)個位出現(xiàn)錯誤，即使測出了錯誤，也不能指出哪一位出現(xiàn)了錯誤。

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

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

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

編碼基本思想

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

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

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

循環(huán)冗余校驗(yàn)碼CRC（Cyclic Redundancy Check）是最著名的一種檢錯方式。

特點(diǎn)：檢錯能力極強(qiáng)，開銷小，易于用編碼器及檢測電路實(shí)現(xiàn)。其漏檢率低于0.0047%，在性能上和開銷上也遠(yuǎn)遠(yuǎn)優(yōu)于奇偶校驗(yàn)等方式。

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

循環(huán)冗余校驗(yàn)碼CRC把任何一個二進(jìn)制編碼都與一個系數(shù)為0或1的多項(xiàng)一一對應(yīng)，因此循環(huán)冗余校驗(yàn)碼CRC又稱為多項(xiàng)式碼。

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

模2除法

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