algorithm - 失われたビットのエラー訂正コード

Question

送信者からビットのチャンク（たとえば8ビット）としてデータを受信する必要がある場合。

ただし、転送の信頼性が低いため、ビットが失われます。（ビットフリップではありません）つまり、チャンク内のどのビットも存在しない可能性があり、レシーバーは7ビットしか受信しません。

「ハミング符号」などの誤り訂正符号を研究しました。ただし、このコードは、この状況で失われたビットではなく、反転したビットを回復するように設計されています。

Answer 1

低エントロピー コードに満足し、メッセージの終わりを検出できる場合は、単純に各ビットを 2 回送信できます。

このコードは、異なる実行で発生する任意の数の削除から回復できます。

受信時に、奇数サイズのランをすべて見つけて、それらを 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