43

我见过 8 位、16 位和 32 位 CRC。

在什么时候我需要跳转到更广泛的 CRC？

我的直觉反应是它基于数据长度：

  1. 1-100 字节：8 位 CRC
  2. 101 - 1000 字节：16 位 CRC
  3. 1001 - ？？？字节：32 位 CRC

编辑：查看关于 CRC 和 Lott 答案的维基百科页面，这里有我们所拥有的：

<64 字节：8 位 CRC

<16K 字节：16 位 CRC

<512M 字节：32 位 CRC

4

7 回答 7

44

这不是一个研究课题。这真的很好理解：http ://en.wikipedia.org/wiki/Cyclic_redundancy_check

数学很简单。8 位 CRC 将所有消息归结为 256 个值之一。如果您的消息长度超过几个字节，则多条消息具有相同哈希值的可能性会越来越高。

同样，16 位 CRC 为您提供 65,536 个可用哈希值之一。任何两条消息具有这些值之一的几率是多少？

32 位 CRC 可为您提供大约 40 亿个可用哈希值。

来自维基百科文章：“最大总块长度等于2**r − 1”。那是一点点。你不需要做很多研究就能看到它2**9 - 1是 511 位。使用 CRC-8，超过 64 字节的多条消息将具有相同的 CRC 校验和值。

于 2010-02-23T21:13:11.167 回答
17

CRC 的有效性取决于多种因素。您不仅需要选择 CRC 的大小，还需要选择要使用的 GENERATING POLYNOMIAL。存在复杂且非直观的权衡取舍，具体取决于：

  • 通道的预期误码率。
  • 错误是倾向于突发还是倾向于分散（突发很常见）
  • 要保护的数据的长度——最大长度、最小长度和分布。

论文 Cyclic Redundancy Code Polynominal Selection For Embedded Networks 由 Philip Koopman 和 Tridib Chakravarty 撰写，发表在 2004 年国际可靠系统和网络会议论文集中，给出了很好的概述并提出了一些建议。它还提供了参考书目以供进一步理解。

http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

于 2012-01-16T23:58:40.683 回答
7

CRC 长度与文件大小的选择主要与以下情况相关：一个输入与“正确”输入的差异可能比“正确”输入相差三个或更少位，而不是一个差异很大的输入。给定两个大不相同的输入，对于大多数形式的 8 位校验值（包括 CRC），错误匹配的可能性约为 1/256，对于大多数形式的 16 位校验值（包括 CRC），错误匹配的可能性约为 1/65536等。CRC 的优势来自于它对非常相似的输入的处理。

对于 8 位 CRC，其多项式生成两个长度为 128 的周期，比未被检测到的更短的数据包中的单位、双位或三位错误的比例不会是 1/256——它将是零。同样，周期为 32768 的 16 位 CRC，使用 32768 位或更少的数据包。

但是，如果数据包长于 CRC 周期，则如果错误位之间的距离是 CRC 周期的倍数，则不会检测到双位错误。虽然这看起来不太可能发生，但 CRC8 在捕获长数据包中的双位错误方面比捕获“数据包完全加扰”错误要差一些。如果双位错误是第二常见的故障模式（在一位错误之后），那就太糟糕了。但是，如果任何破坏某些数据的东西可能会破坏很多数据，那么具有双位错误的 CRC 的劣质行为可能不是问题。

于 2016-09-14T19:23:55.067 回答
4

我认为 CRC 的大小更多地与您需要的 CRC 的独特性有关，而不是与输入数据的大小有关。这与您计算 CRC 的特定用途和项目数量有关。

于 2010-02-23T21:08:34.413 回答
3

应该根据消息的长度专门选择 CRC，这不仅仅是 CRC 大小的问题：http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf

于 2010-02-23T21:18:25.350 回答
2

这是对 CRC-N http://www.backplane.com/matt/crc64.html的一个不错的“真实世界”评估

我使用 CRC-32 和文件大小比较，并且在检查的数十亿个文件中，从来没有遇到匹配的 CRC-32 和文件大小冲突。但我知道有一些存在，而不是故意强迫存在。（被黑的技巧/利用）

进行比较时，您还应该检查“数据大小”。在正确的大小范围内，您很少会遇到具有匹配 CRC 的相同数据大小的冲突。

故意操纵数据以伪造匹配，通常通过添加额外数据直到 CRC 匹配目标来完成。但是，这会导致数据大小不再匹配。尝试暴力破解或循环遍历相同大小的随机或顺序数据，将留下真正狭窄的碰撞率。

您还可能在数据大小内发生冲突，这仅取决于所使用公式的一般限制，以及使用位/字节和以十进制为基础的系统的限制，这取决于浮点值，这些值会被截断和裁剪。

您想要考虑更大的一点是，当您开始看到许多无法“确认”为“原始”的碰撞时。（当它们都具有相同的数据大小时，并且（当反向测试时，它们具有匹配的 CRC。反向/字节或反向/位，或位偏移）

在任何情况下，它都不应该被用作唯一的比较形式，只是为了快速比较，用于索引。

您可以使用 CRC-8 来索引整个互联网，并将所有内容划分为 N 个类别之一。你想要那些碰撞。现在，通过预先排序，您只需检查 N 个目录之一，查找“文件大小”或“反向 CRC”，或者您可以对较小的数据集进行的任何其他比较，快速。 ..

在同一个数据块上向前和向后执行 CRC-32 比仅在一个方向上使用 CRC-64 更可靠。（或者 MD5，就此而言。）

于 2018-04-25T06:38:49.127 回答
0

您可以在任何大小的数据包中使用 CRC 检测单个位错误。检测双位错误或纠正单位错误受限于 CRC 可以采用的不同值的数量，因此对于 8 位，这将是 256；对于 16 位，65535；等 2^n

您可以通过前向纠错纠正的位数也受到多项式的汉明距离的限制。例如，如果汉明距离为 3，则您必须翻转 3 位才能从表示具有匹配 CRC 的一个有效消息的一组位更改为具有其自身匹配 CRC 的另一个有效消息。如果是这种情况，您可以自信地纠正一点。如果汉明距离为 5，则可以校正两位。但是当校正多个位时，您实际上是在索引多个位置，因此您需要两倍的位来表示两个校正位的索引，而不是一个。

通过前向纠错，您可以同时计算数据包上的 CRC 和 CRC，并获得残差值。零错误的好消息将始终具有预期的残差值（除非 CRC 寄存器的初始值不为零，否则为零），并且每个错误位位置都有唯一的残差值，因此使用它来识别位置。如果您曾经得到带有该残差的 CRC 结果，您就知道要翻转哪一位（或几位）来纠正错误。

于 2021-10-17T17:31:00.997 回答