常用crc查表法_请教查表法计算CRC的原理

自己写过的， 希望对你有帮助

Cyclic Redundancy Check(CRC) 原理及实现

///

1: 需求

在数据传送过程中，为了能够进行错误检测， 往往在数据后追加一些检测码，

当接受方收到了数据后， 用同样的算法进行计算检测码， 如果一致说明数据

正确， 否则通知发送方重新发送。 现假定数据为6 23 44：

历史上出现过多个算法， 如：

累加求模：

(6+23+4)%256 == 33， 则发送数据6 23 44 33

XOR：

(6^ 23 ^4) = 21 则发送数据 6 23 4 21

然而， 这却不是好的算法， 好的算法要求数据的数据能散列的分布在检测码

中， 对于累加求模的(6 24 3 )以及xor的(6 22 5)都能输出同样的检测码

于是， CRC诞生了。

///

///

2：CRC的背景理论

crc将数据追加结尾的wbit的0当作一个很大阶的多项式， 用它去除于另一个双方约定的多项式,

得到的余数， 则为检测码，其中w为约定多项式的最大阶数, 最后传输原始数据追加检测码,

其中任何一位发生变化， 都导致最后得到的结果差别很大，

CRC因为容易简单实现以及容错性强， 而被广泛使用。

追加wbit的好处是, 整个传输的数据刚刚能够被约定的多项式

p1|00..00| / p2 = p3 .....p4

则(p1|00.00|+p4) / p2 = p3....0

p1|00.00|+p4 = p1|p4|  (后面的多项式运算能够证明)

这里为了方便说明, 下列进行运行的数据都没有追加结尾的0

这里有2个问题， 如何把数据流转换成多项式， 以及如何做多项式的除法。

数据流的转换：

假如有2个byte(6，23)我们把他转成16进制为0617, 二进制表示为

0000 0110 0001 0111 对应多项式 x^10 + x^9 + x^4 + x^2 + x^1 + 1

多项式除法：

先说多项式加法， 多项式x^4 + x^2 + x + 1 和多项式x^4+x^3+1

为 2*x^4 + x^3 + x^2 + x^1 + 2*(x^0)

由于x是个未知数， 不知道怎么进行系数和阶的转换， 于是规定：

"如果系数mod2==0， 那么则丢弃， 否则保留， 多项式不考虑系数"

所以上述2个多项式相加的结果为 x^3+x^2+x^1

同样根据规定可以知道， 多项式p1+p2 == p1-p2，

即： 多项式相减等同于多项式相加.

用2进制表示有 1011 + 1101 = 0110, 1011 - 1101 = 0110

这即等同与2进制的xor操作。

再来看看多项式乘法, (x^4+x^2+x^1+1) * (x^2 + x^1 + 1)

= (x^6+x^4+x^3+x^2) + (x^5+x^3+x^2+x^1) + (x^4+x^2+x^1+1)

= x^6 + x^5 + x^2 + 1

我们再来看看多项式除法

x^2 + x1 + 1

--------------------

x^4+x^2+x^1+1 ) x^6 + x^5 + x^2 + 1

(x^6+x^4+x^3+x^2) + (x^5+x^3+x^2+x^1) + (x^4+x^2+x^1+1)

-(x^6 + x^4 + x^3 + x^2)

(x^5+x^3+x^2+x^1) + (x^4+x^2+x^1+1)

-(x^5+x^3+x^2+x^1)

(x^4+x^2+x^1+1)

-(x^4+x^2+x^1+1)

0

根据乘/除法和加/减法的运算规则不难看出，

a: p1 % p2 = p3....p4 ===> p1 = p2*p3 + p4

b: 设p2是一个w阶的多项式， 那么余数是一个w-1阶的多项式。 w叫做多项式的位宽。

比如 x^4+x^2+x^1+1的位宽为4， 余数为一个3阶的多项式。 占4个2进制位.

crc中， 把w位宽的多项式叫做crcw, 如约定的除式为X^4+x^2+x^1+1 (10111)

那么就叫crc4, 对于的余数则在(0000 ... 1111)的范围内.

///

///

3: 实现

对于2中定义的多项式. 转成2进制的形式, 有

111

-------------------

10111 (b)   )1100101                   (a)

10111..

11100.

10111.

10111

10111

0

不难看出, 设4bit的crc初始为0, 每次从crc中移走最高位, 从a中移走一位进最

低位,  如果crc中移走的为1, 则将结果xor下10111的低4位(0111), 否则不处理

c语言描述有

while (msg)

{

crc = (crc<<1 | get_msg_bit) ^  ( (crc&1000) ? (10111&1111) : 0000)

}

