バイアスされたランダムな 0 と 1 の無限ストリーム (たとえば、1 は既知の要因により 0 よりも一般的です) が理想的な乱数ジェネレーターである場合、それを (より短い) 無限ストリームに変換したいと思います。理想的ですが偏りもありません。
エントロピーの定義を調べると、理論上、入力の各ビットから取得できる出力のビット数を示すこのグラフが見つかります。
質問:ほぼ理想的に効率的なコンバーターを実際に実装する実用的な方法はありますか?
3 に答える
4
不公平なコインを公正なコインに変えるためのフォン・ノイマンによる有名な装置があります。このデバイスを使用して、ここで問題を解決できます。
ビットが異なるペアを取得するまで、バイアスされたソースから2ビットを繰り返し描画します。次に、最初のビットを返し、2番目のビットを破棄します。これにより、偏りのないソースが生成されます。これが機能する理由は、ソースに関係なく、01の確率が10の確率と同じであるためです。したがって、01または10を条件とする0の確率は1/2であり、01を条件とする1の確率は1/2です。または10は1/2です。
于 2010-03-10T20:27:31.367 に答える
2
参照してください
于 2010-03-10T20:43:03.683 に答える
0
入力をホフマン符号化します。
入力のバイアスが既知の場合、各 n ビット セグメントのチェック サムの確率分布を計算できます。そこからホフマン コードを作成し、シーケンスをエンコードします。
よくわかりませんが、潜在的な問題の 1 つは、これにより連続するビット間に何らかの相関関係が生じる可能性があることです。
于 2010-05-26T18:09:49.210 に答える