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

課題1

上の例の条件で \(p=0.1\) のときの平均符号長を求めよ。ただし、計算結果は四捨五入して小数第二位までにすること (スマホの電卓機能などを使ってよい)。
\( \begin{eqnarray} L&=&\frac{2p}{1-(1-p)^3}\\ &=&\frac{2\times0.1}{1-0.9^3}\\ &=&\frac{0.2}{1-0.729}\\ &=&\frac{0.2}{0.271}\\ &=&0.738...\\ &\simeq&0.74 \end{eqnarray} \)

課題2

「シンボル」を8種類、符号語を3ビットに拡張した場合の平均符号長を \(p\) の関数の形で記述せよ。

\(n_3\) を求めたときと同様に、「シンボル」の平均の長さは
\( \begin{eqnarray} n_7&=&p+2(1-p)p+3(1-p)^2p+4(1-p)^3p+5(1-p)^4p+6(1-p)^5p+7(1-p)^6p+7(1-p)^7\\ &=&\frac{p}{1-p}\Big((1-p)+2(1-p)^2+3(1-p)^3+4(1-p)^4+5(1-p)^5+6(1-p)^6+7(1-p)^7\Big)+7(1-p)^7\\ &=&\frac{p}{1-p}\sum^7_{r=1}r(1-p)^r+7(1-p)^7\\ &=&\frac{\cancel{p}}{\cancel{1-p}}\frac{\cancel{(1-p)}(1-(1-p)^7)}{p^\cancel{2}}-\frac{\cancel{p}}{\cancel{1-p}}\frac{7(1-p)^{7+\cancel{1}}}{\cancel{p}}+7(1-p)^7\\ &=&\frac{1-(1-p)^7}{p}-\cancel{7(1-p)^7}+\cancel{7(1-p)^7}\\ &=&\frac{1-(1-p)^7}{p} \end{eqnarray} \)
となる (3行目から4行目の変形で公式①を使った)。結局、\(n_3\) のときの「3」が「7」に置き換わるだけ。
一方、符号語はいずれも3ビットなので、\(\bar{L}=3\) になる。これらを使えば平均符号長は
\( \begin{eqnarray} L&=&\frac{\bar{L}}{n_7}\\ &=&3\times\frac{p}{1-(1-p)^7}\\ &=&\frac{3p}{1-(1-p)^7} \end{eqnarray} \)
となる。

課題3

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

課題2で求めた式の \(p\) に0.1を入れれば
\( \begin{eqnarray} L&=&\frac{3p}{1-(1-p)^7}\\ &=&\frac{3\times0.1}{1-0.9^7}\\ &=&\frac{0.3}{1-0.4782969}\\ &=&\frac{0.3}{0.5217031}\\ &=&0.575...\\ &\simeq&0.58 \end{eqnarray} \)
となる。

課題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ビットなので、

\( \begin{eqnarray} \bar{L}&=&0.1\times 3+0.4782969\times 1+(1-0.1-0.4782969)\times 4\\ &=&2.4651...\\ &\simeq&2.465 \end{eqnarray} \)
となる。

課題6

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

課題2の途中計算でみたように \( \begin{eqnarray} n_7=\frac{1-(1-p)^7}{p} \end{eqnarray} \) であり、この \(p\) に \(0.1\) を入れれば \(n_7\simeq5.217\) になる。よって
\( \begin{eqnarray} L&=&\frac{\bar{L}}{n_7}\\ &\simeq&\frac{2.465}{5.217}\\ &=&0.472...\\ &\simeq&0.47 \end{eqnarray} \)
となる。
この値は課題3で求めた同条件の固定長ランレングス符号の平均符号長 (\(0.58\)) より小さく、効率が良くなっていることがわかる。
inserted by FC2 system