4 種類の記号 A、B、C、D が互いに独立に、それぞれ確率 0.4、0.3、0.2、0.1 で発生する情報源がある。この情報源をハフマン符号で符号化したときの平均符号長〔bit／記号〕として、適当なものはどれか。なお、この情報源のエントロピーは約 1.85 bit／記号である。
正解・解説を確認する
解答正解 2
ハフマン符号は確率の小さい記号から順に結合して符号木を作り、確率の高い記号に短い符号を割り当てる。ここでは C＋D＝0.3、B＋(CD)＝0.6、A＋0.6 の順に結合し、符号長は A＝1、B＝2、C＝D＝3 となる。平均符号長は 1.9 bit／記号で、エントロピー 1.85 以上、固定長 2.0 未満である。エントロピーは平均符号長の下限という関係を押さえる。
選択肢ごとの判定
1符号長を 1、2、2、3 とした値。この符号長はクラフトの不等式（Σ2^(－l)≦1）を満たさず、一意に復号できる符号を作れない。
2正しい。ハフマン法では C と D（0.3）を結合し、次に B との結合（0.6）を経て A と結合する。符号長は A が 1、B が 2、C と D が 3 で、0.4×1＋0.3×2＋(0.2＋0.1)×3＝1.9 となる。
3エントロピーの値。平均符号長の下限であり、符号長が整数である以上、一般にはこの値に一致しない。
44 記号を 2 bit の固定長符号とした場合の値。ハフマン符号は発生確率に応じた可変長なのでこれより短くなる。