networking - 通过 CRC(循环冗余校验)进行单位错误检测

Question

我正在研究一些与基于 CRC 生成器的单位错误检测相关的问题，并试图分析哪些生成器检测单位错误，哪些不检测。

假设，如果我有一个 CRC 生成多项式作为 x⁴ + x²。现在我想知道它是否保证检测到一位错误？

根据引用文献1和 2 ，我总结了一些观点:-

1) 如果误差多项式 x^k 的 k=1,2,3，则余数将为 x,x²,x³ 分别在生成多项式 x⁴ + x² 的多项式除法的情况下，根据引用文献，如果生成器有一个以上的项和 x ^的系数0 为 1 那么所有单位错误都可以被捕获。但它并没有说如果 x⁰ 的系数不为 1 则无法检测到单位错误。它是说“在循环码中，那些能被 g(x) 整除的 e(x) 错误不会被捕获。”

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

所以，根据我的说法，生成多项式x⁴ +x²保证了基于以上2点的单比特错误检测。请确认我是否对不对。

Answer 1

if coefficient of x⁰ is not 1 then single bit error can't be detected?

如果 x⁰ 的系数不为 1，则相当于将 CRC 多项式左移 1(或更多)位(乘以 x 的某个次方)。将 CRC 多项式左移 1 位或更多位不会影响它检测错误的能力，它只是将 1 位或更多零位附加到代码字的末尾。

generator polynomial x⁴ + x² guarantees the detection of single-bit error

正确。 x⁴ + x² 是 x² + 1 左移两位，x⁴ + x ² = (x²) (x² + 1) = (x²) (x + 1) (x + 1) ，并且由于 x² + 1 可以检测到任何一位错误，因此 x⁴ + x² 也可以。此外，对于 (x + 1) 项(其中两个)，它添加了偶数奇偶校验并可以检测任何奇数位错误。

---

一般而言，无论消息长度如何，所有 CRC 多项式都可以检测到单个位错误。所有 CRC 多项式都有一个“循环”周期:如果您使用 CRC 多项式作为 Linear Feedback Shift Register 的基础, 初始值为 000...0001，经过一定的循环次数后，会循环回到 000...0001。 CRC 最简单的故障是出现 2 位错误，其中 2 位之间的距离等于循环周期。假设 8 位 CRC(9 位多项式)的周期为 255，那么 2 位错误，一个在位 [0]，一个在位 [255] 将导致 CRC = 0，并且无法检测到，这单个位错误不会发生，它将继续经历循环，其中不包含值 0。如果周期为 n 个循环，则如果消息中的位数为 2 位错误，则不会失败+ CRC <= n。作为任何多项式乘积 (x + 1) 的所有 CRC 多项式都可以检测任何奇数位错误(因为 x + 1 本质上是添加偶数奇偶校验)。

---

将 CRC 多项式左移 z 位意味着每个代码字都将有 z 尾随零位。在某些情况下会这样做。假设您有一个快速的 32 位 CRC 算法。要将该算法用于 16 位 CRC，将 17 位 CRC 多项式左移 16 位，以便最低有效非零项为 x¹⁶。使用32位CRC算法计算后，将32位CRC右移16位得到16位CRC。