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

CRC查表法——表的由来

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

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

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

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

假设待测数据是0011 1110 B，生成多项式Poly是10011 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 B；b1= 100110 B；b0 = 10011 B；c1 = 0011 0000 B；c2= 1110 B；c3 = 0011 B

显然，a1=c1 xor c2，且c3是a1和c1的高4位

通过上面计算的过程可以看出，a1对b0 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有关的（这里的c3是4bit，即半字节）。

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则只能是直接计算法。

以下是CRC4，Poly = 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

不知各位看官明白否？

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

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

本文链接：https://xjtudll.cn/Exp/273/

标签: CRC
分享给朋友：
返回列表

上一篇：OKI DSR警告解决

下一篇：回历与公历换算

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

老管3DJ6有可以直接替换的TO-92封装的型号吗？

老管3DJ6有可以直接替换的TO-92封装的型号吗？莫非这是一只无可替代的型号？ 许多几十年前的“天价”三极管如今都有了性能更高的替换型号了，比如901x现在只卖几分钱一个。 但3DJ场效应管，好像没有发现可以直接替换的新型号。在网上搜索了一下，也没得到比较肯定的答案。 哪位...

Keil新增STC 51型号

Keil新增STC 51型号

STC官网提供的方法： （详见：http://www.mcu-memory.com/） 备份KEIL安装目录下的UV2.CDB或者UV3.CDB文件(在文件夹UV2或者UV3里面)，然后用STC提供的同名的CDB文件覆盖。 这种方法操作起来很简单，但缺点是在器件选型时，只能选择STC单片机，其他的都...

利用Excel绘制时序波形

利用Excel绘制时序波形

以Excel2007为例。 打开Excel，点击绘制表格边框按钮，如图所示。 利用“绘图边框”，按照自己的想法绘制波形，如下图所示。 拷贝波形，粘贴到Word。...

验证datatable是否被修改的问题

问题： 举个例子: 会员管理的修改  我先将会员详细信息存在一个datatable  User里面   然后 界面上的控件与该datatable一一绑定, 在用户保存的时候  验证该datatable是否被修改 来判断是否需要操作数据库 &...

BLE 128位UUID规定及使用

BLE 128位UUID规定及使用

参考资料： http://www.deyisupport.com/question_answer/wireless_connectivity/f/45/t/30862.aspx 问题： 私有profile必须要用128位的UUID？ 答案： 16bit UUID是SIG定义的，私有profile需...

C# 百分号格式化 保持原数不变

C# 百分号格式化 保持原数不变

C# 格式化数字 百分号 需求： 格式化数值为百分比 但是保持输入的数值不变 也就是不要C# 自带的格式化百分数 因为他会自动*100 再加上百分号 解决方案： % 外面套一层 ‘ ’Code var column = this.gridViewItemDet...

评论列表

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:
5年前 (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
zjmainstay IP:广东省
5年前 (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
感谢博主的文章！
5年前 (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)
回复该评论

发表评论

访客

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

Powered By Z-BlogPHP. Theme by TOYEAN.