情報理論 第13回　ランレングス符号　練習問題解答例

• 練習問題1
上の例の条件で、$p=0.1$ のときの平均符号長を求めよ。ただし、計算結果は四捨五入して小数第二位までにすること (スマホの電卓機能などを使ってよい)。

• 練習問題2
「シンボル」を8種類、符号語を3ビットに拡張した場合の平均符号長を $p$ の関数の形で記述せよ。

$n_3$ を求めたときと同様に、「シンボル」の平均の長さは
で、まとめた項は公式①で$x$ を $1-p$、$N$ を7と置いたものに等しいので、

となる。一方、符号語はいずれも3ビットなので、$\bar{L}=3$ になる。これらを使えば平均符号長は

• 練習問題3
練習問題2の条件で $p=0.1$ のときの平均符号長の値を求めよ (スマホの電卓機能などを使ってよい)。

• 練習問題4
練習問題2, 3のように拡張した場合には、$p=0.1$ ではそれぞれの「シンボル」が出現する確率は以下のようになる。このときのランレングスハフマン符号 (「シンボル」に対する符号語の対応表) を求めよ。


「シンボル」	確率
$B$	0.1
$WB$	0.09
$WWB$	0.081
$WWWB$	0.0729
$WWWWB$	0.06561
$WWWWWB$	0.059049
$WWWWWWB$	0.0531441
$WWWWWWW$	0.4782969



ハフマン符号のルールに従って符号の木を作るとこのようになる。

これを左から読めば、それぞれの「シンボル」の符号語は以下のようになる。

「シンボル」	確率
$B$	110
$WB$	1000
$WWB$	1001
$WWWB$	1010
$WWWWB$	1011
$WWWWWB$	1110
$WWWWWWB$	1111
$WWWWWWW$	0

• 練習問題5
練習問題4のケースでの「シンボル」一つあたりの符号長の平均 $\bar{L}$ を求めよ。ただし、計算結果は四捨五入して小数第三位までにすること (スマホの電卓機能などを使ってよい)。

練習問題4の結果から、$B$ に対応するのが3ビット、$WWWWWWW$ に対応するのが1ビットで、それ以外はすべて4ビットなので、
$\bar{L}=0.1\times 3+0.4782969\times 1+(1-0.1-0.4782969)\times 4=\mathrm{2.4651...}\fallingdotseq 2.465$

• 練習問題6
練習問題4のケースで $p=0.1$ のときのの平均符号長 $L$ を求めよ。ただし、計算結果は四捨五入して小数第二位までにすること (スマホの電卓機能などを使ってよい)。

練習問題2の途中計算でみたように であり、この $p$ に0.1を入れれば $n_7\fallingdotseq 5.217$ になる。
よって $L=2.465/5.217=\mathrm{0.472...}\fallingdotseq 0.47$ で、練習問題3で求めた同条件の固定長ランレングス符号の平均符号長より小さく、効率が良くなっていることがわかる。