シンボルが2種類しかないときは、それらの組み合わせをシンボルとして扱うことで効率のよい符号化ができる。例えば上のケースで
- \(B\) が出たら区切る
- \(W\) が3個続いたら区切る
というルールでブロックを作ると「\(B\)」「\(WB\)」「\(WWB\)」「\(WWW\)」の4種類ができる。これらを「シンボル」として扱い、
| 「シンボル」 | 符号語 |
|---|
| \(B\) | 00 |
| \(WB\) | 01 |
| \(WWB\) | 10 |
| \(WWW\) | 11 |
のような等長符号を作ることができる (呼び名が紛らわしいので、この授業では以降 \(WWB\) などは鍵カッコつきで「シンボル」、本来の \(W, B\) のことは単にシンボルと書く)。このような符号を
固定長ランレングス符号という。
この符号を使えば、上の例の拡大部分の左上から右の29ピクセル分は
\(WWW\), \(WWW\), \(WWW\), \(WWW\), \(WWW\), \(WWB\), \(B\), \(WWW\), \(B\), \(WWW\)
→ 11 11 11 11 11 10 00 11 00 11
となり、20ビットのデータで送ることができる。
白の割合がもっと多い場合なら、「シンボル」を8種類 (最大7文字)、符号長を3にして
| 「シンボル」 | 符号語 |
|---|
| \(B\) | 000 |
| \(WB\) | 001 |
| \(WWB\) | 010 |
| ・・・ | ・・・ |
| \(WWWWWWB\) | 110 |
| \(WWWWWWW\) | 111 |
のようにすればさらに効率を上げられる。
固定長ランレングス符号の平均符号長は以下のようにして求める。
平均符号長は (本来の) シンボル1つあたりに平均して割り当たる符号語の長さだが、固定長ランレングス符号の表は (ブロック化された)「シンボル」に対するものなので、まずは「シンボル」の長さの平均値を求める。
シンボル \(B\) が発生する確率が \(p\) なら、それぞれの「シンボル」が発生する確率は
|
\(
X'=
\begin{bmatrix}
x_B & x_{WB} & x_{WWB} & x_{WWW} \\
p & (1-p)p & (1-p)^2p & (1-p)^3
\end{bmatrix}
\)
|
となる。そのため、「シンボル」の平均の長さ (\(W, B\) が何個あるか) は
|
\(
n_3=p+2(1-p)p+3(1-p)^2p+3(1-p)^3
\)
|
となる ( \(n\) の右下の \(3\) は「シンボル」が最長3文字であることをあらわす) 。この第1～3項は次のようにまとめられる。
|
\(
\begin{eqnarray}
n_3&=&\frac{p}{1-p}\Big((1-p)+2(1-p)^2+3(1-p)^3\Big)+3(1-p)^3\\
&=&\frac{p}{1-p}\sum^3_{r=1}r(1-p)^r+3(1-p)^3
\end{eqnarray}
\)
|
まとめた項は、数学の公式
\(
\begin{eqnarray}
\sum^N_{r=1}rx^r=\frac{x(1-x^N)}{(1-x)^2}-\frac{Nx^{N+1}}{1-x}\dots①
\end{eqnarray}
\)
の左辺で \(x\) を \(1-p\)、\(N\) を \(3\) と置いたものに等しいので、
|
\(
\begin{eqnarray}
n_3&=&\frac{p}{1-p}\Bigg(\frac{(1-p)(1-(1-p)^3)}{(1-(1-p))^2}-\frac{3(1-p)^{3+1}}{1-(1-p)}\Bigg)+3(1-p)^3\\
&=&\frac{\cancel{p}}{\cancel{1-p}}\frac{\cancel{(1-p)}(1-(1-p)^3)}{p^\cancel{2}}-\frac{\cancel{p}}{\cancel{1-p}}\frac{3(1-p)^{3+\cancel{1}}}{\cancel{p}}+3(1-p)^3\\
&=&\frac{1-(1-p)^3}{p}-\cancel{3(1-p)^3}+\cancel{3(1-p)^3}\\
&=&\frac{1-(1-p)^3}{p}
\end{eqnarray}
\)
|
となる。平均符号長、すなわち(本来の)シンボル1つあたりの符号長は、「「シンボル」1つあたりの符号長」( \(\bar{L}\) と書く。このケースではすべての符号語の長さが2なので \(\bar{L}=2\) ) を「1つの「シンボル」の平均の長さ」(いま求めた \(n_3\) ) で割って
\(
\begin{eqnarray}
L=\frac{\bar{L}}{n_3}=\frac{2p}{1-(1-p)^3}
\end{eqnarray}
\)
となる。