CRC码的简单计算(课下作业).ppt

CRC码的计算 1.什么是 CRC码？ 循环冗余码校验英文名称为 Cyclical Redundancy Check，简称 CRC。 它是利用多项式除法及余数的原理来作错 误侦测（ Error Detecting）的。实际应用时， 发送装置计算出 CRC值 并随数据一同发送给接 收装置，接收装置对收到的数据重新计算 CRC 并与收到的 CRC相比较，若两个 CRC值不同， 则说明 数据通讯 出现错误。 2.多项式的生成 CRC码 把整个数据块当作一串连续的二进制数据。 代数结构可看作是一个报文码多项式，是基于 将位串看成是系数为 0或 1的多项式，一个 k位 帧可以看成是从 x（ k-1）到 x（ 0）的 k次多项 式的系数序列 ，这个多项式的 阶数： k-1。 码 组与多项式系数序列的对应 ，高位 (最左边 )是 x的 k-1项系数，下一位是 x的 k-2项的系数，以此类推， 生成多项式的最高位和最低位必须是 1，且 生成多项式必须比该校验和的多项式短。 For example,110101有 6位，表示成多项式是 x5+x4+x2+0，即它的 6个多项式系数分别是 1， 1， 0， 1， 0，和 1。 when采用多项式编码的方法，发送方和 接收方必须事先商定一个生成多项式 G(x)。要计算 m位帧 M(x)的校验和，生 成多项式必须比该校验和的多项式短。 基本思想是： 将校验和加在帧的末尾，使 这个带校验和的帧的多项式能被 G(x)除 尽。当接收方收到带有校验和的帧时， 用 G(x)去除它，如果有余数，则传输出 错。 CRC码的计算 由以上分析可知，既然 除数是随机， 或者按标准选定的，所以 CRC校验的关键是如何求出 余数，也就是 CRC校验码。 下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式为 G（ X） = X4 + X3 + 1，要求出 二进制序列 10110011的 CRC校验码。具体的计算过 程如下（不会作图没办法啦）： （ 1）首先把生成多项式 转换 成 二进制数 ，由 G（ X） = X4 + X3 + 1可以知道（，它一共是 5位（总位数 等于最高位的幂次加 1，即 4+1=5），然后根据多项 式各项的含义（多项式只列出二进制值为 1的位，也 就是这个二进制的第 4位、第 3位、第 0位的二进制均 为 1，其它位均为 0）很快就可得到它的 二进制比特串 为 11001。 （ 2）因为生成多项式的位数为 5，根据 前面的介绍，得知 CRC校验码的位数为 4 （校验码的位数比生成多项式的位数少 1）。因为 原数据帧 10110011，在它后 面再加 4个 0，得到 101100110000， 然 后把这个数以 “ 模 2除法 ” 方式除以生 成多项式 11001，得到的余数，即得 CRC校验码为 0100。具体操作在黑板上 演示。 【 说明 】 “模 2除法 ” 与 “ 算术除法 ” 类似， 但它既不向上位借位，也不比较除数和被除数 的相同位数值的大小，只要以相同位数进行相 除即可。模 2加法运算为： 1+1=0， 0+1=1， 0+0=0，无进位，也无借位；模 2减法运算为： 1-1=0， 0-1=1， 1-0=1， 0-0=0，也无进 位，无借位。 相当于二进制中的逻辑异或运算 。 也就是比较后， 两者对应位相同则结果为 “ 0”，不同则结果为 “ 1”。如 100101除以 1110，结果得到商为 11，余数为 1，再如 11 11=101。 总结计算 ： 只要会把生成多项式按 项系数转化为二进制数作为除数， 在原帧后补上多项式阶数个 0得到的 新串作为被除数，做多项式除法时 按 “ 模 2除法 ” ，相减异或，商到最 低位余数即为 CRC码，将原帧加上 CRC码发送就 O啦 ！谢谢！ 2014-z0