for(int i=0; i

{

crc = (crc<<1 | 0) ^  ( (crc&1000) ? (10111&1111) : 0000)

}

上述即是crc的标准算法. 下面我们开始优化.

----------------------------------------

优化a: 查表法

设a,b,c都是4bit的数, 有

(a^b) ^ c == a ^ (b^c)

证明: 因为xor都是位对其操作, 所以我们只要证明bit具有属性(b1^b2)^b3==b1^(b2^b3)

因 (b1^b2)^b3 == ((b1+b2)+b3)mod2,   b1^(b2^b3) == (b1+(b2+b3))mod2

bit operator + 具有交换率,  所以 (a^b)^c == a^(b^c)

因为计算机的操作单元一般都是byte, 如果每次都进行一次bit操作, 那么效率上

会大打折扣.

现在我们假设w是32, 即crc32. 有个4byte的寄存器R [b1 b2 b3 b4] 用来存储CRC32的值

根据前面的交换率, 我们可以先计算出b1对于后4个字节的影响值来, 记做table[b1]

然后把b2 b3 b4 a (a为读出的一个byte的msg) 跟 table[b1]来xor下. 有

while(msg)

{

crc =     (crc<<8 | get_msg_byte) ^  table[crc >> 24];

}

for(int i=0; i

{

crc =     (crc<<8 | 0) ^ table[crc>>24];

}

前提是要提前计算出一个静态的256项的表来, 当然你也可以计算出65536项的表来, 一次

update 2个byte, 但这样意义不大.

----------------------------------------

优化b:  我们现在开始把后面烦琐的 for(int i=0; i

假如数据 aa bb cc dd .. xx 00 00 00 00 有crc32为 (a1 a2 a3 a4)         .....(1)

数据 aa bb cc dd .. xx yy 00 00 00 00 有crc32为(b1 b2 b3 b4)       .....(2)

数据 aa bb cc dd .. xx yy 00 00 00 有crc32(c1 c2 c3 c4)            .....(3)

不难看出, c1=a1^yy c2=a2 c3=a3 c4=a4,  这是因为yy处于最后w位移进R的， 他不会被R

移出左边, 所以他不会影响到后面3个0. 他只会被前面的值xor影响到, 由于xor具有

交换率, 所以c1=a1^yy, 现在..

aa bb cc dd .. xx yy 00 00 00 有crc32(a1^yy a2 a3 a4)         .....(3)

aa bb cc dd .. xx yy 00 00 00 00 有crc32(b1 b2 b3 b4)         .....(2)

根据a的查表, 我们可以知道

(b1 b2 b3 b4)  ==     table[a1^yy] ^ (a2 a3 a4 00)

回到刚开始, crc32 init == (x1 x2 x3 x4),  那么 x1 x2 x3 x4 00 00 00 00 = (y1 y2 y3 y4)

现在init=0, 所以x1x2x3x4y1y2y3y4 = 0

有 aa 00 00 00 00 为 table[aa], 也就是 table[aa^0] ^ (0)

综合有.

crc = 0

while(msg)

{

crc  = table[crc>>24 ^ get_msg_byte] ^ (crc<<8)

}

-------------------------------------------

优化c : Reflected

由于我们用字节存储的时候， 都是LSBF(least significant bit first)

而我们b里面是用的MSBF,  也就是说, 在算法b中, 我们需要:

把每次get_msg_byte都需要Reflected

initial value需要reflected

最后的结果需要reflected下

byte reflected(byte b)

{

byte c;

for(int i=0; i<8; ++i)

{

c <<= 1;

if (b&1) c|=1;

b >>= 1;

}

return c;

}

于是有

while(msg)

{

crc = table[crc ^ get_msg_byte] ^ (crc>>8)

}

注意这里的table, 是用reflected的多项式生成的.

initial value也是reflected的. 为了get_msg_byte不需要reflect, 那么

table中, index也是被reflected了.

///

///

4: 可变参数

我们知道了, CRC算法受到下列形态的影响

* 多项式的w, 以及多项式

* initial value

* 做处理的时候是 MSBF还是LSBF

* final register

(同initial value, 为了区分不同的crc, 当同一个消息时,

所以定义了最后的xor final register)

下面给出一种模型.

Rocksoft^tm Model CRC Algorithm

Name, Width, Poly, Init, Refin, Refout

下列是一份常用的CRC列表

X25   standard : 1021       [CRC-CCITT, ADCCP, SDLC/HDLC]

X25   reversed : 0811

CRC16 standard : 8005

CRC16 reversed : 4003       [LHA]

Name   : "CRC-16"

Width  : 16

Poly   : 8005

Init   : 0000

RefIn  : True

RefOut : True

XorOut : 0000

Check  : BB3D

Name   : "CRC-16/CITT"

Width  : 16

Poly   : 1021

Init   : FFFF

RefIn  : False

RefOut : False

XorOut : 0000

Name   : "XMODEM"

Width  : 16

Poly   : 8408

Init   : 0000

RefIn  : True

RefOut : True

XorOut : 0000

Name   : "ARC"

Width  : 16

Poly   : 8005

Init   : 0000

RefIn  : True

RefOut : True

XorOut : 0000

Name   : "CRC-32"

Width  : 32

Poly   : 04C11DB7        [PKZIP, AUTODIN II, Ethernet, FDDI]

Init   : FFFFFFFF

RefIn  : True

RefOut : True

XorOut : FFFFFFFF

Check  : CBF43926

///