循环冗余校验(CRC校验)

1、 循环冗余校验（循环冗余校验（CRC校验）校验） nCRC校验的定义nCRC校验的原理nCRC校验中生成多项式的选择nCRC校验的应用CRCCRC校验的定义校验的定义 CRC，即循环冗余校验码：它是数据通信领域中最常用的一种差错校验码 CRC校验，是一种检验数据在传输过程中是否发生错误的方法CRCCRC校验的原理校验的原理n发送端发送数据T 假设 T=101001n将发送端数据看成系数为0或1的多项式： T(x)=1*x5+0*x4+1*x3+0*x2+0*x1+1*x0=x5+x3+1n发送端和接收端选定一个r阶的生成多项式G(x) 假设 G(x) =x3+x2+1（r=3） 即 二进制表示

2、为：1101 n将T(x)扩大xr倍得到P(x) P(x)= T(x)* xr = (x5+x3+1)* x3 = x8+x6+ x3 即 二进制表示为：101001000n用P(x)除以生成多项式G(x)得 式中，Q(x)为商，R(x)为余数)()()()(xGxRxQxGxxTr）（ 1101）1 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 0 10 0 1模二除法余数余数 1 1 00111 0000模二除法n用除数对被除数最高几位做模2减（异或），没有

3、借位 nb、除数右移一位，若余数最高位为1，商为1，并对余数做模2减。若余数最高位为0，商为0，除数继续右移一位 nc、一直做到余数的位数小于除数时，该余数就是最终余数n将P(x) + R(x) 所对应的比特序列作为一个整体传输到接收端即 二进制表示为：101001000+001T(x)R(x)xr 发送数据：101001001接收端数据校验接收端数据校验n方案一：直接用接收到的序列除以生成多项式G(x)，如果余数R(x) = 0，则证明传输正确n方案二：提取接收到序列的信息码元，重复发送方的操作T(x)xr ，再除以生成多项式G(x)，如果余数R(x) = R(x)，则证明传输正确CRC校验

4、中生成多项式的选择校验中生成多项式的选择n只要xr和x0项的系数不为0，可检测所有的单比特错n只要G(x)含有一个至少三项的因子，可检测所有的双比特错n只要G(x)包含因子(x+1)，可检测任意奇数个错n序列长度小于r比特（大部分大于r比特的突发性差错也能检测到），可检测任何“突发性”差错（即连续的差错比特序列）通用通用CRCCRC生成多项式生成多项式名称名称 生成多项式生成多项式CRC-8 xCRC-8 x8 8+x+x2 2+x+x1 1+1+1CRC-10 xCRC-10 x1010+x+x9 9+x+x5 5+x+x4 4+x+x1 1+1+1CRC-12 xCRC-12 x1212+x+x1111+x+x3 3+x+x2 2+1+1CRC-16 xCRC-16 x1616+x+x1515+x+x2 2+1+1CRC-CCITT xCRC-CCITT x1616+x+x1212+x+x5 5+1+1CRC-32 CRC-32 x x3232+x+x2626+x+x2323+x+x2222+x+x1616+x+x1212+x+x1111+x+x1010+x+x8 8+x+x7 7+x+x5 5+ + x x4 4+x+x2 2+x+x1 1+1+1CRCCRC校验的应用校验的应用n特点：检错能力极强，开销小，易于用硬件