可以在不增加额外位的情况下进行纠错和检测吗？

Question

我经历过像Hamming码这样的错误检测和校正技术，并且BCH码需要额外的奇偶校验位来检测和校正。在发送数据时，我们似乎总是通过添加奇偶校验和在检查错误时使用奇偶校验来引入纠错。

可以在不增加任何额外位的情况下进行错误检测和纠正？

Answer 1

一般情况下，不。假设您有一个数据向量x of k位，并且有一个位被错误翻转。除非错误的数据向量x'不是另一个有效的数据向量，否则没有检测的方法，更不用说纠正这一点了。

如果错误的向量x'不是有效的数据向量，并且可以进行检测，那么所有的k位都不能用作任意的数据位，因此您的数据速率低于k位，这意味着您在某种意义上使用奇偶。

更简单地说，如果没有奇偶校验位，那么所有2^k数据向量都是有效的，因此所有错误都会导致另一个有效的数据向量，使所有错误都无法检测。

由于校正比检测更难，所以相同的参数排除了校正，就像well.You无法检测到的那样。

Answer 2

不，是因为针孔原理。

假设您希望能够发送任意的k-bit消息。有2^k可能的位模式，2^k可能有预期的消息.

现在，假设您想要添加错误更正。这意味着，在您希望能够发送的2^k正确消息的基础上，您还希望能够发送一些不正确的消息(这些消息将在另一端被检测和修复)。每条不正确的消息都必须与每条有效的消息区分开来，否则就没有办法纠正它。

但是只有2^k位模式可用；如果您想要区分2^k正确的消息，再加上一些额外的不正确消息，那么您需要的不仅仅是k位。

(例如，为奇偶校验添加一位可以提供2^{k+1}可能的模式，足以满足2^k正确消息和2^k错误消息的需要。)

Answer 3

对于一般情况，柯德鲁斯回答解释说这是不可能的。为了检测或纠正错误，您需要有冗余。但许多信息都包含了冗余：

• 有些文件格式有固定的标头。
• 一些文件格式/协议只使用部分可用的符号空间。
• 某些信息只允许特定上下文中的某些信息。
• ..。

检测协议中只允许7位-ASCII码的传输错误的一种典型方法是使用第8位作为奇偶校验比特。所以你删除多余的信息，用允许错误检测甚至纠错的信息来代替它。

或者，如果您发送A类型的请求并期望A类型的响应，但得到B类型的响应，您就知道出了问题。