1

すべてゼロである1024ビットの配列があるとします。

例：[0,0,0,0,0,0,0、...]

次に、20個のゼロを完全にランダムな位置にあるゼロで上書きします。

例：[0,1,0,0,0,0,0、...]

私が完璧なエンコーダーを持っていると仮定して、これらのランダムに配置された20ビットの位置をエンコードするために必要な理論上の最小ビット数はいくつですか？

これを教えてくれる通信理論の方程式があることは知っていますが、計算を再確認したいと思います。

より難しいボーナスの質問：この最小制限に近づくエンコーディングを実装するアルゴリズムのコードを見せてください。

ボーナスボーナス：ビットレベルではなくバイトレベルでビットが反転した場合はどうなりますか？たとえば、バイト全体が反転します。同じ結果？

4

3 に答える 3

5

天井（log2（1024は20を選択））=139ビット

（Wolfram Alphaでの計算）

143ビットという他の回答では、正確に20ビットあることがわかっています。その知識を使用する1つの方法を示す具体的なエンコーディングを次に示します。算術コーディングを使用して、1024個の「0」または「1」の各シンボルを連続して送信します。最初のシンボルは、「1」である確率が20/1024で重み付けされます。ただし、後の各シンボルの重み付けは異なります。最初の記号が「0」の場合、次の記号は20/1023を使用します。ただし、「1」の場合は、19/1023を使用します。最後まで同じように続けます。算術符号化は、適切な確率を示す限り、約139ビットに収まるようにすべてのハードワークを実行します。

「ボーナスボーナス」について：エラー訂正は元の質問にはありませんでした。上記のように、エラーがないと仮定して最初に最適なエンコーディングを見つける上に、エラー訂正コードを重ねることができます（これは通常、問題を解決するための良い方法です）。その方法でコーディング効率を失うことはありませんが、堅牢性を失う可能性があると思います。たとえば、ECCで修正できるよりも多くのエラーが発生した場合、メッセージは完全なゴミとして出力されますか、それともより適切に劣化しますか？

于 2010-01-21T23:19:07.490 に答える
2

デコーダーにも辞書がある辞書ベースのエンコードを使用する場合、絶対的な最小値はありません。ただし、周波数ベースのエンコーディングの場合、必要なのはエントロピーを計算することです。

E = -(P(0) * log_2(P(0)) + P(1) * log_2(P(1)))
E = -(1004/1024 * log_2(1004/1024) + 20/1024 * log_2(20/1024))
E = 0.1388005

したがって、入力の各ビットには、平均して0.1388005ビットの出力が必要です。合計で：

0.1388005 * 1024 = 142.1317 bits.

これは、理論的には、最適なアルゴリズムを使用して、143ビットを使用して1004個のゼロと20個の1（またはその逆）の任意の文字列をエンコードできることを意味します。

于 2010-01-21T23:11:42.623 に答える
1

200 ビットの文字列を 20 個の 10 ビット数値の配列として扱い、それぞれが 1 ビットの 1 つの位置をリストしている場合、824 ビットを節約できます。

しかし、これが最低限ではないと思います。たとえば、各数値を絶対位置ではなく、前の項目との相対位置として扱う場合、分析によっては、次の 1 ビットまでの距離をエンコードするのに、平均して 8 ビットしか必要ないことが示される場合があります。したがって、先頭にビットを追加します。0 の場合、200 ビットが絶対位置に続きます。1 の場合、相対位置に 160 ビットが続きます。これにより、完全な値をエンコードするための平均ビット数が少なくなります。

一般化すると、これは単なるデータ圧縮です。「1024 の 21 ビット」をエンコードするのに必要な平均ビット数を非常に小さい数に減らすことができる圧縮アルゴリズムはおそらく多数あります。適切なバイナリ ツリーを計算し、その表現を格納し、ツリーをトラバースするために必要なビットを格納すると、非常に効率的なアルゴリズムが得られる可能性があります (実際、これは最新のデータ圧縮の基礎です)。

于 2010-01-21T23:02:28.310 に答える