Register

  • 点击获取
  •   

已有账号直接登录    

公告:
理解CRC校验算法
首页 > IT计算机 > 计算机知识    作者:RainFly   2015年10月18日 8:43 星期日   热度:2509°   字号:   评论:3    
时间:2015-10-18 8:43   热度:2509°  评论:3 条 

c995d143ad4bd1132ebc0c1758afa40f4bfb05a5.jpg

   循环校验码(CRC码):是数据通信领域中最常用的一种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。

    被处理的数据块可以看作是一个二进制多项式,例如,10110101可以看作是2^7+2^5+2^4+2^2+2^0,多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进,错位,和逻辑异或运算一致。 

采用CRC校验时,发送方和接收方用同一个生成多项式gx,并且gx)的首位和最后一位的系数必须为1CRC的处理方法是:发送方以gx)去除tx),得到余数作为CRC校验码。校验时,以计算的校正结果是否为0为据,判断数据帧是否出错。 

CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于kkgx)的阶数)的突发错误。所以CRC的生成多项式的阶数越高,那么误判的概率就越小。

CCITT建议:2048 kbit/sPCM基群设备采用CRC-4方案,使用的CRC校验采用16CRC校验。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中,使用CRC-16gx)的位数越高,检错能力就越强。由于CRC-32的可靠性,把CRC-32用于重要数据传输十分合适,所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片(如MC6582Intel8273Z80-SIO)内,都采用了CRC校验码进行差错控制;以太网卡芯片、MPEG解码芯片中,也采用CRC-32进行差错控制。

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

(转自http://www.equn.com/forum/viewthread.php?tid=5470&sid=3rrqVomR)    

 

CRC校验码的基本思想是利用线性编码理论, 在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的监督码(既CRC码)r位,并附在信息后边,构成一个新的二进制码序列数共(k+r)位,最后发送出去。在接收端,则根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。

    在数据存储和数据通讯领域,CRC无处不在:著名的通讯协议X.25FCS(帧检错序列)采用的是CRC. CCITTARJLHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIFTIFF等也都用CRC作为检错手段。

    CRC的本质是模-2除法的余数,采用的除数不同,CRC的类型也就不一样。通常,CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式有CRC16,CRC32.

    以CRC16为例,16位的CRC码产生的规则是先将要发送的二进制序列数左移16位(既乘以2^16)后,再除以一个多项式,最后所得到的余数既是CRC码,如下式所示,其中K(X)表示n位的二进制序列数,G(X)为多项式,Q(X)为整数,R(X)是余数(既CRC码)。

K(X)>>16=G(x)Q(x)+R(x)

    求CRC码所采用模2加减运算法则,既是不带进位和借位的按位加减,这种加减运算实际上就是逻辑上的异或运算,加法和减法等价,乘法和除法运算与普通代数式的乘除法运算是一样,符合同样的规律。生成CRC码的多项式如下,其中CRC-16CRC-CCITT产生16位的CRC码,而CRC-32则产生的是32位的CRC

    接收方将接收到的二进制序列数(包括信息码和CRC码)除以多项式,如果余数为0,则说明传输中无错误发生,否则说明传输有误,关于其原理这里不再多述。用软件计算CRC码时,接收方可以将接收到的信息码求CRC码,比较结果和接收到的CRC码是否相同。

    CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中,使用CCITT-16CRC16,其生成多项式为G(x)=x16+x12+x5+1, CRC-32的生成多项式为G(x)=x32+x26+x23+x22+x16+x11+x10+x16+x8+x7+x5+x4+x2+x+1

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

CRC校验码的算法分析

 

CRC校验码的编码方法是用待发送的二进制数据tx)除以生成多项式gx),将最后的余数作为CRC校验码。其实现步骤如下:

设待发送的数据块是m位的二进制多项式tx),生成多项式为r阶的gx)。在数据块的末尾添加r0,数据块的长度增加到m+r位,对应的二进制多项式为 。

用生成多项式gx)去除 ,求得余数为阶数为r-1的二进制多项式yx)。此二进制多项式yx)就是tx)经过生成多项式gx)编码的CRC校验码。

用 以模2的方式减去yx),得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。

CRC的编码规则可以看出,CRC编码实际上是将代发送的m位二进制多项式tx)转换成了可以被gx)除尽的m+r位二进制多项式,所以解码时可以用接受到的数据去除gx),如果余数位零,则表示传输过程没有错误;如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时可以看做是由tx)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到的就是原始数据。

为了更清楚的了解CRC校验码的编码过程,下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32CRC-16CCITTCRC-4的编码过程基本一致,只有位数和生成多项式不一样。为了叙述简单,用一个CRC-4编码的例子来说明CRC的编码过程。

