校驗碼

在原始傳輸?shù)亩M制碼中，增加與傳輸信息無關的位，以用來檢驗或者糾錯傳輸?shù)男畔?/p>

奇偶校驗

名稱是個錯誤，應該叫奇偶驗碼，因為他只能驗不能校。

一、奇校驗

整個校驗碼(奇校驗位+有效信息位)中1的個數(shù)為奇(每位相加和為奇數(shù))

二、偶校驗

整個校驗碼(奇校驗位+有效信息位)中1的個數(shù)為偶(每位相加和為偶數(shù))
三、舉例說明

四、局限性

只能發(fā)現(xiàn)奇數(shù)個位置出錯，而且僅僅是發(fā)現(xiàn)不能糾正。

海明(Hamming)校驗碼

一、基本概念本質(zhì)上是多重奇偶校驗碼，有一位出錯可以影響多個奇偶校驗碼，然后比對這幾個奇偶校驗碼都出現(xiàn)的位，這幾個位就是出問題的。
如果出錯的幾組校驗碼都指向相同的位，那么就把這些位的數(shù)字取反即可，這就是校;如果出錯的幾組校驗碼都指向位不是唯一的，那么這幾種情況的出錯位就是可能出錯，但是不確定到底是那個，這就是驗。編碼的最小碼距為?L?，檢測錯誤的位數(shù)D，?糾正位數(shù)為C?，則他們滿足下列關系

二、舉例說明

編碼前有效信息為10011101，求校驗碼位數(shù)？

求海明碼值——一般采用偶校驗

到此整個編碼工作結(jié)束，各校驗碼的碼值和碼位如下

求解海明碼值

你會發(fā)現(xiàn)只有S1和S3的值為1,對比表格發(fā)現(xiàn)只有H5為兩個共有的元素(陰影的那列)，所以判斷是H5出了問題

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

循環(huán)冗余碼(Cyclic Redundancy Code, CRC)又稱多項式碼， 任何一個二進制串都可以跟一個只含01的多項式建立關系。

模二除法

循環(huán)冗余碼組成

假設發(fā)送端傳輸K位二進制信息碼，雙方實現(xiàn)預訂好G(x)(其中G(x)的階數(shù)R)，將K左移r位，K與G(x)模2除法，得余數(shù)(正好也是R位)，放到K后面拼接成功。除數(shù)不是隨便找一個多項式就可以用來計算的，事實上有一套標準。

舉例說明

設要傳輸?shù)男畔⒋a?101001?生成多項式

求對應的CRC碼

1)移位

將原先的 K 左移 R位，得?101001?000，此時校驗位為 000，信息位為 101001

2)模2除法

根據(jù)前面的模2除法求解得到余數(shù)?001

3)余數(shù)放到校驗位

得到余數(shù) 001，重新放到校驗位得到最終報文?101001001

撿錯與糾錯

在接收端收到了CRC碼后用生成多項式為G(x)去做模2除，若得到余數(shù)為0,則碼字無誤。若如果有一位出錯，則余數(shù)不為0，而且不同位出錯，其余數(shù)也不同?？梢宰C明，余數(shù)與出錯位的對應關系只與碼制及生成多項式有關，而與信息位無關。

但這個例子不太滿足一般使用習慣，僅僅是用來舉例說明CRC，所以，我們重新計算一個循環(huán)冗余碼，假設傳輸信息為?1010 ，多項式為G(x)＝1011，可得下表

根據(jù)上面得到的結(jié)論，如果我們在求出余數(shù)不為0后，一邊對余數(shù)補0繼續(xù)做模2除，同時讓被檢測的校驗碼字循環(huán)左移。重新的CRC碼說明，當出現(xiàn)余數(shù)(101)時，出錯位也移到A7位置，當出現(xiàn)余數(shù)(100)，出錯位也移到A3位置上，可通過異或門將它糾正后在下一次移位時送回A1。這樣我們就不必像海明校驗那樣用譯碼電路對每一位提供糾正條件。當位數(shù)增多時，循環(huán)碼校驗能有效地降低硬件代價，這是它得以廣泛應用的主要原因。

eg:對上圖的CRC碼(G(x)＝1011，C(x)＝1010)，若接收端收到的碼字為1010111，用G(x)＝1011做模2除得到一個不為0的余數(shù)100，說明傳輸有錯。將此余數(shù)繼續(xù)補0用G(x)＝1011作模2除，同時讓碼字循環(huán)左移1010111。做了4次后，得到余數(shù)為101，這時碼字也循環(huán)左移4位，變成1111010。說明出錯位已移到最高位A7，將最高位1取反后變成0111010。再將它循環(huán)左移3位，補足7次，出錯位回到A3位，就成為一個正確的碼字1010011。