CRC冗余校验码及查表法CRC冗余校验码及查表法

80 阅读 0 评论 53 点赞

我是靠谱客的博主典雅人生，最近开发中收集的这篇文章主要介绍CRC冗余校验码及查表法CRC冗余校验码及查表法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

CRC冗余校验码及查表法

什么是CRC编码

它将一个长度为k的位串看作是系数是0或者1的k-1次多项式
使用一个长度为r+1的生成多项式进行模2计算，生成一个长度为r的字符序列，能检测长度小于等于r的所有突发错误，当突发错误长度为r+1时，只有其刚刚好等于生成多项式，才检测不出来。
多项式的最高位、最低位系数必须为1（我不知道为什么）

计算方法：（此处使用的减法是模2减法，不进位不借位，相当于XOR运算）
例如：使用G(x)=11001检测位串10110110

101101100000
11001
-----
011111
11001
-----
001101
00000
------
011010
11001
-----
000110
00000
-----
001100
00000
-----
011000
11001
-----
000010
00000
-----
00010

每次计算开始时，和G(x)进行计算的g(x)，例如11001，若第一个位置是0，则可以跳过计算，若第一个数字是1，则可以在商位填入1进行模2减法，例如上式计算过程可以简化为：

101101100000
11001
-----
011111
11001
-----
0011010
11001
-----
00011000
11001
-----
000010

每次计算结束后，g(x)的最高位都会被舍去，即g(x)整体左移一位、右边填充新的位数，然后再判断它的第一个位置是否是0、是否进行计算。因此，我们不关心g(x)最高位的计算（反正都要舍去），因此，G(x)也没必要跟着计算最高位

101101100000
1001
-----
11111
1001
----
011010
1001
----
0011000
1001
----
00010

根据离散知识，我们可以证明，(a+b)|c等同于a|c + b|c。因此，我们可以构造一个寄存器，它的长度为r，初始的时候，从字串取r位进行初始化，然后每次计算开始前，先左移一位，判断溢出的位是否为1，是，则与G(x)去掉最高位后的位串进行一次异或运算，然后进行下一次移位，每移r次，则再从字串取r位进行异或运算；否，则继续左移，直至溢出，或者左移次数已满。这样子，把所有位串都使用后，寄存器里就是最终的值。
代码实现：

unsigned char crc4(unsigned char *p, size_t s)
{
unsigned char crc4 = 0x00;
// 寄存器，长度为4
while (s --)
{
unsigned char val = *p++;
while (val)
{
crc4 ^= ((val & 0xf0) >> 4) & 0x0f;
// 寄存器获取4位数字
val <<= 4;
// 低位转移到高位
int count = 4;
// 4次移位
while (count --)
{
int b = crc4 & 0x08;
// 获取最高位
crc4 = (crc4 << 1) & 0x0f;
// 左移一位
if (b)
// 最高位是1
crc4 ^= 0x03;
// x4 + x + 1，0b10011
}
}
}
return crc4;
}

将此代码简化，得到如下版本

unsigned char crc4(unsigned char *p, size_t s)
{
unsigned char crc4 = 0x00;
while (s --)
{
crc4 ^= *p++;
// get byte
int count = 8;
// 8 byte for per bit
while (count --)
{
int b = crc4 & 0x80;
// get the highest byte
crc4 <<= 1;
if (b)
crc4 ^= 0x30;
// x4 + x + 1
}
}
return crc4 >> 4;
}

将crc4的高4b比特当作是寄存器进行计算

查表法

注意到我们上述的最后一项发现中说，(a+b)|c等同于a|c + b|c
也就是说，分块进行计算是完全可行的（我们上述的代码也证明了这一点）
那么，对于有限的被除数，我们完全可以先将其存起来，存成一张表，在计算的时候直接查表
也就是说，将代码一中的

int count = 4;
// 4次移位
while (count --)
{
int b = crc4 & 0x08;
// 获取最高位
crc4 = (crc4 << 1) & 0x0f;
// 左移一位
if (b)
// 最高位是1
crc4 ^= 0x03;
// x4 + x + 1，0b10011
}

简化为

crc4 ^= table[crc4];

crc4的长度为4byte，一共有16种可能，全部存起来。
生成表的计算代码为

for (int i = 0x00; i <= 0x0f; i ++)
table[i] = crc4((unsigned char*)&i, 1);

整理之后的代码如下：

unsigned char crc4_table(unsigned char *p, size_t s)
{
unsigned char crc4 = 0x00;
// the register, size 4 byte
while (s --)
{
unsigned char val = *p++;
while (val)
{
crc4 ^= ((val & 0xf0) >> 4) & 0x0f;
// get 4 byte;
val <<= 4;
// mv lower to high
crc4 ^= table[crc4];
}
}
return crc4 ^= table[crc4];
}

之所以最后要再查一次表，是因为，CRC需要在字串后面添加4个0，这4个0也会纳入计算
简略之后的代码为

unsigned char crc4_4(unsigned char *p, size_t s)
{
unsigned char crc = 0x00;
while (s --)
{
crc ^= *p ++;
for (int i = 0; i < 2; i ++)
{
crc = (table[(crc >> 4) & 0xf] << 4) ^ (crc << 4);
}
}
return crc >> 4;
}

crc<<4是因为，每一次计算要左移一位，计算4次就是左移4位

同样的，我们可以写出查8位表的代码：

unsigned char crc4_8(unsigned char *p, size_t s)
{
unsigned char crc = 0x00;
while (s --)
{
crc = table[(crc ^ *p++) & 0xff] << 4;
}
return crc >> 4;
}

这里crc = table[(crc ^ *p++) & 0xff] << 4;中，位移的含义是，我们的寄存器放在高4位的地方，因此需要将计算结果移到前面
这一行是

crc ^= *p ++;
crc = table[crc & 0xff] << 4;

的合并

如果是crc8，则就简单了很多：

crc8 = table[(crc ^ *p++) & 0xff];

镜像编码

我们在这里使用编码，默认高位在前、低位在后，但是，实际使用的时候，通常是低位在前、高位在后。
要解决这个问题，有两种方法，一种是先翻转、再编码、再翻转，另一种方法是进行镜像编码，即输入的是镜像、输出的也是镜像

对镜像翻转进行计算，要求计算结果也为镜像

首先进行表的编写

unsigned char crc4_table[16];
void init_crc4_table()
{
unsigned char crc4;
for (int i = 0x00; i <= 0xf; i ++)
{
crc4 = i;
for (int j = 0; j < 8; j ++)
// 8byte
{
int b = crc4 & 0x01;
crc4 >>= 1;
if (b)
crc4 ^= 0x0c;
// 0b0011 reverse
}
crc4_table[i] = crc4;
}
}

接下来进行计算

unsigned char crc4(unsigned char *p, size_t s)
{
unsigned char crc4 = 0x0;
while (s --)
crc4 = crc4_table[(crc4 ^ *p++) & 0x0f] ^ (crc4 >> 4);
return crc4 & 0x0f;
}