2

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

皮尔逊散列可以成为一个解决方案吗？

4

3 回答 3

7

检测任何消息中的单个位翻转只需要一个额外的位，与消息的长度无关：只需将消息中的所有位异或在一起，然后将其附加到最后。如果任何单个位翻转，最后的奇偶校验位将不匹配。

如果您要求检测哪个位翻转，这是无法做到的，并且一个简单的参数显示它：额外的八位可以表示多达 256 类 32 字节消息，但零消息和 256 条消息每一位都必须属于不同的类别。因此，有 257 条消息必须明确分类，只有 256 类。

于 2011-08-26T01:37:29.047 回答
5

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

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

摘要：：您需要 33 字节 + 1 位来检测前 32 字节中翻转的位。

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

于 2012-12-27T07:41:01.723 回答
1

如果您需要使用整个字节而不是一个位，并且只需要检测错误，那么标准的解决方案是使用循环冗余校验 (CRC)。有几种著名的 8 位 CRC 可供选择。

CRC 的典型快速实现使用包含 256 个条目的表来一次处理一个字节的消息。对于 8 位 CRC，这是 Pearson 算法的一个特例。

于 2011-08-26T07:11:09.557 回答