CRC字节算法

在研究CRC字节算法的时候参考了网上的一些博客,但是感觉写的不够透彻,有的也出现一些错误。本文的目的是详细讲解CRC字节算法。

有关CRC算法的介绍请参见:

参考链接一:最通俗的CRC校验原理剖析

参考链接二:CRC查找表法推导及代码实现比较

在此,强调一下CRC算法中两个重要的点:

1、 原始序列要左移n位,再除以生成多项式;

2、生成多项式所包含的比特数比CRC校验比特数多1。

以上两点注意事项可在最通俗的CRC校验原理剖析中的例子观察。

在证明之前,先复习一下取余运算的计算法则:

  1. (a+b)%p=(a%p+b%p)%p

  2. (a*b)%p=(a%p*b%p)%p

  3. [(a+b)*c]%p=[(a+b)%p*c%p]%p=[(a%p+b%p)%p*c%p]%p=[(a%p+b%p)*c]%p

  4. (a%p+b%p+c%p+…)%p=(a+b+c+…)%p=[(a+b)%p+b%p+c%p+…]%p

提示:取余运算符和乘除运算符的优先级相同。

接下来,将详细讲解CRC24的字节算法。

假设有一组比特数据流,将它们每8个分为一组,按照字节的方式表示为

表示成数学表达式为

现在要产生24位CRC校验比特,假设生成多项式为G25(共有25个比特,比校验比特多一个),那么生成的24位CRC校验比较可表示为

乘到括号里面,得到

使用取余公式1可得到下式

之后的公式的关注点都是红色部分,因为黑色部分没有发生变化。对上式的红色部分使用取余公式2,可得到下式

观察上式红色部分中的,可以发现它表示的24位CRC校验比特,记为,那么上式可写为

又因为包含24比特,那么必然有,因此,上式可化为

使用取余公式2可得到

使用取余公式4可得到

提出公因式2^(n-1)可得到

写成高8位和低16位的形式,可得到下式

去掉最内层括号并提取公因式2^24可得到

因为第一项是低16比特左移8位,只有24个有效比特,因此必然有,因此上式又可写成

经过上边的化简,可将第n个字节(8比特)删除,并将第n-1个字节修订为

因此,每经过一次迭代,就能删掉一个字节并修订下一个字节,经过n+1次迭代可将n+1个字节的数据全部计算完毕并得出最后的24位校验码。另外,上式中的第二项可通过查表的方法快速得到,大大提高了计算效率。

 

计算表项的MATLAB程序:

crc24Main.m

crcTableG_24.m

 

计算一组信息比特的CRC24A校验码的C程序:

 

分享到:

发表评论