情報理論と符号の基礎
0を確率0.8、1を確率0.2で、互いに独立に出す2値の情報源がある。2記号ずつまとめた00、01、10、11の4種類をそれぞれ1つの記号とみなし、ハフマン符号で符号化する。元の1記号あたりの平均符号長はどれか。
- A約0.72ビット
- B0.78ビット
- C1ビット
答えと解説を見る
正解：B. 0.78ビット
4種類の確率は、00が0.64、01と10が0.16、11が0.04です。0.04と0.16をまとめて0.2、0.2と0.16をまとめて0.36、最後に0.64とまとめるので、符号長は1、2、3、3ビットとなり、2記号あたりの平均は 0.64 × 1 + 0.16 × 2 + 0.16 × 3 + 0.04 × 3 = 1.56 ビットです。元の1記号あたりでは 1.56 ÷ 2 = 0.78 ビットです。1記号ずつでは0と1に1ビットずつ割り当てるしかありませんが、まとめて符号化すると、エントロピーの約0.72ビットに近づけられます。
- A. 約0.72ビットはこの情報源のエントロピーで、平均符号長の下限です。2記号ずつのまとめ方では、まだそこまでは下がりません。
- B. 正しい。1.56 ÷ 2 = 0.78 ビットです。
- C. 1ビットは、1記号ずつ符号化したときの値です。2値の記号を1つずつ符号化すると、どちらにも1ビットが必要です。