上のケースで「Bがいくつ続いたか」「Wがいくつ続いたか」に応じて、シンボルの並びに対して符号語を作ってみる。
符号語の先頭には「何が」、それに続くものとして「続いた数-1」を入れることにして、続いた数を1～8の範囲で許容することにすると、種類用に1ビット、カウント用に3ビット使って以下のような「シンボルの並びに対する等長符号」ができる。

表1

シンボル の並び	意味	符号語
B	Bが1個	0000
BB	Bが2個	0001
BBB	Bが3個	0010
⋮	⋮	⋮
BBBBBBBB	Bが8個	0111
W	Wが1個	1000
WW	Wが2個	1001
WWW	Wが3個	1010
⋮	⋮	⋮
WWWWWWWW	Wが8個	1111

のような等長符号を作ることができる。 このような符号を固定長ランレングス符号という。
この符号を使えば、上の例の画像の上側82ピクセル分 は


Wが8個, Wが8個, Wが8個, Wが8個, Wが7個, Bが2個, Wが8個, Wが8個, Wが5個, Bが4個
→ 1111 1111 1111 1111 1110 0001 1111 1111 1100 0011
となり、40ビットのデータで送ることができる (白黒でなくても、色の数がそれほど多くない場合であれば符号語の先頭に割り当てるビット数を色数に応じて増やせば同様のことができる)。

この方法の効率は、BとWの単独の出現率ではなく、その切り替わりがどれほど頻繁に起こるかに依存する。
図1のようにBとWの変化があまり起こらない場合であればこの方法で効率は上がるが、

図2

のようなケースでは「Bが1個」「Wが1個」のように1つのピクセルあたり4ビットの符号語が割り当てられ、データ量は4倍に増えてしまう。
このときはシンボル「B」「W」に対して符号語の長さはいずれも4ビットなので、平均符号長も4ビットになる。

もう少しだけシンボルが連続する

図3

のようなケースでは「Bが2個」「Wが2個」の並びに対して4ビットの符号語が割り当てられる。このときのデータ量は、シンボルの並びに対しては4ビット、1つのシンボルに対しては2ビットとなる。
つまり、このときの平均符号長は2ビットになる。

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

図4

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

図5

一般的な場合の固定長ランレングス符号の平均符号長は以下のようにして求める。
「B」「BB」「BBB」...「BBBBBBBB」の出現率を \(p_{b1}\)～\(p_{b8}\)、「W」「WW」「WWW」...「WWWWWWWW」の出現率を \(p_{w1}\)～\(p_{w8}\) とすると、シンボルの並びの平均の長さ (その並びにあるシンボルの個数の平均) \(L_s\) は


のように表わせる。

一方、どの並びに対する符号語も4ビットなので、「シンボルの並び」に対応する符号語の平均の長さ \(\bar{L}\) は、\(\bar{L}=4\) (ビット) となる。

よって、平均符号長、つまり「シンボル1つあたりに平均して割り当たる符号語の長さ」は以下のようになる。

表1の方法で \(p_{b1}=p_{w1}=0.43\) で、 \(p_{b2}\)～\(p_{b8}\) と \(p_{w2}\)～\(p_{w8}\) がすべて \(0.01\) のときの平均符号長 \(L\) を求めよ。

表1の方法で \(p_{b1}\)～\(p_{b7}\) と \(p_{w1}\)～\(p_{w7}\) がすべて\(0.01\)、\(p_{b8}=p_{w8}=0.43\) のときの平均符号長 \(L\) を求めよ。