1

我正在阅读有关错误检测的内容，偶然发现了一个我不太理解的声明。声明说“对于 ak 位字符串，我们需要 lg k 奇偶校验位来检测 2 位错误”。其中 lg 是以 2 为底的日志

我不太明白为什么这是真的，是否有任何正式的推导可以证实这一点。

这本书的名字是加拉赫格的数据网络。

我并不怀疑这本书所说的，但我只是好奇地看到了一个推导。

谢谢，钱德

4

2 回答 2

1

查看循环冗余检查的维基百科页面。严格来说，奇偶校验位是 1 位检查，因此谈论超过 1 个奇偶校验位可能是等效 CRC 的简写。文章“CRC 的数学”给出了更多的推导。

于 2010-09-22T09:25:58.647 回答
0

术语

  • 对于“线性”码（CRC、汉明码等），每个数据位总是影响一组固定的一些（但不是全部）奇偶校验位。例如，如果（仅）数据的第 7 位在传输过程中被翻转，并且在重新计算的奇偶校验位中翻转奇偶校验位 2 和 4 而不是奇偶校验位 5，与接收到的奇偶校验位相比，则翻转对于每个可能的有效载荷数据位帧，数据的第 7 位将翻转奇偶校验位 2 和 4，但不会翻转奇偶校验位 5 。
  • 有效载荷中影响特定奇偶校验位（例如奇偶校验位 5）的所有位，以及该奇偶校验位本身，都被该奇偶校验位“覆盖”或“保护”。

  • 当接收端重新计算奇偶校验位，并将重新计算的奇偶校验位与接收到的奇偶校验位进行比较时，差值称为校正子。当没有错误时，综合症为零。

    In other words, syndrome = recalculated_parity XOR recieved_parity.

证明

证明需要 n 个奇偶校验位来检测 2^n 位有效载荷数据位帧中的 2 位错误：

当整帧只有1个错误时，接收端重新计算奇偶校验位时，有两种情况：

  • 没有覆盖错误位的每个重新计算的奇偶校验位与相应的接收到的奇偶校验位相同。（校正子中的对应位为“0”）。
  • 覆盖错误位的每个重新计算的奇偶校验位与相应接收的奇偶校验位不同，并检测到错误。（校正子中的对应位是“1”）。

当整个帧中恰好有 2 个错误时，生成的校正子是每个单独错误引起的校正子的 XOR。当接收端重新计算奇偶校验位时，有3种情况：

  • (a) 每个重新计算的未覆盖任一错误位的奇偶校验位与相应的接收到的奇偶校验位相同。（校正子中的对应位为“0”）。
  • (b) 覆盖两个错误位的每个重新计算的奇偶校验位与相应的接收到的奇偶校验位相同。（每个错误翻转一次这样的位，并且两个翻转结合起来将该位返回到原始状态，因此校正子中的对应位为“0”）。
  • (c) 覆盖一个错误位但不覆盖另一个错误位的每个重新计算的奇偶校验位与相应接收到的奇偶校验位不同，并检测到错误。（校正子中的对应位是“1”）。

如果假设存在一些有效载荷位，因此翻转它会产生一些校正子 S，并且存在任何其他有效载荷位会产生完全相同的校正子 S，那么命中这两个位的两位错误将是不可检测的。换句话说，两位错误会产生S xor S == zero. 换句话说，每个奇偶校验要么是情况（a），要么是情况（b），两者都不能检测到这样的错误。那会很糟糕。

因此，为了检测帧中每一个可能的两位错误，我们必须设计错误检测代码，使得每个单位错误必须产生不同的校正子。换句话说，对于帧中两个错误位的每种可能情况，必须至少有一个类型为 (c) 的奇偶校验位。

使用 n 个奇偶校验位给出 n 个校正子位。对于 n 个校正子位，最多有 2^n 个可能的不同校正子。因此，为了确保帧中的每一位（当它是唯一错误时）给出不同的校正子，我们必须在帧中最多有 2^n 位。

我敢打赌，如果你在https://math.stackexchange.com/上发布这个问题，你会得到一个更短、更优雅的证明 :-)。

于 2013-05-31T04:24:33.127 回答