背景

数据校验一般都用 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. 数据尽可能长。

但其实还有两个维度：

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

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

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

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

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