错误校正码上限

Question

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

Answer 1

你或许应该阅读维基百科页面上这样的：

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

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

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

使用方案，你可以看一下来自链接表的一些示例值。

Answer 2

你有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的上限。

保罗提到了汉明码，这是一个很好的例子。它达到Hamming bound。对于（7,4）汉明码，你有4位信息和7位码字，并且你的最小距离为3。显然*，你永远不会得到大于你正在添加的位数的最小距离所以这是你能做的最好的事情。不要太习惯于这个。汉明码是非重要的少数例子之一perfect code，其中大多数的最小距离小于您添加的位数。

*这不是很明显，但我非常确定这是非常重要的纠错码。添加一个奇偶校验位可使您获得至少两个距离，从而可以检测到错误。由{000111}组成的代码通过添加2位来获得最小距离为3，但这很简单。