设待发送的数据tx)为12位的二进制数据100100011100CRC-4的生成多项式为gx,阶数r4,即10011。首先在tx)的末尾添加40构成 ,数据块就成了1001000111000000。然后用gx)去除,不用管商是多少,只需要求得余数yx)。下表为给出了除法过程。

除数次数 被除数/ gx/结果     余数 

0  1 001000111000000 100111000000 

 1 0011 

 0 000100111000000 

1  1 00111000000   1000000 

 1 0011  

 0 00001000000 

2  1 000000 1100 

 1 0011 

 0 001100 

 

从上面表中可以看出,CRC编码实际上是一个循环移位的模2运算。对CRC-4,我们假设有一个5 bits的寄存器,通过反复的移位和进行CRC的除法,那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述:

//reg是一个5 bits的寄存器

reg中的值置0. 

把原始的数据后添加r0. 

While (数据未处理完

Begin 

If (reg首位是1) 

reg = reg XOR 0011. 

reg中的值左移一位,读入一个新的数据并置于register0 bit的位置。 

End

reg的后四位就是我们所要求的余数。

这种算法简单,容易实现,对任意长度生成多项式的Gx)都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话,这种方法就不太适合了。它一次只能处理一位数据,效率太低。为了提高处理效率,可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理,所以一次处理8位比较合适。

为了对优化后的算法有一种直观的了解,先将上面的算法换个角度理解一下。在上面例子中,可以将编码过程看作如下过程:

由于最后只需要余数,所以我们只看后四位。构造一个四位的寄存器reg,初值为0,数据依次移入reg0reg0位),同时reg3的数据移出 reg。有上面的算法可以知道,只有当移出的数据为1时,reg才和gx)进行XOR运算;移出的数据为0时,reg不与gx)进行XOR运算,相当与和0000进行XOR运算。就是说,reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit,所以有 种选择。上述算法可以描述如下,

//reg是一个4 bits的寄存器

初始化t[]={0011,0000}

reg中的值置0. 

把原始的数据后添加r0. 

While (数据未处理完

Begin 

reg中的值左移一位,读入一个新的数据并置于register0 bit的位置。

reg = reg XOR t[移出的位]

End

上面算法是以bit为单位进行处理的,可以将上述算法扩展到8位,即以Byte为单位进行处理,即CRC-32。构造一个四个Byte的寄存器reg,初值为0x00000000,数据依次移入reg0reg0字节,以下类似),同时reg3的数据移出reg。用上面的算法类推可知,移出的数据字节决定reg和什么样的数据进行XOR。由于有8bit,所以有 种选择。上述算法可以描述如下:

//reg是一个4 Byte的寄存器

初始化t[]{…}//共有 =256

reg中的值置0. 

把原始的数据后添加r/80字节

While (数据未处理完

Begin 

reg中的值左移一个字节,读入一个新的字节并置于reg的第0byte的位置。

reg = reg XOR t[移出的字节]

End

算法的依据和多项式除法性质有关。如果一个m位的多项式tx)除以一个r阶的生成多项式gx), ,将每一位(0=<k<m)提出来,在后面不足r0后,单独去除gx),得到的余式位 。则将后得到的就是tx)由生成多项式gx)得到的余式。对于CRC-32,可以将每个字节在后面补上320后与生成多项式进行运算,得到余式和此字节唯一对应,这个余式就是上面算法种t[]中的值,由于一个字节有8位,所以t[]共有=256项。多项式运算性质可以参见参考文献[1]。这种算法每次处理一个字节,通过查表法进行运算,大大提高了处理速度,故为大多数应用所采用

阅读全文(11274) | 评论(7) | 推荐(56)

本文来自:我爱研发网(52RD.com) - R&D大本营

详细出处:http://www.52rd.com/Blog/Detail_RD.Blog_zx_zx_13124.html

循环校验码(CRC码):是数据通信领域中最常用的一种差错校验码,其特征是信息字段和      


被处理的数据块可以看作是一个二进制多项式,例如,10110101可以看作是2^7+2^5+2^4+2^2+2^0,多项式乘除法运算过程与普通代数多项式的乘除法相同。多项式的加减法运算以2为模,加减时不进,错位,和逻辑异或运算一致。 

采用CRC校验时,发送方和接收方用同一个生成多项式gx,并且gx)的首位和最后一位的系数必须为1CRC的处理方法是:发送方以gx)去除tx),得到余数作为CRC校验码。校验时,以计算的校正结果是否为0为据,判断数据帧是否出错。 

CRC校验可以100%地检测出所有奇数个随机错误和长度小于等于kkgx)的阶数)的突发错误。所以CRC的生成多项式的阶数越高,那么误判的概率就越小。

