algorithm - 丢失位的纠错码

Question

如果我们必须从发送方接收数据作为一大块位（比如 8 位）。

但是，传输不可靠，导致比特丢失。（不是位翻转）这意味着，块中的任何位都可以不存在，并且接收器将仅接收 7 位。

我研究了一些纠错编码，例如“汉明码”。但是，该代码旨在在这种情况下恢复翻转位而不是丢失位。

Answer 1

如果您对低熵代码感到满意并且可以检测到消息结束，则可以简单地将每个位发送两次。

此代码可以从不同运行中发生的任意数量的删除中恢复：

在接收时，找到所有奇数大小的运行并将它们扩展一位。如果最终得到的位数少于预期的位数，则无法从多次删除中恢复。

如果要确保可以恢复的固定错误率，请使用位填充。

例子：

0110

encoded as:
00 11 11 00

a double error occurs:
0x 11 x1 00

received:
011100

'0' and '111' are odd-sized runs. Fix:
00111100

we have 8 bits, and have recovered from a double error.
decode:
0110

示例 2：

0101

encoded as
00110011

transmitted as
0xxx0011

received as
00011

corrected as
000011

decoded as
001

which is shorter than expected. A transmission error has occured.

示例 3（运行 3 位后的位填充）：

0000 1111

stuffed as
00010 11101

sent as
0000001100 1111110011