数と符号講座

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


Home   ∥ 二値 | αγδ | KZ | CBT | SSS | 0-1-2

二値モデル(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進数表記した時のビット数をα符号で出力し、続いて最上位ビットを除いてた残りの下位ビットを出力する。
δ符号は、γ符号でビット数を表すのにα符号を用いたものを、γ符号に変更したものである。

N α符号 γ符号 δ符号
1 1 1 1
2 01 01 0 010 0
3 001 01 1 010 1
4 0001 001 00 011 00
5 00001 001 01 011 01
6 000001 001 10 011 10
7 0000001 001 11 011 11
8 00000001 0001 000 00100 000
9 000000001 0001 001 00100 001
10 0000000001 0001 010 00100 010

ページの上部へ

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]

全ての自然数はフィボナッチ数の和で表すことができ、同じフィボナッチ数を2回使うことなく、
また隣接するフィボナッチ数は使われないことが知られている。
このことから、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から2k-1以下の数値はk ビットの固定長で表すことができる。
しかし、数値n (0 <= n < m) の上限値mが2k-1よりも小さい場合、m以上2k-1 以下の符号語は使われない。
CBT符号はこの部分を有効に利用する方法である。

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

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

復号化は、k-1ビット読み込み、その値が2k-m以上であれば、
もう1ビット読み込み、kビットの値から2k-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以上のものを更に分類する。

Num GR1 GR2 Code
0 0

1 1

2 2 0
3,4 2 1 0,1
5,6,7,8 2 2 0,1,2,3
9-16 2 3 0-7
17-32 2 4 0-15
33-64 2 5 0-31
65-128 2 6 0-63
129-256 2 7 0-127

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

ページの上部へ
容量300MB、月額125円、高性能なサーバが日本最大級のバックボーンに直結。
さくらのレンタルサーバ
ロリポップのドメインが65種類 → 85種類に!!
きっとお好みのドメインが見つかるはず!
アフィリエイトならリンクシェア