レンジコーダ講座その2

Revised : 2006/07/31
Since : 2006/07/31

レンジコーダ（桁上がりなし）

説明を簡単にするために、全体を符号なし７bit（負は無）
レンジの精度を７bitとし最低確保する精度は３bitととする。（JAVAのbyte型を想定）
（通常はＣＰＵが高速にあつかえる最大サイズがよい）
最低確保する精度とは、両隣と区別可能であること。つまり、頻度総数の最大値を保証するものである。

ページの上部へ

符号化

例としてａｂｃaｂaを考える。
まず頻度表を作る。

総数は７であり3bitで表せるから、ここから符号化を開始する。
区間は[low , low + range)と表せる。

初期の区間は[0 , 128)とする。
この時128は含まないためレンジは127とする。下限値は0である。

まず、現在のレンジを頻度総数で割り、一個あたりの幅を算出する。
入力文字の下限値に一個あたりの幅を掛け、増加分の下限値を算出し、現在の下限値に加算する。（新たな下限値）
入力文字の頻度に一個あたりの幅を掛け、新たなレンジを算出する。

以上を繰り返す。
low + rangeが5bit以下になった場合、レンジ拡大する。
通常7-5=2bitを作業領域とする。
拡大も下限値、幅とも2bit左シフト（4倍）する。lowの上位2bitは出力する。

low + rangeが5bit以下にならなくても、rangeが3bit以下になった場合はレンジ拡大する。
この時、rengeはlow下位5bitの2の補数とし、3bitより大きくなるまで拡大する。(桁上がりしないようにレンジ縮小)

ａｂｃaｂaの符号化について下表に示す。

よって出力符号は出力済み+最終下限値となる。
2進数表記すると00111110010111010となる。

ページの上部へ

復号化

次はこの00111110010111010を復号化する。
頻度表は符号化時と同じである。

区間は[low , low + range)と表せる。

初期のレンジは符号時と同じ127とする。
codeは符号語の上位7bitを読み込む。

まず、現在のレンジを頻度総数で割り、一個あたりの幅を算出する。
(code - low)を一個あたりの幅で割り、どの文字の区間に入るか判定する。（桁上がり判定のためlowも記憶する）
入力文字の下限値に一個あたりの幅を掛け、増加した分の下限値を算出する。
入力文字の頻度に一個あたりの幅を掛け、新たなレンジを算出する。

符号化と同判定でレンジ拡大する。
符号化時と同様に2bit左シフトするが、この時codeの下位2bitに符号語の次の2bitを読み込む。

以上を繰り返す。
上で符号化した00111110010111010について復号化を下表に示す。

よってabcabaが復号できた。
（当然であるが）符号化と復号化では幅とレンジ拡大のタイミングがおなじである。