Golomb-Code - LinkFang.de





Golomb-Code


Der Golomb-Code ist eine Entropiekodierung für alle nichtnegativen ganzen Zahlen, die im Gegensatz zu anderen Codes der Quellenkodierung nur einen endlichen Bereich (z. B. den Wertebereich 0–255) darstellen können. Er wurde 1966 von Solomon W. Golomb entwickelt.[1] Der Code verwendet wenige Bits für kleine und viele Bits für größere Zahlen. Dabei kann er über einen positiven, ganzzahligen Parameter gesteuert werden. Je größer der Parameter, desto langsamer wächst die Anzahl der zur Darstellung benötigten Bits, aber desto größer ist die Anzahl der minimal benötigten Bits für die kleinen Zahlen.

Der Rice-Code ist eine Variante des Golomb-Codes, bei dem der Steuerparameter eine Zweierpotenz ist. Diese Einschränkung ist von Vorteil, da insbesondere in der digitalen Verarbeitung die Multiplikation bzw. Division von 2 sehr effizient implementiert werden kann. Der Rice-Code wurde 1971 von Robert F. Rice und J. Plaunt vorgestellt.[2]

Der Code kann im Bereich der verlustlosen Datenkompression verwendet werden, wenn die Wahrscheinlichkeiten der zu kodierenden Quellendaten (näherungsweise) eine geometrische Verteilung bilden. Typische Anwendungsbereiche sind, als ein Teilverfahren neben anderen Algorithmen, die Bildkompression und Audiodatenkompression.

Arbeitsweise

Der Code arbeitet mit der Idee, die darzustellende Zahl [math]n[/math] durch einen Quotienten [math]q[/math] und den Rest [math]r[/math] bei einer Division mit einem Parameter [math]b[/math] zu ersetzen.

Die Zahl [math]n[/math] mit [math]n \geq 0[/math] wird durch

[math]q=\left\lfloor \frac{n}{b} \right\rfloor[/math]

und

[math]r = n - qb\,[/math]

beschrieben. Zur besseren Beschreibung wird noch die Zahl

[math]c = \left\lceil\log_2 b\right\rceil[/math]

benötigt. Als erstes wird q + 1 unär ausgegeben, d. h. es werden [math]q[/math] "1" Bits gefolgt von einer "0" abgelegt.

Der Rest wird dann in einer „abgeschnittenen binären Darstellung“ (Truncated-Binary-Encoding) genannten Codierung abgelegt. Diese Darstellung legt einen Teil der Werte, falls möglich, mit [math]c - 1[/math] Bits und den anderen Teil mit [math]c[/math] Bits ab. Die Anzahl der Werte, die mit [math]c - 1[/math] Bits abgelegt werden können, ist [math]2^{c}-b[/math].

Beispiele

Die Darstellung der Zahl 10 mit einem Parameter 4:

[math]q = \left\lfloor\frac{10}{4}\right\rfloor = 2[/math]
[math]r = 10 - 2 \cdot 4 = 2[/math]
[math]c = \left\lceil\log_2 4\right\rceil = 2[/math]

Abhängig von [math]c[/math] wird die Codierung vervollständigt:

  • falls [math]r[/math] < [math]2^{c}-b[/math] ist, wird [math]r[/math] als Binärcode mit der Länge [math]c - 1[/math] geschrieben.
  • falls [math]r[/math][math]2^{c}-b[/math] ist, wird [math]r + 2^{c}-b[/math] als Binärcode mit der Länge [math]c[/math] geschrieben.

Daraus resultiert die Bitfolge "110 10". Das Leerzeichen zeigt den Übergang vom Quotienten zum Rest.

Ein paar weitere Beispiele:

n 0 1 2 3 4 5 6 7 8 9 10
b=3 0 0 0 10 0 11 10 0 10 10 10 11 110 0 110 10 110 11 1110 0 1110 10
b=4 0 00 0 01 0 10 0 11 10 00 10 01 10 10 10 11 110 00 110 01 110 10
b=5 0 00 0 01 0 10 0 110 0 111 10 00 10 01 10 10 10 110 10 111 110 00
b=7 0 00 0 010 0 011 0 100 0 101 0 110 0 111 10 00 10 010 10 011 10 100

Anwendung

Der Golomb-Code kann angewendet werden, wenn Zahlen unbekannter Größe abgespeichert werden sollen, doch das eigentliche Anwendungsgebiet liegt in der Datenkompression.

Wenn die Wahrscheinlichkeiten der Zahlen eine bestimmte Verteilung (geometrische Verteilung) aufweisen, dann kann der Golomb-Code ähnlich effizient wie der Huffman-Code sein, ist dabei aber sparsamer mit Speicher, leichter zu implementieren und schneller in der Ausführung.

Rice-Code

Der Rice-Code ist eine Variante des Golomb-Codes, bei dem der Parameter [math]b[/math] eine Potenz von 2 ist. Diese Codes lassen sich sehr einfach mit Bitshiften und logischen Bitoperationen umsetzen.

Angenommen, es gilt [math]b=2^p[/math]. Dann ist

[math]q = n \gg p[/math]

und

[math]r = n \and (b-1)[/math]

Das Symbol [math]\gg[/math] steht dabei für bitweises Verschieben nach rechts und [math]\and[/math] für bitweise Und-Verknüpfung. [math]r[/math] wird dabei immer mit genau [math]p[/math] Bits und normal binär dargestellt.

Einzelnachweise

  1. Solomon W. Golomb: Run-Length Encodings. In: IEEE Transactions on Information Theory IT-12 (3). 1966, S. 399–401, abgerufen am 19. April 2013.
  2. Robert F. Rice, J. Plaunt: Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data. Hrsg.: IEEE Transactions on Communication Technology. Band 19, Nr. 6. California Institute of Technology, Pasadena 1971, S. 889–897, doi:10.1109/TCOM.1971.1090789 .

Kategorien: Datenkompression

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Golomb-Code (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.