Elias-γ-Code

Der Elias-γ-Code (benannt nach Peter Elias und dem griechischen Kleinbuchstaben Gamma), auch Elias-Gamma-Code oder Gamma-Code, ist eine Methode der Entropiekodierung, mit dem beliebige positive natürliche Zahlen effizient dargestellt und gespeichert werden können. Dabei beansprucht der Gamma-Code mehr Speicherplatz für größere Zahlen, eignet sich also insbesondere für Daten, bei denen kleinere Werte wahrscheinlicher sind als größere.

Der Gamma-Code wurde von Peter Elias 1975 zusammen mit anderen universellen Codes wie dem Elias-δ-Code publiziert. Er ist identisch zum exponentiellen Golomb-Code, würde dort $n-1$ statt $n$ codiert. Er findet in teilweise abgewandelter Form somit Anwendung an verschiedenen Stellen in der Datenkompression. Wie auch der exponentielle Golomb-Code eignet sich der Gamma-Code für geometrisch verteilte Eingabewerte, bei denen die Häufigkeit größerer Zahlen exponentiell abnimmt. Allerdings ist der Gamma-Code nicht optimal, wie es beispielsweise der Huffman-Code ist, dafür ist die Kodierung und Dekodierung deutlich einfacher und ohne Zusatzinformationen möglich.

Arbeitsweise

Um natürliche Zahlen, digital zu speichern, muss üblicherweise die Anzahl der Bits bekannt sein, mit denen eine Zahl gespeichert wurde. Diese Bitzahl begrenzt auch die größtmögliche speicherbare Zahl, z. B. 255 bei 8 Bit. Um dieses Problem zu lösen, enthält der Elias-Gamma-Code zusätzlich die Anzahl der für die Darstellung verwendeten Bits, die zwischen den codierten Zahlen variiert.

In der natürlichen Darstellung, genannt $\beta (n)$, werden für eine Zahl $n$ genau $b=\left\lfloor \log _{2}(n)\right\rfloor$ Bit benötigt, beispielsweise 1 Bit für $1$ oder 4 Bit für $15$ ($=1111_{2}$). Wenn nun $b$ unär codiert wird (als Folge von 0 und abschließende 1), lässt sich diese unäre Zahl benutzen, um die Menge der für $n$ benötigten Bits anzuzeigen. Anders als bei binärer Codierung kann eine unär codierte Zahl in einem Bitstrom immer eindeutig erkannt werden (präfixfreier Code). Die abschließende 1 der unär codierten Zahl muss nicht geschrieben werden, da $\beta (n)$ immer mit 1 beginnt; sie hat somit eine Doppelfunktion.

Es ergeben sich also die folgenden Codes:

$n$	$\gamma (n)$		$b$
1	1	1	1
2	010	0 1 0	2
3	011	0 1 1	2
4	00100	00 1 00	3
5	00101	00 1 01	3
6	00110	00 1 10	3
7	00111	00 1 11	3
8	0001000	000 1 000	4
9	0001001	000 1 001	4
10	0001010	000 1 010	4
15	0001111	000 1 111	4
16	000010000	0000 1 0000	5

Zur Verdeutlichung ist die codierte Zahl in der dritten Spalte aufgeteilt in unäre Länge, $1$ mit Doppelfunktion, und hinterer Teil von $n$.

Algorithmus

Zur Codierung einer Zahl $n$ im Elias-Gamma-Code:

• Ermittle die Anzahl der binären Stellen in $n$ abzüglich 1: $c=\left\lfloor log_{2}(n)\right\rfloor -1$
• Schreibe diese Anzahl Nullen gefolgt von $n$: $\gamma (n)=0^{c}\beta (n)$

Zur Dekodierung einer Zahl $n$ aus einem Bitstrom:

• Zähle Anzahl $c$ der Nullen bis zur ersten 1
• Lese weitere $c$ Bits hinter der ersten 1
• $n$ bildet sich aus allen diesen Bits, einschließlich der ersten 1