问题标签 [error-correction]

我需要为串行协议做一些设计，并且遇到了一些我认为必须在其他地方考虑过的问题。

所以我想知道是否有一些关于设计串行协议的最佳实践的建议。（请说明一个易于验证的事实，或者如果您提出索赔，请引用有信誉的来源。）也欢迎对网站/书籍的一般建议。

特别是我必须处理诸如

• 将字节流解析为数据包
• 验证数据包是否正确（例如，使用 CRC 很容易）
• 识别可能发生的合理错误类型（例如，在点对点串行流中，偶发的单比特错误和丢失的字节系列都是可能的，但不太可能出现额外的幻像字节；而在闪存中存储的记录或在磁盘驱动器上占主导地位的错误类型不同）
• 错误纠正或恢复（如果我检测到数据包中有错误，我可以纠正它吗？如果没有，我可以重新同步到下一个数据包的边界吗？）
• 如何使可变长度数据包对纠错/恢复具有鲁棒性。

有什么建议么？

我正在寻找一种在微控制器上编码相对容易/快速的前向纠错码；解码将在 PC 上完成，因此可能会更复杂。

我对纠错码了解不多，除了简单的汉明码之外，它们似乎都比我能处理的更复杂。

有什么建议吗？

编辑：我会缩短事情并接受卡尔的回答......我想有两件事我没有提到：

(1) 我并不严格需要纠错，这对我来说只是有利的，而且我认为可能有一些纠错算法可以以最小的成本获得合理的收益。汉明码可能非常合适，即使它们看起来对我的编码应用程序来说成本太高。

(2) 比纠错本身更大的优势是能够正确地重新同步到跟随错误的数据包。（如果我长时间不同步，那很糟糕）所以我认为保持简单会更好。

我正在上关于编码理论的数学课，我们必须为我们的学期标记做一个项目。

我的项目是一个带有回显服务器的客户端，它显示了从客户端到服务器然后返回的过程中引入了哪些错误。并测试不同的纠错方案的效率以及它们对这项任务的适用程度。

编码并不是真正的问题，我能够制作一些可以检测错误的东西，如果无法修复它们则要求重新传输等等。

我遇到的问题是，到目前为止，要引入任何类型的位错误，我必须人为地进行——因为其他数据传输层有自己的纠错协议。

我的问题：有没有办法解决这个问题？

我不知道我会怎么做，甚至不知道从哪里开始。

此外，我知道有些协议是我无法修改的，因此在这些级别的后台总是会进行纠错。但我想要的是能够假装其中一个层本身没有检查事物，然后我的应用程序将有机会扮演这个角色。

如果不能做到这一点，有什么好的方法可以模拟传输过程中引入的错误。即使是一个简单的通道示例，我也无法找到有关错误分布的统计信息。鉴于这些，我可以继续使用当前让服务器在消息中引入错误的方法。

Reed-Solomon 纠错是否适用于存在丢失字节（或多个丢失字节）的情况？例如，假设它是 (12,8) Reed Solomon 码，所以理论上它应该能够纠正 2 个错误（如果位置已知，则可以纠正 4 个擦除）。但是，如果只接收到 11（或 10）个字节并且不知道丢弃了哪些字节，会发生什么？Reed-Solomon 纠错会起作用吗？

谢谢，
本

我有一个应用程序，理想情况下，它允许使用 12 到 16 个字节（8 位字节）长的原始消息来纠正 25% 的错误。限制是消息不能被重新传输，如果没有收到部分消息，则不知道哪些字节没有显示。例如，假设我正在使用 Reed Solomon 之类的东西，并且我在最初的 16 字节消息中添加了 8 个字节的代码字，这将适合 25% 的错误被纠正，但如果 24 个中只有 20 个呢？实际接收到的字节数？是否有纠错算法或算法组合可以纠正这种情况？

谢谢，
本

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

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

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

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

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

编辑：

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

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

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

是否有用于 Java 的 ECC（纠错码）库（例如 Reed-Solomon）的知名实现，具有友好的开源许可（非 GPL）？

我在工作中进行了一些单元测试，其中一个断言出现了一个特殊的错误。请注意，expectedValue 和 actualValue 都是双精度值。

例外声明它们不相等，详细说明“预期值：<6.8> 实际值：<6.8>”。

预期值是硬编码的 6.8，而实际值是使用通过我们的分类方法（例如 Equal Records 或 Jenks Natural Breaks）的数据库值制定的。

我的猜测是，差异可能是 2 个值的尾数相似，直到最低有效位。我更新了测试以包含一个 epsilon 以查找这两个值是否足够接近，但我很好奇是否有一种方法可以强制尾数与我显示该双精度的显示值相匹配。是否存在这样的尾数校正？

问题

我试图通过组合来自三个不同 OCR 系统（tesseract、cuneinform、ocrad）的输出来改进 OCR 过程的结果。我已经进行了图像预处理（去歪斜、去斑、阈值处理等等）。我不认为这部分可以改进很多。通常要识别的文本长度在 1 到 6 个单词之间。文本的语言是未知的，并且经常包含幻想词。我在 Linux 上。首选语言是 Python。

到目前为止我所拥有的

通常每个结果都有一两个错误。但他们在不同的字符/位置有错误。错误可能是它们识别出错误的字符或它们包含不存在的字符。他们不经常忽略一个角色。

一个示例可能如下所示：

AX 是错误识别字符，Y 是文本中不存在的字符。空格替换为“_”以提高可读性。

在这种情况下，我会尝试结合不同的结果。在三对之间重复使用“最长公共子串”算法，我可以获得给定示例的以下结构

但是我现在被困在这里。我无法将这些部分组合成一个结果。

问题

你有

• 一个想法如何组合不同的常见最长子串？
• 或者你有更好的想法如何解决这个问题？

我知道使用 CRC 的全部目的是进行错误检测，但我听说有人说除了错误检测之外，它还可以用来进行基本的纠错。我很好奇是不是这样，如果是这样，它有多强大？我的意思是，我们通常将 CRC 称为能够执行 x 位检测，但我很好奇它是否能够执行 x 位校正。如果是这样，这是如何工作的？谢谢。