ゴロム符号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

ゴロム符号(ゴロムふごう、Golomb coing)とは、南カリフォルニア大学ソロモン・ゴロムによって開発された、幾何分布に従って出現する整数を最適に符号化することのできる整数の符号化手法である。 ゴロム符号と類似の手法にライス符号があるが、ゴロム符号の特別な場合がライス符号になるため、ライス符号のことをゴロム・ライス符号(Golomb-Rice coding)と呼称することが多い。特にライス符号は符号化・復号の計算量が少ないことが特徴。圧縮率は幾何分布の時はハフマン符号と同一で、それ以外ではそれよりも悪い。

符号化の原理[編集]

符号化のパラメータとして、1 以上の整数値 m を用いる。

m > 1 のとき、符号化対象とする整数値 x(≧0) に対して、x を m で割った商を q 余りを r とする。

  1. 商 q をunary符号を用いて符号化する。
  2. 余り r は \log_2 m に従って、次のように符号化する。
    1. \log_2 m が整数値である。すなわち、m が 2 の冪であるならば、r を \log_2m ビットのバイナリ符号で符号化する。
    2. それ以外の場合、b=\lceil\log_2 m\rceil としたとき
      1. r < 2^b-m なら、b - 1 ビットで r をバイナリ符号化
      2. それ以外は、r+2^b-m を b ビットのバイナリ符号化

m = 1 のときは、unary符号に等しくなる。また、m が 2 の冪であるとき( m=2^k )は、ライス符号に等しくなる。

本質的な差はないが、ゴロム符号の原論文では、商の符号化で、通常の unary 符号とは 0 と 1 を反転させている。

符号化の例[編集]

m = 3 とする。このとき b = 2, 2^b-m=1 である。 よって、 r = 0 を 1 ビットで、r = 1, 2 を r+2^b-m とした上で2ビットで符号化する。

m = 3 の場合
数値(x) 商(q) 剰余(r) 商の符号 剰余の符号 符号(全体)
0 0 0 1 0 10
1 0 1 1 10 110
2 0 2 1 11 111
3 1 0 01 0 010
4 1 1 01 10 0110
5 1 2 01 11 0111
6 2 0 001 0 0010
7 2 1 001 10 00110
その他の符号化の例
x m = 4 m = 5 m = 8
0 100 100 1000
1 101 101 1001
2 110 110 1010
3 111 1110 1011
4 0100 1111 1100
5 0101 0100 1101
6 0110 0101 1110
7 0111 0110 1111
8 00100 01110 01000
9 00101 01111 01001
10 00110 00100 01010
11 00111 00101 01011
12 000100 00110 01100

x = 255, m = 8 なら、00000000000000000000000000000001111 となる。

応用[編集]

整数値の符号化として用いられるほか、画像(動画・静止画)や音声の圧縮で用いられる予測符号化の一部として、予測値との残差をエントロピー符号するのに利用される。

関連項目[編集]

外部リンク[編集]