CCITT建议:2048 kbit/sPCM基群设备采用CRC-4方案,使用的CRC校验采用16CRC校验。在IBM的同步数据链路控制规程SDLC的帧校验序列FCS中,使用CRC-16gx)的位数越高,检错能力就越强。由于CRC-32的可靠性,把CRC-32用于重要数据传输十分合适,所以在通信、计算机等领域运用十分广泛。在一些UART通信控制芯片(如MC6582Intel8273Z80-SIO)内,都采用了CRC校验码进行差错控制;以太网卡芯片、MPEG解码芯片中,也采用CRC-32进行差错控制。

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

(转自http://www.equn.com/forum/viewthread.php?tid=5470&sid=3rrqVomR)    

 

CRC校验码的基本思想是利用线性编码理论, 在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的监督码(既CRC码)r位,并附在信息后边,构成一个新的二进制码序列数共(k+r)位,最后发送出去。在接收端,则根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。

    在数据存储和数据通讯领域,CRC无处不在:著名的通讯协议X.25FCS(帧检错序列)采用的是CRC. CCITTARJLHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIFTIFF等也都用CRC作为检错手段。

    CRC的本质是模-2除法的余数,采用的除数不同,CRC的类型也就不一样。通常,CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式有CRC16,CRC32.

    以CRC16为例,16位的CRC码产生的规则是先将要发送的二进制序列数左移16位(既乘以2^16)后,再除以一个多项式,最后所得到的余数既是CRC码,如下式所示,其中K(X)表示n位的二进制序列数,G(X)为多项式,Q(X)为整数,R(X)是余数(既CRC码)。

K(X)>>16=G(x)Q(x)+R(x)

    求CRC码所采用模2加减运算法则,既是不带进位和借位的按位加减,这种加减运算实际上就是逻辑上的异或运算,加法和减法等价,乘法和除法运算与普通代数式的乘除法运算是一样,符合同样的规律。生成CRC码的多项式如下,其中CRC-16CRC-CCITT产生16位的CRC码,而CRC-32则产生的是32位的CRC

    接收方将接收到的二进制序列数(包括信息码和CRC码)除以多项式,如果余数为0,则说明传输中无错误发生,否则说明传输有误,关于其原理这里不再多述。用软件计算CRC码时,接收方可以将接收到的信息码求CRC码,比较结果和接收到的CRC码是否相同。

    CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中,使用CCITT-16CRC16,其生成多项式为G(x)=x16+x12+x5+1, CRC-32的生成多项式为G(x)=x32+x26+x23+x22+x16+x11+x10+x16+x8+x7+x5+x4+x2+x+1

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

CRC校验码的算法分析

 

CRC校验码的编码方法是用待发送的二进制数据tx)除以生成多项式gx),将最后的余数作为CRC校验码。其实现步骤如下:

设待发送的数据块是m位的二进制多项式tx),生成多项式为r阶的gx)。在数据块的末尾添加r0,数据块的长度增加到m+r位,对应的二进制多项式为 。

用生成多项式gx)去除 ,求得余数为阶数为r-1的二进制多项式yx)。此二进制多项式yx)就是tx)经过生成多项式gx)编码的CRC校验码。

用 以模2的方式减去yx),得到二进制多项式 。 就是包含了CRC校验码的待发送字符串。

CRC的编码规则可以看出,CRC编码实际上是将代发送的m位二进制多项式tx)转换成了可以被gx)除尽的m+r位二进制多项式,所以解码时可以用接受到的数据去除gx),如果余数位零,则表示传输过程没有错误;如果余数不为零,则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时可以看做是由tx)和CRC校验码的组合,所以解码时将接收到的二进制数据去掉尾部的r位数据,得到的就是原始数据。

为了更清楚的了解CRC校验码的编码过程,下面用一个简单的例子来说明CRC校验码的编码过程。由于CRC-32CRC-16CCITTCRC-4的编码过程基本一致,只有位数和生成多项式不一样。为了叙述简单,用一个CRC-4编码的例子来说明CRC的编码过程。

设待发送的数据tx)为12位的二进制数据100100011100CRC-4的生成多项式为gx,阶数r4,即10011。首先在tx)的末尾添加40构成 ,数据块就成了1001000111000000。然后用gx)去除,不用管商是多少,只需要求得余数yx)。下表为给出了除法过程。

除数次数 被除数/ gx/结果     余数 

0  1 001000111000000 100111000000 

 1 0011 

 0 000100111000000 

1  1 00111000000   1000000 

 1 0011  

 0 00001000000 

2  1 000000 1100 

 1 0011 

 0 001100 

 

从上面表中可以看出,CRC编码实际上是一个循环移位的模2运算。对CRC-4,我们假设有一个5 bits的寄存器,通过反复的移位和进行CRC的除法,那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述:

//reg是一个5 bits的寄存器

