• Github 中文镜像
Sign inSign up
Watch966
Star102.4k
Fork61.8k
Branch: master
Switch branches/tags
Branches
Tags
  • master
  •  
K / CRC 循环冗余算法最佳长度的选择.md
移动浏览 Clone
加载中...
到移动设备上浏览
35 lines 4.78 KB
First commit on 25 Nov 2022

    背景

    数据校验一般都用 CRC 循环冗余算法,CRC 也是有碰撞的,对于给定长度的数据,如何选择一个碰撞最小的 CRC 长度,我做了一点“细微的”研究。

    最开始我以为只要选择一个 CRC 的长度就可以了,类似对于特定长度的数据,只要知道 CRC-8 或 CRC-16 还是 CRC-32 哪个是最短的且不会碰撞就行了,最终发现实际并不是这样简单地选择,而是一种权衡。

    搜了一圈中文资料都是算法讲解,没有关于“选择”的文章,于是改搜英语资料。

    初步

    最先找的是英文版的 Wikipedia,里面提到了可校验的最大数据长度和 CRC 多项式的指数相关,给了两个计算方式:\( 2^r - 1 \) 或 \( 2^{r-1} - 1 \)(因为有原始多项式和生成多项式两种多项式)。

    这样算的话,CRC-8 可校验的数据长度(单位是 bit)就是 \( 2^8 - 1 = 127 \) 或 \( 2^{8-1} - 1 = 63 \)。

    CRC-16 可校验 65535 bit 约 8KiB 或 32765 约 4KiB。

    但是我在 Stack Overflow 上看到了一些讨论,关于长度的选择并不是这么简单计算的。

    进阶

    在上面那篇讨论中有人提到一篇论文《Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Network》,我下载看了一遍,感谢 Google 翻译。《循环冗余码(CRC)在嵌入式网络中的多项式选择》是机翻版本,不能直接作为中文读,但是可以对比着看。

    论文中最重要的思想是探索关于 CRC 大小、消息长度和可达到的汉明距离(HD)之间的关系。这里汉明距离的大意是用于衡量“出现了给定位数的错误,却无法校验出来”的一个指标,而这个数字不是固定的,所以多项式的选择是一种权衡,而不是简单判断。

    最终情况是:不光是选择多项式的位数,还要选出一个表现尽可能好的值。

    论文摘要

    表格 1,以第一行为例,对于 48 位长度的数据,多项式 0x8810 有 84 个 4 位错误校验不出来,2430 个 6 位错误校验不出来,因为 4 位已经出现校验不到的情况,所以标记 HD = 4

    到这里,似乎只是 HD 的值越大越好。

    图形 1,多项式 0x15 对于 10 位数据可以提供 HD = 4 的检验,0x12 只能做到 HD = 3,但是数据超过 10 位后,0x15 的 HD 值就只有 2 了,而 0x12 可以将 HD = 3 保持到 26 位数据长度,数据再长才会降到 HD = 2

    对于很短的数据(小于 11 位),选择 0x15 更好,但如果是 16 位的数据呢?0x12 才是更好的选择,所以 CRC 的选择不是线性判断的。

    现在主要围绕 HD 的值来考虑了两个维度:

    1. HD 的值尽可能大。
    2. 数据尽可能长。

    但其实还有两个维度:

    1. 相同 HD 值和数据长度的情况下,无法校验出的错误数量的多少。
    2. 数据超过规定的最大长度后,表现如何。

    后面论述的就是关于这几个维度的加权取舍,不做研究的不用细看,可以直接看结果。

    表格 3,格子里面上面的数字是数据长度,下面是多项式,有下划线的多项式说明是论文认为比较好的选择,大体的选择原则是:

    如果你有 119 位长度的数据,想选择 CRC-8,那么 HD = 40x97 是最好的选择,但如果你的数据是 247 位,HD = 30xA6 可能是更好的选择。

    最后还有一个大表,比表格 3 更详细,就不截取了,直接看原文