循環(huán)冗余檢測(cè)

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

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

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

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

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

D×2r

=nGXORR

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

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

8比特的CRC用于保護(hù)ATM信元首部；

32比特的標(biāo)準(zhǔn)CRC-32用于鏈路級(jí)協(xié)議：GCRC-32=10110110111

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

生成碼:11001

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

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

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

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

100001←Q(X)

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

11001.

10000

11001

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

生成碼:11001

,生成多項(xiàng)式: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)可檢測(cè)出所有奇數(shù)位錯(cuò)；

2)可檢測(cè)出所有雙比特的錯(cuò)；

3)可檢測(cè)出所有小于、等于校驗(yàn)位長(zhǎng)度（r+1）的突發(fā)錯(cuò)。例如：

100110←Q(X)

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

11001.

10110

11001.

11110