0

请推荐一种使用非常奇怪的数据通道的纠错算法。

图表

通道由两部分组成：Corrupter 和 Eraser。

Corrupter 接收到一个由 3 符号字母表中的 10000 个符号组成的单词，例如 {'a','b','c'}。
腐蚀者以 10% 的概率更改每个符号。
例子：

Corrupter input:  abcaccbacbbaaacbcacbcababacb...
Corrupter output: abcaacbacbbaabcbcacbcababccb...

Eraser 接收到损坏的输出并以 94% 的概率擦除每个符号。
橡皮擦在 4 符号字母表 {'a','b','c','*'} 中产生相同长度的单词。
例子：

Eraser input:  abcaacbacbbaabcbcacbcababccb...
Eraser output: *******a*****************c**...

因此，在橡皮擦输出中，大约 6%*10000=600 个符号不会被擦除，其中大约 90%*600=540 个将保​​留其原始值，大约 60 个将被损坏。

哪种带纠错的编码-解码算法最适合这个通道？
如果成功解码的概率 > 99.99%，可以传输多少有用数据？
是否可以通过该通道传输 40 字节的数据？(256^40 ~ 3^200)

4

1 回答 1

1

这是您至少可以分析的内容：

将你的 40 字节分成 13 个 25 位块（有一些浪费，所以这个位显然可以改进）

2^25 < 3^16 因此您可以将 25 位编码为 16 a/b/c “trits” - 再次浪费意味着改进的余地。

有了 10,000 个可用的 trit，您可以为 13 个编码字节三元组中的每一个提供 769 个输出 trit。在 16 个 trits 上选择（可能随机）769 个不同的线性（mod 3）函数 - 每个函数由 16 个 trits 指定，并且您在这些 trits 和 16 个输入 trits 之间取向量点积。这为您提供了 769 个输出三重奏。

通过考虑所有可能的 (2^25) 块进行解码，并选择与大多数幸存的 trits 匹配的块。只要至少有 16 个幸存的三重奏，你就有希望得到正确的答案，我认为 excel 通过 BINOMDIST() 告诉我的情况经常发生，很有可能所有 13 个三重奏都会发生25 位块。

我不知道你从乱码中得到的错误率是多少，但随机线性码有很好的声誉，即使这个码块大小很短，因为我的脑死解码技术。在最坏的情况下，您可以尝试模拟 25 位块的编码传输和解码并从那里解决。如果你假装乱码阶段也被擦除，那么你可以获得比上面更准确的错误率下限，因此以略高的擦除概率重新计算。

如果你能负担得起每 25 位块的 2^25 次猜测来解码，我认为这实际上可能在实践中起作用。OTOH，如果这是课堂上的一个问题，我猜你需要证明你对课堂上已经讨论过的一些不太特别的技术的了解。

于 2013-02-20T21:34:22.097 回答