18

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

如果使用 Reed Solomon 纠错，将 4 个“奇偶校验”字节附加到 4 个“数据”字节的末尾，例如 DDDDPPPP，那么您最终会得到 DDDEPPP（其中 E 是一个错误）并且一个奇偶校验字节已被丢弃，我不相信有办法重建初始消息（尽管如果我错了，请纠正我）......

将最初的 4 字节消息乘以一个常数（或执行另一个数学运算），然后利用逆数学运算的属性来确定丢弃了什么字节呢？或者，对消息的结构施加一些限制，因此每隔一个字节需要是奇数，而其他字节需要是偶数。

或者，它也可以是 4 个十进制数字，而不是字节，以某种方式编码为 8 个十进制数字，在上面提到的相同情况下可以检测和纠正错误 - 不重新传输并且不知道丢弃字节的位置。

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

编辑：

这可能有点做作，但我试图解决的情况是你有一个故障打印机，可以将重要的数字打印到表格上，然后邮寄给使用 OCR 的处理公司阅读表格。OCR 不会是完美的，但它应该很接近，只有数字可以读取。有故障的打印机可能是一个更大的问题，它可能会丢失一个整数，但无法知道它会丢失哪个，但它们总是会以正确的顺序出现，不会交换任何数字。

可以更改表格，使其始终在最初的四个数字和纠错数字之间打印一个空格，即 1234 5678，这样人们就会知道是丢弃了 1234 初始数字还是丢弃了 5678 纠错数字，如果这样的话使问题更容易解决。我的想法有点类似于他们通过算法验证信用卡号码的方式，但是是四位数的。

希望这可以澄清我在寻找什么......

4

7 回答 7

4

在没有“好的”代数结构的情况下，我怀疑很难找到一个简洁的方案，让你一直到 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 处有一个不正确的评估，并且有六个正确的评估。

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

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

于 2010-03-06T23:08:42.440 回答
3

我认为您需要研究擦除代码可能会为您提供什么。我自己不知道任何界限，但也许某种 MDS 代码可以实现这一点。

编辑：快速搜索后，我找到了 RSCode库，在示例中它说

In general, with E errors, and K erasures, you will need
* 2E + K bytes of parity to be able to correct the codeword
* back to recover the original message data.

所以看起来 Reed-Solomon 代码确实是答案，你实际上可以从 8,4 代码中的一个擦除和一个错误中恢复。

于 2010-03-06T21:11:54.800 回答
1

只要两个不同的数据字节不受错误或丢失的影响，并且只要错误不等于任何数据字节，而奇偶校验字节丢失，奇偶校验码就可以工作，恕我直言。

于 2010-03-06T21:33:40.817 回答
1

纠错码通常可以处理擦除，但在文献中假设擦除的位置是已知的。在大多数情况下，当对可以从信道中检索到正确数据的置信度较低时，解调器将引入擦除。例如，如果信号不是明确的 0 或 1，则设备可以指示数据已丢失，而不会有引入错误的风险。由于擦除本质上是已知位置的错误，因此它们更容易修复。

我不确定您的情况是什么情况下您可能会丢失单个值，并且您仍然可以确信剩余的值以正确的顺序传递，但这不是经典编码理论所解决的情况。

上面的算法专家建议是这样的：如果您可以将自己限制为仅 7 位信息，则可以用交替的 0 和 1 填充每个字节的第 8 位，这样您就可以知道丢失字节的位置。也就是说，将 0 放在字节 0、2、4、6 的高位中，并将 1 放在其他字节的高位中。在接收端，如果您只接收到 7 个字节，则丢失的字节将在高位匹配的字节之间被丢弃。不幸的是，这并不完全正确：如果擦除和错误是相邻的，你不能立即知道哪个字节被丢弃了。例如，高位 0101101 可能是由于丢掉第 4 个字节，或者是由于第 4 个字节中的错误并丢掉了第 3 个字节，或者是由于第 4 个字节中的错误并丢掉了第 5 个字节。

您可以使用线性代码：

1 0 0 0  0 1 1 1
0 1 0 0  1 0 1 1
0 0 1 0  1 1 0 1
0 0 0 1  1 1 1 0

（即，您将发送类似 (a, b, c, d, b+c+d, a+c+d, a+b+d, a+b+c) 的数据（其中加法是用 XOR 实现的，因为a,b,c,d 是 GF(128))) 的元素。它是一个距离为 4 的线性代码，因此它可以纠正一个单字节错误。您可以使用伴随式解码进行解码，并且由于代码是自对偶的，因此矩阵 H 将与上述相同。

如果有一个丢弃的字节，您可以使用上面的技术来确定它是哪一个。一旦你确定了这一点，你实际上是在解码一个不同的代码——通过删除给定字节创建的“穿孔”代码。由于打孔码仍然是线性的，您可以使用校正子解码来确定错误。您必须为每个缩短的代码计算奇偶校验矩阵，但您可以提前执行此操作。缩短的代码距离为 3，因此它可以纠正任何单字节错误。

于 2010-03-10T21:00:46.917 回答
0

在十进制数字的情况下，假设第一个数字是奇数，第二个数字是偶数，第三个数字是奇数，等等 - 用两个数字，你会得到 00-99，它可以用 3 个奇数/偶数/奇数位表示（总共 125组合） - 00 = 101, 01 = 103, 20 = 181, 99 = 789 等。因此，将两组十进制数字编码为 6 个总数字，然后最后两个数字表示关于第一组 2 个数字或 a某种校验和......我想，最后一位数字的下一个数字可能是每个初始 2 位初始消息中的某种奇数/偶数指示符（1 = 前 2 位偶数，3 = 前两位奇数）和遵循奇怪的模式。然后，最后一个数字可能是单个数字之和的一个位，这样如果缺少一个数字，它会立即显现出来，并且可以在假设最后一个数字正确的情况下进行更正。

于 2010-03-06T21:33:52.813 回答
0

如果我们假设错误字节中有 1 位错误，这在理论上是可能的。我们需要 3 位来识别丢弃的字节，3 位来识别错误的字节，3 位来识别错误的位。我们有 3 倍的额外位。

但是，如果我们需要识别错误字节中的任意位数错误，则需要 30 位。即使使用 32 位看起来也是可能的，尽管 32 对我来说有点太接近了。

但我不知道如何编码来获得它。试试涡轮码？

于 2010-03-10T17:49:22.730 回答
0

实际上，正如 Krystian 所说，当您更正 RS 代码时，消息和“奇偶校验”字节都会被更正，只要您有 v+2e < (nk) 其中 v 是擦除次数（您知道位置) 和 e 是错误的数量。这意味着如果您只有错误，您最多可以纠正 (nk)/2 个错误，或 (nk-1) 个擦除（大约是错误数量的两倍），或两者的混合（参见Blahut 的文章：Transform错误控制码和通用 Reed-Solomon 解码器的技术）。

更好的是，您可以检查校正是否成功：通过检查校正多项式仅包含 0 个系数，您知道消息+奇偶校验字节都是正确的。您可以在之前检查消息是否需要更正，也可以在解码后进行检查以检查消息和奇偶校验字节是否已完全修复。

边界 v+2e < (nk) 是最优的，你不能做得更好（这就是为什么 Reed-Solomon 被称为最优纠错码）。事实上，使用 bruteforce 方法可以超越这个限制，直到某个点（每 8 个符号可以多获得 1 或 2 个符号）使用列表解码，但它仍然是一个处于起步阶段的领域，我不知道任何可行的实际实施。

于 2015-05-13T12:26:48.007 回答