情報理論と符号の基礎
記号A、B、C、Dを確率0.4、0.3、0.2、0.1で、互いに独立に出す情報源を、ハフマン符号で符号化する。1記号あたりの平均符号長はどれか。
- A約1.85ビット
- B1.9ビット
- C2ビット
答えと解説を見る
正解：B. 1.9ビット
ハフマン符号では、確率の最も小さい2つをまとめる操作を繰り返します。0.1と0.2をまとめて0.3、次に0.3と0.3をまとめて0.6、最後に0.6と0.4をまとめるので、符号長はAが1、Bが2、CとDが3ビットになります。平均符号長は 0.4 × 1 + 0.3 × 2 + 0.2 × 3 + 0.1 × 3 = 1.9 ビットです。
- A. 約1.85ビットはこの情報源のエントロピーで、平均符号長の下限です。確率が1/2や1/4のような2のべき乗分の1ではないので、ハフマン符号でもここまでは短くなりません。
- B. 正しい。0.4 + 0.6 + 0.6 + 0.3 = 1.9 ビットです。
- C. 2ビットは、4種類を同じ長さで表す固定長符号の符号長です。