algorithm - 简单的错误检查以替换闪存中的重复代码

Question

我在闪存中有一个 16 位字段，用于存储8 位数字（更具体地说，是从 0 到 254 的封闭范围内的值）。我想使用额外的 8+ 位进行错误检查（不需要纠错），最明显的方法是简单地重复该值两次。XMODEM数据包编号方法仅稍微不那么明显：将数字存储在第一个八位字节中，255 减去第二个八位字节中的数字。

是否有更好的选项可以在可用空间中提供更强大的错误检测，并且易于实施且执行速度快？也许可以利用闪存位更可能从1 变为 0而不是0 变为 1的事实？

Answer 1

预先注意：我认为 XMODEM 方法是合理的，所以我会接受它并开始做一些更重要的事情。无论如何，你用算法标记了这个问题，所以你也可以用证明这一点的方式来解决这个问题......

由于您需要错误检测，最重要的部分是可以检测到任何更改的单个位，因此数字的两个表示不能仅相隔一个位，最好它们尽可能相距遥远。此外，并非每一个位的变化都同样可能发生。

如果将其建模为图形，您将获得由 16 位数字标识的顶点以及定义该转换概率的两个顶点之间的有向边。这将是一个完整的图表，因此请考虑如何存储它（如果您完全存储它而不是按需计算它）。您现在正在搜索的是一个正好有 255 个顶点且最大权重的圆形路径。

为此，只需使用具有重边倾向的 DFS 搜索任何具有 255 个顶点的圆形路径。从这个圆圈中，取其最轻的边并从图中删除所有非较重的边。然后，在生成的（可能已断开连接！）图表中重复搜索一个图表，直到您再也找不到一个。

最后，将您的输入值映射到（其中一个）剩余圆圈的顶点 ID，以将它们存储在您的闪存中。

Answer 2

如果我正确理解了您的困境，那么您正在尝试检测由于使用闪存而消失的位。问题是如果它们在一个八位字节中消失，那么它们也会在其他八位字节中消失。所以这告诉你简单地复制是行不通的。

就个人而言，我会否定这个数字并存储它。这样，例如，如果值为 1（大部分为零），您将使用 11111110（大部分为 1），因此数据逐渐消失将是显而易见的。

如果退化到数据接近全零的地方真的很糟糕，那么问题就会变得更加严重。所以使用否定会有很大帮助，因为没有任何情况下所有数据都应该为零。