题

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

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

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

或者，代替字节，它也可以是以某种方式编码为 8 个十进制数字的 4 个十进制数字，其中在上述相同情况下可以检测和纠正错误 - 不重传并且丢失字节的位置未知。

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

编辑：

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

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

希望这可以澄清我正在寻找的内容......

有帮助吗？

解决方案

在没有“好”代数结构，我怀疑这将是很难找到让你一路10个** 4个码字的简明方案，因为理论上信息，没有很多的松弛。 （在一个下面可以使用GF（5）5 ** 5 = 3125）幸运的是，这个问题是足够小，你可以尝试Shannon的贪婪代码施工方法（找到一个码字与一个已经选择并不冲突，将其添加到集合）。

编码多达35个比特作为在GF四次多项式f（128）。评估八个预定点X0，...，X7和编码为0F（X0）1F（X1）0F（×2）1F（×3）0F（×4）1F（X5）0F（5233）1F（X7）的多项式，其中交替的零和一被存储在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和6分正确的评价。

有这些之外更多的可能性，但我们从来没有少于六个正确的评价，这足以恢复F。

其他提示

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

编辑：经过快速搜索后我发现 RS代码 图书馆和在 例子 它说 

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 代码中的一次擦除和一个错误中恢复。

奇偶校验码作为两个不同的数据字节不受到错误或损失，并且只要工作只要误差不等于任何数据字节而奇偶字节丢失，IMHO。

纠错码可以在一般手柄擦除，但在文献中擦除的位置被假定是已知的。在大多数情况下，擦除将由解调器被引入时，有低的置信度正确的数据可以从信道进行检索。例如，如果信号没有清楚地0或1，该装置能够指示数据丢失，而不是冒着引进的错误。由于擦除实质上是一个带有已知位置的误差，它们是固定变得更加容易。

我不知道你是什么情况，你可以失去一个值，你还可以相信，剩下的值在正确的顺序传递，但它不是古典的情况编码理论地址。

什么algorithmist上面提示是这样的：如果你可以限制自己只是信息的7位，您可以填写每个字节的第8位交替0和1，这将让你知道丢失的字节的位置。也就是说，在字节0，2，4，6中的高比特和在其他的高比特的1把一个0。在接收端，如果你只收到7个字节，缺少一个将被从其高位匹配字节之间下降。不幸的是，这是不完全正确：如果擦除和错误是相邻的，你不能马上知道哪个字节被放弃了。例如，高比特0101101可能导致脱落的第四字节，或从错误中的第4个字节并丢弃所述第三，或从错误中的第4个字节并丢弃所述第五

您可以使用线性代码：

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，所以它可以校正任何单字节错误。

在十进制数字的情况下，假定一个去与第一数字奇数，第二位数字偶数，第三位数奇数，等等 - 用两位数字，则得到00-99，其可在3奇/偶/奇数字来表示（125个总组合） - 00 = 101，01 = 103，20 = 181，99 = 789等，所以一个编码两套十进制数为6个总位数，那么最后两位数字，则意味着东西关于第一组的2数字或某种形式的校验和。第二天到最后的数字，我想，可以是在每个初始2位初始消息（1 =甚至前2个位数的某种奇/偶指示符的，3 =奇数前两个位）并按照为奇数的图案。然后，最后一个数字可能是个别数字的总和的人的地方，如果这样一个数字是丢失，它会立即显现出来，并可能被纠正假设最后一个数字是正确的。虽然，这会让事情了，如果最后两位数字的一个被放弃了......

它看起来是理论上可能的，如果我们假设在错误字节1个错误。我们需要3位来标识丢弃的字节和3位来标识错误字节和3位来识别错误位。我们有3次，许多额外的比特。

但是，如果我们需要找出错误的字节任何位数的错误的，它涉及到30位。即使是看起来是可能的32位，32虽然是有点太接近我的安慰。

但我不知道烫到编码来获取。尝试turbo码？

实际上，正如 Krystian 所说，当您纠正 RS 代码时，只要 v+2e < (n-k) 其中 v 是擦除次数（您知道位置），消息和“奇偶校验”字节都会被纠正），e 是错误数。这意味着，如果只有错误，则最多可以纠正 (n-k)/2 个错误，或 (n-k-1) 次擦除（大约是错误数量的两倍），或两者的混合（请参阅 布拉胡特的文章：错误控制码的变换技术 和 通用里德-所罗门解码器).

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

边界 v+2e < (n-k) 是最优的，你不能做得更好（这就是 Reed-Solomon 被称为最优纠错码的原因）。事实上，使用暴力破解方法可以超越此限制，达到一定程度（每 8 个符号您可以多获得 1 或 2 个符号），使用 列表解码, ，但它仍然是一个处于起步阶段的领域，我不知道有任何有效的实际实现。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top