第7回 ランレングス符号 課題解答例

課題1

以下に示す図4のような画像を表1の方法でランレングス符号にしたときの平均符号長を求めよ。
図4

「BBBB」「WWWW」の並びを最小単位として、全体はこれの繰り返しになっている。
そこで、これらのシンボル数と変換された信号の長さを求めれば平均符号長が求められる。
「BBBBWWWW」のシンボル数は8個であり、「BBBB」「WWWW」に対応する符号語はそれぞれ4ビットで、計8ビットの信号に変換される。
よって、平均符号長は \(8/8=1\) で1ビットになる。

課題2

以下に示す図5のような画像を表1の方法でランレングス符号にしたときの平均符号長を求めよ。ただし、結果は四捨五入して小数第2位までにすること。
図5

画像のうち最後の4つのピクセルを除く部分は「Bが5個」か「Wが5個」のいずれかで、その数は \((1024-4)/5=204\) 組である。
最後の「Bが4個」の1つを加えて全部で205組の並びがあり、 いずれも4ビットの符号語に置き換えられるので、全体の信号の長さは \(205\times4=820\) ビットになる。
一方シンボルは全部で1024個あるので、平均符号長は \(820/1024=0.800...≒0.80\) より 0.80ビット になる。
小数第2位が0になるからといって、解を「0.8ビット」としてはいけない。 0.80は小数第2位の「0」までが有効数字なので、誤差の範囲として「0.795以上0.805未満」を意味するが、0.8だと小数第1位の「8」までが有効数字で、「0.75以上0.85未満」で、10倍の誤差の範囲を含むことになってしまう。

課題3

表1の方法で \(p_{b1}\)~\(p_{b7}\) と \(p_{w1}\)~\(p_{w7}\) がすべて\(0.01\)、\(p_{b8}=p_{w8}=0.43\) のときの平均符号長 \(L\) を求めよ。ただし、結果は四捨五入して小数第2位までにすること。

白と黒のピクセルの同じ数の並び対応する確率が同じなので、符号の並びの数の平均は
\( \begin{eqnarray} L_s&&=\sum_i p_il_i\\ &&=2\left(p_{b2}\times(1+2+3+4+5+6+7)+p_{b8}\times 8\right)\\ &&=2\left(0.01\times(1+2+3+4+5+6+7)+0.43\times8\right)\\ &&=2\times3.72\\ &&=7.44 (個) \end{eqnarray} \)

となるので、並びに対する符号長をこれで割って \(L=4/L_s=4/7.44=0.537...≒0.54\) より \(L=0.54\) ビット となる。
この結果は、なにも工夫せずにそれぞれのピクセルを1ビットに置き換えた場合の平均符号長 (1ビット) より小さく、データが半分近くに減らせていることを意味する。

課題4

概要の符号の木を元にしてハフマン符号の表を完成させ、その場合の平均符号長を求めよ。

符号の木をもとに表を書き下すと以下のようになる。
シンボル
の並び
符号語
B 111111
BB 111110
BBB 111101
BBBB 111100
BBBBB 111011
BBBBBB 111010
BBBBBBB 111001
BBBBBBBB 10
W 111000
WW 110111
WWW 110110
WWWW 110101
WWWWW 110100
WWWWWW 11001
WWWWWWW 11000
WWWWWWWW 0

符号長は「W8個」が1ビット、「B8個」が2ビット、「W7個」と「W6個」が5ビットで、それ以外の12通りの並びではすべて6ビットになる。
よって、シンボルの並びに対応する符号語の平均の長さ \(\bar{L}\) は
\( \begin{eqnarray} \bar{L}=&&\sum_i p_il_i\\ =&&0.43\times(1+2)+0.01\times(5\times2+6\times12)\\ =&&1.29+0.82\\ =&&2.11 (ビット) \end{eqnarray} \)

よって、平均符号長は
\( \begin{eqnarray} L=&&\frac{\bar{L}}{L_s}\\ =&&\frac{2.11}{7.44}\\ =&&0.283...\\ ≒&&0.28 (ビット) \end{eqnarray} \)
となる。