2.4 校驗(yàn)碼

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

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

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

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

奇偶校驗(yàn)碼

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

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

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

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

• 特點(diǎn)：

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

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

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

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

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

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

**合法代碼集合——**檢0位錯(cuò)，糾0位錯(cuò)

編碼的最小距離

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

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

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

   

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

   

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

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

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

海明校驗(yàn)碼

引言

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

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

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

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

編碼基本思想

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

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

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

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

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

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

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

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

模2除法

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