哪种算法可以实现极高的非突发错误？

Question

我有一个错误率非常高的二进制流。错误率为50％，意味着每个位有50％的机会被翻转。错误不会在突发中发生并且是完全随机的，因此Reed＆＃8211; Solomon代码将无法正常工作。

我应该将哪种方案或算法应用于流？我根本不关心开销。

这完全是理论上的，所以没有必要问我是否可以减少流的错误。

修改

不要说它不可能，它的第一个答案告诉你可以使用嘈杂的频道编码定理。

Answer 1

噪声信道编码定理说你实际上可以实现信道的香农容量。 不表示频道的容量非零！

如果随机化通道中100％的位，其中50％将保持不变，因此您只需随机翻转50％的位。很明显，你不能通过这样一个频道发送任何数据 - 它的香农容量为零。

Answer 2

如果错误率是50％，那基本上是随机噪音不是吗？我的意思是，考虑只是尝试传输一个位。如果发送右侧位的无限流，误差率为50％，则无论正确的位是1还是0，都会得到半个1和0的半。

如果它实际上小于50％（例如50％的位将是“随机”而不是“翻转”）那么你可以重复数据 - 每个位发送128次并计算出你得到更多对于每100位接收。这是简单的代码，非常低效，而不是数学解决方案：）

Answer 3

嗯，Reed-Solomon纠错的重点是大多数现实世界中的错误都是以突发形式发生的，因此您可以对数据进行交错和解交织。如果您的错误是完全随机的，即Poisson-distributed，那么只需以简单，数学上有效的方式向流添加冗余就可以了。您可以看到的一件事是某种隐藏的马尔可夫模型，例如格子代码。基本上只是一种数学上有效的添加冗余的方法。

另外，请查看嘈杂的信道编码定理。严格来说，它不是不适用于数字数据，但是如果这些位的来源是某些模拟过程，或者如果你可以模拟你的位就好像它们是某些模拟过程的结果，它可以给你一些洞察力你能做的最好的事情可能是什么。这可以防止你浪费时间试图做得比数学上更好。

Answer 4

当信道接近50％的实际噪声率时，根本不可能传输任何信息。对于Jon Skeet的答案，如果错误率低于50％噪声，那么您可以通过冗余地对预期数据进行更长时间的突发并在统计上将结果视为对原始值的某种程度的置信度来获取数据。然后，基于噪声的表征，导出给定长度的所需突发长度和置信水平。但是，要了解您在这里所做的是有效降低数据速率，以提高传输流的净信噪比。

在您的问题中，您可能已将此作为选项进行排除，但更好的编码方案可能基于数据流本身的相对存在（或不存在）。换句话说，传输二进制数据....发送1/0的交替流。要发送零，不发送任何内容或者发送一个恒定级别。这个想法是发送（和接收）任何东西代表一个状态，发送（和接收）没有代表另一个状态。这实际上类似于数据的双极编码。

Answer 5

如果错误率为50％，则比特流是随机的，并且与原始比特流无关。就像你用完全随机的比特流对流进行异或，结果是完全随机的。你无能为力。

翻转率必须低于50％才能使任何方案有效。当然，它可能超过50％，但是你可以先反转流，然后像错误率低于50％一样处理它。

如果错误是完全随机且非常频繁的（例如，25％的位被翻转），则很难提出鲁棒的错误检测方案。您需要添加大量冗余。

Answer 6

您是否查看了turbo代码？

- MarkusQ

卫生署！我误读为50％随机，而不是50％翻转。

Answer 7

如果完全 50％的位在任何给定的传输中被翻转，而不是以50％的概率翻转每个位，您可以通过发送两位传输来发送一些信息 - - 将0发送为00，将1发送为01.如果接收到的代码字的第一位为1，则另一位未被删除。