错误检测代码为33个字节,检测位在前32个字节中翻转

Question

您能否建议一种错误检测方案,用于检测33字节消息的前32个字节中的一个可能的位翻转,使用不超过8位的附加数据？

Pearson哈希能成为解决方案吗？

Answer 1

在任何消息中检测单个位翻转只需要一个额外的位,与消息的长度无关:只需将消息中的所有位xor组合在一起,然后将其添加到最后.如果任何单个位翻转,则末尾的奇偶校验位将不匹配.

如果您要求检测哪个位翻转,则无法完成,并且一个简单的参数显示:额外的8位可以表示多达256个类的32字节消息,但零消息和256个消息一个位上每个都必须在不同的类.因此,有257条消息必须明确分类,并且只有256类.

Answer 2

您可以在任何长度的消息中仅用一个额外的位来检测一位翻转（如@Daniel Wagner 所述）。简单地说，奇偶校验位可以指示 1 位的总数是奇数还是偶数。显然，如果错误的位数是偶数，则奇偶校验位将失败，因此您无法检测到 2 位错误。

现在，为了更容易理解为什么你不能只用 8 位来纠正 32 字节（256 位），请阅读汉明码（如在 ECC 内存中使用）。这种方案使用特殊的纠错奇偶校验位（以下称为“EC 奇偶校验”），它只对总位数的一个子集的奇偶校验进行编码。对于每个2^m - 1总位，您需要使用mEC 位。这些代表每个可能的不同掩码，遵循模式“x 位打开，x 位关闭”，其中x是 2 的幂。因此，一次的位数越多，您获得的数据/奇偶校验位比就越好。例如，总共 7 位将允许在丢失 3 个 EC 位后仅编码 4 个数据位，但在丢失 5 个 EC 位后，总共 31 个位可以编码 26 个数据位。

现在，要真正理解这一点，可能需要举个例子。考虑以下几组面具。前两行将自上而下读取，指示位数（我标记为 MSB 的“最高有效字节”）：

  MSB                                LSB
   |                                  |
   v                                  v
   33222222 22221111 11111100 0000000|0
   10987654 32109876 54321098 7654321|0
   -------- -------- -------- -------|-
1: 10101010 10101010 10101010 1010101|0
2: 11001100 11001100 11001100 1100110|0
3: 11110000 11110000 11110000 1111000|0
4: 11111111 00000000 11111111 0000000|0
5: 11111111 11111111 00000000 0000000|0

首先要注意的是，0 到 31 的二进制值在每列中从右到左表示（读取第 1 行到第 5 行中的位）。这意味着每个垂直列彼此不同（重要部分）。出于特定原因，我在位号 0 和 1 之间添加了一条垂直的额外线：列 0 没有用，因为它没有设置位。

为了执行纠错，我们将对接收到的数据位与每个 EC 位的预定义掩码进行按位与运算，然后将结果奇偶校验与 EC 位进行比较。对于发现不匹配的任何计算奇偶校验，找到仅设置这些位的列。例如，如果根据接收到的数据值计算错误纠正位 1、4 和 5 是错误的，那么第 25 列——仅在那些掩码中包含 1——必须是错误的位，可以通过翻转它来纠正. 如果只有一个纠错位是错误的，那么错误就在那个纠错位中。这是一个类比，可以帮助您理解为什么会这样：

有 32 个相同的盒子，其中一个装有大理石。您的任务是仅使用旧式秤（带有两个平衡平台以比较不同物体的重量的那种）来定位大理石，并且您只能尝试 5 次称重。解决方案相当简单：在秤的每一侧放 16 个盒子，较重的一侧表示大理石在哪一侧。丢弃较轻一侧的 16 个盒子，然后称重 8 和 8 个盒子，保持较重的，然后是 4 和 4，然后是 2 和 2，最后通过比较最后 2 个盒子的重量来定位大理石 1 比 1：最重盒子里装有大理石。您仅在 32、16、8、4 和 2 个箱子的 5 次称重中完成了任务。

