数と符号講座

Revised : 2006/09/17
Since : 2006/09/16

二値モデル（binary model）

二値レンジコーダでは2種類の文字{0,1}のみで符号化するため、0と1以外の数値は符号化できない。
そのため、2以上の数値は0と1からなる文字列に変更する必要がある。

簡単な方法は、0からNまでの数値を表すのにN個の「コンテキスト(context)」を用意することである。

コンテキストは二値レンジコーダの出現頻度表とみなすことができる。
ひとつのコンテキストでは2つの文字{0,1}を符号化することができる。
例えば0から7までの数値を符号化する場合、次のようになる。

  Context＼ N |  0  1  2  3  4  5  6  7
  ------------+--------------------------
  [Context 0] |  1  0  0  0  0  0  0  0
  [Context 1] |     1  0  0  0  0  0  0
  [Context 2] |        1  0  0  0  0  0
  [Context 3] |           1  0  0  0  0
  [Context 4] |              1  0  0  0
  [Context 5] |                 1  0  0
  [Context 6] |                    1  0
    

符号化する数値とコンテキストの番号を対応させるところが味噌である。
数値Nを符号化する場合、0からN-1番目までのコンテキストでは0を符号化し、N番目のコンテキストで1を符号化する。
復号は、0番目のコンテキストから順番に復号していき、1を復号したときのコンテキストの番号が復号する数値となる。
上の場合0から7までの範囲だから、コンテキストが全て0の場合、7を復号する。

ページの上部へ

α符号　γ符号　δ符号

自然数を符号化する方法で、小さな数ほど短い符号語が割り当てられるのが特徴である。

α符号は、自然数Nを符号化する時、N-1個の0を出力し、N番目に1を出力する。
復号は、連続する0の個数をカウントし、1が出現した時に0のカウント数+1を出力する。

γ符号は、自然数Nを2進数表記した時のビット数をα符号で出力し、続いて最上位ビットを除いてた残りの下位ビットを出力する。
δ符号は、γ符号でビット数を表すのにα符号を用いたものを、γ符号に変更したものである。

ページの上部へ

KZ符号（Kautz-Zeckendorf　Code）

α符号と同様の性質を持つが、その他に符号化されたビット列を途中からでも復号できるという性質も持つ。

この性質はKZ符号が符号化にフィボナッチ数列を利用していることによるものである。
フィボナッチ数列は最初にf(0) = 1,f(1) = 1が与えられ、f(n) = f(n-1) + f(n-2)で定義される。

フィボナッチ数をα符号で表すと（[自然数]を表す）
f(1) = 1 [1]
f(2) = 01 [2]
f(3) = 001 [3]
f(4) = 0001 [5]
f(5) = 00001 [8]

全ての自然数はフィボナッチ数の和で表すことができ、同じフィボナッチ数を２回使うことなく、
また隣接するフィボナッチ数は使われないことが知られている。
このことから、1であるbitは連続しないという性質を持つ。

1：1
2：01
3：001
4：101 f(1) + f(3)
5：0001
6：1001 f(1) + f(4)
7：0101 f(2) + f(4)
8：00001

KZ符号はこのビット列の先頭に110を付けたビット列をその文字の符号語とする。
これにより、途中から復号しても110が出現した所が文字の始まりだと認識できる。

1：110 1
2：110 01
3：110 001
4：110 101

ページの上部へ

CBT符号(Complete Binary Tree Code)

CBT符号は固定長の符号を改良したものである。
0から2^k-1以下の数値はk ビットの固定長で表すことができる。
しかし、数値n (0 <= n < m) の上限値mが2^k-1よりも小さい場合、m以上2^k-1 以下の符号語は使われない。
CBT符号はこの部分を有効に利用する方法である。

CBT符号は0 <= n < 2^k-mの数値nをk-1ビットで表し、2^k-m <= n < mの数値nをkビットで表す。

符号化は、0 <= n < 2^k-mならばnをk-1ビットの2進数で表す。
2^k-m <= n < mならばn + 2^k-mをkビットで表す。

復号化は、k-1ビット読み込み、その値が2^k-m以上であれば、
もう1ビット読み込み、kビットの値から2^k-mを減算する。

    k = 4, m = 10    k = 4, m = 11    k = 4, m = 12 
    n   符号語       n   符号語       n   符号語    
  ---------------   ---------------  ---------------
    0    0 0 0       0    0 0 0       0    0 0 0    
    1    0 0 1       1    0 0 1       1    0 0 1    
    2    0 1 0       2    0 1 0       2    0 1 0    
    3    0 1 1       3    0 1 1       3    0 1 1    
    4    1 0 0       4    1 0 0       4  1 0 0 0    
    5    1 0 1       5  1 0 1 0       5  1 0 0 1    
    6  1 1 0 0       6  1 0 1 1       6  1 0 1 0    
    7  1 1 0 1       7  1 1 0 0       7  1 0 1 1    
    8  1 1 1 0       8  1 1 0 1       8  1 1 0 0    
    9  1 1 1 1       9  1 1 1 0       9  1 1 0 1    
                    10  1 1 1 1      10  1 1 1 0    
                                     11  1 1 1 1    
    

ページの上部へ

SSS符号(Start Step Stop Code)

SSS符号は3つの数値パラメータで決まる符号化方式である。
例えば、Start=2,Step=3,Stop=8の場合、SSS(2,3,8)と表す。

SSS(2,3,8)の場合、Startより長さ2のビット列を順に生成する。
00,01,10,11が生成され、数値0から3に対応する。
次に、Start + Stepより長さ5のビット列を生成する。
00000から11111まで32個のビット列が生成され、数値4から35に対応させる。
さらに、ビット長をStep分の3ビット増やし、長さ8のビット列を生成する。
00000000から11111111までの256個のビット列が生成され、数値36から291に対応する。
ここでStopビットまでの生成が済んだので終了する。

SSS(2,3,8)では、0から291までの292個の数値が符号化できることが分かる。
しかし、このままでは2,5,8ビットの符号語が混在し、復号できない。

そこで、符号語の前にどのStepで生成されたかをα符号で付加する。
2ビットには1を、5ビットには01を付加する。
8ビットは最後なので、最後の1を除いて00を付加する。

0：1 00
1：1 01
2：1 10
3：1 11
4：01 00000
5：01 00001
35：01 11111
36：00 00000000
291：00 11111111

ページの上部へ

0-1-2 coding

0-1-2 codingでは、文字を0,1,2の3種類に分類し、符号化する方法である。
分類後は適切な情報源モデルで符号化する。

例えば、1バイト(0-255)とEOF(256)を符号化する場合、0-256の257個を考え、
次のように分類することとする。
グループ1で0,1,2に分類する。2以上は2とする。
グループ2で2以上のものを更に分類する。

GR1,GR2,Codeはそれぞれ独立であるため、各々で適切な情報源モデルに切り替えたり、
頻度表や更新方法を切り替えたりすることで圧縮率を向上させることができる。