8 计算机网络技术 2.循环冗余校验码CRC 循环冗余校验码(Cycle Redundancy Check,简称CRC)是一种被广泛采用的多项式编 码。CC码由两部分组成，前一部分是k+1个比特的待发送信息，后一部分是r个比特的 冗余码。由于前一部分是实际要传送的内容，因此是固定不变的，CC码的产生关键在于 后一部分冗余码的计算。 计算中主要用到两个多项式：f(x)和G(x)。其中，f(x)是一个k阶多项式，其系数是 待发送的k+1个比特序列：G(x)是一个r阶的生成多项式，由发收双方预先约定。 例如，设实际要发送的信息序列是1010001101（十个比特，k=9),则以它们作为f(x) 的系数，得到对应的9阶多项式为 f(x)=1·x40x+1·x2+0x+0x+0x+1x+1·x40x1 =x+x2+x3+x2+1。 再假设发收双方预先约定了一个5阶(5)的生成多项式 G(x)=x+x+x2+1=1·x+1·x+0·x+1·x2+0·x+1,则其系数序列为110101。 CRC码的产生方法如下： a)生成r个比特的冗余码 用模2除法进行xf(x)/G(x)运算，得余式R(x),其系数即是冗余码。 例如，x5f(x)=x+x+x+x'+x5,对应的二进制序列为101000110100000，也就是f(x) 信息序列向左移动r=5位，低位补0。 x5f(x)/G(x)=(101000110100000)/(110101),得余数为01110，也就是冗余码， 对应的余式R(x)=0·x+x+x2+x+0·x°（注意：若G(x)为r阶，则R(x)对应的比特序列长 度为r)。 注意，模2除法在做减法时不借位，相当于在进行异或运算。上述多项式的除法过程 如下： 1101010110 110101)101000110100000 110101 0111011 110101 00111010 110101 00111110 110101 00101100 110101 0110010 110101 01110余数，即校验序列(=5位，r也是Gx) 的阶)。8 计算机网络技术 2. 循环冗余校验码 CRC 循环冗余校验码（Cycle Redundancy Check，简称 CRC）是一种被广泛采用的多项式编 码。CRC 码由两部分组成，前一部分是 k+1 个比特的待发送信息，后一部分是 r 个比特的 冗余码。由于前一部分是实际要传送的内容，因此是固定不变的，CRC 码的产生关键在于 后一部分冗余码的计算。 计算中主要用到两个多项式：f(x)和 G(x)。其中，f(x)是一个 k 阶多项式，其系数是 待发送的 k+1 个比特序列；G(x)是一个 r 阶的生成多项式，由发收双方预先约定。 例如，设实际要发送的信息序列是 1010001101（十个比特，k=9），则以它们作为 f(x) 的系数，得到对应的 9 阶多项式为 f(x)=1·x 9 +0·x 8 +1·x 7 +0·x 6 +0·x 5 +0·x 4 +1·x 3 +1·x 2 +0·x+1 =x9 + x7 + x3 + x2 +1。 再假设发收双方预先约定了一个 5 阶 （ r=5 ）的生成多项式 G(x)=x5 +x4 +x2 +1=1·x 5 +1·x 4 +0·x 3 +1·x 2 +0·x+1,则其系数序列为 110101。 CRC 码的产生方法如下： a) 生成 r 个比特的冗余码 用模 2 除法进行 x r f(x)/G(x)运算,得余式 R(x)，其系数即是冗余码。 例如，x 5 f(x)=x14+x12+x8 +x7 +x5 ，对应的二进制序列为 101000110100000，也就是 f(x) 信息序列向左移动 r=5 位，低位补 0。 x 5 f(x)/ G(x)= （101000110100000）/（110101），得余数为 01110，也就是冗余码， 对应的余式 R(x)=0﹒x 4 +x3 +x2 +x+0﹒x 0 (注意：若 G(x)为 r 阶，则 R(x)对应的比特序列长 度为 r)。 注意，模 2 除法在做减法时不借位，相当于在进行异或运算。上述多项式的除法过程 如下： 1 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 ）1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 余数，即校验序列（r=5 位，r 也是 G(x) 的阶）