循环冗余检测

6循环冗余检测计算机网络中广泛采用。循环冗余检测CRC(cyclicredundancycheck)编码：即多项式编码，把要发送的比特串看作为系数是0或1的一个多项式，对比特串的操作看作为多项式运算。基本思想：设发送节点要把数据D（d比特）发送给接收节点。发送方和接收方先共同选定一个生成多项式G（r+1比特），最高有效位是1。发送方：计算出一个r位附加比特R，添加到D的后面产生DR（d+r比特）DR能被G模2运算整除，一起发送。接收方：用G（r+1比特）去除接收到的DR（d+r比特）余数非0：传输发生差错；余数为0：传输正确，去掉尾部r位，得所需数据D。10111x4+x2+x+1D:要发送的数据（d位）R:CRC校验（r位）DR（d+r位）模2运算：加法不进位，减法不借位，即操作数的按位异或(XOR)例1011XOR0101=1110；1011-0101=11101001XOR1101=0100；1001-1101=0100乘法和除法与二进制运算类似，其中加法或减法没有进位或借位。乘以2r，即比特模式左移r个位置。D×2rXORR=D00…00XORR=DR(d+r比特)计算R（CRC比特）：DR能被G模2运算整除：即D×2rXORR=nG等式两边都用R异或，得到D×2r=nGXORR即用G来除D×2r，余数值刚好为R。R的计算：将数据D后面添加r个0，除以给定的生成多项式G，所得余数即为R（r位）。例设D=101110，d=6，G=1001，r=3实际传输的数据形式是：101110011r+1位D后添加3个03位生成多项式G的选择：有8、12、16和32比特生成多项式G。8比特的CRC用于保护ATM信元首部；32比特的标准CRC-32用于链路级协议：GCRC-32=100000100110000010001110110110111例1.已知：信息码:110011信息多项式:K(X)=X5+X4+X+1生成码:11001生成多项式:G(X)=X4+X3+1,(r=4)求：循环冗余码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)*Xr11001.10000110011001←CRC(冗余码)由计算结果知冗余码CRC=1001。把data=110011,crc=1001一起发送。CRC例子：例2.已知：接收数据:110011+1001,多项式:T(X)=X9+X8+X5+X4+X3+1生成码:11001,生成多项式:G(X)=X4+X3+1(r=4)判断数据的正确性，若正确，求冗余码和信息码。解：1)用接收码除以生成码:100001←Q(X)G(x)→11001)1100111001←K(X)*Xr＋R(x)11001，11001110010←S(X)(余数)余数S(x)为0，所以码字正确。2)因r=4，所以冗余码CRC是：1001，信息码是:1100111)可检测出所有奇数位错；2)可检测出所有双比特的错；3)可检测出所有小于、等于校验位长度（r+1）的突发错。例如：100110←Q(X)G(x)→11001)1101111001←K(X)*Xr＋R(x)11001.1011011001.1111011001.1111←S(X)余数S(x)不为0，所以数据不正确。循环冗余校验码的特点