CRC查表法——表的由来

4

本文作者:xjtudll  发布于:2013-6-24  分类:技术心得  点击:


为了更容易理解这篇文章,拿出纸笔跟着算一遍吧文中的一些假定:a0,a1,b0,b1,b2,b3,c1,c2,c3等等,拿笔将其含义记下来,免得思维混乱。

查表法实际上利用的是XOR运算的交换律和结合律,即(A XOR B XOR C = A XOR B XOR C

我们再以一个简单的例子来说明。

假设待测数据是0011 1110 B,生成多项式Poly10011 B

10011

 

0

0

1

1

1

1

1

0

0

0

0

0

 

Poly

 

 

 

1

0

0

1

1

0

 

b1

 

 

 

 

 

1

1

0

0

0

 

 

 

 

 

 

 

 

 

 

1

0

0

1

1

 

b0

 

 

 

 

 

 

1

0

1

1

 

 

 

 

 

 

 

 

 

 

 

-

-

-

-

 

后面计算过程省略

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

上面的计算可以变成这样:

10011

 

0

0

1

1

1

1

1

0

0

0

0

0

 

Poly

 

0

0

0

0

0

0

0

0

 

b3

 

 

 

0

1

1

1

1

 

 

 

 

 

 

 

 

 

 

0

0

0

0

0

0

0

 

b2

 

 

 

 

1

1

1

1

1

 

 

 

 

 

 

 

 

 

 

1

0

0

1

1

0

 

b1

 

 

 

 

 

1

1

0

0

0

 

 

 

 

 

 

 

 

 

 

1

0

0

1

1

 

b0

 

 

 

 

 

 

1

0

1

1

 

 

 

 

 

 

 

 

 

 

 

-

-

-

-

 

后面计算过程省略

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

假设a1 = 0011 1110 Bb1= 100110 Bb0 = 10011 Bc1 = 0011 0000 Bc2= 1110 Bc3 = 0011 B

显然,a1=c1 xor c2,且c3a1c1的高4

通过上面计算的过程可以看出,a1b0 CRC除法的过程等同于:

a1 XOR b3 XOR b2 XOR b1 XOR b0 = c1 XOR c2 XOR b3 XOR b2 XOR b1 XOR b0 = (c1 XOR b3 XOR b2 XOR b1 XOR b0) XOR c2

 

 

0

0

1

1

0

0

0

0

 

c1

 

XOR

0

0

0

0

0

0

0

0

 

b3 = (Poly&0) << 3

 

XOR

 

0

0

0

0

0

0

0

 

b2 = (Poly&0) << 2

 

XOR

 

 

1

0

0

1

1

0

 

b1 = Poly << 1

 

XOR

 

 

 

1

0

0

1

1

 

b0 = Poly

 

 

 

 

 

 

0

1

0

1

 

c1 XOR b3 XOR b2 XOR b1 XOR b0

 

XOR

 

 

 

 

1

1

1

0

 

c2

 

 

 

 

 

 

1

0

1

1

 

 

 

通过上面的计算和推导过程,我们知道可以事先计算好(c1 XOR b3 XOR b2 XOR b1 XOR b0),最后再与c2亦或,就可以得到最终值了。

 

前面已经说了,可以事先计算好c1 XOR b3 XOR b2 XOR b1 XOR b0,这就是驱动表。要得到驱动表,需要知道b0~b3。现在的关键是b0~b3是怎么来的?除了与Poly相关,还与什么有关呢?仔细观察,b0~b3实际上是与c3有关的(这里的c34bit,即半字节)。

b3

0

c3 bit3 = 0

Poly <<3

c3 bit3 = 1

b2

0

c3 bit2 = 0

Poly <<2

c3 bit2 = 1

b1

0

c3 bit1 = 0

Poly <<1

c3 bit1 = 1

b0

0

c3 bit0 = 0

Poly

c3 bit0 = 1

从计算过程来看,很明显,驱动表法和直接计算法处理方式一样,只是每次能够处理多位而已。

对于半字节索引,每次处理4bit 表格大小是24 = 16

对于字节索引,每次处理8bit 表格大小是28 = 256

注意

由于每次处理多bit(假设是N),那么数据长度必须是N的倍数。

以半字节为例,由于每次处理4bit,所以数据长度必须为4的倍数。如果非4的倍数,需要特殊处理(驱动表法和直接计算法混用)。例如,数据长度是74bit,前面72bit可以按照查表法,后面2bit则只能是直接计算法。

以下是CRC4Poly = 10011B的驱动表:

索引

 

表值

0

0000 B = 0x00

0000 B = 0x00

1

0001 B = 0x01

0011 B = 0x03

2

0010 B = 0x02

0110 B = 0x06

3

0011 B = 0x03

0101 B = 0x05

4

0100 B = 0x04

1100 B = 0x0C

5

0101 B = 0x05

1111 B = 0x0F

6

0110 B = 0x06

1010 B = 0x0A

7

0111 B = 0x07

1001 B = 0x09

8

1000 B = 0x08

1011 B = 0x0B

9

1001 B = 0x09

1000 B = 0x08

10

1010 B = 0x0A

1101 B = 0x0D

11

1011 B = 0x0B

1110 B = 0x0E

12

1100 B = 0x0C

0111 B = 0x07

13

1101 B = 0x0D

0100 B = 0x04

14

1110 B = 0x0E

0001 B = 0x01

15

1111 B = 0x0F

0010 B = 0x02

我们用查表法重新计算之前的例子

10011

 

0

0

1

1

1

1

1

0

0

0

0

0

 

Poly

 

 

 

 

 

0

1

0

1

 

0011 B 查表而来

 

 

 

 

 

 

1

0

1

1

 

 

 

 

 

 

 

 

 

 

 

-

-

-

-

 

后面计算过程省略

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

查表法实现的结果与直接计算法完全一致。 

 

 后注:

最近几年来,不停的有人问,为什么1000-1111B计算的结果与表格里不一样。我再解释一遍。以1000为例,下面是简易的计算过程。

C3=1000 0000
 
b3=1001 1000(bit=1,0001 0011<<3)
b2=0000 0000(bit=0,0000 0000)
b1=0000 0000(bit=0,0000 0000)
b0=0000 0000(bit=0,0000 0000)
 
c3 xor b3 xor b2 xor b1 xor b0
1000 0000
1001 1000
0000 0000
0000 0000
0000 0000
---------
0001 1000

这个时候,有人就说,结果是1000B,不是1011B啊。实际上你根本没算完,你得到的结果是11000B,对于4bit CRC来说,这个结果是还没除完的,4bit CRC除法的结果不可能有第5位,只可能是4位。

所以 11000 xor 10011 = 1011 B = 0x0B

不知各位看官明白否?

本文标签: CRC  
本文Url: http://www.xjtudll.cn/Exp/273/ (出自: 鸟的天空)
我要引用: 点击这里获取该日志的TrackBack引用地址

相关文章:

269. CRC除法  (2013-5-18 8:30:40)

4 Comments

Write a comment ?