通过循环冗余校验（CRC）进行单比特错误检测

Question

我正在研究基于CRC生成器的单比特错误检测相关的问题，试图分析哪些生成器可以检测到单比特错误，哪些不能。

假设，如果我的CRC生成器多项式为x⁴+ x²。现在我想知道它是否能够保证检测到单比特错误呢?

根据参考资料1和2，我得出以下结论：

1) 如果k=1,2,3代表错误多项式x^k，则在除以生成多项式x⁴+ x²时，余数分别为x、x²、x³。根据这些参考资料，如果生成器具有多个项，并且x⁰的系数为1，则可以捕获所有单比特错误。但是它并没有说，如果x⁰的系数不为1，则无法检测到单比特错误。它所说的是：“在循环码中，那些可以被g(x)整除的e(x)错误是无法检测到的。”

2) 我必须检查E(x)/g(x)的余数，其中E(x)(假设为x^k)，k=1,2,3,...是错误多项式，g(x)是生成多项式。如果余数为零，则无法检测到错误，当余数为非零时，则可以检测到错误。

因此，根据上述两点，我认为生成多项式x⁴+x²可以保证检测到单比特错误。请确认我是否正确。

- ankit

Answer 1

如果x的0次方系数不为1，则无法检测单比特错误？如果x的0次方系数不为1，则相当于将CRC多项式向左移动1位（或更多位）（乘以某个x的幂）。将CRC多项式向左移动1位或更多位不会影响其检测错误的能力，它只是在码字末尾附加了1个或多个零位。 生成多项式x的4次方+x的2次方可以保证检测单比特错误。

正确。x的4次方加上x的2次方是将x的2次方加1左移两位得到的，x的4次方加上x的2次方等于(x的2次方)×(x的2次方加1)=(x的2次方)×(x+1)×(x+1)，而且由于x的2次方加1可以检测任何单个比特错误，因此x的4次方加上x的2次方也可以。另外，有(x+1)项（两个），它添加了一个偶校验检查，并且可以检测出任何奇数个比特错误。

---

通常情况下，所有的CRC多项式都能检测到单个比特错误，无论消息长度如何。所有的CRC多项式都有一个“循环”周期：如果你将CRC多项式作为线性反馈移位寄存器的基础，并且初始值为000...0001，那么经过一定数量的循环后，它将循环回到000...0001。CRC的最简单故障是出现2位错误，其中2位之间的距离等于循环周期。假设8位CRC（9位多项式）的周期为255，则在位[0]和位[255]处出现1个2位错误将导致CRC=0，无法被检测到。单个比特错误不会发生这种情况，它只会继续通过循环，其中没有包括值0。如果周期为n个循环，则如果消息+ CRC中的位数<= n，则不会发生2位错误失败。所有的CRC多项式都是任意多项式乘以（x + 1）的乘积，可以检测到任何奇数比特错误（因为x + 1本质上添加了一个偶校验检查）。

---

将CRC多项式向左移动z位意味着每个码字都将具有z个尾随零位。有些情况下会这样做。比如你有一个快速的32位CRC算法。为了将该算法用于16位CRC，17位CRC多项式向左移动16位，以便最不重要的非零项是x¹⁶。使用32位CRC算法计算后，将32位CRC向右移动16位以生成16位CRC。

- rcgldr