请推荐一种使用非常奇怪的数据通道的纠错算法。
channel 由两部分组成:Corrupter 和 Eraser。
Corrupter 收到一个由 3 个符号字母表中的 10000 个符号组成的单词，比如 {'a','b','c'}。
Corrupter 以 10% 的概率更改每个符号。
示例:
Corrupter input: abcaccbacbbaaacbcacbcababacb...
Corrupter output: abcaacbacbbaabcbcacbcababccb...
橡皮擦接收损坏的输出并以 94% 的概率删除每个符号。
Eraser 在 4 符号字母表 {'a','b','c','*'} 中生成相同长度的单词。
示例:
Eraser input: abcaacbacbbaabcbcacbcababccb...
Eraser output: *******a*****************c**...
因此，在橡皮擦输出中，大约 6%*10000=600 个符号不会被删除，其中大约 90%*600=540 个会保留其原始值，大约 60 个会损坏。
什么带纠错的编解码算法最适合这个 channel ？
如果成功解码的概率 > 99.99%，可以传输多少有用数据？
是否可以通过此 channel 传输 40 个字节的数据？ (256^40 ~ 3^200)
以下是您至少可以分析的内容:
将您的 40 个字节分成 13 个 25 位 block (有一些浪费，所以这个位显然可以改进)
2^25 < 3^16 因此您可以将 25 位编码为 16 a/b/c“trits”——再次浪费意味着改进的余地。
有了 10,000 个可用的 trits，您可以为 13 个编码字节三元组中的每一个提供 769 个输出 trits。在 16 个 trits 上选择(可能是随机的)769 个不同的线性(mod 3)函数——每个函数由 16 个 trits 指定，你在这些 trits 和 16 个输入 trits 之间取一个向量点积。这为您提供了 769 个输出 trits。
通过考虑所有可能的 (2^25) block 来解码并选择与大多数幸存的 trits 匹配的 block 。只要至少有 16 个幸存的 trits，你就有希望得到正确的答案，我认为 excel 通过 BINOMDIST() 告诉我的情况经常发生，很有可能所有 13 个都会发生25 位 block 。
我不知道你从乱码中得到的错误率是多少，但随机线性码有一个很好的声誉，即使由于我的脑死亡解码技术这个代码块大小很短。在最坏的情况下，您可以尝试模拟 25 位 block 的编码传输和解码，然后从那里开始计算。如果您假装乱码阶段也已删除并因此以略高的删除概率重新计算，您可以获得比上述错误率稍微更准确的下限。
我认为，如果您能够负担得起对每个 25 位 block 进行 2^25 次猜测以进行解码，那么这在实践中可能确实有效。 OTOH 如果这是类里面的一个问题，我猜你需要展示你对类里面已经讨论过的一些不太特别的技术的了解。