0

非常に奇妙なデータ チャネルを使用するためのエラー修正アルゴリズムを推奨してください。

ダイアグラム

チャネルは、Corrupter と Eraser の 2 つの部分で構成されています。

コラプターは、{'a','b','c'} のように、3 記号のアルファベットで 10000 記号からなる単語を受け取ります。
コラプターは各シンボルを 10% の確率で変更します。
例：

Corrupter input:  abcaccbacbbaaacbcacbcababacb...
Corrupter output: abcaacbacbbaabcbcacbcababccb...

Eraser は破損した出力を受け取り、各シンボルを 94% の確率で消去します。
Eraser は、4 シンボルのアルファベット {'a','b','c','*'} で同じ長さの単語を生成します。
例：

Eraser input:  abcaacbacbbaabcbcacbcababccb...
Eraser output: *******a*****************c**...

したがって、消しゴムの出力では、約 6%*10000=600 個のシンボルが消去されず、そのうちの約 90%*600=540 個が元の値を保持し、約 60 個が破損します。

このチャネルに最適なエラー訂正付きのエンコード/デコード アルゴリズムはどれですか?
99.99% を超える確率でデコードが成功する場合、どの程度の有用なデータを送信できますか?
このチャネルで 40 バイトのデータを送信できますか? (256^40 ~ 3^200)

4

1 に答える 1

1

少なくとも分析できるものは次のとおりです。

40 バイトを 13 個の 25 ビット チャンクに分割します (多少の無駄があるため、このビットは明らかに改善できます)。

2^25 < 3^16 であるため、25 ビットを 16 の a/b/c "trits" にエンコードできます。ここでも、浪費は改善の余地を意味します。

10,000 トリットが利用できるので、13 のエンコードされたバイト トリプルのそれぞれに 769 トリットの出力を与えることができます。16 トリットで 769 の異なる線形 (mod 3) 関数を (おそらくランダムに) 選択します。各関数は 16 トリットで指定され、それらのトリットと 16 の入力トリットの間のベクトル内積を取得します。これにより、769 の出力トリットが得られます。

すべての可能な (2^25) チャンクを考慮してデコードし、生き残ったトリットのほとんどに一致するものを選択します。少なくとも 16 個のトリットが生き残っている限り、正しい答えが得られる見込みがあります。これは、BINOMDIST() を介して Excel が教えてくれていると思いますが、13 個すべてで発生する可能性が十分にあるほど頻繁に発生します。 25 ビットのチャンク。

ガブリングから得られるエラー率はわかりませんが、ランダムな線形コードはかなり良い評判を得ています。最悪の場合、25 ビット チャンクのエンコード送信とデコードをシミュレートして、そこから解決することもできます。ガーブリング ステージも同様に消去するふりをして、わずかに高い消去確率で再計算すると、上記よりもわずかに正確なエラー率の下限を得ることができます。

25 ビット ブロックごとに 2^25 の推測をデコードする余裕がある場合、これは実際に機能する可能性があると思います。OTOH これがクラスでの質問である場合、クラスで既に説明されているアドホックではないテクニックの知識を示す必要があると思います。

于 2013-02-20T21:34:22.097 に答える