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