5

これは、単純なプログラミングの問題というよりは、コンピュータ サイエンス/情報理論の問題です。この問題を投稿するのに適したサイトを誰か知っている場合は、お知らせください。

M メッセージで冗長に送信される N ビットのデータがあり、少なくとも M-1 のメッセージが正常に受信されるとします。メッセージあたりのビット数を減らして N ビットのデータをエンコードするさまざまな方法に興味があります。(これはRAIDに似ていますが、はるかに小さいレベルであり、N = 8 または 16 または 32 です)

例: N = 16 で M = 4 と仮定すると、次のアルゴリズムを使用できます。

1st and 3rd message: send "0" + bits 0-7
2nd and 4th message: send "1" + bits 8-15

4 つのメッセージのうち 3 つのメッセージが通過することを保証できれば、各グループから少なくとも 1 つのメッセージが通過します。したがって、9 ビット以下でこれを機能させることができます。おそらく総ビット数を少なくしてこれを行う方法がありますが、その方法はわかりません。

この種のことを行うための単純なエンコード/デコードアルゴリズムはありますか? この問題に名前はありますか？（名前がわかれば、ググってみます！）

注：私の特定のケースでは、メッセージが正しく到着するか、まったく到着しません（メッセージがエラーで到着しません）。

（編集：2番目の部分を別の質問に移動しました）

4

5 に答える 5

5

（不完全な回答が続きます。後で追加する可能性があります。）

興味のある用語はチャネル コーディングです。ノイズの多いチャネルを介した送信中にソースを堅牢にするために、ソースに冗長性を追加します。情報理論では、チャネル コーディングの補足的な問題はソース コーディングです。つまり、ソースの冗長性を減らして、より少ないビットを使用してそれを表現します。(これら 2 つの問題の組み合わせは、ジョイント ソースチャネル コーディングと呼ばれます。)

最初の質問は、チャンネル コードを見つけることです。あなたが与える単純な例は、繰り返しコードに似ています。つまり、同じメッセージを 2 回以上 (通常は奇数回) 送信すると、最も頻繁に受信されるメッセージが元のメッセージとして受け入れられます。

このコードは非効率的です。標準表記法を使用するには、k = 元のメッセージのビット数、n = 送信メッセージのビット数とします。たとえば、k = 16 および n = 36 です。コーディング効率の尺度は k/n であり、高いほど効率的です。あなたの場合、k/n = 0.44 です。これは低いです。

繰り返しコードは単純な種類のブロック コードです。つまり、冗長性が k ビットの各ブロックに追加され、n ビットのコードワードが作成されます。他の人が述べたように、ハミングとリードソロモンのコードもそうです。ハミング符号は、基本的な線形代数を使えば比較的簡単に理解できます。

これらは、自分で検索するのに十分な用語です。幸運を。

于 2010-01-28T20:14:32.407 に答える
3

あなたの質問の詳細をすべて正しく理解できたかどうかはわかりませんが、あなたの問題は間違いなく、ある種のエラー修正コードの設計に関するものです。これはコンピュータ サイエンスの広大な領域であり、それについては分厚い本が書かれています。ウィキペディアから始めて、単純なスキーム (ハミングやリードソロモン コードなど) があなたのケースで機能するかどうかを確認してください。

シンボルの破損だけでなく、シンボルの削除も処理したい場合は、消去コードを検討する必要があります。これは間違いなくより困難な作業ですが、多くの場合、適切な方法が存在します。

編集: hackersdelight.org からのこの資料は、良い紹介のようです。

于 2010-01-28T20:07:21.607 に答える
1

パケット消去コードを探しています。特許によって完全に妨げられていない有用なパケット消去コードは 2 つしかなく、それらを実装するオープンソース ライブラリは 1 つだけです。ここで見つけてください: http://planete-bcast.inrialpes.fr/rubrique.php3?id_rubrique=5

于 2010-01-28T21:20:07.877 に答える
1

消去コードを参照してください。

于 2010-01-28T20:03:37.660 に答える
1

これは、あなたの例のほぼ2倍の効率の自明な単純なスキームです。

メッセージを (N/M)*2 ビットのブロックに分割しました。代わりに、N/(M-1) ビット ブロックに分割します。(必要に応じて切り上げます。) 最初のブロック はsrc[0]、それ自体としてエンコードされます: enc[0]=src[0]. 最後のブロックも同じです: enc[M-1]=src[M-1]. 他の各ブロックは、左隣の と XOR されますenc[i]=src[i-1]^src[i]。

エンコードされた各ブロックの前に log(M) ビットのシーケンス番号を付けます。これは、基本的にはあなたが行ったように、受信者がどれがドロップされたかを知ることができるようにするためです。(到着するブロックが順番に到着することが確実な場合は、1 ビットのシーケンス番号で十分です。0 と 1 を交互に繰り返すだけです。)

デコードするには、ドロップしたブロックにヒットするまで、左右から XOR を続けます。例src[1] == enc[0]^enc[1]。(エンドポイント ブロックの 1 つをドロップすることは特別なケースではありません。たとえば、最初のブロックがドロップされた場合、右からのスキャンはそれを回復し、左からのスキャンの長さは 0 です。)

于 2011-01-14T22:54:21.650 に答える