CRC校验原理和推导过程及Verilog实现(一文讲透) |
您所在的位置:网站首页 › crc校验位 › CRC校验原理和推导过程及Verilog实现(一文讲透) |
目录
一、CRC简介1.1 CRC可检测的错误1.2 CRC需要知道的基本名称1.2.1 多项式公式1.2.2 多项式简记式1.2.3 数据宽度1.2.4 初始值与结果异或值1.2.5 输入值反转与输出值反转
二、CRC校验原理2.1 CRC校验计数基础知识2.2 CRC多项式的选择(除数的选择)
三、CRC校验码手动计算四、CRC校验算法推导与Verilog实现4.1 生成矩阵G4.2 CRC校验公式4.3 CRC串行计算公式推导4.4 CRC校验串行计算的Verilog实现4.5 CRC校验并行计算的Verilog实现4.6 CRC校验在多个字节(数据包)场景下的计算方法
五、相关工具六、Reference
一、CRC简介
循环冗余校验和(Cyclic Redundancy Checksum, CRC)是一种检错技术。 数据通信领域中最常用的一种差错校验码,其信息字段和校验字段长度可以任意指定,但要求通信双方定义的CRC标准一致。主要用来检测或校验数据传输或者保存后可能出现的错误。 在数据传输过程中,无论传输系统的设计再怎么完美,差错总会存在,这种差错可能会导致在链路上传输的一个或者多个帧被破坏(出现比特差错,0变为1,或者1变为0),从而接受方接收到错误的数据。 为尽量提高接受方收到数据的正确率,在接收方接收数据之前需要对数据进行差错检测,当且仅当检测的结果为正确时接收方才真正收下数据。检测的方式有多种,常见的有奇偶校验、因特网校验和循环冗余校验等。 CRC检错能力强,开销小,易于用编码器及检测电路实现,从性能和开销上考虑均优奇偶校验和累加校验。在数据存储和数据通讯领域,多用CRC校验,不能发现的错误在0.005%以下。著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC-CCITT,WinRAR、NERO、ARJ、LHA等压缩工具软件采用的是CRC32,磁盘驱动器的读写采用了CRC16,通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。 另外,CRC校验多数都是用于检错而不是纠错。 1.1 CRC可检测的错误 可检测出所有奇数个错误;可检测出突发长度n-k+1的错误可以检测出,其中不可检出的错误占2-(n-k)。其中,n为信息码+监督码总长度,k为信息码长度。 突发错误是指几乎是连续发生的一串错,突发长度就是指从出错的第一位到出错的最后一位的长度(但是,中间并不一定每一位都错)。 1.2 CRC需要知道的基本名称这里需要知道几个组成部分或者说计算概念:多项式公式、多项式简记式、数据宽度、初始值、结果异或值、输入值反转、输出值反转、参数模型。 1.2.1 多项式公式对于CRC标准除数,一般使用多项式(或二项式)公式表示,如下图中除数11011(poly值为0x1b)的二项式为G(X)=X4+X3+X+1,X的指数就代表了该bit位上的数据为1(最低位为0) 这里特别注意一下位数问题,除数的位数为二项式最高次幂+1(4+1=5),这个很重要 通过对CRC的基本了解我们知道,多项式的首尾必定为1,而这个1的位置在下一步计算一定为0,所以就把前面这个1给省略掉了,出现了一个叫简记式的东西,如上例中除数11011的简记式为1011,很多看过CRC高级语言源码的人会知道,对于CRC_16标准下G(X)=X16+X15+X2+1(16#18005)的poly值实际上是8005,这里使用的就是简记式,以后见到的基本都是简记式 1.2.3 数据宽度数据宽度指的就是CRC校验码的长度(二进制位数),知道了CRC的运算概念和多项式,就可以理解这个概念了,CRC长度始终要比除数位数少1,与简记式长度是一致的。 1.2.4 初始值与结果异或值在一些标准中,规定了初始值,则数据在进行上述二项式运算之前,需要先将要计算的数据与初始值的最低字节进行异或,然后再与多项式进行计算。 而在结果异或值不为零的情况下,则需要将计算得到的CRC结果值再与结果异或值进行一次异或计算,得到的最终值才是我们需要的CRC校验码。 这里可以看出,初始值与结果值的位数要求与数据宽度一致。 1.2.5 输入值反转与输出值反转输入值反转的意思是在计算之前先将输入数据反转,然后再计算。如对于输入数据,其正向值为1 1000 0000 0000 0101,反转值则为1010 0000 0000 0001 1,注意这里反转并不是按位取反,而是低bit位与高bit位交换位置 输出值反转则是将最终得到的CRC结果反转。 通常,输入值反转后的结果值也会是反转的,所以这两个选项一般是同向的。 二、CRC校验原理CRC校验根本思想就是先在要发送的数据帧后面附加一个数(这个就是用来校验的校验码),生成一个新帧发送给接收端。当然,这个附加的数不是随意的,它是数据帧除以选定的CRC除数产生的余数 新帧到达接收端后,有两种方法比较传输是否出错: 一是用同样的方法对数据帧除以CRC除数产生的余数跟校验码相比,如果相同,则数据正确,否则数据错误; 二是对新帧除以CRC除数,如果余数为0,则数据正确,否则数据错误。 要校验的数据加上此数据计算出来的crc校验码组成新的数据帧,如下图所示。 CRC校验中的运算不是普通的运算,称为“模2运算” 模2加法和减法都是异或运算,例子如下: 1010+0110=1100,1010-0110=1100 模2乘法的定义: 0×0=0,0×1=0,1×0=0,1×1=1。 1011×101=100111 模2除法,其实也是异或运算: 0/1=0,1/1=1。 1011/101=10,余数为100。 对于CRC标准除数,一般使用多项式(或二项式)公式表示(参照节1.2.1和1.2.2),CRC除数位数越高,检错能力越强,通常是根据设计中的数据流大小与格式来选择。数据流是8bit为一个包的话,则CRC校验位数选择8bit或者16bit等比较好。 CRC校验码就是两个数相除的余数,而且余数位数要正好比除数少一位,即使MSB为0。 下面举例说明CRC校验码手动计算过程: 对于数据1110 0101,指定多项式为x4+x3+x+1,则除数为11011。首先要将数据左移4bit(校验码的位数),然后再进行计算: 第三大节讲了如何手动计算CRC校验码,但如何在编程中实现,这就是个难题,网上很多文章都只是浅浅地谈了一下,并没有具体推导,如果对推导过程没兴趣的,可以直接翻到第五大节直接用链接生成Verilog代码。 4.1 生成矩阵GCRC是循环码的一种,这是通信原理上的内容。由生成矩阵G,就可以由k个信息位得到整个码组,即要传输的完整数据(信息码+监督码): CRC校验码其实是两个多项式相除的余数,我们要传输的数据(也是被除数)是多项式M(x) 的系数,除数是生成多项式G(x) 的系数,G(x) 的最高次幂为xn-k ,校验码是余数多项式R(x) 的系数,Q(x) 为商,则计算公式为 上面的式子其实已经可以计算得到CRC校验码了,但还无法在硬件上实现,所以需要用硬件的思想推导可实现的计算方法,这里以CRC-32的标准来进行举例推导。 根据二进制信息码转换成多项式的方法,对于任意一个长度为(m+1)的二进制信息码,可以转换成一个最高次幂为m的多项式: 其中,2m 是二进制的科学计数法。 为求此二进制序列的CRC值,首先将M(x) 乘以232,然后再除以生成多项式G(x),所得余数R(x) 是一个最高次幂为31的多项式,其系数为CRC-32的值,那么: 4.1和4.2节讲了公式推导,这一节讲如何用Verilog表达出来。 首先得了解LFSR,线性反馈移位寄存器简称LFSR,用于产生可重复的伪随机序列,也可用来实现CRC校验。LFSR主要由触发器(寄存器)、异或门以及反馈线路组成。 4.3节是串行的表述,每一bit数据需要一个时钟周期,为提高速率还得用上并行计算的思想,输入数据S要并行输入到G(x)系数为1的支路中,输入数据从输入端按高到低逐bit输入,就可以实现。 假如被除数是2位的数据S[1:0]=01,多项式是10011,x4 +x+1。在CRC校验里面,习惯省略最高位的1,多项式用0011表示。那么S除以0011的模二运算数字电路结构为: d2= S[1]^ q1^q4; d3=q2; d4=q3。 经过一次移位后: q1=d1= S[1]^q4; q2= d2= S[1]^ q1^q4; q3= d3=q2; q4= d4=q3。 此时有: d1=S[0]^q3; d2= S[0]^ S[1]^ q4^q3; d3= S[1]^ q1^q4; d4= q2。 令c[3:0]={q4,q3,q2,q1},d[3:0]={d4,d3,d2,d1},那么d就是最终的运算结果表达式,如下 d[3]=c[1]; d[2]= S[1]^ c[0]^c[3]; d[1]= S[0]^ S[1]^ c[3]^ c[2]; d[0]= S[0]^ c[2]。 令c的初值为0,则01对0011的模二除法的余数为0011。 再比如多项式为x5 +x3 +x+1,简记式为01011,其数字电路结构为: 对于多个字节(数据包),这里举个例子,如果数据是10bit*100个包,则每次输入10bit得到校验码后,该检验码为下次数据计算时寄存器D的初值,如此反复计算得到最后的检验码添加到整个数据后面即可,而不需要每个数据包后面都添加检验码。 五、相关工具如果不理解推导过程的话,可以由相关工具帮忙计算出结果和得到Verilog代码: CRC校验Verilog代码生成链接:http://outputlogic.com/?page_id=321 CRC校验计算工具链接:http://www.ip33.com/crc.html,这个工具只能计算16bit为一个数据包的数据,如果数据包为10bit等之类的就不太适用 六、Referencehttps://www.cnblogs.com/y0011/p/15076764.html https://www.cnblogs.com/season-peng/p/6713533.html http://www.webzuan.cn/szk/12258.html https://www.cnblogs.com/kingstacker/p/9848191.html https://www.cnblogs.com/nanxiaoxiang/p/5887916.html https://www.zhihu.com/question/286086320 樊昌信, 曹丽娜. 通信原理(第7版) [M]. 北京:国防工业出版社, 2012. |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |