エリアスガンマコーディング

正の整数のためのユニバーサル符号化方式

エリアス符号 ${\displaystyle \gamma }$またはエリアスガンマ符号は、ピーター・エリアスによって開発された正の整数を符号化する汎用符号である。^{[1] : 197, 199}これは、上限を事前に決定できない整数を符号化するときに最もよく使用されます。

エンコーディング

数値 x  ≥ 1をコード化するには：

1. がそれに含まれる 2 の最大の累乗であるとすると、 2 ^N ≤ x < 2 ^{N +1}となります。 ${\displaystyle N=\lfloor \log _{2}x\rfloor }$
2. ゼロビットを書き出し、 ${\displaystyle N}$
3. ビットの 2 進数である の2 進形式を追加します。 ${\displaystyle x}$ ${\displaystyle (N+1)}$

同じプロセスを表現する同等の方法:

1. 単項でエンコードします。つまり、ゼロの後に 1 が続くものとしてエンコードします。 ${\displaystyle N}$ ${\displaystyle N}$
2. の残りの2 進数字をのこの表現に追加します。 ${\displaystyle N}$ ${\displaystyle x}$ ${\displaystyle N}$

数値を表現するために、エリアスのガンマ（γ）はビットを使用する。^{[1] : 199} ${\displaystyle x}$ ${\displaystyle 2\lfloor \log _{2}(x)\rfloor +1}$

コードは次のように始まります (わかりやすくするために、コードの暗黙の確率分布が追加されています)。

番号	バイナリ	γエンコーディング	暗黙の確率
1 = 2 0  + 0	1	1	1/2
2 = 2 1 + 0	1 0	0 1 0	1/8
3 = 2 1 + 1	1 1	0 1 1	1/8
4 = 2 2 + 0	1 00	00 1 00	1/32
5 = 2 2 + 1	1 01	00 1 01	1/32
6 = 2 2 + 2	1 10	00 1 10	1/32
7 = 2 2 + 3	1 11	00 1 11	1/32
8 = 2 3 + 0	1 000	000 1 000	1/128
9 = 2 3 + 1	1 001	000 1 001	1/128
10 = 2 3 + 2	1 010	000 1 010	1/128
11 = 2 3 + 3	1 011	000 1 011	1/128
12 = 2 3 + 4	1 100	000 1 100	1/128
13 = 2 3 + 5	1 101	000 1 101	1/128
14 = 2 3 + 6	1 110	000 1 110	1/128
15 = 2 3 + 7	1 111	000 1 111	1/128
16 = 2 4 + 0	1 0000	0000 1 0000	1/512
17 = 2 4  +  1	1 0001	0000 1 0001	1/512

デコード

エリアスガンマコード化整数をデコードするには:

1. 最初の 1 に達するまで、ストリームから 0 を読み取ってカウントします。このゼロのカウントをN と呼びます。
2. 到達した数字が整数の最初の桁であり、その値が 2 ^Nであると考えて、整数の残りのN桁を読み取ります。

用途

ガンマ コーディングは、エンコードされた最大の値が事前にわからないアプリケーションや、大きな値よりも小さな値がはるかに多く含まれるデータを圧縮するために使用されます。

このような状況では、ガンマ符号化の方がサイズ効率が良い場合があります。例えば、上の表で、5のような小さな数値を格納するために固定の8ビットサイズを選択した場合、結果として得られるバイナリは になります00000101が、γ符号化の可変ビットバージョンは となり00 1 01、3ビット少なくなります。逆に、254のような大きな値を固定の8ビットサイズで格納すると になります11111110が、γ符号化の可変ビットバージョンは となり0000000 1 1111110、7ビット多く必要になります。

ガンマ符号化は、エリアスデルタ符号の構成要素です。

一般化

ガンマ符号化では、ゼロや負の整数は符号化されません。ゼロを扱う方法の一つは、符号化前に1を加算し、復号後に1を減算することです。もう一つの方法は、ゼロ以外の符号の前に1を付加し、ゼロを単一の0として符号化することです。

すべての整数をコード化する方法の一つは、コード化前に整数 (0, −1, 1, −2, 2, −3, 3, ...) を (1, 2, 3, 4, 5, 6, 7, ...) にマッピングする一対一写像を設定することです。ソフトウェアでは、非負の入力を奇数の出力に、負の入力を偶数の出力にマッピングすることで、これを最も簡単に実現できます。これにより、最下位ビットは反転された符号ビットになります。
${\displaystyle {\begin{cases}x\mapsto 2x+1&\mathrm {when~} x\geq 0\\x\mapsto -2x&\mathrm {when~} x<0\\\end{cases}}}$

指数ゴロム符号化は、ゴロム符号化が単項符号を一般化するのと同様に、ガンマ符号をより「平坦な」べき乗分布を持つ整数に一般化します。これは、数値を正の除数（通常は2のべき乗）で割り、商より1大きい値をガンマ符号で表し、剰余を通常の2進符号で表すというものです。

参照

• エリアスデルタ（δ）コーディング
• エリアス・オメガ（ω）符号化 – 正の整数を符号化するユニバーサルコード
• 正数（数値形式）  – コンピュータにおける浮動小数点数の変形リダイレクト先の簡単な説明を表示するページ

参考文献

1. エリアス, ピーター(1975年3月). 「ユニバーサルコードワードセットと整数の表現」. IEEE Transactions on Information Theory . 21 (2): 194– 203. doi :10.1109/tit.1975.1055349.

さらに読む

• Sayood, Khalid (2003). 「LevensteinとEliasのガンマ符号」.ロスレス圧縮ハンドブック. Elsevier . ISBN 978-0-12-620861-0。

「https://en.wikipedia.org/w/index.php?title=Elias_gamma_coding&oldid=1285268729」より取得