CRC基础知识的几个问题

Question

我是一名电子工程师，从纯数学角度考虑CRC并不重要。然而，我有以下问题：

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

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

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

- quantum231

Answer 1

我们在计算n位CRC时添加n个零，因为当将CRC附加到消息并发送整个消息（这是电信中的一种常见做法）时：

1. 这允许接收方处理CRC的位，就像处理消息的其余部分一样，从而导致对于任何无误传输都有已知的余数。当消息的结尾由跟随CRC的某些内容指示时（这是一种常见做法），在接收端它可以节省一个n位缓冲区，在发送端它几乎不增加复杂性（x(n)的额外项在CRC传输期间减少为AND门，强制消息位在CRC传输期间变为零，并且n个额外的约简步骤在CRC传输时执行）。 从数学上讲，发送的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)，这是零（或所述常量）。

2. 它确保同时影响消息末尾和连续CRC的错误突发受益于所选择的多项式提供的全面保护水平。特别地，如果我们将C(x)计算为M(x) mod P(x)，翻转M(x)的最后一位和C(x)的最后一位将不会被检测到，而大多数用于误差检测的多项式保证任何两位错误在某些大的消息大小上都可以被检测到。

常见做法是将用于误差检测的CRC多项式可被x+1整除，因为它确保检测到影响奇数位数的任何错误。然而，这种做法并非普遍适用，并且有时会阻止选择更好的多项式，以便对于某些m和n的组合，包括最大化消息长度，以便始终检测到m个错误（假设没有同步丢失）。特别地，如果我们想要能够检测到最长消息的任何2位错误（包括n位CRC的2^n-1位），则需要使多项式为原始多项式，因此为不可约多项式，因此（对于n>1）不能被x+1整除。

通常情况下，用于误差检测的CRC多项式不可被x整除，因为否则生成的CRC的最后一位将是恒定的，并且不会对消息+CRC的其余部分中的错误检测有所帮助。

- fgrieu

---

非常好的回答，加1。我只想补充一下，添加_n_个零是CRC的定义的一部分，但几乎从不包括在实现中。软件或硬件中的CRC可以并且几乎总是采用避免这些额外_n_步骤的方式进行实现。对于问题3，我认为它确实是普适的。如果多项式没有1项，则不是CRC。 - Mark Adler

@Mark Adler：已经采纳了您的意见。我猜您就是Adler-32的Mark Adler，对此我表示赞赏！ - fgrieu

嗯，我需要更多时间思考第二个问题的答案。顺便问一下，在第二个问题中，“它防止多项式不可约”是什么意思？为什么我们想要不可约多项式？ - quantum231

@quantum231：修正了关于2的参数，这个参数在使用不可约多项式时的理由是错误的。现在我至少给出一个好的理由：这样多项式可以是原始的，从而最大化所有2位错误都能被检测到的消息长度。 - fgrieu