information-theory - 纠错码上限

Question

如果我想发送一个 d 位数据包并添加另一个 r 位用于纠错码 (d>r)
，我最多可以找到并纠正多少个错误？

Answer 1

您有 2^d 种不同类型的长度为 d 位的数据包要发送。向它们添加 r 位会使它们成为长度为 d+r 的代码字，因此现在您可以发送 2^d 个可能的代码字。接收方可以获得 2^(d+r) 个不同的接收字（可能有错误的码字）。那么问题就变成了，你如何将那些 2^(d+r) 接收到的词映射到 2^d 码字？

这归结为代码的最小距离。也就是说，对于每对码字，找出它们不同的位数，然后取这些值中的最小值。

假设您的最小距离为 3。您收到了一个单词，并且注意到它不是代码字之一。也就是说，有一个错误。所以，由于缺乏更好的解码算法，你翻转第一位，看看它是否是一个码字。如果不是，则将其翻转并翻转下一个。最终，您会得到一个密码字。由于所有代码字在 3 个位置上不同，因此您知道该代码字与接收到的字“最接近”，因为您必须翻转接收到的字中的 2 位才能到达另一个代码字。如果一次只翻转一位没有得到一个码字，你就无法确定错误在哪里，因为你可以通过翻转两位得到多个码字，但你知道至少有两个错误。

这导致了一般原则，即对于最小距离 md，您可以检测 md-1 错误并纠正 floor((md-1)/2) 错误。计算最小距离取决于您如何生成代码字（也称为代码）的详细信息。您可以使用各种界限来根据 d 和 (d+r) 计算 md 的上限。

保罗提到了汉明密码，这是一个很好的例子。它达到了汉明界。对于 (7,4) 汉明码，您有 4 位消息和 7 位码字，并且您实现了 3 的最小距离。显然*，您永远不会获得大于您添加的位数的最小距离所以这是你能做的最好的。不过不要太习惯这个。汉明码是非平凡完美码的少数示例之一，其中大多数的最小距离小于您添加的位数。

*这不是很明显，但我很确定这对于非平凡的纠错码是正确的。添加一个奇偶校验位可使您的最小距离为 2，从而使您能够检测到错误。由 {000,111} 组成的代码只需添加 2 位，就可以得到 3 的最小距离，但这很简单。

Answer 2

您可能应该阅读有关此的维基百科页面：

http://en.wikipedia.org/wiki/Error_detection_and_correction

听起来您特别想要一个汉明码：

http://en.wikipedia.org/wiki/Hamming_code#General_algorithm

使用该方案，您可以从链接表中查找一些示例值。