ゴロム符号

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

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

m > 1 のとき、符号化対象とする整数値 x(≧0) に対して、x を m で割った商を q 余りを r とする。
商 q をunary符号を用いて符号化する。
余り r は  に従って、次のように符号化する。
  が整数値である。すなわち、m が 2 の冪であるならば、r を  ビットのバイナリ符号で符号化する。
 それ以外の場合、 としたとき
 なら、b - 1 ビットで r をバイナリ符号化
それ以外は、 を b ビットのバイナリ符号化

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

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

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

+ m = 3 の場合 数値(x) 商(q) 剰余(r) 商の符号 剰余の符号 符号(全体) 0 0 0 0 00 000 1 0 1 0 10 010 2 0 2 0 11 011 3 1 0 10 00 1000 4 1 1 10 10 1010 5 1 2 10 11 1011 6 2 0 110 00 11000 7 2 1 110 10 11010

+ その他の符号化の例 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 となる。

応用
整数値の符号化として用いられるほか、画像（動画・静止画）や音声の圧縮で用いられる予測符号化の一部として、予測値との残差をエントロピー符号するのに利用される。
画像 - JPEG-LS, LOCO-I, FELICS, SFALIC
音声 - FLAC
動画 - H.264

関連項目
データ圧縮
整数の符号化

外部リンク
 Golomb, S.W. (1966). , Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401 
 R. F. Rice (1971) and R. Plaunt, , "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data, " IEEE Transactions on Communications, vol. 16(9), pp. 889–897, Dec. 1971.

ころむふこう