第6回 ハフマン符号 課題解答例

課題1

表2のハフマン符号の平均符号長 \(L\) を求めよ。

\( \begin{eqnarray} L&&=(0.25+0.35+0.18)\times2+0.14\times3+(0.02+0.06)\times4\\ &&=1.56+0.42+0.32\\ &&=2.3 \end{eqnarray} \)
より、平均符号長は 2.3ビット になる。

やるべきことは積和の計算だが、符号語の長さが同じものをまとめた方が計算が楽になる。\(l_b=l_d=l_f=2, l_c=l_e=4\) なので、上の導出ではそれらをまとめてから計算している。

課題2

シンボルが a~h の8つで、情報源事象系が
\( X= \begin{bmatrix} x_a & x_b & x_c & x_d & x_e & x_f & x_g & x_h \\ 0.05 & 0.16 & 0.07 & 0.13 & 0.18 & 0.09 & 0.11 & 0.21 \end{bmatrix} \)
である場合のハフマン符号を求めよ。ただし導出に使った符号の木も残すこと。

ハフマン符号の規則にしたがって接点をつなぐと以下のようになる (図の下のボタンをクリックすると1ステップ前後に移動する)。

よって最終的な符号の木は以下のようになる。


これに対応する符号は以下の通り。
シンボル 符号語
a 1111
b 101
c 1110
d 110
e 100
f 011
g 010
h 00

課題3

課題2で求めたハフマン符号の平均符号長 \(L\) を求めよ。

h の符号語の長さが2、b, d, e, f, g の符号語の長さが3、a, c の符号語の長さが4なので、
\( \begin{eqnarray} L&&=0.21\times2+(0.16+0.13+0.18+0.09+0.11)\times3+(0.05+0.07)\times4\\ &&=0.42+2.01+0.48\\ &&=2.91 \end{eqnarray} \)
で、平均符号長は 2.91ビット になる。