纠错码上界

Question

如果我想发送一个d比特的数据包并为纠错码(d>r)添加另外的r比特

我最多能找到并纠正多少个错误？

Answer 1

您有2^d个长度为d比特的不同类型的数据包要发送。将r比特与它们相加，使它们成为长度为d+r的码字，因此现在您有2^d个可能的码字可以发送。接收器可以得到2^(d+r)个不同的接收字(可能有错误的码字)。然后问题就变成了，如何将这2^(d+r)个接收到的单词映射到2^d个码字？

这归结于代码的minimum distance。也就是说，对于每对码字，找出它们不同的比特数，然后取这些值中的最小值。

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

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

Paul提到了Hamming Code，这是一个很好的例子。它实现了Hamming bound。对于(7,4)汉明码，你有4比特的消息和7比特的码字，并且你得到的最小距离是3。显然，你永远不会得到比你添加的比特数更大的最小距离，所以这是你能做的最好的。不过，不要太习惯这一点。Hamming码是少数几个非平凡perfect code的示例之一，其中大多数都具有小于您添加的比特数的最小距离。

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

Answer 2

你可能应该阅读维基百科关于这个的页面：

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

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

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

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