奇偶校驗(yàn)碼作為一種檢錯碼雖然簡單,但是漏檢率太高。在計算機(jī)網(wǎng)絡(luò)和數(shù)據(jù)通信中用E得最廣泛的檢錯碼,是一種漏檢率低得多也便于實(shí)現(xiàn)的循環(huán)冗余碼CRC (Cyclic Redundancy .Code),CRC碼又稱為多項式碼。
任何一個由二進(jìn)制數(shù)位串組成的代碼,都可以惟一地與一個只含有0和1兩個系數(shù)的多項式建立一一對應(yīng)的關(guān)系。例如,代碼1010111對應(yīng)的多項式為X
6+X
4+X
2+X+1,同樣.多項式X
5+X
3+X
2+X+1對應(yīng)的代碼為101111。
CRC碼在發(fā)送端編碼和接收端校驗(yàn)時,都可以利用事先約定的生成多項式G(X)來得到。 k位要發(fā)送的信息位可對應(yīng)于一個(k-1)次多項式K(X),r位冗余位則對應(yīng)于一個(r-1)次多項式R(X),由k位信息位后面加上r位冗余位組成的n=k+r位碼字則對應(yīng)于一個(n-1)次多項式T(X)=X
r·K(X)+R(X)。例如
由信息位產(chǎn)生冗余位的編碼過程,就是已知K(X)求R(X)的過程。在CRC碼中可以通過找到一個特定的r次多項式G (X)(其最高項Xr的系數(shù)恒為1),然后用Xr·K(X)去除以G(X),得到的余式就是R(X)。特別要強(qiáng)調(diào)的是,這些多項式中的"+"都是模2加(也即異或運(yùn)算);此外,這里的除法用的也是模2除法,即除法過程中用到的減法是模2減法,它和模2加法的運(yùn)算規(guī)則一樣,都是異或運(yùn)算,這是一種不考慮加法進(jìn)位和減法借位的運(yùn)算,即
0+O=0,0+1=1,1+0=1,1+1=0
0-0=0,0-1=1,1-0=1,1-1=0
在進(jìn)行基于模2運(yùn)算的多項式除法時,只要部分余數(shù)首位為1,便可上商1,否則上商0。然后按模2減法求得余數(shù),該余數(shù)不計最高位。當(dāng)被除數(shù)逐位除完時,最后得到比除數(shù)少一位的余數(shù)。此余數(shù)即為冗余位,將其添加在信息位后便構(gòu)成CRC碼字。
仍以上例中K(X)=X6+X4+X3+1為例(即信息位為1011001),若G(X)=X4+X3+1
(對應(yīng)代碼11001),取r=4,則X4·K(X)=X10+X8+X7+X4(對應(yīng)代碼為0110010000),其由模2除法求余式R(X)的過程所示如下:
得到的最后余數(shù)為1010,這就是冗余位,對應(yīng)R(X)=X3+X。
由于R(X)是Xr·K(X)除以G(X)的余式,那么下列關(guān)系式必然滿足
Xr·K(X)=G(X)Q(X)+R(X)
其中Q(X)為商式。根據(jù)模二運(yùn)算規(guī)則R(X)+R(X)=0的特點(diǎn),可將上式改記為
[Xr-K(X)+R(X)]/G(X)=Q(X)
即 T(X)/G(X)=Q(X)
由此可見,信道上發(fā)送的碼字多項式T(X)=Xr-K(X)+R(X)。若傳輸過程無錯，則接收方收到的碼字也對應(yīng)于此多項式,也即接收到的碼字多項式能被G(X)整除。因而接收端的校驗(yàn)過程就是將接收到的碼字多項式除以G(X)的過程。若余式為零則認(rèn)為傳輸元差錯;若余式不為零則傳輸有差錯。
例如,前述例子中若碼字10110011010經(jīng)傳輸后由于受噪聲的干擾,在接收端變成為10110011100,則求余式的除法如下:
求得的余式不為零,相當(dāng)于在碼字上面半加上了差錯模式00000000110。差錯模式對應(yīng)的多項式記為E(X),上例中E(X)=X2+X。有差錯時,接收端收到的不再是T(X),而是T(X)與E(X)之模二加,即
[T(X)+E(X)]/G(X)=T(X)/G(X)+E(X)/G(X)
若E(X)/G(X)=0,則這種差錯就能檢測出來;若E(X)/G(X)=0,那么由于接收到的碼字多項式仍然可被G(X)整除,錯誤就檢測不出來,也即發(fā)生了漏檢。
理論上可以證明循環(huán)冗余校驗(yàn)碼的檢錯能力有以下特點(diǎn):
(1)可檢測出所有奇數(shù)位錯。
(2)可檢測出所有雙比特的錯。
(3)可檢測出所有小于、等于校驗(yàn)位長度的突發(fā)錯。
CRC碼是由r-K(X)除以某個選定的多項式后產(chǎn)生的,所以該多現(xiàn)式稱生成多項式。一般來說,生成多項式位數(shù)越多校驗(yàn)?zāi)芰υ綇?qiáng)。但并不是任何一個r+1位的二進(jìn)制數(shù)都可以做生成多項式。目前廣泛使用的生成多項式主要有以下四種:
