Elias-γ-Code

Algorithmus zur Datenkompression

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 statt 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

Bearbeiten

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  , werden für eine Zahl   genau   Bit benötigt, beispielsweise 1 Bit für   oder 4 Bit für   ( ). Wenn nun   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   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   immer mit 1 beginnt; sie hat somit eine Doppelfunktion.

Es ergeben sich also die folgenden Codes:

     
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,   mit Doppelfunktion, und hinterer Teil von  .

Algorithmus

Bearbeiten

Zur Codierung einer Zahl   im Elias-Gamma-Code:

  • Ermittle die Anzahl der binären Stellen in   abzüglich 1:  
  • Schreibe diese Anzahl Nullen gefolgt von  :  

Zur Dekodierung einer Zahl   aus einem Bitstrom:

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

Einzelnachweise

Bearbeiten
  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

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