精华内容
下载资源
问答
  • CRC的全称Cyclic Redundancy Check,中文名称差错控制理论是在...利用CRC进行检错的过程可简单描述:在发送端根据要传送的k位二进制序列,以一定的规则产生一个校验用的r位监督 (CRC),附在原始信息后边...

    5d1201e9a455f446206af216ecb02ab8.png

    CRC的全称为Cyclic Redundancy Check,中文名称为

    差错控制理论是在代数理论基础上建立起来的。这里我们着于介绍CRC的算法与实现,对原理只能捎带说明一下。若需要进一步了解线性码、分组码、循环码、纠错编码等方面的原理,可以阅读有关资料。

    利用CRC进行检错的过程可简单描述为:在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的r位监督 码(CRC码),附在原始信息后边,构成一个新的二进制码序列数共kr位,然后发送出去。在接收端,根据信息码和CRC码之间所遵循的规则进行检验,以 确定传送中是否出错。这个规则,在差错控制理论中称为“生成多项式”。

    1 代数学的一般性算法

    在代数编码理论中,将一个码组表示为一个多项式,码组中各码元当作多项式的系数。例如 1100101 表示为

    1·x61·x50·x40·x31·x20·x1,即 x6x5x21。

    设编码前的原始信息多项式为P(x),P(x)的最高幂次加1等于k;生成多项式为G(x),G(x)的最高幂次等于r;CRC多项式为R(x);编码后的带CRC的信息多项式为T(x)。

    发送方编码方法:将P(x)乘以xr(即对应的二进制码序列左移r位),再除以G(x),所得余式即为R(x)。用公式表示为

    T(x)=xrP(x)R(x)

    接收方解码方法:将T(x)除以G(x),如果余数为0,则说明传输中无错误发生,否则说明传输有误。

    举例来说,设信息码为1100,生成多项式为1011,即P(x)=x3x2,G(x)=x3x1,计算CRC的过程为

    即 R(x)=x。注意到G(x)最高幂次r=3,得出CRC为010。

    如果用竖式除法,计算过程为

    因此,T(x)=(x6x5)(x)=x6x5x, 即 1100000010=1100010

    如果传输无误,

    无余式。回头看一下上面的竖式除法,如果被除数是1100010,显然在商第三个1时,就能除尽。

    上述推算过程,有助于我们理解CRC的概念。但直接编程来实现上面的算法,不仅繁琐,效率也不高。实际上在工程中不会直接这样去计算和验证CRC。

    下表中列出了一些见于标准的CRC资料:

    ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS

    ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS

    4.CRC算法的实现

    ---------------

    要用程序实现CRC算法,考虑对第2节的长除法做一下变换,依然是M = 11100110,G = 1011,

    其系数r为3。

    11001100

    ------------------------

    1011 )11100110000

    1011.......

    ----.......

    1010......

    1011......

    ----......

    1110...

    1011...

    ------...

    1010..

    1011..

    -------

    100

    本文来自电脑杂谈,转载请注明本文网址:

    http://www.pc-fly.com/a/tongxinshuyu/article-38614-1.html

    展开全文
  • 循环冗余校验在一些传输协议中,发送端并不指出消息长度,而是采用结束标志,考虑以下几种差错:1)在消息之前,增加1个或多个0字节;2)消息以1个或多个连续的0字节开始,丢掉1个或多个0;3)在消息(包括校验码)之后,...

    接收端对收到的len 2字节执行do_crc,如果没有差错发生则结果应为0。循环冗余校验

    在一些传输协议中,发送端并不指出消息长度,而是采用结束标志,考虑以下几种差错:

    1)在消息之前,增加1个或多个0字节;

    2)消息以1个或多个连续的0字节开始,丢掉1个或多个0;

    3)在消息(包括校验码)之后,增加1个或多个0字节;

    4)消息(包括校验码)以1个或多个连续的0字节结尾,丢掉1个或多个0;

    显然,这几种差错都检测不出来,其原因就是如果寄存器为0,处理0消息字节(或位),寄存器不变。为了解决前2个问题,只需寄存器的初非0即可,对do_crc作以下改进:

    unsigned short do_crc(unsigned short reg_init, unsigned char *message, unsigned int len)

    {

    unsigned short crc_reg = reg_init;

    while (len--)

    crc_reg = (crc_reg >> 8) ^ crc16_ccitt_table[(crc_reg ^ *message) & 0xff];

    return crc_reg;

    }

    在CRC16-CCITT标准中reg_init = 0xffff,为了解决后2个问题,在CRC16-CCITT标准中将计算出的校验码与0xffff进行异或,即:

    unsigned short code = do_crc(0xffff, message, len);

    code ^= 0xffff;

    message[len] = code & 0x00ff;

    message[len 1] = (code >> 8) & 0x00ff;

    显然,现在接收端对收到的所有字节执行do_crc,如果没有差错发生则结果应为某一常GOOD_CRC。其满足以下关系:

    unsigned char p[]= {0xff, 0xff};

    GOOD_CRC = do_crc(0, p, 2);

    其结果为GOOD_CRC = 0xf0b8。

    在同一程序中验证如下(放在main函数中可试验):

    unsigned char p[]= {0xa0,0xb0,0xff, 0xff};

    unsigned short crc;

    crc= do_crc(0xffff, p, 2); //计算前两位的CRC码

    crc^=0xffff; //对其取反

    p[2]=crc&0x00ff; //将计算的CRC码加到信息序列后面

    p[3]=crc>>8&0x00ff;

    printf("p[2]=%x,p3=%x\n",p[2],p[3]);

    crc=do_crc(0xffff,p,4); //对信息码+CRC码共同计算得出CRC=0xf0b8

    printf("crc is %x\n",crc);

    假设发送的信息是p[0],p[1];低位先发,对其计算的CRC加到信息码后面

    然后对信息码+CRC码共同计算CRC,此时应该是常数0xf0b8。不管信息码如何变化,内容和长度都可变,只要把计算的CRC码加进去一起计算CRC,就应该是得该常数GOOD_CRC。

    参考文献

    --------

    [1] Ross N. Williams,"A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS",Version 3,

    ,August 1993

    [2] Simpson, W., Editor, "PPP in HDLC Framing",RFC 1549, December 1993

    [3] P. E. Boudreau,W. C. Bergman and D. R. lrvin,"Performance of a cyclic redundancy check and its interaction with a data scrambler",IBM J. RES. DEVELOP.,VOL.38 NO.6,November 1994

    本文来自电脑杂谈,转载请注明本文网址:

    http://www.pc-fly.com/a/tongxinshuyu/article-38614-6.html

    展开全文
  • 校验码(循环冗余校验码) 循环冗余校验码,又称CRC码。它利用生成多项式来k个数据位产生r个校验位来进行编码。其编码长度k+r。

    校验码(循环冗余校验码)

    循环冗余校验码,又称CRC码。它利用生成多项式来为k个数据位产生r个校验位来进行编码。其编码长度为k+r。

    循环冗余校验码由两部分组成,左边为信息码(数据),右边为校验码,如下图
    循环冗余校验码的组成
    若信息码占k位,则校验码就占n-k位,其中,n为CRC码的字长,所以又称为(n,k)码。校验码位数越多,校验能力越强。

    CRC编码的计算
    采用的是模2运算,其加减运算的规则是按位运算,不发生借位和进位。
    下面以实例解释:
    假设使用的生成多项式是G(X)=X3+X+1。4位的原始报文为1010,求编码后的报文。
    解:
    1、将生成多项式G(X)=X3+X+1转换成对应的二进制除数1011。
    转换方式为Xi中的i对应二进制数的指数2^i。如上式X3+X+1可解为
    二进制除数的计算
    2、生成多项式有4位(R+1)。
    注意:4位的生成多项式计算所得的校验码为3位,R为校验码位数(校验码的位数=二进制除数位数-1)。

    要把原始报文C(X)=1010左移3位(即校验码的位数),低位补0,变成1010 000,即被除数

    3、用生成多项式对应的二进制除数对左移3位后的原始报文(即1010 000)进行模2除(高位对齐),相当于按位异或得到的余位011,所以最终编码为:1010 011。如下图
    校验位r的计算
    所得的商没有意义,余数保留r位(即校验码的位数)。然后将原数据与校验码(即上面所求得的余数)拼接在一起,就构成了一个CRC码。

    展开全文
  • 循环冗余校验码

    2021-05-08 20:28:02
    循环冗余校验码 基本思想 设计一个数 如8 被4整除余数0,如数据7不能被4整除余数3 数据发送、接受约定一个“除数” K个信息位+R个校验位作为“被除数”,添加校验位后保证除法余数位0 收到数据后,进行除法检查...

    循环冗余校验码

    基本思想

    设计一个数 如8 被4整除余数0,如数据7不能被4整除余数3

    数据发送、接受约定一个“除数”

    K个信息位+R个校验位作为“被除数”,添加校验位后保证除法余数位0

    收到数据后,进行除法检查余数是否为0

    题目:设生成多项式为G(X)=x3+x2+1,信息码为101001,求对应的CRC码

    1. 转换二进制系数

    1101这个为除数

    K=信息码的长度=6,R=生成多项式最高次幂=3——》校验码位数N=K+R=9

    1. 移位 计算机处理实现:信息码左移R位,低位补0

    1. 对移位后的信息码进行模2除法,产生余数

      模2除运算理解:被除数最高位1则商1,之后模2减,模2减和模2加效果一样(异或运算)最终得到一个余数(位数只比除数少一位)

      得到的信息位+余数得到CRC

    2. 检错和纠错

      接受到的数据用1101进行模2除余数为000,余数不为0则出错

    总结

    循环冗余校验码有一定的纠错功能

    K个信息位,R个校验位,若生成多项式选择得当,且2R>=K+R+1,则CRC码可纠正1位错

    特点

    可检测出所有奇数个错误

    可检测出所有双比特的错误

    可检测出所有小于等于校验位长度的连续错误

    展开全文
  • CRC循环冗余校验码

    2017-07-10 16:43:19
    2》循环冗余校验码又称多项式编码,其思想是将位串看成是系数0或1的多项式。CRC校验要保护的单位是数据块(也就是传输过程中的有效载荷),数据块的大小不是固定的可根据实际情况确定,每一个数据块均被看做是一...
  • 四、循环冗余校验码  在串行传送(磁盘、通讯)中,广泛采用循环冗余校验码(CRC)。...循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度N位,因此,这种编码又叫
  • 文章目录一、奇偶校验码二、海明码三、循环冗余校验码 一、奇偶校验码 特点:能检错,但是不能纠错。 码距: 一个编码系统中任意两个合法编码(码字)之间不同的二进数位(bit)数叫这两个码字的码距,而整个编码...
  • 设生成多项式G(x)= x^3 + x^2+1,信息码为101001,求对应的CRC码,即循环冗余校验码 解:
  • 模2加法1+1=0, 0+1=1, 1+0=1, 0+0=0模2减法1-1=0,...模2乘法基于模2加法模运算举例CRC校验码的位数余数的位数一定要是比除数位数只能少一位,哪怕前面位是0,甚至是全为0(附带好整除时)余数 是指 CRC校验码除数 是指...
  • CRC校验(循环冗余校验码

    千次阅读 2017-06-21 14:23:53
    一、概念: CRC即循环冗余校验码:是数据通信领域中最常用的一种查错校验码,其特征是信息字段和校验字段的长度... 循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度N位,因此,这
  • 细说循环冗余校验码

    万次阅读 多人点赞 2017-07-12 20:01:08
    初识循环冗余校验码: 为了保证数据传输的可靠性,在计算机网络传输数据时,必须采用各种差错检验措施,目前广泛使用的是循环冗余(CRC)检验的检错技术。 CRC检验原理: 在发送端,先把数据划分组,假定每个组...
  • 由此可知,循环冗余校验码是由两部分组成的,左边信息码(数据),右边校验码。若信息码占k位,则校验码占n-k位。其中,nCRC码的字长,所以CRC码又称为(n,k)码。校验码是由信息产生的,校验码位数越长,该...
  • 循环冗余校验码(CRC)的基本原理是:在K位信息码后再拼接R位的校验码,整个编码长度N位,因此,这种编码又叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂N-K=R的多项式G(x)。根据G(x)可以...
  • 循环冗余校验码CRC

    2017-07-02 19:21:37
    CRC:循环冗余校验码 CRC是数据通信领域中最常用的一种差错校验码,其特征信息是信息字段和校验字段的长度可以任意选定。CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列),从而...
  • 循环冗余校验码(CRC)

    千次阅读 2017-06-12 17:43:35
    循环冗余校验码(CRC)的基本原理在K位信息码后再拼接R位的校验码,整个编码长度N位,因此,这种编码也叫(N,K)码。对于一个给定的(N,K)码,可以证明存在一个最高次幂N-K=R的多项式G(x)。根据G(x)可以生成K...
  • 奇偶校验码,海明校验码 和 循环冗余校验码(CRC)   奇偶校验码是 奇校验码 和 偶校验码 的统称. 它们都是通过在要校验的编码上加一位校验位组成. 如果是 奇校验 加上校验位后,编码中1的个数 奇数...
  • 奇偶校验 奇偶校验包含奇校验和偶校验两种...有效信息(被校验的信息)部分可能是奇性(“1”的个数奇数)的,也可能是偶性的,所以奇、偶两种校验都只需配一个校验码,就可以使整个校验码满足指定的奇偶性要求。...
  • 循环冗余校验码的思想: 例题: 注:产生的余数R位(比除数少一位)二进制数。 注:这里与海明码不同,余数转换成十进制后的数与出错位没有必然的联系。 ——————————————————————————...
  • 奇偶校验码是 奇校验码 和 偶校验码 的统称. 它们都是通过在要校验的编码上加一位校验位组成. 如果是 奇校验 加上校验位后,编码中1的个数 奇数个 如果是 偶校验 加上校验位后,编码中1的个数 偶数个 水平奇偶校验...
  • 一、什么要使用校验码? 数据在计算机系统内加工、存取和传送的过程中可能会产生错误。为了减少和避免这类错误,引入了数据校验码。数据校验码是一种常用的带有发现某些错误,甚至带有一定自动改错能力的数据编码...
  • CRC循环冗余校验码总结

    万次阅读 2015-04-28 15:53:45
    先在此说明下什么是CRC:循环冗余码校验 英文名称Cyclical Redundancy Check,简称CRC,它是利用除法及余数的原理来作错误侦测(Error Detecting)的。实际应用时,发送装置计算出CRC值并随数据一同发送给接收装置...
  • 循环冗余校验码中冗余码的计算

    千次阅读 2019-06-24 22:55:04
    接收方:使用相同的生成进行校验:接收到的字段/生成(二进制除法),如果能够除尽,则正确 除法没有数学上的含义,而是采用计算机的模二除法,即除数和被除数做异或运算。进行异或运算时除数和被除数最高位对齐,...
  • 循环冗余校验码原理

    千次阅读 2014-07-16 10:04:05
    来自 循环冗余校验码原理  CRC校验采用多项式编码方法,如一个8位二进制数(B7B6B5B4B3B2B1B0)可以用7阶二进制码多项式B7X7+B6X6+B5X5+B4X4+B3X3+B2X2+B1X1+B0X0表示。   例如11000001可表示   1X7+1X6+0X...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 614
精华内容 245
关键字:

循环冗余校验码为