第02回 情報源符号化 課題解答例

課題1

例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なので、平均符号長は

\(\begin{eqnarray} L&=&(1+2+3+4)\times 0.25\\ &=&10\times 0.25\\ &=&2.5 \end{eqnarray}\)

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

課題2

例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なので、平均符号長は

\(\begin{eqnarray} L&=&1\times0.8+2\times0.1+(3+4)\times0.05\\ &=&0.8+0.2+0.35\\ &=&1.35 \end{eqnarray}\)

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

課題3

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 よりも小さくなる条件は

\(\begin{eqnarray} 1+28p&&\lt3\\ 28p&&\lt2\\ p&&\lt\frac{1}{14} \end{eqnarray}\)

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

書く必要はないが、拡張版の例1, 例2の符号は以下のようになる。
シンボル符号語
a000
b001
c010
d011
e100
f101
g110
h111
シンボル符号語
a1
b01
c001
d0001
e00001
f000001
g0000001
h00000001

課題4

以下の符号の符号の木を描け。
シンボル符号語
a1
b10
c100
d1000


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