CRC循环校验码详解

CRC校验码设计中科大软件学院2012-8-19CRC产生背景在数字通信系统中可靠与快速往往是矛盾的。如何合理地解决可靠与速度这一对矛盾呢？可靠性快速性可靠性快速性•纠错码：在每一个发送的数据块中包含足够的冗余信息，以便接收方可以推断出被发送的数据中肯定有哪些内容。•检错码：包含一些冗余信息，但是这些信息只能让接收方推断出发生了错误，但推断不出发生了哪个错误，然后接收方可以请求重传。•参考：《计算机网络》中3.2节错误检测和纠正•海明码、CRC校验码的区别•在无线链路、光纤、铜线上应用的区别•checksum:3A0101FFF1002CCRC产生背景多项式编码•特点:检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。•从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，CRC无处不在：著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。多项式编码•多项式编码（polynomialcode），也称为CRC(cyclicredundancycheck，循环冗余校验码)，多项式编码的思想是：将位串看成是系数为0或1的多项式。CRC校验保护的单位是数据块。数据块的大小根据实际情况而定。每一个数据块均被看作是一个二进制多项式，即所有系数均为二进制（即1或0）的多项式。•当使用多项式编码时，发送方和接受方必须预先商定一个生成多项式（generatorpolynomial）G(x)。生成多项式的最高位和最低位必须为1。CRC应用CRC的主要特点检错能力极强开销很小易于实现1.ARJ,LHA,ZIP等压缩软件采用的是CRC-32；2.GIF,TIFF等图像存储格式；3.所有链路层或网络接口层协议中，例如HDLC、DDCMP等众多领域。应用范围广CRC原理将待发送的位串看成系数为0或1的多项式；收发双方约定一个生成多项式G(x)（其最高阶和最低阶系数必须为1），发送方用位串及G(x)进行某种运算得到校验和，并在帧的末尾加上校验和，使带校验和的帧的多项式能被G(x)整除;接收方收到后，用G(x)除多项式，若有余数，则传输有错。CRC校验和计算法1.若生成多项式G(x)为r阶(即r＋1位位串)，原帧为m位，其多项式为M(x)，则在原帧后面添加r个0，即循环左移r位，帧成为m+r位，相应多项式成为xrM(x);2.按模2除法用G(x)对应的位串去除对应于xrM(x)的位串,得余数R(x)；3.按模2减法(即模2加)从对应于xrM(x)的位串中减去(加上)余数R(x),结果即传送的带校验和的帧多项式T(x)。T(x)=xrM(x)+R(x)CRC验证发送方接收方设xrM(x)除以G(x)的商和余数分别为Q(x)和R(x)。则有:xrM(x)=G(x)Q(x)+R(x)即：接收方收到带CRC校验和的帧多项式T(x)=xrM(x)+R(x)。由于模2加减相当于异或运算,于是接收方模2除后商Q(x),余数0.得证！举一个例子（1）发送数据110011；（2）生成多项式G(x)=x4+x3+1；（3）将要发送的数据系列左移4位，新的序列为1100110000；（4）按模2算法，将生成的新序列除以生成多项式序列；（5）将余数多项式比特序列加到新的序列中即得发送端传送序列。下面。10000111001110011000011001100001001110011100111001接收方校验方案方案二：提取接收到序列的信息码元，重复发送方的操作xrM(x)，再除以生成多项式G(x),如果余数R’(x)=R(x),则证明传输正确。方案一：直接用接收到的序列除以生成多项式G(x),如果余数R’(x)=0,则证明传输正确。接收方校验方案生成多项式G(x)的国际标准CRC-12：x12+x11+x3+x2+x+1CRC-32：x32+x26+x23+x22+x16+x12CRC-8:x8+x2+x+1CRC-10:x10+x9+x5+x4+x2+1CRC-16：x16+x15+x2+1+x11+x10+x8+x7+x5+x4+x2+x+1CRC-CCITT：x16+x12+x5+1差错检测循环冗余校验码(CRC，CyclicRedundancycheck)•编码对于一个码长为n，信息码元为k位的循环码(n，k),其构成形式为：12knk+1k+2n位信息码元k位校验码元r位差错检测循环冗余校验码(CRC，CyclicRedundancycheck)•若生成多项式G(x)为r阶(即r＋1位位串)，原帧为m位，其多项式为M(x)，则在原帧后面添加r个0，即循环左移r位，帧成为m+r位，相应多项式成为xrM(x);•按模2除法用G(x)对应的位串去除对应于xrM(x)的位串,得余数R(x)；•按模2减法(即模2加)从对应于xrM(x)的位串中减去(加上)余数R(x),结果即传送的带校验和的帧多项式T(x)。•例m(x)=x9+x8+x6+x4+x3+x+1,k=10(3)1101011011.000010011(模二除)商数：1100001010余数：1110r(x)=x3+x2+x+0所需的循环编码C(x)为C(x)=xn·m(x)+r(x)=1101011011，1110设编码的信息码元为1101011011(1)假设G(x)=x4+x+1系数形成的位串为10011则将m(x)·x4余数取4位(2)x4·m(x)=1101011011，0000另一个例子•多项式除法1101011011,0000100111001110011100111011010011101001001111101100001010商数被除数m(x)余数r(x)除数P(x)1101011011.000010011另一个例子模2运算①模2加法运算定义为：（对应于逻辑异或）0＋0＝00＋1＝11＋0＝11＋1＝0例如0101＋0011＝0110，列竖式计算：0101＋0011──────0110异或计算为：1^1=00^0=01^0=10^1=1多项式的算术运算采用代数域理论的规则，加法没进位，减法没借位，加法和减法都等同于异或。模2运算②模2减法运算定义为：（对应于逻辑异或）0－0＝00－1＝11－0＝11－1＝0例如0110－0011＝0101，列竖式计算：0110－0011──────0101异或计算为：1^1=00^0=01^0=10^1=1模2运算③模2乘法运算定义为：0×0＝00×1＝01×0＝01×1＝1例如1011×101＝100111，列竖式计算：1011×101──────10110000＋1011────────100111模2运算④模2除法运算定义为：0÷1＝01÷1＝1模二除法是利用模二减求余数的，余数最高位为“1”，则商“1”，否则商“0”，每商1位则余数减少一位，直到余数位数少于除数位数。1110────────1011〕1100100－1011──────1111－1011──────1000－1011──────0110－0000──────110位运算按位与运算按位与运算符&是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1，否则为0。参与运算的数以补码方式出现。例如：9&5可写算式如下：00001001(9的二进制补码)&00000101(5的二进制补码)00000001可见9&5=1。按位或运算按位或运算符“|”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为1时，结果位就为1。参与运算的两个数均以补码出现。例如：9|5可写算式如下：00001001|0000010100001101(十进制为13)可见9|5=13求反运算符～为单目运算符，具有右结合性。其功能是对参与运算的数的各二进位按位求反。例如～9的运算为：~(0000000000001001)结果为：1111111111110110位运算按位异或运算按位异或运算符“^”是双目运算符。其功能是参与运算的两数各对应的二进位相异或，当两对应的二进位相异时，结果为1。参与运算数仍以补码出现，例如9^5可写成算式如下：00001001^0000010100001100(十进制为12)左移运算左移运算符“”是双目运算符。其功能把“”左边的运算数的各二进位全部左移若干位，由“”右边的数指定移动的位数，高位丢弃，低位补0。例如：a4指把a的各二进位向左移动4位。如a=00000011(十进制3)，左移4位后为00110000(十进制48)。右移运算右移运算符“”是双目运算符。其功能是把“”左边的运算数的各二进位全部右移若干位，“”右边的数指定移动的位数。例如：设a=15，a2表示把000001111右移为00000011(十进制3)。CRC校验码设计实验要求：(1)、完成基本CRC校验码生成的功能；（位数不限）；(2)、尝试完成CRC-16；CRC-16发送数据为:0X02生成多项式：0X18005余数为：0X800F