tag 标签: 循环冗余校验

相关博文
  • 热度 22
    2013-6-9 15:40
    2241 次阅读|
    3 个评论
    CRC 校验:从原理到实现   CRC 校验,就是循环冗余校验, Cyclic Redundancy Check ,是数据通信领域中最常用的一种差错校验码,用于保障数据的完整性。其特征是信息字段和校验字段的长度可以任意选定,也就是说,不管信息序列(明文序列, plaintext 或者 message )有多长,只要选定某一种 CRC 校验,最后得到的校验序列(校验和)的长度是一定的。   通常使用的 CRC 校验有 CRC-8 、 CRC-12 , CRC-16 , CRC-32 ,后面的数字就表示校验之后校验字段的长度(以 bit 记)。   1、 CRC校验的基本原理——多项式求余运算   所有的 CRC 校验都是基于以下 几个 等式 ,但是发送端和接收端的工作机制的不同会使得下面的等式有一些细微变化。为了便于说明,我们选定这种机制:发送端将校验序列附在明文序列之后发出去,接收端对明文序列和校验序列做校验,结果为 0 说明校验正确 :   发送端, 或者 接收端: 或者 M 是 明文序列的 多项式, R 是校验 序列的 多项式, r 是校验 序列 多项式的最高次幂(也就是校验字段的长度, CRC-32 对应的 r=32 ,依次类推)。 G 是生成 (Generator) 多项式 , 对某一种确定的 CRC 校验,其 G 是固定的。   发送端 用 G 对 M 做模运算(求余运算),得到校验序列 R ,将 R 附加到明文序列 M 之后传给接收端;   接收端收到 M+R 的序列后么,也用 G 对 M+R 做模运算,将公式 1 或 2 带入 3 或 4 ,得出结论:如果的到结果为 0 ,说明序列正确,数据完整。   所以, CRC 校验最根本的就是用生成多项式对明文多项式(或者是明文 + 校验序列的多项式)做除法求余计算,而它的实现方法就是用线性反馈移位寄存器( Liner Feedback Shift Register , LFSR )实现多项式的求余计算。   2、 LFSR和多项式取模运算的关系   为什么用 LFSR 就能实现 CRC 校验 / 多项式求余运算呢?我们首先来看一个简单的 LFSR ,每经过一个时钟周期, 3bit 的移位寄存器都会按照异或逻辑由低到高做一次值的更新,左侧串行输入多项式序列 M 。     我们假设寄存器的初始值为( R2 , R1 , R0 ) = ( 0 , 0 , 1 ),输入序列一直为 0 ,则寄存器的值( R2 , R1 , R0 )会按照如下状态机跳转,遍历除 000 外的所有 7 个状态 ,相当于一个状态机 。 再假设 M 输入在时间上展开不是全 0 的,而是以 1 开始后面有若干个 0 ,就对应了不同的多项式序列 x^n ,寄存器剩余的值 就是用 x^3+x+1 除以 多项式序列对应的余数序列。   M 在时间上展开的值 多项式序列 M(x) 寄存器最后的值 / 余数 R(x) 1 1 1 10 x x 100 x^2 x^2 1000 x^3 x+1 10000 x^4 x^2+1 100000 x^5 x^2+x+1 1000000 x^6 x^2+1   如果将这张表延续下去,会看到周期性的效果: x^7 对应的 R(x) 为 1 ,依次类推, x^n 对应的 R(x) 都可以用这张表中的内容来表示,有公式:   又根据伽罗华域的性质, GF(2^m) 域的本原多项式为 P(x) = x^8 + x^4 +x^3 + x^2 + 1 ,将 a 作为 P(x) 的根,则有 a^8=a^4+a^3+a^2+1 ,所以任何多项式 M(x) 都可以用 x^n ( 0=n=255 )来表示,如下表所示:     所以任何 M(x) 的余数 R(x) 都可以 x^0~x^7 的余数准确的表示,所以用 LFSR 可以实现多项式的取模运算。   举个例子来说明,对 CRC16 而言,其生成多项式 G(x)=x^16+x^15+x^2+1 。如图所示,这是一个根据生成多项式设计的 CRC16 校验逻辑,由初始值为全 0 的 16 位以为寄存器和由 G(x) 确定的异或逻辑组成(只有一个输入的异或门默认为另一个输入为 0 ,也就是输出等于输入)。每经过一个时钟周期,移位寄存器都会按照异或逻辑由低到高做一次值的更新,按照图中所示,用 X 表示输入的值,用 R 表示当前的寄存器值, R ’ 表示前一时钟的寄存器值,有:   R =X^R ’ ^R ’ , R =R ’ ; R = X^R ’ ^R ’ ; R =R ’ ; R = X^R ’ ;