reg中的值置0. 

把原始的数据后添加r0. 

While (数据未处理完

Begin 

If (reg首位是1) 

reg = reg XOR 0011. 

reg中的值左移一位,读入一个新的数据并置于register0 bit的位置。 

End

reg的后四位就是我们所要求的余数。

这种算法简单,容易实现,对任意长度生成多项式的Gx)都适用。在发送的数据不长的情况下可以使用。但是如果发送的数据块很长的话,这种方法就不太适合了。它一次只能处理一位数据,效率太低。为了提高处理效率,可以一次处理4位、8位、16位、32位。由于处理器的结构基本上都支持8位数据的处理,所以一次处理8位比较合适。

为了对优化后的算法有一种直观的了解,先将上面的算法换个角度理解一下。在上面例子中,可以将编码过程看作如下过程:

由于最后只需要余数,所以我们只看后四位。构造一个四位的寄存器reg,初值为0,数据依次移入reg0reg0位),同时reg3的数据移出 reg。有上面的算法可以知道,只有当移出的数据为1时,reg才和gx)进行XOR运算;移出的数据为0时,reg不与gx)进行XOR运算,相当与和0000进行XOR运算。就是说,reg和什么样的数据进行XOR移出的数据决定。由于只有一个bit,所以有 种选择。上述算法可以描述如下,

//reg是一个4 bits的寄存器

初始化t[]={0011,0000}

reg中的值置0. 

把原始的数据后添加r0. 

While (数据未处理完

Begin 

reg中的值左移一位,读入一个新的数据并置于register0 bit的位置。

reg = reg XOR t[移出的位]

End

上面算法是以bit为单位进行处理的,可以将上述算法扩展到8位,即以Byte为单位进行处理,即CRC-32。构造一个四个Byte的寄存器reg,初值为0x00000000,数据依次移入reg0reg0字节,以下类似),同时reg3的数据移出reg。用上面的算法类推可知,移出的数据字节决定reg和什么样的数据进行XOR。由于有8bit,所以有 种选择。上述算法可以描述如下:

//reg是一个4 Byte的寄存器

初始化t[]{…}//共有 =256

reg中的值置0. 

把原始的数据后添加r/80字节

While (数据未处理完

Begin 

reg中的值左移一个字节,读入一个新的字节并置于reg的第0byte的位置。

reg = reg XOR t[移出的字节]

End

算法的依据和多项式除法性质有关。如果一个m位的多项式tx)除以一个r阶的生成多项式gx), ,将每一位(0=<k<m)提出来,在后面不足r0后,单独去除gx),得到的余式位 。则将后得到的就是tx)由生成多项式gx)得到的余式。对于CRC-32,可以将每个字节在后面补上320后与生成多项式进行运算,得到余式和此字节唯一对应,这个余式就是上面算法种t[]中的值,由于一个字节有8位,所以t[]共有=256项。多项式运算性质可以参见参考文献[1]。这种算法每次处理一个字节,通过查表法进行运算,大大提高了处理速度,故为大多数应用所采用

详细出处:http://www.52rd.com/Blog/Detail_RD.Blog_zx_zx_13124.html

 您阅读这篇文章共花了:  
捐赠支持:如果觉得这篇文章对您有帮助,请"扫一扫"鼓励作者!
 本文无需标签!
二维码加载中...
本文作者:RainFly      文章标题: 理解CRC校验算法
本文地址:http://www.rainfly.cn/?post=152
版权声明:若无注明,本文皆为“雨夜轩”原创,转载请保留文章出处。

已有3条吐槽

每天签到赚10元  Google Chrome 31.0.1650.63 Google Chrome 31.0.1650.63 Windows 7 Windows 7  河北省石家庄市 电信 2015-10-20 21:22 地板
哈哈
大学问社区  Google Chrome 42.0.2311.154 Google Chrome 42.0.2311.154 Windows 8.1 Windows 8.1  陕西省西安市 西电大学 2015-10-19 19:01 板凳
来学习学习 赞
安安博客  Firefox 41.0 Firefox 41.0 Windows 7 Windows 7  广东省深圳市 联通 2015-10-18 12:10 沙发
安安博客来访

QQ游客评论

返回顶部    首页    捐赠支持    手气不错    友情链接    关于我们    站长工具    站长介绍    手机版本    后台登陆   
版权所有:雨夜轩    站长:RainFly    特别鸣谢   文章归档   皖ICP备15003600号-1   百度统计
Copyright©2015雨夜轩 Powered by emlog强力驱动 七牛CDN全球加速 360站长联盟安全认证 中国博客联盟荣誉成员 可信赖网站 谷歌地图   百度地图   
页面加载耗时:0.071秒 数据库查询次数:20次
背景设置
-->