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.^[1] Er ist identisch zum exponentiellen Golomb-Code, würde dort ${\displaystyle n-1}$ statt ${\displaystyle 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^{[Anm 1]}, 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 ${\displaystyle \beta (n)}$, werden für eine Zahl ${\displaystyle n}$ genau ${\displaystyle b=\left\lfloor \log _{2}(n)\right\rfloor }$ Bit benötigt, beispielsweise 1 Bit für ${\displaystyle 1}$ oder 4 Bit für ${\displaystyle 15}$ (${\displaystyle =1111_{2}}$). Wenn nun ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle \beta (n)}$ immer mit 1 beginnt; sie hat somit eine Doppelfunktion.

Es ergeben sich also die folgenden Codes:

${\displaystyle n}$	${\displaystyle \gamma (n)}$		${\displaystyle 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, ${\displaystyle 1}$ mit Doppelfunktion, und hinterer Teil von ${\displaystyle n}$.

Algorithmus

Zur Codierung einer Zahl ${\displaystyle n}$ im Elias-Gamma-Code:

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

Zur Dekodierung einer Zahl ${\displaystyle n}$ aus einem Bitstrom:

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

Einzelnachweise

1. P. Elias: Universal codeword sets and representations of the integers. In: IEEE Transactions on Information Theory. Band 21, Nr. 2, März 1975, ISSN 0018-9448, S. 194–203, doi:10.1109/TIT.1975.1055349 (ieee.org [abgerufen am 14. Mai 2024]). 

Anmerkungen

1. Natürliche Zahl heißt hier: positive ganze Zahlen, also bei 1 beginnend.