非常に高い非バーストエラーのアルゴリズム

Question

エラー率が非常に高いバイナリストリームがあります。エラー率は50％です。これは、各ビットが50％の確率で反転することを意味します。エラーはバーストでは発生せず、完全にランダムであるため、Reed＆＃8211;ソロモンコードはうまく機能しません。

ストリームに適用するスキームまたはアルゴリズムはどれですか？オーバーヘッドはまったく気にしません。

これはすべて理論的であるため、ストリームのエラーを減らすことができるかどうかを尋ねても意味がありません。

編集

それは不可能だとは言わないでください。最初の答えは、ノイズの多いチャンネルで可能であることを示しています。コーディング定理。

Answer 1

ノイズの多いチャネルコーディングの定理によれば、チャネルのシャノン容量を実際に達成することができます。チャンネルの容量がゼロではないということはではありません！

チャンネルのビットの100％をランダム化した場合、それらの50％は変更されないため、ランダムな50％のビットのみを反転します。そのようなチャネルを介してデータを送信できないことは明らかです。そのシャノンの容量はゼロです。

Answer 2

エラー率が50％の場合、それは基本的にランダムノイズではありませんか？つまり、1ビットだけを送信することを検討してください。右ビットの無限ストリームを50％のエラーレートで送信すると、右ビットが1でも0でも半分の1と半分の0が得られます。

実際に50％未満の場合（たとえば、ビットの50％が「反転」ではなく「ランダム」になります）、データを繰り返すことができます-各ビットを128回送信し、より多くを取得します受信した100ビットごとにこれはコーディングが簡単で、非常に非効率的で、数学的なソリューションではありません：）

Answer 3

まあ、リードソロモンのエラー修正のポイントは、ほとんどの実世界のエラーがバーストで発生するため、データをインターリーブおよびデインターリーブすることです。エラーが完全にランダムな場合、つまりポアソン分布の場合、単純で数学的に効率的な方法でストリームに冗長性を追加するだけで機能します。ご覧いただけるものの1つは、トレリスコードなど、ある種の隠れマルコフモデルです。基本的に冗長性を追加する数学的に効率的な方法です。

また、ノイズのあるチャネルコーディング定理をご覧ください。厳密には、デジタルデータには適用されませんが、これらのビットのソースが何らかのアナログプロセスである場合、またはビットを何らかのアナログプロセスの結果であるかのようにモデル化できる場合は、何らかの洞察を得ることができます最善を尽くすかもしれません。これにより、数学的に可能な以上のことをしようとして時間を無駄にすることがなくなります。

Answer 4

チャネルが実際のノイズレートの50％に近づくと、情報を送信できなくなります。 Jon Skeetの答えに、エラー率がノイズ50％未満の場合、意図したデータの長いバーストを冗長的に実行し、元の値のある程度の信頼度で結果を統計的に調べることでデータを取得できます。次に、ノイズの特性に基づいて、所定の長さに必要なバースト長と信頼レベルを導き出します。ただし、ここで実行しているのは、データレートを効果的に下げて、送信ストリームの正味の信号対雑音比を改善することです。

あなたの質問では、これをオプションとして除外しているかもしれませんが、より良いエンコーディングスキームは、データストリーム自体の相対的な存在に基づいているかもしれません。つまり、バイナリ1を送信するには、... 1/0の交互ストリームを送信します。ゼロを送信するには、何も送信しないか、一定レベルを送信します。アイデアは、何かを送信（および受信）すると1つの状態を表し、送信（および受信）何も別の状態を表さないというものです。これは、データのバイポーラエンコーディングのタイプに効果的に似ています。

Answer 5

エラー率が50％の場合、ビットストリームはランダムであり、元のビットストリームとは相関がありません。ストリームを完全にランダムなビットストリームとXORしているようなもので、結果は完全にランダムです。そして、あなたがそれについてできることは何もありません。

スキームが機能するには、フリップレートが50％未満でなければなりません。もちろん、50％を超えることもありますが、最初にストリームを反転させてから、エラー率が50％未満の場合のように処理することができます。

エラーが完全にランダムで非常に頻繁に発生する場合（たとえば、ビットの25％が反転する場合）、堅牢なエラー検出スキームを考え出すことは非常に困難です。かなりの量の冗長性を追加する必要があります。

Answer 6

ターボコードを調べましたか

-MarkusQ

Doh！ 50％が反転したのではなく、50％がランダム化されていると誤解しています。

Answer 7

50％の確率で各ビットが反転するのではなく、50％のビットが任意の送信で反転する場合、2ビットの送信を送信することで情報のビットを送信できます- -0を00として、1を01として送信します。受信したコードワードの最初のビットが1の場合、他のビットは反転されません。