導入
ガンマ コーディングまたはエリアス ガンマ コーディングは、ピーター エリアスによって発明され、主にデータ圧縮に使用されるエントロピー コーディングです。
生成されるガンマ コードはプレフィックスおよびユニバーサルコードです。
原理
ガンマコーディングを使用すると、コーディングする値の間隔を最初に知る必要がなく、ゼロを除くすべての自然整数をコーディングすることができます（たとえば、以下の数値のみを許可する固定サイズのバイナリコーディングとは異なります）。符号化する際の上限は予め定められている）。
このため、ガンマ コーディングは 2 つの手順で行われます。
- 整数を表すために必要なビット数を単項エンコードでエンコードする。
- これと同じ数の必要なビットをバイナリコーディングして整数を実際にコーディングします。
実際には、整数の最上位ビットは暗黙的であるためエンコードされず、最初のステップで (同じ理由で) 1 を減じたビット数がエンコードされます。
数学的には、整数をエンコードするには
$$ {N, N \in \mathbb{N}^*} $$
、最初にコーディングします$$ {\lfloor \log_2 N \rfloor} $$
単項の場合、 $$ {\lfloor \log_2 N \rfloor} $$
バイナリのNの最下位ビット (プロセス中に暗黙的な最上位ビットが失われます)。コード長
厳密に正の自然数Nに関連付けられたガンマ コードの長さL は、次のように表すことができます。
相対整数のコーディング
実際のコーディングの前に、全単射を使用してガンマ コーディングで相対整数をエンコードし、負の数値またはゼロの数値を厳密に正の数値に変換することができます。デコード後、元の相対整数を見つけるために逆の演算を実行する必要があります。
たとえば、間隔の相対整数をエンコードするには
$$ {\left [ -A; +\infty \right ), A \in \mathbb{N}} $$
、関数を適用できます$$ {\begin{cases}\begin{align}&\scriptstyle f \colon \left [ -A; +\infty \right ) \to \mathbb{N}^* \\ &\textstyle x \mapsto x + A + 1\end{align}\end{cases}} $$
ガンマコーディングの前とその逆$$ {\begin{cases}\begin{align}&\scriptstyle f \colon \mathbb{N}^* \to \left [ -A; +\infty \right ) \\ &\textstyle x \mapsto {x – A – 1}\end{align}\end{cases}} $$
ガンマデコード後。 $$ {\begin{cases}\begin{align}&\scriptstyle f \colon \mathbb{Z} \to \mathbb{N}^* \\ &\textstyle x \mapsto \begin{cases} 2 \times x, x > 0\\ -2 \times x + 1, x \le 0\end{cases}\end{align}\end{cases}} $$
一般化
ガンマコーディングを一般化したものがゼータコーディングです。ガンマ コーディングは、パラメーター1 を使用したゼータ コーディングとして見ることができます。
例
| 10進数 N | バイナリ N | ビット数から 1 を引いた値 $$ {U = \lfloor \log_2 N \rfloor} $$ | ビット数から 1 を引いた値 (単項コーディングのU ) | 最上位ビットを除いたバイナリ B = N − 2 U + 1 | ガンマコード 単項のU の後にBが続く |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 | |
| 2 | 10 | 1 | 10 | 0 | 10 0 |
| 3 | 11 | 1 | 10 | 1 | 10 1 |
| 4 | 100 | 2 | 110 | 00 | 110 00 |
| 5 | 101 | 2 | 110 | 01 | 110 01 |