CRC校验原理和verilog实现方法(一)

时间:2023-02-01 03:25:35

1.CRC简介

CRC全称循环冗余校验(Cyclic Redundancy Check, CRC),是通信领域数据传输技术中常用的检错方法,用于保证数据传输的可靠性。网上有关这方面的博客和资料很多,本文尽量简洁的梳理一下它的原理。后面还会结合自己的实践经验(不多),说一说如何使用verilog语言在FPGA中做CRC校验。感兴趣的朋友可以关注我后续的更新,一起交流学习!

CRC校验的基本思路是数据发送方发送数据之前,先生成一个CRC校验码,这个校验码可以是单bit也可以是多bit,并附在有效数据末尾,以串行方式发送到接收方。接收方接收到数据后,进行CRC校验,根据校验结果就可以知道数据是否有误。

CRC校验码的生成:将有效数据扩展后作为被除数,使用一个指定的多项式作为除数,进行模二除法,得到的余数就是校验码。

数据接收方的CRC校验:将接受的数据(有效数据+CRC校验码)扩展后作为被除数,用上述指定的多项式作为除数,进行模二除法,得到余数为0,则表示校验正确。

2.CRC校验过程

需要注意的是,CRC校验中的被校验数据在进行扩展之前,尽量以字节(8bit)为单位,如果数据不够一个完整的字节,可以高位补0。这一点在后面verilog实现时很关键。

2.1多项式选取

多项式的选择会影响检查错误的可靠性,检测错误的概率和多项式之间存在一定的数学关系,涉及到一些算法原理,这里不去深究,感兴趣的朋友可以查阅通信原理和线性编码相关书籍。

多项式的表达式:G(x)=x^n+x^(n-1)…+1,其中n>=1。

该表达式可以用2进制数表示,以便软件编程。例如多项式G(x)=x^5+x^3+x^2+1,用2进制表示就是101101;多项式G(x)=x^6+x^5+x^1+1,用2进制表示就是1100011。很容易看出规律吧。

有些资料里将多项式最高位的1省略,不过这里建议手动计算时保留这一位,免得出错。

通信上有一些常用的多项式,如下表示所示。这是前人总结好的,广泛使用的,可根据通信方式选择,例如CRC-5/USB算法对应的是用于USB通信的CRC多项式。

CRC校验原理和verilog实现方法(一)

2.2求余数(发送方)

求余目的是得到CRC校验码。首先将有效数据扩展n位作为被除数,n是多项式的最高次幂,例如前面的多项式101101最高次幂是5(比2进制位数少1),则有效数据扩展5位。然后用多项式的2进制数用模2除法去除被除数,得到的余数是CRC校验码。

先搞明白模2除法运算机制。

模2除法可以借助逻辑上的异或运算移位实现,例如被除数是2进制的10001111,除数是1010,则模2除法求余数的计算过程如下图所示,得到商是101,余数是111。可以看出,每次计算,除数最高位的“1”都要和被除数最高位的“1”对齐,然后进行异或运算。得到的余数位数不小于除数,则移位后再次对齐、计算,直到余数位数(从最高位的1开始算)小于除数位数。

CRC校验原理和verilog实现方法(一)

再看CRC校验码的计算过程。

假如发送的有效数据是10101010(注意是2进制),我们把它作为被除数。这里选择CRC-5/USB校验算法,多项式是x^5+x^2+1,对应2进制形式是100101。

首先对有效数据扩展5bit,也就是在后面添5个0,得到被除数1010101000000。然后进行模2除法,最终得到5bit(比多项式少1bit)余数11000,这就是CRC校验码。

CRC校验原理和verilog实现方法(一)

把上面得到的校验码附在有效数据后面,构成数据1010101011000,然后发送给接收方。

2.3求余数(接收方)

数据接收方对数据(包含校验码)求余数,计算过程与上述完全相同。最终得到的余数为0,才能说明数据传输无误。

假如接收的数据无误,这里写出来接收方的计算过程:

CRC校验原理和verilog实现方法(一)

最终得到余数为0,证明数据无误。

3.CRC校验计算实例

关于CRC校验码的计算,用上面比较繁琐的手算方式有助于了解计算过程,实际上现在有很多CRC计算工具,在线的和离线的都有。例如参考链接1的在线计算工具,可以用来验证自己手算或者自己写的校验代码结果是否正确。

这里用一个2byte数据做一次完整CRC校验,其中校验码的计算分别用手算和在线工具计算进行对比。

1)假设要发送的数据是0x8421,对应2进制为1000 0100 0010 0001;校验算法使用CRC-8,对应多项式是100000111。

2)手动计算求校验码:有效数据扩展后为1000 0100 0010 0001 0000 0000,计算得CRC校验码为00000101,16进制为0x05。(算到眼疼~

3)在线工具计算校验码:0x05,结果一致,说明手算无误。

CRC校验原理和verilog实现方法(一)

4)发送数据后面附上校验码:1000 0100 0010 0001 0000 0101,即0x842105。

4)手动计算求接收方校验结果:0x00。

5)在线工具计算求接收方校验结果:0x00,接收无误。

CRC校验原理和verilog实现方法(一)

参考链接:

1、http://www.ip33.com/crc.html

2、https://www.cnblogs.com/liushui-sky/p/9962123.html