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

最短の等長符号は、例えば

シンボル	符号語
a	000
b	001
c	010
d	011
e	100
f	101

で、計算するまでもなく平均符号長 \(L\) は \(3\)。

上の例で求めたハフマン符号の平均符号長 \(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}\)

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

最短の等長符号は、例えば

シンボル	符号語
a	000
b	001
c	010
d	011
e	100
f	101
g	110
h	111

で、計算するまでもなく平均符号長 \(L\) は \(3\)。

シンボルが 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\) を求めよ (必要なのは図、表、数値)。

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

シンボル	符号語
a	1111
b	101
c	1110
d	110
e	100
f	011
g	010
h	00

のようになり、平均符号長は

\(\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}\)

となる。

シンボルが 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

シンボル	符号語
a	111111
b	11101
c	0
d	11110
e	110
f	111110
g	11100
h	10

この符号の平均符号長は

\(\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

シンボル	符号語
a	11111
b	11010
c	0
d	11011
e	1100
f	11110
g	1110
h	10

この符号の平均符号長は

\(\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\) は最小値なはずなので、どちらか片方でだけ計算すれば十分)