algorithm - 哪种算法可以解决极高的非突发错误？

Question

我有一个错误率非常高的二进制流。错误率为 50%，这意味着每个位都有 50% 的机会被翻转。该错误不会以突发形式发生并且是完全随机的，因此 Reed-Solomon 码不能很好地工作。

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

这都是理论上的，所以问我是否可以减少流的错误是没有意义的。

编辑

不要说它不可能，它告诉你的第一个答案是有可能的噪声信道编码定理。

Answer 1

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

如果它实际上小于 50%（例如 50% 的位将是“随机”而不是“翻转”），那么您可以重复数据 - 传输每个位 128 次并计算出每 100 位您获得的更多已收到。那是简单的代码，非常低效，根本不是数学解决方案:)

Answer 2

好吧，Reed-Solomon 纠错的全部意义在于，大多数现实世界的错误都发生在突发中，因此您可以对数据进行交织和去交织。如果您的错误是完全随机的，即泊松分布，那么只需以简单、数学上有效的方式将冗余添加到流中即可。您可以看到的一件事是某种隐藏的马尔可夫模型，例如格子代码。 这基本上只是一种在数学上有效的添加冗余的方法。

另外，看看嘈杂的信道编码定理。 严格来说，它不适用于数字数据，但如果这些位的来源是某个模拟过程，或者如果您可以将您的位建模为好像它们是某个模拟过程的结果，它可以让您深入了解什么你能做的最好的可能是。这将防止您浪费时间试图做得比数学上可能的更好。

Answer 3

当信道接近 50% 的实际噪声率时，根本无法再传输任何信息。对于 Jon Skeet 的回答，如果错误率低于 50% 的噪声，那么您可以通过对预期数据进行更长的突发冗余和统计查看结果以对原始值有一定程度的信心来获取数据。然后将基于噪声的特征推导出给定长度所需的突发长度和置信水平。但是，请理解，您在这里所做的是有效地降低数据速率以提高传输流的净信噪比。

在您的问题中，您可能已将其排除在外，但更好的编码方案可能基于数据流本身的相对存在（或不存在）。换句话说，要传输一个二进制......发送一个 1/0 的交替流。要发送零，不发送任何内容，或者发送恒定电平。这个想法是发送（和接收）任何东西代表一种状态，而发送（和接收）任何东西都代表另一种状态。这将有效地类似于数据的一种双极编码。

Answer 4

如果您的错误率为 50%，则比特流是随机的，并且与原始比特流没有关联。就像您正在用完全随机的比特流对流进行异或运算，结果是完全随机的。您对此无能为力。

为了使任何方案起作用，翻转率必须低于 50%。当然，它可能高于 50%，但是您可以先反转流，然后像错误率低于 50% 一样对其进行处理。

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

Answer 5

噪声信道编码定理表明您实际上可以实现信道的香农容量。它并不是说通道具有非零容量！

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

Answer 6

你看过涡轮代码吗？

——马库斯

嗬！我误认为 50% 是随机的，而不是 50% 的翻转。

Answer 7

如果在任何给定的传输中恰好有50% 的位被翻转，而不是每个位都以 50% 的概率被翻转，您可以通过发送两位的传输来发送一些信息——发送 0 作为 00，发送 1 作为01.如果接收到的码字的第一位是1，则另一位不翻转。