エリアス符号またはエリアスガンマ符号は、ピーター・エリアスによって開発された正の整数を符号化する汎用符号である。[1] :197、199 これは、上限を事前に決定できない整数を符号化するときに最もよく使用されます。
エンコーディング
x ≥ 1 の数値 をコード化するには :
- がそれに含まれる2の最大の累乗であるとします。したがって、2 N ≤ x < 2 N +1です。
- ゼロビットを書き出し、
- ビットの2進数である の2 進形式を追加します。
同じプロセスを表現する同等の方法:
- 単項でエンコードします。つまり、ゼロの後に 1 が続きます。
- の残りの2 進数桁をのこの表現に追加します。
数値を表現するために、エリアスのガンマ(γ)はビットを使用する。[1] :199
コードは次のように始まります (わかりやすくするために、コードの暗黙の確率分布が追加されています)。
デコード
エリアスガンマコード化整数をデコードするには:
- 最初の 1 に達するまで、ストリームから 0 を読み取ってカウントします。このゼロのカウントをN と呼びます。
- 到達した数字を整数の最初の桁(2 N )として、残りの整数のN桁を読み取ります。
用途
ガンマ符号化は、最大のエンコード値が事前に分からないアプリケーションや、小さな値が大きい値よりはるかに頻繁に発生する データを圧縮するために使用されます[疑わしい–議論] 。
ガンマ符号化は、エリアスデルタ符号の構成要素です。
一般化
ガンマ コーディングでは、ゼロまたは負の整数はコーディングされません。ゼロを処理する 1 つの方法は、コーディング前に 1 を加算し、デコード後に 1 を減算することです。もう 1 つの方法は、ゼロ以外の各コードの前に 1 を付け、ゼロを単一の 0 としてコーディングすることです。
すべての整数をコード化する方法の 1 つは、コード化する前に整数 (0, −1, 1, −2, 2, −3, 3, ...) を (1, 2, 3, 4, 5, 6, 7, ...) にマッピングする一対一変換を設定することです。ソフトウェアでは、非負の入力を奇数の出力にマッピングし、負の入力を偶数の出力にマッピングすることで、これを最も簡単に行うことができます。これにより、最下位ビットが反転した符号ビットになります。
指数ゴロム符号化は、ゴロム符号化が単項符号化を一般化するのと同様に、ガンマ コードを「より平坦な」べき乗分布を持つ整数に一般化します。この符号化では、数値を正の除数 (通常は 2 の累乗) で割り、商より 1 大きいガンマ コードを記述し、余りを通常の 2 進コードで記述します。
参照
- エリアスデルタ(d)コーディング – 正の整数をエンコードするユニバーサルコード
- エリアス・オメガ(?)コーディング – 正の整数をエンコードするユニバーサルコード
- Posit(数値形式) – コンピュータの浮動小数点数の変形
参考文献
- ^ ab エリアス、ピーター(1975年3月)。 「ユニバーサルコードワードセットと整数の表現」IEEE Transactions on Information Theory。21(2):194–203。doi :10.1109/tit.1975.1055349。
