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

課題1

上の例の条件で、a~f を扱える最短の等長符号と、その平均符号長 \(L\) を求めよ (必要なのは表と数値)。

最短の等長符号は、例えば
シンボル符号語
a000
b001
c010
d011
e100
f101
で、計算するまでもなく平均符号長 \(L\) は \(3\)

課題2

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

a~f に対応する符号語の長さがそれぞれ3, 2, 4, 2, 4, 2なので、
\(\begin{eqnarray} L&=&(0.25+0.35+0.18)\times 2+0.14\times 3+(0.02+0.06)\times 4\\ &=&1.56+0.42+0.32\\ &=&2.3 \end{eqnarray}\)

課題3

a~h の8つのシンボルを扱える最短の等長符号と、その平均符号長 \(L\) を求めよ (必要なのは表と数値)。

最短の等長符号は、例えば
シンボル符号語
a000
b001
c010
d011
e100
f101
g110
h111
で、計算するまでもなく平均符号長 \(L\) は \(3\)

課題4

シンボルが a~h の8つで、情報源事象系が
\( X= \begin{bmatrix} x_a & x_b & x_c & x_d & x_e & x_f & x_g & x_h \cr 0.05 & 0.16 & 0.07 & 0.13 & 0.18 & 0.09 & 0.11 & 0.21 \end{bmatrix} \)
である場合のハフマン符号を求めよ。また、その平均符号長 \(L\) を求めよ (必要なのは図、表、数値)。

ハフマン符号を求めるための符号の木とハフマン符号は

シンボル符号語
a1111
b101
c1110
d110
e100
f011
g010
h00
のようになり、平均符号長は
\(\begin{eqnarray} L&=&0.21\times 2+(0.16+0.13+0.18+0.09+0.11)\times 3+(0.05+0.07)\times 4\\ &=&0.42+0.67\times 3+0.12\times 4\\ &=&0.42+2.01+0.48\\ &=&2.91 \end{eqnarray}\)
となる。

課題5

シンボルが a~h の8つで、情報源事象系が
\( X= \begin{bmatrix} x_a & x_b & x_c & x_d & x_e & x_f & x_g & x_h \cr 0.01 & 0.03 & 0.45 & 0.03 & 0.07 & 0.02 & 0.04 & 0.35 \end{bmatrix} \)
である場合のハフマン符号を2通り求めよ。また、その平均符号長 \(L\) を求めよ (必要なのは図x2、表x2、数値x1)。

タイプ1

シンボル符号語
a111111
b11101
c0
d11110
e110
f111110
g11100
h10
この符号の平均符号長は
\(\begin{eqnarray} L&=&0.45\times 1+0.35\times 2+0.07\times 3+(0.03+0.03+0.04)\times 5+(0.01+0.02)\times 6\\ &=&0.45+0.7+0.21+0.1\times 5+0.03\times 6\\ &=&1.36+0.5+0.18\\ &=&2.04 \end{eqnarray}\)
となる。

タイプ2

シンボル符号語
a11111
b11010
c0
d11011
e1100
f11110
g1110
h10
この符号の平均符号長は
\(\begin{eqnarray} L&=&0.45\times 1+0.35\times 2+(0.07+0.04)\times 4+(0.01+0.03+0.03+0.02)\times 5\\ &=&0.45+0.7+0.11\times 4+0.09\times 5\\ &=&1.15+0.44+0.45\\ &=&2.04 \end{eqnarray}\)
(ハフマン符号はコンパクト符号で、\(L\) は最小値なはずなので、どちらか片方でだけ計算すれば十分)

最初の3回の組み合わせ方をタイプ2と同じようにして、そのあとの組み合わせ方を変えてこのようにしたものもハフマン符号としては正しいが、これだとタイプ1と同様に最長の符号語の長さは6になってしまう。

シンボル符号語
a111111
b11100
c0
d11101
e110
f111110
g11110
h10
inserted by FC2 system