当前位置:首页 > 技术心得 > 正文内容

CRC查表法——表的由来

xjtudll12年前 (2013-06-24)技术心得97396

为了更容易理解这篇文章,拿出纸笔跟着算一遍吧文中的一些假定: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

不知各位看官明白否?

扫描二维码推送至手机访问。

版权声明:本文由鸟的天空发布,如需转载请注明出处。

本文链接:http://xjtudll.cn/Exp/273/

标签: CRC
分享给朋友:

“CRC查表法——表的由来” 的相关文章

OKI编译器路径设置及uEase驱动的安装

OKI编译器路径设置及uEase驱动的安装

1、OKI编译器系统路径的设置 OKI的编译器环境IDEU8默认是安装到C盘的。在安装时,若选择到其他盘,则在默认设置下无法编译成功,编译报错。原因是默认的路径都是在C盘,要解决这个问题,必须重新设置系统路径。 设置步骤:File -> Environment settings -> S...

金蝶K3获取当前会计期间 以及会计期间的开始结束时间

SELECT @CurPeriod =CONVERT(smallint,FValue) FROM t_SystemProFile WHERE FCategory='IC' AND FKey='CurrentPeriod'   SELECT @CurYear =CONVERT(smallin...

CC254x android6.x无法配对

参考资料: https://e2e.ti.com/support/wireless_connectivity/bluetooth_low_energy/f/538/t/457958 问题: 配对时提示密码或PIN错误,但是根本就没有到输入密码这一步,就直接说密码错误了。 环境: android 6....

File.Create创建文件后,需要释放

重点就是要close if (!File.Exists(SavePath))             {       ...

电子元件E系列及R系列规格

电子元件E系列及R系列规格

由于工厂商品化生产的需要,电阻电容电感等电抗元件产品的规格是按一种特定数列提供的,考虑到技术上和经济上的合理性,目前主要采用E数列作为电抗元件规格。 E数列通项公式: 当E取不同数值时,计算所得数值四舍五入取近似值,形成数值系列。目前主要有E6,E12,E24,E48,E96,E192。对于...

远程计算机需要网络级别身份验证,而您的计算机不支持该验证

远程计算机需要网络级别身份验证,而您的计算机不支持该验证

问题:使用Win7可以连接服务器的远程桌面,使用XP不行。 服务器是Windows Server 2012 解决办法有两种: 一、修改本地电脑设置 参考资料:https://jingyan.baidu.com/article/380abd0a713f061d91192c63.html 1、点击开始...

评论列表

Q
Q IP:
3年前 (2022-04-10)

使用&quot;后注:&quot;中说明的方法消除了高4位产生的1.

q
q IP:
3年前 (2022-04-10)

另:如果多项式不同0000-0111也会在高4位中多产生1.

zjmainstay
zjmainstay IP:
4年前 (2020-09-09)

好吧,我算是看懂了。b0~b3对应c3的4个位置,当前位置为1时等于poly对应的偏移值,否则为0;
比如c3=1001,b3=Poly &lt;&lt;3; b2=0; b1 = 0; b0 = Poly &lt;&lt; 0
计算驱动表的时候,是c3左移4个位置作为测试护具,也就是c3=10010000,因此,驱动表的值为:c3^b3^b2^b1 = 10010000^10011000^0^0^10011 = 1000^10011=11011^10011=1000
感谢博主的文章!

xjtudll
xjtudll IP:
6年前 (2019-05-16)

这只是计算过程
CRC查表法本身无需再次判断,得表的过程已经判断完了。

xjtudll
xjtudll IP:
9年前 (2016-09-16)

笔误,应该是0

xjtudll
xjtudll IP:
9年前 (2016-06-01)

说白了,最高位如果是1,表明没除尽,还得继续除。对于CRC4来说,你的结果不可能是5位,只能是4位,所以当第5位是1时,意味着还没除尽,需要继续除。

xjtudll
xjtudll IP:
9年前 (2016-06-01)

1、简单的说下为什么可能少做了一次除法。以普通除法为例,你除以100,如果余数是101(当然实际上余数不可能为101,这个是类比),是不是还得继续除一次?
2、CRC16和CRC32均有查表法,我这里只是说表如何来的。实际上这个表网上大把,只是没告诉你怎么算来的而已。

abzhang
abzhang IP:
9年前 (2016-01-14)

我计算这个驱动表:感觉计算1000B 以后的(含),都是反的,
例如我计算1000B 结果是1000B, 但是实际结果是1011B
方法如下: 1000B, 则bit3=1,bit2=0,bit1=0,bit0=0
b3=10011000B
b2=00000000B
b1=00000000B
b0=00000000B
则 =10011000B 则结果取低4位 为1000B, 与表中(1011B)不符合。

xjtudll
xjtudll IP:
11年前 (2014-07-03)

你可能少做了一次亦或运算,CRC除法最高位是不能为1的。

q
q IP:辽宁省
3年前 (2022-04-10)

在第一个表(本文中共有2个表)中说明的计算驱动表的方法不全面,没有消除在高4位中多产生的1,如在1000-1111中就涉及这个问题,而在0000-0111中就不涉及这个问题.

Q IP: 回复:
使用&quot;后注:&quot;中说明的方法消除了高4位产生的1.
3年前 (2022-04-10)
q IP: 回复:
另:如果多项式不同0000-0111也会在高4位中多产生1.
3年前 (2022-04-10)
zjmainstay
4年前 (2020-09-09)

您好,有两个疑问麻烦帮忙解答下,谢谢!
1. b2 = (Poly&0) << 2 和 b3 = (Poly&0) << 3 是怎么推导出来的
2. C3=1000 0000的时候,b0=Poly,Poly不是10011么,怎么b0=0000 0000了,b3又怎么等于1001 1000?如果按1的推导,任意值&0都等于0,那b2和b3不是永远等于0么?

zjmainstay IP: 回复:
好吧,我算是看懂了。b0~b3对应c3的4个位置,当前位置为1时等于poly对应的偏移值,否则为0;
比如c3=1001,b3=Poly &lt;&lt;3; b2=0; b1 = 0; b0 = Poly &lt;&lt; 0
计算驱动表的时候,是c3左移4个位置作为测试护具,也就是c3=10010000,因此,驱动表的值为:c3^b3^b2^b1 = 10010000^10011000^0^0^10011 = 1000^10011=11011^10011=1000
感谢博主的文章!
4年前 (2020-09-09)
XJTUer
XJTUer IP:
6年前 (2019-03-04)

[F]Haha[/F]感谢楼主!写得很好,被CRC校验困扰了好几天,终于理解了!(虽然这个算法还是有些不完美,1000-1111B还需要额外判断是否除尽,但是也很不错了)。对了,惊奇发现咱俩是同一个学校的[QUOTE][/QUOTE]

xjtudll IP: 回复:
这只是计算过程
CRC查表法本身无需再次判断,得表的过程已经判断完了。
6年前 (2019-05-16)
士大夫
士大夫 IP:广东省
9年前 (2016-09-14)

在第一次计算时:
b3 = (Poly&0) << 3
b2 = (Poly&0) << 2
b1 = Poly << 1
b0=Poly
为什么C3=1000 时,
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)
括号里的bit=1,是什么意思?

xjtudll IP: 回复:
笔误,应该是0
9年前 (2016-09-16)
w7
w7 IP:
9年前 (2016-05-30)

1、您好,我看到了留言中的问题,发现我计算时也存在同样的问题,同时我也不理解什么是“少做了一次异或运算,crc除法最高位不能为1”,您能再解释一下吗?
2、如果是crc16这种生成多项式很长的,如何才能做到同时处理4位或者8位呢?因为太长了,不知道如何做除法啊移位啊等等
希望得到您的回复,谢谢!

xjtudll IP: 回复:
说白了,最高位如果是1,表明没除尽,还得继续除。对于CRC4来说,你的结果不可能是5位,只能是4位,所以当第5位是1时,意味着还没除尽,需要继续除。
9年前 (2016-06-01)
xjtudll IP: 回复:
1、简单的说下为什么可能少做了一次除法。以普通除法为例,你除以100,如果余数是101(当然实际上余数不可能为101,这个是类比),是不是还得继续除一次?
2、CRC16和CRC32均有查表法,我这里只是说表如何来的。实际上这个表网上大把,只是没告诉你怎么算来的而已。
9年前 (2016-06-01)
风行883
风行883 IP:四川省
11年前 (2014-07-01)

楼主,这个方法很好,对于0000-0111B我按照方法算了是正确的,但是从1000-1111B用楼主的方法算出来却是正好是两两相反的,比如1000B,按照方法C3=1000_0000B, b3=1001_1000B,b2=000_0000B, b1=00_0000B, b0=0_0000B,然后将c3 xor b3 xor b2 xor b1 xor b0得到的结果是1000B;而1001B得到的结果是1011B,正好和正确结果相反,1000-1111B均是如此,是我理解的有偏差吗?

abzhang IP: 回复:
我计算这个驱动表:感觉计算1000B 以后的(含),都是反的,
例如我计算1000B 结果是1000B, 但是实际结果是1011B
方法如下: 1000B, 则bit3=1,bit2=0,bit1=0,bit0=0
b3=10011000B
b2=00000000B
b1=00000000B
b0=00000000B
则 =10011000B 则结果取低4位 为1000B, 与表中(1011B)不符合。
9年前 (2016-01-14)
xjtudll IP: 回复:
你可能少做了一次亦或运算,CRC除法最高位是不能为1的。
11年前 (2014-07-03)

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。