ゴロム符号

ゴロム符号（ゴロムふごう、Golomb coding)とは、南カリフォルニア大学のソロモン・ゴロムによって開発された、幾何分布に従って出現する整数を最適に符号化することのできる整数の符号化手法である。 ゴロム符号と類似の手法にライス符号があるが、ゴロム符号の特別な場合がライス符号になるため、ライス符号のことをゴロム・ライス符号(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 _{2}m$ ビットのバイナリ符号で符号化する。
   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	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.