algorithm - 错误检测和纠错算法

Question

假设我们有一大块数据来自具有以下属性的数据传输介质:

• 总 block 大小为 8 字节。
• 数据传输不可靠，因此可能会出现许多位错误。
• 数据传输是循环的， block 的开始是未知的。例如，代码 0123456789ABCDEF 与 3456789ABCDEF012 (0123456789ABCDEF << 12) 和 02468ACF13579BDE (0123456789ABCDEF << 1) 相同。接收端应根据代码自行确定开始。

这种情况下最好的错误检测和纠错算法是什么？当然，它始终是每个 block 的有用数据量和成功验证(纠正)概率之间的折衷。

Answer 1

这是从 http://en.wikipedia.org/wiki/Frame_Relay 中提取的一些想法的尝试。 .

从每个 64 位 block 开始，固定 header 为 01110。如果您有更多 header 信息(例如序列号或交替位标志、校验和...)，您可能可以安排位模式 01110 永远不会出现。对于任意数据，将任何出现的 0111 替换为 01111 - 这意味着有效数据速率现在取决于基础数据。让该层的数据提供者确保数据几乎是随机的，例如通过应用 http://en.wikipedia.org/wiki/Randomizer .我认为您这里的总数据丢失约为 6 位，这符合描述 0..63 移位所需的 6 位。

在接收器中，查找 01110 以标记 block 的真正开始。如果您看不到一个这样的模式，您就知道该 block 已被乱码。我认为至少需要两位错误才能破坏现有的 01110 并产生假的。

导致 block 未对齐的乱码看起来不像典型的位乱码，因此 CRC 错误率计算不会开箱即用。我会在每个 block 中包含一个非 CRC 校验和 - 可能是一个校验计算的 mod 31 或 mod 961，以避免禁止的 5 位模式 01110，尽管这取决于你可能需要更严格的限制。与多项式 CRC 不同，未检测到错误的几率约为 31 分之一或 961 分之一，与所有单个错误没有特别保证。

我认为您没有足够的空间来明智地进行每个 block 的纠错，但是您可以在每 M 个普通 block 之后包含 N 个纠错 block ，例如使用SECDED 向下应用到列中。你可能有例如57 个数据承载 block ，然后是 6 个纠错 block ，将每个有效负载位位置视为承载 57 个数据位，然后是 6 个校验和位。如果错误倾向于破坏单个 block 的全部或不破坏，这应该会很好地工作，例如通过导致 block 重新对齐失败。

评论后-

编辑

好的，对于一个连续传输的消息，您的带宽较少但 cpu 相对较多。我想到两件事:

1) 给定消息的任何类型的校验和或其他约束，您可以通过例如考虑所有单位错误，翻转接收到的消息的一部分，然后查看校验和现在是否有效。

2) 可以通过仅查看传递给消息的 5 位窗口来检查消息是否符合上面建议的位填充方案。我认为即使您需要调整它以在环绕时正常工作，这也是正确的。这意味着消息可以通过可处理大小的 BDD 检查(Knuth 4A 第 7.1.4 节)。这意味着您可以计算符合位填充方案的 64 位消息的数量，并在消息编号和消息(同一部分)之间进行高效转换。因此，您可以使用此方案，而无需对要发送的数据进行潜在的随机化或最坏情况假设，只需将其视为 0..N 范围内的数字编码(其中 N 将通过 BDD 计算)和64 位消息。事实上，不太优雅，我认为您可以使用具有 5 位状态的动态编程而不是 BDD。