Menu Close

循环冗余校验码CRC原理

CRC(Cyclic Redundancy Check)循环冗余校验码,是数据通信领域中最常用的一种差错校验码,其特征是信息字段和校验字段的长度可以任意选定。循环冗余检查(CRC)提供了一种数据传输检错功能,对数据进行多项式计算,并将计算得到的结果附在帧的后面,接收设备对接收到的数据也执行相同的算法,以保证数据传输的正确性和完整性。下面对CRC的原理,计算以及如何校验进行描述。

  1. CRC的校验原理

使用CRC进行数据校验,其根本思想就是先在要发送的帧后面附加一个数,这个数就是用来对接收方对接收到的数据进行校验的校验码。但要注意,这里的数也是二进制序列的。源数据与附着的校验码生成一个新帧发送给接收端。当然,这个附加的数不是随意的,它要使所生成的新帧能被发送端和接收端共同选定的某个特定数整除(注意,这里不是直接采用二进制除法,而是采用一种称之为“模2除法”)。到达接收端后,再把接收到的新帧除以(同样采用“模2除法”)这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数,做了“去余”处理(也就已经能整除了),所以结果应该是没有余数或余数为0。如果有余数或余数不为零,则表明该帧在传输过程中出现了差错。在介绍CRC算法中除法原理之前先介绍CRC使用的模2除的概念。

  • 模2除法

模2除法与算术除法类似,但每一位除的结果不影响其它位,即不向上一位借位,所以实际上就是异或。在循环冗余校验码(CRC)的计算中有应用到模2除法。图1演示了8位二进制数10110011模2除5位二进制数的除法过程。

%title插图%num

图1   CRC的计算过程

  • CRC的计算步骤:

    • 在被计算数据后补0。补0的位数由除数的位数决定,比除数少一位。这表明X位的二进制除数,除法计算后余数的结果应为X-1位,否则除法可以继续进行。上例中对于5位2进制除数,在被除数后面补4个0。
    • 对已补0的被除数自左向右进行模2除,计算过程如图1所示的除法竖式所展示的步骤,直到所有的被除数的位都已经参与运算,而且余数的位数小于除数的位数(本例中除数的位数为5)
    • 如果最终的位数小于X-1,则在余数的左边补相应的0以满足余数的位数为X-1。如本例中在余数前补一位0,形成为0100的4位二进制余数。
    • 将余数替换源被除数补0的位置,形成附着的CRC(这里为0100)。
    • 校验,将新组成的二进制数(101100110100),如图2

%title插图%num

图2 CRC4的校验计算

2. CRC常用的生成多项式

CRC的计算要用到收发双方都约定好的除数,除数是用二进制表达的,为了方便表示除数,CRC的除数采用生成多项式表示,常用的CRC生成多项式如下:

  • CRC5=X5 +X2+1                               CRC5 用于USB数据包的计算

对应的除数为 100101  —X5 +0X4+0X3+X2+0X+1

  • CRC8=X8+X5+X4+1                       CRC8用于USB数据包的计算

对应的除数为100110001

  • CRC-CCITT=X16+X12+X5+1        CRC16由于通信数据包的校验

 

  • CRC12=X12+X11+X3+X2+1          CRC12 用于8-bit通信数据包校验

 

  • CRC32=X32+ X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1   用于网络通信

对应的除数为1_0000_0100_1100_0001_0001_1101_1011_0111=33’h1_04c1_1db7

上面介绍了生成多项式,那么生成多项式与CRC的计算有什么关系呢?由生成多项式得到二进制除数,如CRC8=X8+X5+X4+1,则二进制除数为1_0011_0001,总共9位。CRC32的二进制除数为1_0000_0100_1100_0001_0001_1101_1011_0111共33位。除法运算后的结果为32位,并把结果附在数据之后,形成32位CRC的FCS。关于CRC的计算与推导公式在后续章节中介绍。

练习题:

(1)采用竖式计算模2除求解CRC5的结果,假设数据为8’h1011_0110

(2)由CRC12,CRC16的生成表达式,列出CRC计算中的除数,余数的位数。

 

Posted in FPGA, FPGA, 教材与教案, 文章
0 0 投票数
Article Rating
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论

相关链接