相关资源
  • 所需E币: 0
    时间: 2021-3-18 16:52
    大小: 278.84KB
    上传者: Argent
    FPGA是一个技术密集型的行业,没有坚实的技术功底,很难形成有竞争力的产品。从技术上来看FPGA未来的发展,至少在几年内还是遵循摩尔定律的规则,工艺不断升级,目前xilinx16nm工艺的FPGA已经成熟商用,xilinx下一代产品会升级到7nm,重点应该还是瞄准通信和可能出现的新兴行业如大数据处理等。有这方面需求的网友不妨来共同学习探讨。
  • 所需E币: 0
    时间: 2020-12-22 13:38
    大小: 270.15KB
    上传者: samewell
    ADI_循环冗余校验确保正确的数据通信
  • 所需E币: 0
    时间: 2020-12-22 13:38
    大小: 270.29KB
    上传者: samewell
    ADI_循环冗余校验确保正确的数据通信
  • 所需E币: 5
    时间: 2020-6-19 19:28
    大小: 280.52KB
    上传者: Goodluck2020
    循环冗余校验确保正确的数据通信.pdf
  • 所需E币: 3
    时间: 2019-12-24 23:28
    大小: 238.56KB
    上传者: rdg1993
    摘要:全部1-Wire®器件,包括iButton®器件,都具有唯一的8字节注册码,储存在只读存储器(ROM)中。该注册码在1-Wire总线上用作唯一的网络地址。为确保数据通信的完整性,每个注册码的一个字节是一个DOWCRC字节。本篇应用笔记说明了8位DOWCRC的计算方法以及用于验证器件存储器记录的16位CRC的计算。DOWCRC和CRC-16还会在选择1-Wire器件验证数据的硬件中产生。理解和运用MaximiButton产品中的循环冗余校验(CRC)Aug25,2004摘要:全部1-Wire器件,包括iButton器件,都具有唯一的8字节注册码,储存在只读存储器(ROM)中。该注册码在1-Wire总线上用作唯一的网络地址。为确保数据通信的完整性,每个注册码的一个字节是一个DOWCRC字节。本篇应用笔记说明了8位DOWCRC的计算方法以及用于验证器件存储器记录的16位CRC的计算。DOWCRC和CRC-16还会在选择1-Wire器件验证数据的硬件中产生。引言Maxim的iButton系列产品是通过单线按照1-Wire协议传送特定命令序列,进行数据通信。该系列产品都有个很重要的特性,就是在出厂前每个器件都被写入了唯一的8字节ROM码。其ROM码组成如图1所示,最低有效字节为家族代码,代表iButton器件的类型,如:DS1990A的家族码为01,DS1991的家族码为02。由于在同一条1-Wire总线上可同时挂接多个相同系列或不同系列的1-Wire器件,因此主机必须能够决定如何正确地访问位于1-Wire总线上的各个器件,这一点尤为重要。家族码提供器件的类型,随后的6个字节是器件的唯一序列号,用以区分同一个系列的不同器件。该序列号可作为1-Wire总线上器件的“地址”,这样1-Wire总线上的所有器件连同主机就构成了一个微型局域网(MicroLAN),它们之间通过一条公共线来进行通信。1-Wire器件ROM码的最高有效字节是循环冗余校验(CRC)码,该值基于前面的7个字节数据。当系统主机开始与某个器件进行通信时,可以读取8个ROM字节,低位在前。如果主机计算出的CRC码与ROM数据本身所含的CRC码相同,则通信有效;反之,则表明有错误发生,需重新读取器件的ROM……
  • 所需E币: 3
    时间: 2019-12-24 22:54
    大小: 238.55KB
    上传者: 16245458_qq.com
    摘要:全部1-Wire®器件,包括iButton®器件,都具有唯一的8字节注册码,储存在只读存储器(ROM)中。该注册码在1-Wire总线上用作唯一的网络地址。为确保数据通信的完整性,每个注册码的一个字节是一个DOWCRC字节。本篇应用笔记说明了8位DOWCRC的计算方法以及用于验证器件存储器记录的16位CRC的计算。DOWCRC和CRC-16还会在选择1-Wire器件验证数据的硬件中产生。理解和运用MaximiButton产品中的循环冗余校验(CRC)Aug25,2004摘要:全部1-Wire器件,包括iButton器件,都具有唯一的8字节注册码,储存在只读存储器(ROM)中。该注册码在1-Wire总线上用作唯一的网络地址。为确保数据通信的完整性,每个注册码的一个字节是一个DOWCRC字节。本篇应用笔记说明了8位DOWCRC的计算方法以及用于验证器件存储器记录的16位CRC的计算。DOWCRC和CRC-16还会在选择1-Wire器件验证数据的硬件中产生。引言Maxim的iButton系列产品是通过单线按照1-Wire协议传送特定命令序列,进行数据通信。该系列产品都有个很重要的特性,就是在出厂前每个器件都被写入了唯一的8字节ROM码。其ROM码组成如图1所示,最低有效字节为家族代码,代表iButton器件的类型,如:DS1990A的家族码为01,DS1991的家族码为02。由于在同一条1-Wire总线上可同时挂接多个相同系列或不同系列的1-Wire器件,因此主机必须能够决定如何正确地访问位于1-Wire总线上的各个器件,这一点尤为重要。家族码提供器件的类型,随后的6个字节是器件的唯一序列号,用以区分同一个系列的不同器件。该序列号可作为1-Wire总线上器件的“地址”,这样1-Wire总线上的所有器件连同主机就构成了一个微型局域网(MicroLAN),它们之间通过一条公共线来进行通信。1-Wire器件ROM码的最高有效字节是循环冗余校验(CRC)码,该值基于前面的7个字节数据。当系统主机开始与某个器件进行通信时,可以读取8个ROM字节,低位在前。如果主机计算出的CRC码与ROM数据本身所含的CRC码相同,则通信有效;反之,则表明有错误发生,需重新读取器件的ROM……
  • 所需E币: 3
    时间: 2019-12-24 21:19
    大小: 387.61KB
    上传者: 238112554_qq
    CRCisoneofthemostversatileerrorcheckingalgorithmusedinvariousdigitalcommunicationsystems.CRCstandsforCyclicRedundancyCodeCheckorsimplyCyclicRedundancyCheck.Mostofthepopularcommunicationprotocols,likeCAN,USB,IrDAÆ,SDLC,HDLCandEthernet,employCRCforerrordetection.Normally,fortheerrordetectionindigitalcommunicationsystems,achecksumiscomputedonthemessagethatneedstobetransmitted.Thecom-putedchecksumisthenappendedattheendofthemessagestreamandistransmitted.Atthereceivingend,themessagestreamíschecksumiscomputedandcomparedwiththetransmittedchecksum.Ifbothareequal,thenthemessagereceivedistreatedaserrorfree.CRCworksinasimilarway,butithasgreatercapabilitiesforerrordetectionthantheconventionalforms.DifferentCRCpolynomialsareemployedforerrordetection.ThesizeofCRCdependsuponthepolynomialchosen.ThisapplicationnotedescribestheCRCoperationanditsimplementationusingadedicatedhardwaremodule.AN1148CyclicRedundancyCheck(CRC)Author:SudhirBommenaConsideramessageof‘M’of‘k’bitsandgeneratorMicrochipTechnologyInc.polynomial‘G’of‘n+1’bits.Dividingthemessagebythegeneratorwillyieldaremainder‘R’of‘n’bits.There-fore,M=GQ+R;whereQisthequotientobtainedINTRODUCTIONwhenMisdividedbyG.CRCisoneofthemostversatileerrorchecking……