编码/纠错挑战

Question

编码和初始化4字节消息到8字节是否在数学上是可行的,如果8字节中的一个完全丢弃而另一个错误重建初始4字节消息？将无法重新传输,也不会知道丢弃字节的位置.

如果使用Reed Solomon纠错,并在4"数据"字节的末尾添加4个"奇偶校验"字节,例如DDDDPPPP,并且最终得到DDDEPPP(其中E是错误)并且丢弃了奇偶校验字节,我不相信有一种方法可以重建最初的信息(虽然如果我错了,请纠正我)......

如何将初始4字节消息乘以(或执行另一个数学运算)常数,然后利用逆数学运算的属性来确定丢弃的字节.或者,对消息的结构施加一些约束,因此每隔一个字节需要是奇数而其他字节需要是偶数.

或者,也可以是4个十进制数字,而不是字节,它可以以某种方式编码成8个十进制数字,其中可以在上述相同的情况下检测和纠正错误 - 没有重传和丢弃的字节的位置是未知的.

我正在寻找任何人可能拥有的任何疯狂的想法......有什么想法吗？

编辑:

它可能有点人为,但我想解决的情况是你有一个错误的打印机,它将重要数字打印到表格上,然后邮寄给使用OCR的加工公司阅读表格.OCR不会是完美的,但它应该只有数字才能读取.有故障的打印机可能是一个更大的问题,它可能会丢弃一个整数,但没有办法知道它会丢弃哪一个,但它们将始终以正确的顺序出现,不会有任何数字交换.

表格可以改变,以便它总是在最初的四个数字和纠错数字之间打印一个空格,即1234 5678,这样就可以知道是否丢弃了1234个初始数字或者删除了5678个纠错数字,如果是使问题更容易解决.我认为它们有点类似于他们如何通过算法验证信用卡号码,但是有四位数的块.

希望这能为我正在寻找的东西提供一些澄清......

Answer 1

在缺乏“好的”代数结构的情况下，我怀疑很难找到一个简洁的方案来让你一直得到 10**4 个码字，因为从信息理论上来说，没有太多的余裕。（下面的代码可以使用 GF(5) 来表示 5**5 = 3125。）幸运的是，问题足够小，您可以尝试香农的贪婪代码构造方法（找到一个与已选择的代码字不冲突的代码字，将其添加到集合中）。

将最多 35 位编码为 GF(128) 上的四次多项式 f。计算八个预定点 x0,...,x7 处的多项式并编码为 0f(x0) 1f(x1) 0f(x2) 1f(x3) 0f(x4) 1f(x5) 0f(x6) 1f(x7)，其中交替的 0 和 1 存储在 MSB 中。

解码时，首先看MSB。如果 MSB 与索引 mod 2 不匹配，则该字节已损坏和/或因删除而左移。假设它很好，并将其移回右侧（可能在一个点累积多个不同的可能值）。现在我们在已知点处对四次多项式 f 至少有七次求值，其中至多有一个是损坏的。我们现在可以尝试所有的腐败可能性。

编辑：bmm6o 提出了我的解决方案的第二部分不正确的主张。我不同意。

让我们回顾一下 MSB 为 0101101 的情况的可能性。假设 X 是发送的字节数组，Y 是接收的字节数组。一方面，Y[0]、Y[1]、Y[2]、Y[3] 具有正确的 MSB，并假定为 X[0]、X[1]、X[2]、X[3] 。另一方面，Y[4]、Y[5]、Y[6]具有不正确的MSB并且被假定为X[5]、X[6]、X[7]。

如果 X[4] 被删除，那么我们对 f 有七个正确的评估。

如果 X[3] 被丢弃并且 X[4] 被损坏，那么我们在 3 处有一个错误的评估，并且有 6 个正确的评估。

如果 X[5] 被丢弃并且 X[4] 被损坏，那么我们在 5 处有一个错误的评估，并且有 6 个正确的评估。

除此之外还有更多的可能性，但我们的正确评估永远不会少于六个，这足以恢复 f。