crc - 循环冗余校验：单位和双位错误

Question

在 Forouzan（数据通信和网络 5E）的书中找到了这一点。但是，无法理解这背后的逻辑。

这是在主题两个孤立的单位错误的上下文中

换句话说，g(x) 不能整除 x^t + 1，其中 t 介于 0 和 n - 1 之间。但是，t = 0 是没有意义的，需要 t = 1，我们将在后面看到。这意味着 t 应该在 2 和 n – 1 之间

为什么 t=1 在这里被排除在外？(x^1 + 1) 是两个连续的错误，也必须使用我们的 g(x) 正确检测到。

Answer 1

第三幅图表明 (x+1) 应该是 g(x) 的因子，但这会减少 CRC 保证检测从 n-1 到 (n/2)-1 的 2 位错误的最大长度，但是它提供了能够检测任何奇数位错误的优势，例如 (x^k + x^j + x^i) 其中 k+j+i <= (n/2)-1。

书中没有提到，有些生成器可以检测到 3 个以上的错误，但为了做到这一点，牺牲了消息的最大长度。

如果 CRC 可以检测到e错误，那么它也可以纠正 floor( e /2) 错误，但我不知道有一种有效的算法可以做到这一点，除了一个巨大的表查找（如果有足够的空间）。例如，有一个 32 位 CRC（十六进制：1f1922815 = 787·557·465·3·3）可以检测 7 位错误或纠正 3 位错误，消息大小高达 1024 位，但快速纠正需要 1.4千兆字节查找表。

至于“需要t = 1”，该书后来通过指出g（x）=（x + 1）无法检测相邻位错误来澄清这一点。在另一条语句中，这本书没有特殊情况 t = 0 或 t = 1，它指出，“如果生成器不能在 0 和 n-1 之间划分 (x^t + 1), t，那么所有孤立的双位错误可以检测到”，除非 t = 0，(x^0 + 1) = (1 + 1) = 0，这将是一个零位错误的情况。