以下に示す図4のような画像を表1の方法でランレングス符号にしたときの平均符号長を求めよ。
|
図4 |
「BBBB」「WWWW」の並びを最小単位として、全体はこれの繰り返しになっている。
そこで、これらのシンボル数と変換された信号の長さを求めれば平均符号長が求められる。
「BBBBWWWW」のシンボル数は8個であり、「BBBB」「WWWW」に対応する符号語はそれぞれ4ビットで、計8ビットの信号に変換される。
よって、平均符号長は \(8/8=1\) で
1ビットになる。
以下に示す図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倍の誤差の範囲を含むことになってしまう。
表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ビット) より小さく、データが半分近くに減らせていることを意味する。
概要の符号の木を元にしてハフマン符号の表を完成させ、その場合の平均符号長を求めよ。
符号の木をもとに表を書き下すと以下のようになる。
シンボル の並び |
符号語 |
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}
\)
|
となる。