循環(huán)冗余檢測

6循環(huán)冗余檢測計算機網(wǎng)絡中廣泛采用。循環(huán)冗余檢測CRC(cyclicredundancycheck)編碼：即多項式編碼，把要發(fā)送的比特串看作為系數(shù)是0或1的一個多項式，對比特串的操作看作為多項式運算?；舅枷耄涸O發(fā)送節(jié)點要把數(shù)據(jù)D（d比特）發(fā)送給接收節(jié)點。發(fā)送方和接收方先共同選定一個生成多項式G（r+1比特），最高有效位是1。發(fā)送方：計算出一個r位附加比特R，添加到D的后面產(chǎn)生DR（d+r比特）

DRG模2運算整除，一起發(fā)送。接收方：用G（r+1比特）去除接收到的DR（d+r比特）：傳輸發(fā)生差錯；：傳輸正確，去掉尾部r位，得所需數(shù)據(jù)D。10111

x4+x2+x+1D:要發(fā)送的數(shù)據(jù)（d位）R:CRC校驗（r位）DR（d+r位）1模2運算：加法不進位，減法不借位，即操作數(shù)的按位異或(XOR)例1011XOR0101=1110；1011-0101=11101001XOR1101=0100；1001-1101=0100乘法和除法與二進制運算類似，其中加法或減法沒有進位或借位。乘以2r，即比特模式左移r個位置。D×2r

XORR=D00…00XORR=DR(d+r

比特)2計算R（CRC比特）：DR能被G模2運算整除：即D×2rXORR=nG等式兩邊都用R異或，得到

D×2r

=nGXORR

即用G來除D×2r，余數(shù)值剛好為R。R的計算：將數(shù)據(jù)D后面添加r個0，除以給定的生成多項式G，所得余數(shù)即為R（r位）。3例設D=101110，d=6，G=1001，r=3實際傳輸?shù)臄?shù)據(jù)形式是：101110011r+1位D后添加3個03位4

生成多項式G的選擇：有8、12、16和32比特生成多項式G。

8比特的CRC用于保護ATM信元首部；

32比特的標準CRC-32用于鏈路級協(xié)議：GCRC-32=10110110111

5例1.已知：信息碼:110011信息多項式:K(X)=X5+X4+X+1

生成碼:11001

生成多項式:G(X)=X4+X3+1,(r=4)

求：循環(huán)冗余碼CRC。

解：1)(X5+X4+X+1)*X4的積是X9+X8+X5+X4,對應的碼是1100110000。

2)CRC=積／G(X)(異或算法)。

100001←Q(X)

G(x)→11001)1100110000←K(X)*Xr

11001.

10000

11001

1001←CRC(冗余碼)由計算結果知冗余碼CRC=1001。把data=110011,crc=1001 一起發(fā)送。CRC例子：6例2.已知：接收數(shù)據(jù):110011+1001,多項式:T(X)=X9+X8+X5+X4+X3+1

生成碼:11001

,生成多項式:G(X)=X4+X3+1(r=4)

判斷數(shù)據(jù)的正確性，若正確，求冗余碼和信息碼。

解：1)用接收碼除以生成碼:

100001←Q(X)

G(x)→11001)1100111001←K(X)*Xr＋R(x)

11001，

11001

11001

0←S(X)(余數(shù))余數(shù)S(x)為0，所以碼字正確。2)因r=4，所以冗余碼CRC是：1001，信息碼是:110011

71)可檢測出所有奇數(shù)位錯；

2)可檢測出所有雙比特的錯；

3)可檢測出所有小于、等于校驗位長度（r+1）的突發(fā)錯。例如：

100110←Q(X)

G(x)→11001)1101111001←K(X)*Xr＋R(x)

11001.

10110

11001.

11110