checksum - 关于CRC基础的几个问题

Question

我是一名电子工程师，并没有发现从纯数学角度考虑 CRC 很重要。但是，我有以下问题:

为什么我们在计算 CRC 时要在消息中添加 n 个零，n 是生成多项式的次数吗？我在模2长除法以及CRC的硬件实现中看到了这一点

为什么我们希望生成多项式可以被 (x+1) 整除？

为什么我们希望生成多项式不能被 x 整除？

Answer 1

我们添加 n计算 n 时为零-bit CRC 因为，当将 CRC 附加到消息并发送整个消息时(电信中的通常做法):

这允许接收方像消息的其余部分一样处理 CRC 的位，从而为任何无差错传输产生已知的余数。当消息的结尾由 CRC 后面的内容指示时，这尤其有用(一种常见做法)；在接收方，它保存了一个 n位缓冲器，并且在发送端它几乎没有增加复杂性(x(n) 的额外项减少到在 CRC 传输期间强制消息位为零的与门，并且在发送 CRC 时执行 n 额外的减少步骤)。
在数学上，发送的 CRC 是 (M(x) * x^n) mod P(x) = R(x) (也许，在一些常数内，或者/或者在 M(x) 的开头添加一些规定的位，对应于 CRC 寄存器的初始化)，并且在接收端计算的 CRC 超过了 M(x) 的串联。和 R(x) ， 那是(M(x) * x^n + R(x)) mod P(x) , 为零(或所说的常数)。

它确保影响消息结尾和连续 CRC 的突发错误受益于多项式选择提供的全级别保护。特别是，如果我们计算 C(x)如 M(x) mod P(x) , 翻转 M(x) 的最后一位和 C(x) 的最后一位当错误检测中使用的大多数多项式确保检测到任何大消息大小的任何两位错误时，将无法检测到。

通常的做法是让用于错误检测的 CRC 多项式被 x+1 整除。 ，因为它确保检测到影响奇数位的任何错误。然而，这种做法并不普遍，它有时会阻止为更好的一些有用定义选择更好的多项式，包括最大化消息的长度，使得 m对于 m 的某些组合，总是会检测到错误(假设没有同步丢失)和 n .特别是，如果我们希望能够检测最长消息的任何 2 位错误(这将是 2 n -1 位，包括 n -bit CRC)，我们需要多项式是原始的，因此不可约，因此(对于 n >1)不能被 x+1 整除.

用于错误检测的 CRC 多项式不能被 x 整除是普遍的做法。 ，因为否则生成的 CRC 的最后一位将是常数，并且无助于检测消息 + CRC 的其余部分中的错误。