例2の符号で、情報源事象系が \( X= \begin{bmatrix} x_a & x_b & x_c & x_d \cr 0.25 & 0.25 & 0.25 & 0.25 \end{bmatrix} \) である場合の平均符号長を求めよ。また、この場合に例1と例2のどちらが効率が良いか述べよ。

a, b, c, dに対応する符号語の長さはそれぞれ1, 2, 3, 4なので、平均符号長は


となる。これは例1の平均符号長 2 よりも大きいので、例1の方が効率が良い。

例2の符号で、情報源事象系が \( X= \begin{bmatrix} x_a & x_b & x_c & x_d \cr 0.8 & 0.1 & 0.05 & 0.05 \end{bmatrix} \) である場合の平均符号長を求めよ。また、この場合に例1と例2のどちらが効率が良いか述べよ。

a, b, c, dに対応する符号語の長さはそれぞれ1, 2, 3, 4なので、平均符号長は


となる。これは例1の平均符号長 2 よりも小さいので、例2の方が効率が良い。

a～hの8文字を扱えるように例1, 例2を拡張した符号を考え、情報源事象系が

\( X= \begin{bmatrix} x_a & x_b & x_c & x_d & x_e & x_f & x_g & x_h \cr 1-7p & p & p & p & p & p & p & p \end{bmatrix} \)

である場合の例1(拡張)、例2(拡張)の平均符号長を求めよ。また、例2(拡張)の方が例1(拡張)よりも効率が良くなる条件を記述せよ。

例1を拡張したものではすべての符号語の長さが3なので、平均符号長は \(L=3\) となる。
一方、例2を拡張したものではa～hに対応する符号語の長さは1～8になるので、平均符号長は

\(\begin{eqnarray} L&=&1\times(1-7p)+(2+3+4+5+6+7+8)\times p\\ &=&1-7p+35p\\ &=&1+28p \end{eqnarray}\)

となる。これが例1の平均符号長 3 よりも小さくなる条件は


つまり、\(p\) が \(\frac{1}{14}\) より小さければよい。

書く必要はないが、拡張版の例1, 例2の符号は以下のようになる。

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

シンボル 符号語 a 1 b 01 c 001 d 0001 e 00001 f 000001 g 0000001 h 00000001

以下の符号の符号の木を描け。

シンボル	符号語
a	1
b	10
c	100
d	1000

この図は「0の枝を右上に、1の枝を右下に」向けて描いてあるが、どちらにするかには特にルールはない。
もっとも、「0, 1のどちらを上にするか」の規則が混在していると混乱しがちなので、ひとつの図の中でははそろえた方がよい。
資料の説明にある通り、この符号では途中の節点にもシンボルが割り当たる。