哪种算法可以处理极高的非突发错误？
我有一个错误率非常高的二进制流。 错误率为 50%，这意味着每个位有 50% 的机会被翻转。 该错误不会突发发生，并且完全是随机的，因此里德-所罗门码不能很好地工作。
我应该对流应用哪种方案或算法？ 我根本不关心开销。
这都是理论上的，所以询问我是否可以减少流的错误是没有意义的。
编辑
不要说它不可能，它的第一个答案告诉你这是可能的 噪声信道编码定理。
I have a binary stream that has a very high error rate. The error rate is 50% meaning each bit has a 50% chance of being flipped. The error does not occur in bursts and is completely random, so Reed–Solomon codes wouldn't work well.
Which scheme or algorithm should I apply to the stream? I don't care about the overhead at all.
This is all theoretical, so there's no point in asking if I could just reduce the error of the stream.
EDIT
Don't say its not possible, the very first answer it tells you it is possible with noisy channel coding theorem.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
如果错误率为 50%，那么这基本上就是随机噪声，不是吗？ 我的意思是，考虑只尝试传输一位。 如果您发送正确位的无限流，错误率为 50%，无论正确位是 1 还是 0，您都会得到一半 1 和一半 0。
如果它实际上小于 50%（例如，50% 的位将是“随机”而不是“翻转”），那么您可以重复数据 - 将每个位传输 128 次，并算出每接收 100 个位您将获得更多的数据。 这是一种易于编码、效率极低、根本不符合数学的解决方案:)
If the error rate is 50%, then that's basically random noise isn't it? I mean, consider just trying to transmit a single bit. If you send an infinite stream of the right bit, with a 50% error rate you'll get half 1s and half 0s whether the right bit is 1 or 0.
If it's actually less than 50% (e.g. 50% of the bits will be "random" rather than "flipped") then you could just repeat the data - transmit each bit 128 times and work out which you get more of for each 100 bits received. That's the simple-to-code, hugely inefficient, not mathematical at all solution :)
嗯，里德-所罗门纠错的全部意义在于，大多数现实世界的错误都是突发发生的，因此您可以对数据进行交错和解交错。 如果您的错误是完全随机的，即泊松分布，那么只需以简单、数学上有效的方式向流添加冗余就可以了。 您可以查看的一件事是某种隐藏的马尔可夫模型，例如 网格代码。基本上只是添加冗余的一种数学上有效的方法。
另外，请查看噪声信道编码定理。严格来说，它并不适用到数字数据，但如果这些位的来源是某种模拟过程，或者如果您可以将这些位建模就像它们是某种模拟过程的结果，那么它可以让您深入了解这些位的含义你能做的最好的可能就是。 这可以防止您浪费时间试图做得比数学上可能的更好。
Well, the whole point of Reed-Solomon error correction is that most real-world errors occur in bursts, so you interleave and de-interleave the data. If your errors are completely random, i.e. Poisson-distributed, then just adding redundancy to the stream in a straightforward, mathematically efficient way will work. One thing you could look at is some kind of hidden Markov model, such as trellis code. This is basically just a mathematically efficient way of adding redundancy.
Also, have a look at the noisy channel coding theorem. Strictly speaking, it doesn't apply to digital data, but if your source of these bits is some analog process, or if you could model your bits as if they were the result of some analog process, it could give you some insight into what the best you could do might be. This would prevent you from wasting time trying to do better than is mathematically possible.
当信道接近 50% 的真实噪声率时，就不再可能传输任何信息。 对于 Jon Skeet 的回答，如果错误率小于 50% 的噪声，那么您可以通过冗余地执行更长的预期数据突发来获取数据，并以统计方式查看结果，以达到对原始值的某种程度的置信度。 然后将基于噪声的特征导出给定长度所需的突发长度和置信水平。 然而，请理解，您在这里所做的实际上是降低数据速率，以提高传输流的净信噪比。
在您的问题中，您可能已经排除了这种选择，但更好的编码方案可能基于数据流本身的相对存在（或不存在）。 换句话说，要传输二进制......发送 1/0 的交替流。 要发送零、不发送任何内容或者发送恒定电平。 这个想法是发送（和接收）任何东西代表一种状态，发送（和接收）任何东西代表另一种状态。 这实际上类似于数据的一种双极性编码。
As the channel approaches 50% real noise rate, it no longer becomes possible to transmit any information at all. To Jon Skeet's answer, if the error rate is anything less than 50% noise, then you can get data through by doing longer bursts of the intended data redundantly and statistically looking at the result to some level of confidence in the original value. The needed burst length and confidence levels for a given length would then be derived based on a characterization of the noise. Understand, however, what you are doing here is effectively lowering the data rate to improve the net Signal to Noise Ratio of the transmitted stream.
In your question, you might have ruled this out as an option, but a better encoding scheme might be based on the relative existence (or not) of the data stream itself. In other words, to transmit a binary one....send an alternating stream of 1/0. To send a zero, send nothing or perhaps send a constant level. The idea is that sending (and receiving) anything represents one state and sending (and receiving) nothing represents the other state. This would effectively resemble a type of bipolar encoding of the data.
噪声信道编码定理表明，您实际上可以实现信道的香农容量。 它没有表示该通道具有非零容量！
如果您对通道中 100% 的位进行随机化，则其中 50% 将保持不变，因此您只需随机翻转 50% 的位。 很明显，您不能通过这样的通道发送任何数据——它的香农容量为零。
The noisy-channel coding theorem says you can actually achieve the Shannon capacity for the channel. It does not say the channel has nonzero capacity!
If you randomize 100% of the bits in the channel, 50% of them will be unchanged, so you only flip a random 50% of the bits. It should be obvious that you can't send any data over such a channel -- its Shannon capacity is zero.
如果错误率为 50%，则比特流是随机的，与原始比特流没有相关性。 这就像您将流与完全随机的比特流进行异或，结果是完全随机的。 你对此无能为力。
翻转率必须低于 50% 才能使任何计划发挥作用。 当然，它可能高于 50%，但是您可以先反转流，然后像错误率低于 50% 一样处理它。
如果错误是完全随机的并且非常频繁（例如，25% 的位被翻转），则很难提出稳健的错误检测方案。 您需要添加大量冗余。
If your error rate is 50% the bit stream IS random and bears NO CORRELATION to the original bit stream. It is like you are XORing the stream with a completely random bit stream, and the result is completely random. And there is nothing you can do about it.
The flip rate must be below 50% in order for any scheme to work. Of course, it could be ABOVE 50%, but then you can first invert the stream and then process it like if the error rate was below 50%.
If the errors are completely random and very frequent (e.g. 25% of the bits are flipped), it is very difficult to come up with a robust error detection scheme. You need to add a significant amount of redundancy.
你研究过涡轮码吗？
——马库斯
Q 哦！ 我误读为 50% 随机，而不是 50% 翻转。
Have you looked into turbo codes?
-- MarkusQ
Doh! I misread that as 50% randomized, not 50% flipped.
如果恰好在任何给定的传输中翻转了 50% 的位，而不是每个位以 50% 的概率翻转，则可以通过发送两个位的传输来发送一个信息位 - 发送一个0 为 00，1 为 01。如果接收到的码字的第一位为 1，则另一位不翻转。
If exactly 50% of the bits are flipped in any given transmission, rather than each bit being flipped with 50% probability, you can send a bit of information by sending a transmission of two bits -- send a 0 as 00 and a 1 as 01. If the first bit of the received codeword is 1, then the other bit is unflipped.