CRC循环校验码详解PPT学习课件.ppt

CRC校验码设计中科大软件学院2012-8-191CRC产生背景在数字通信系统中可靠与快速往往是矛盾的。在数字通信系统中可靠与快速往往是矛盾的。在数字通信系统中可靠与快速往往是矛盾的。在数字通信系统中可靠与快速往往是矛盾的。如何合理地解决可靠与速度这一对矛盾呢？如何合理地解决可靠与速度这一对矛盾呢？如何合理地解决可靠与速度这一对矛盾呢？如何合理地解决可靠与速度这一对矛盾呢？可靠性快速性可靠性可靠性可靠性可靠性快速性快速性快速性快速性2纠错码纠错码：在每一个发送的数据块中包含足够的冗余信息，以便接收方可以推断出被发送的数据中肯定有哪些内容。检错码检错码：包含一些冗余信息，但是这些信息只能让接收方推断出发生了错误，但推断不出发生了哪个错误，然后接收方可以请求重传。参考：计算机网络中 3.2节 错误检测和纠正海明码、CRC校验码的区别在无线链路、光纤、铜线上应用的区别checksum:3A 01 01 FF F1 00 2C2C CRC产生背景3多项式编码特点:检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，CRC无处不在：著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。4多项式编码多项式编码（多项式编码（polynomial codepolynomial code），也称为CRC(cyclic CRC(cyclic redundancy checkredundancy check，循环冗余校验码，循环冗余校验码)，多项式编码的思想是：将位串看成是系数为0或1的多项式。CRC校验保护的单位是数据块。数据块的大小根据实际情况而定。每一个数据块均被看作是一个二进制多项式，即所有系数均为二进制（即1或0）的多项式。当使用多项式编码时，发送方和接受方必须预先商定一个生成多项式（生成多项式（generator polynomialgenerator polynomial）G(x)。生成多项式的最高位和最低位必须为1。5CRC应用CRCCRC的主要的主要特点特点检错能力检错能力极强极强开销很小开销很小易于实现易于实现1.1.1.1.ARJ,LHA,ZIPARJ,LHA,ZIPARJ,LHA,ZIPARJ,LHA,ZIP等压缩软件采等压缩软件采等压缩软件采等压缩软件采用的是用的是用的是用的是CRC-32CRC-32CRC-32CRC-32；2.2.2.2.GIF,TIFFGIF,TIFFGIF,TIFFGIF,TIFF等图等图等图等图像存储格式；像存储格式；像存储格式；像存储格式；3.3.3.3.所有链路层或所有链路层或所有链路层或所有链路层或网络接口层协网络接口层协网络接口层协网络接口层协议中，例如议中，例如议中，例如议中，例如HDLCHDLCHDLCHDLC、DDCMPDDCMPDDCMPDDCMP等众多领域。等众多领域。等众多领域。等众多领域。应用范围广应用范围广应用范围广应用范围广6CRC原理将待发送的位串看成系数为将待发送的位串看成系数为将待发送的位串看成系数为将待发送的位串看成系数为 0 0 0 0 或或或或 1 1 1 1 的多项式；的多项式；的多项式；的多项式；收发双方约定一个生成多项式收发双方约定一个生成多项式收发双方约定一个生成多项式收发双方约定一个生成多项式 G(x)G(x)G(x)G(x)（其最高阶和（其最高阶和（其最高阶和（其最高阶和最低阶系数必须为最低阶系数必须为最低阶系数必须为最低阶系数必须为1 1 1 1），发送方用位串及），发送方用位串及），发送方用位串及），发送方用位串及 G(x)G(x)G(x)G(x)进进进进行某种运算得到校验和，并在帧的末尾加上校验行某种运算得到校验和，并在帧的末尾加上校验行某种运算得到校验和，并在帧的末尾加上校验行某种运算得到校验和，并在帧的末尾加上校验和，使带校验和的帧的多项式能被和，使带校验和的帧的多项式能被和，使带校验和的帧的多项式能被和，使带校验和的帧的多项式能被 G(x)G(x)G(x)G(x)整除整除整除整除;接收方收到后，用接收方收到后，用接收方收到后，用接收方收到后，用 G(x)G(x)G(x)G(x)除多项式，若有余数，除多项式，若有余数，除多项式，若有余数，除多项式，若有余数，则传输有错。则传输有错。则传输有错。则传输有错。7CRC校验和计算法1.1.若生成多项式若生成多项式 G(x)G(x)为为 r r 阶阶(即即r r1 1位位串位位串)，原帧为原帧为 m m 位，位，其多项式为其多项式为 M(x)M(x)，则在原帧后面，则在原帧后面添加添加 r r 个个 0 0，即循环左移，即循环左移r r位，帧成为位，帧成为 m+r m+r 位，位，相应多项式成为相应多项式成为 x xr rM(x);M(x);2.2.按模按模2 2除法用除法用 G(x)G(x)对应的位串去除对应于对应的位串去除对应于 x xr r M(x)M(x)的位串的位串,得余数得余数 R(x)R(x)；3.3.按模按模2 2减法减法(即模即模2 2加加)从对应于从对应于 xr M(x)xr M(x)的位串的位串中减去中减去(加上加上)余数余数 R(x),R(x),结果即传送的带校验和结果即传送的带校验和的帧多项式的帧多项式T(x)T(x)。T(x)=xT(x)=xr rM(x)+R(x)M(x)+R(x)8CRC验证发送方接收方设设设设 x x x xr r r r M(x)M(x)M(x)M(x)除以除以除以除以 G(x)G(x)G(x)G(x)的商和余数分别为的商和余数分别为的商和余数分别为的商和余数分别为 Q(x)Q(x)Q(x)Q(x)和和和和 R(x)R(x)R(x)R(x)。则有。则有。则有。则有:x x x xr r r rM(x)=G(x)Q(x)+R(x)M(x)=G(x)Q(x)+R(x)M(x)=G(x)Q(x)+R(x)M(x)=G(x)Q(x)+R(x)即：即：即：即：接收方收到带接收方收到带接收方收到带接收方收到带CRCCRCCRCCRC校验和的校验和的校验和的校验和的帧多项式帧多项式帧多项式帧多项式T(x)=xT(x)=xT(x)=xT(x)=xr r r r M(x)M(x)M(x)M(x)+R(x)+R(x)+R(x)+R(x)。由于模由于模由于模由于模2 2 2 2加减相当于异或运算加减相当于异或运算加减相当于异或运算加减相当于异或运算,于是接收方模于是接收方模于是接收方模于是接收方模2 2 2 2除后商除后商除后商除后商Q(x),Q(x),Q(x),Q(x),余余余余数数数数0.0.0.0.得证！得证！得证！得证！9举一个例子（1 1）发送数据）发送数据110011110011；（2 2）生成多项式）生成多项式G(x)=xG(x)=x4 4 +x+x3 3+1+1；（3 3）将要发送的数据系列）将要发送的数据系列左移左移4 4位，新的序列为位，新的序列为 11001100001100110000；（4 4）按模）按模2 2算法，将生成算法，将生成的新序列除以生成多项式的新序列除以生成多项式序列；序列；（5 5）将余数多项式比特序）将余数多项式比特序列加到新的序列中即得发列加到新的序列中即得发送端传送序列。送端传送序列。下面下面。1 0 0 0 0 11 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 01 0 0 1 1 1 0 0 1 1100111100111001100110接收方校验方案方案二：提取接方案二：提取接收到序列的信息收到序列的信息码元，重复发送码元，重复发送方的操作方的操作xrM(x)，再除以生成多，再除以生成多项式项式G(x),G(x),如果如果余数余数R R(x)=(x)=R(x),R(x),则证明传则证明传输正确。输正确。方案一：直接方案一：直接用接收到的序用接收到的序列除以生成多列除以生成多项式项式G(x),G(x),如如果余数果余数R R(x)(x)=0,=0,则证明传则证明传输正确。输正确。接收方接收方校验方案校验方案11生成多项式 G(x)的国际标准CRC-12 CRC-12：x x1212+x+x1111+x+x3 3+x+x2 2+x+1+x+1CRC-32 CRC-32：x x3232+x+x2626+x+x2323+x+x2222+x+x1616+x+x1212CRC-8:xCRC-8:x8 8+x+x2 2+x+1+x+1CRC-10:xCRC-10:x1010+x+x9 9+x+x5 5+x+x4 4+x+x2 2+1+1CRC-16 CRC-16：x x1616+x+x1515+x+x2 2+1+1+x+x+x111111+x+x+x101010+x+x+x8 88+x+x+x7 77+x+x+x5 55+x+x+x4 44+x+x+x2 22+x+1+x+1+x+1CRC-CCITT CRC-CCITT：x x1616+x+x1212+x+x5 5+1112差错检测差错检测 循环冗余校验码循环冗余校验码(CRC，Cyclic Redundancy check)编码编码对对于于一一个个码码长长为为n，信信息息码码元元为为k位位的的循循环环码码(n，k),其其构成形式为：构成形式为：12knk+1 k+2n位位信息码元信息码元k位位校验码元校验码元r位位13差错检测差错检测 循环冗余校验码循环冗余校验码(CRC，Cyclic Redundancy check)若生成多项式 G(x)为 r 阶(即r1位位串)，原帧为 m 位，其多项式为 M(x)，则在原帧后面添加 r 个 0，即循环左移r位，帧成为 m+r 位，相应多项式成为 xrM(x);按模2除法用 G(x)对应的位串去除对应于 xr M(x)的位串,得余数 R(x)；按模2减法(即模2加)从对应于 xr M(x)的位串中减去(加上)余数 R(x),结果即传送的带校验和的帧多项式T(x)。14例例m(x)=x9+x8+x6+x4+x3+x+1,k=10(3)1101011011.0000 10011(模二除模二除)商数：商数：1100001010 余数：余数：1110 r(x)=x3+x2+x+0所需的循环编码所需的循环编码C(x)为为C(x)=xnm(x)+r(x)=1101011011，1110设编码的信息码元为设编码的信息码元为1101011011(1)假设假设 G(x)x4+x+1 系数形成的位串为系数形成的位串为10011 则将则将m(x)x4 余数取余数取4位位(2)x4m(x)=1101011011，0000另一个例子另一个例子15多项式除法多项式除法1 1 0 1 0 1 1 0 1 1,0 0 0 01 0 0 1 11 0 0 1 11 0 0 1 11 0 0 1 11 0 1 1 01 0 0 1 11 0 1 0 01 0 0 1 11 1 1 0 1 1 0 0 0 0 1 0 1 0商数商数被除数被除数 m(x)余数余数 r(x)除数除数 P(x)1101011011.0000 10011另一个例子另一个例子16模2运算模2加法运算定义为：（对应于逻辑异或）000 011 101 110例如010100110110，列竖式计算：0 1 0 1 0 0 1 1 0 1 1 0异或计算为：11=0 00=0 10=1 01=1多项式的算术运算采用代数域理论的规则，加法没进位，减法没借位，加法和减法都等同于异或。17模2运算模2减法运算定义为：（对应于逻辑异或）000 011 101 110例如011000110101，列竖式计算：0 1 1 0 0 0 1 1 0 1 0 1异或计算为：11=0 00=0 10=1 01=118模2运算模2乘法运算定义为：000 010 100 111例如1011101100111，列竖式计算1 0 1 1 1 0 1 1 0 1 1 0 0 0 01 0 1 1 1 0 0 1 1 119模2运算模2除法运算定义为：010 111模二除法是利用模二减求余数的，余数最高位为“1”，则商“1”，否则商“0”，每商1位则余数减少一位，直到余数位数少于除数位数。1 1 1 0 1 0 1 11 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 1 1 020位运算按位与运算按位与运算 按位与运算符&是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1，否则为0。参与运算的数以补码方式出现。例如：9&5可写算式如下：00001001(9的二进制补码)&00000101(5的二进制补码)00000001 可见 9&5=1。按位或运算按位或运算按位或运算符“|”是双目运算符。其功能是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为 1时，结果位就为1。参与运算的两个数均以补码出现。例如：9|5可写算式如下：00001001|00000101 00001101(十进制为13)可见9|5=13 求反运算符求反运算符为单目运算符，具有右结合性。其功能是对参与运算的数的各二进位按位求反。例如 9的运算为：(0000000000001001)结果为：111111111111011021位运算按位异或运算按位异或运算按位异或运算符“”是双目运算符。其功能是参与运算的两数各对应的二进位相异或，当两对应的二进位相异时，结果为 1。参与运算数仍以补码出现，例如95可写成算式如下：00001001 00000101 00001100(十进制为12)左移运算左移运算左移运算符“”是双目运算符。其功能把“”左边的运算数的各二进位全部左移若干位，由“”右边的数指定移动的位数，高位丢弃，低位补 0。例如：a”是双目运算符。其功能是把“”左边的运算数的各二进位全部右移若干位，“”右边的数指定移动的位数。例如：设 a=15，a2 表示把 000001111右移为00000011(十进制3)。22CRC校验码设计实验要求：(1)、完成基本CRC校验码生成的功能；（位数不限）；(2)、尝试完成CRC-16；23CRC-16发送数据为:0X02生成多项式：0X18005余数为：0X800F24