同样，我们的位模式将盒子分成 5 个不同的组。往回看，第五个EC位决定了错误是在左边还是右边。在我们使用位 #25 的场景中，它是错误的，因此我们知道错误位位于组的左侧（位 16-31）。在 EC 位 #4 的下一个掩码中（仍在向后步进），我们只考虑位 16-31，我们发现“较重”的一侧又是左侧，因此我们缩小了位 24-31。沿着决策树向下，每次将可能的列数减半，当我们到达 EC 位 1 时，只剩下 1 个可能的位——我们的“盒子里的大理石”。

注意：这个类比很有用，但并不完美：1 位不是由弹珠表示——错误位的位置由弹珠表示。

现在，一些玩弄这些掩码并思考如何安排事物的人会发现存在一个问题：如果我们尝试制作所有 31 位数据位，那么我们还需要 5 位用于 EC。但是，那么，我们如何判断 EC 位本身是否错误呢？仅仅一个 EC 位错误就会错误地告诉我们某些数据位需要更正，我们将错误地翻转该数据位。EC 位必须以某种方式为自己编码！解决方案是将奇偶校验位放置在数据内部，在上面位模式中只设置一位的列中。这样，任何数据位错误都会触发两个EC 位是错误的，因此如果只有一个 EC 位错误，我们就知道它本身是错误的，而不是表示数据位是错误的。满足一位条件的列是 1、2、4、8 和 16。数据位将在这些位之间从位置 2 开始交错。（请记住，我们不使用位置 0，因为它永远不会提供任何信息-- 我们的 EC 位根本不会被设置）。

最后，为整体奇偶校验再增加一位将允许检测 2 位错误并可靠地纠正 1 位错误，因为我们可以将 EC 位与其进行比较：如果 EC 位表示某些错误，但奇偶校验位表示相反，我们知道有 2 位错误，无法进行更正。我们可以使用丢弃的位 #0 作为我们的奇偶校验位！事实上，现在我们正在编码以下模式：

0: 11111111 11111111 11111111 11111111

这给了我们最终总共 6 个错误检查和纠正 (ECC) 位。无限期扩展使用不同掩码的方案如下所示：

32 bits - 6 ECC bits = 26 data
64 bits - 7 ECC bits = 57 data
128 bits - 8 ECC bits = 120 data
256 bits - 9 ECC bits = 247 data
512 bits - 10 ECC bits = 502 data

现在，如果我们确定我们只会得到 1 位错误，我们可以省去 #0 奇偶校验位，因此我们有以下内容：

31 bits - 5 ECC bits = 26 data
63 bits - 6 ECC bits = 57 data
127 bits - 7 ECC bits = 120 data
255 bits - 8 ECC bits = 247 data
511 bits - 9 ECC bits = 502 data

这没有变化，因为我们不再获得任何数据位。哎呀！您要求的 32 字节（256 位）不能用单个字节进行纠错，即使我们知道在最坏的情况下只能有 1 位错误，并且我们知道 ECC 位将是正确的（允许我们移动它们）超出数据区域并将它们全部用于数据）。我们需要比我们多两个位——一个必须向上滑动到下一个 512 位范围，然后去掉 246 个数据位以获得我们的 256 个数据位。所以这是一个多 ECC 位和一个多数据位（因为我们只有 255，这正是 Daniel 告诉您的）。

总结:: 您需要 33 个字节 + 1 位来检测前 32 个字节中哪一位翻转。

注意：如果您要发送 64 个字节，那么您的比率低于 32:1，因为您可以仅在 10 位中进行错误纠正。但在实际应用中，ECC 的“帧大小”不能无限增加，原因如下：1) 一次处理的位数可能远小于帧大小，导致严重低效（想想 ECC RAM）。2）能够准确纠正一点的机会越来越少，因为帧越大，出现更多错误的机会就越大，2个错误无法纠正纠错能力，而3个或更多甚至可以击败错误-检测能力。3) 一旦检测到错误，帧大小越大，必须重传的损坏块的大小就越大。