ゴロム符号のソースを表示

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

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

m > 1 のとき、符号化対象とする整数値 x(≧0) に対して、x を m で割った商を q 余りを r とする。
#商 q を[[アルファ符号|unary符号]]を用いて符号化する。
#余り r は <math>\log_2 m</math> に従って、次のように符号化する。
## <math>\log_2 m</math> が整数値である。すなわち、m が 2 の冪であるならば、r を <math>\log_2m</math> ビットのバイナリ符号で符号化する。
## それ以外の場合、<math>b=\lceil\log_2 m\rceil</math> としたとき
###<math>r < 2^b-m</math> なら、b - 1 ビットで r をバイナリ符号化
###それ以外は、<math>r+2^b-m</math> を b ビットのバイナリ符号化

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

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

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

{| class="wikitable"
|+ 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
|}

{| class="wikitable"
|+ その他の符号化の例
! 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 となる。

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

==関連項目==
*[[データ圧縮]]
*[[整数の符号化]]

==外部リンク==
* Golomb, S.W. (1966). [http://urchin.earth.li/~twic/Golombs_Original_Paper/ , Run-length encodings. IEEE Transactions on Information Theory, IT--12(3):399--401 ]
* R. F. Rice (1971) and R. Plaunt, [https://doi.org/10.1109/TCOM.1971.1090789 , "Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data, " IEEE Transactions on Communications, vol. 16(9), pp.&nbsp;889–897, Dec. 1971.]

{{デフォルトソート:ころむふこう}}
[[Category:データ圧縮|ころむふこう]]
{{Computer-stub|ころむふこう}}
{{データ圧縮}}