Quelltext der Seite 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.&nbsp;B. den Wertebereich 0–255) darstellen können. Er wurde 1966 von [[Solomon W. Golomb]] entwickelt.<ref name="golomb1" /> 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.<ref name="rice1" /> Einige Varianten des Rice-Codes werden auch als '''Exponentieller Golomb-Code''' ([[Englische Sprache|englisch]]: ''Exponential-Golomb Code'') bezeichnet.

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]]. Beispielsweise verwenden das Videokompressionsformat [[H.264]] und das Audiokompressionsformat [[FLAC]]<ref>{{Internetquelle |autor=van Beurden & Weaver |url=https://datatracker.ietf.org/doc/html/draft-ietf-cellar-flac-06#section-5.4 |titel=Free Lossless Audio Codec: 5.4. Residual Coding |werk=Internet-Draft |hrsg=Internet Engineering Task Force |datum=2022-10-11 |sprache=en |abruf=2022-10-18}}</ref> je eine verschiedene Variante des exponentiellen Golomb-Codes.

== 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ärsystem|unär]] ausgegeben, d.&nbsp;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 <code>110 10</code>. Das Leerzeichen zeigt den Übergang vom Quotienten zum Rest.

Ein paar weitere Beispiele:

{| class="wikitable"
|- class="hintergrundfarbe6"
| n
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
|-
|class="hintergrundfarbe8" | b=3
| 0 0
| 0 10
| 0 11
| 10 0
| 10 10
| 10 11
| 110 0
| 110 10
| 110 11
| 1110 0
| 1110 10
|-
|class="hintergrundfarbe8" | b=4
| 0 00
| 0 01
| 0 10
| 0 11
| 10 00
| 10 01
| 10 10
| 10 11
| 110 00
| 110 01
| 110 10
|-
|class="hintergrundfarbe8" | b=5
| 0 00
| 0 01
| 0 10
| 0 110
| 0 111
| 10 00
| 10 01
| 10 10
| 10 110
| 10 111
| 110 00
|-
|class="hintergrundfarbe8" | 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 ==
[[Datei:GolombCodeRedundancy.svg|mini|hochkant=1.5|Die beiden Grafiken zeigen die Redundanz des Golomb-Codes pro Symbol.]]

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 \land (b-1)</math>

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

=== Exponentieller Golomb-Code ===
Der exponentielle Golomb-Code ist eine weitere Variante des Rice-Codes und gleichzeitig identisch zum [[Elias-γ-Code]], würde dort <math>n+1</math> statt <math>n</math> kodiert.

<math>p</math> wird für jede Zahl genau als <math>p = \left\lceil \log_2 (n+1) \right\rceil</math> gewählt, was der „natürlichen“ Bitbreite von <math>n+1</math> entspricht. Dann wird die unäre Codierung von <math>q</math> nicht mit „1“-Bits gefolgt von „0“, sondern mit „0“-Bits gefolgt von „1“ umgesetzt. Da die binär gespeicherte Zahl <math>r</math> immer an höchster Stelle eine „1“ aufweist, muss diese höchste „1“ nicht doppelt gespeichert werden. Die Enkodierung und Dekodierung vereinfachen sich somit zu folgenden Schritten:

* Zum Kodieren von <math>n</math>: Schreibe <math>p</math> viele „0“-Bits, danach schreibe <math>n+1</math> mit der natürlichen Anzahl Bits.
* Zum Dekodieren von <math>n</math>: Lese „0“-Bits bis einschließlich des ersten „1“-Bits, und lese so viele darauffolgende Bits, wie zuvor „0“-Bits gelesen wurden. Das Ergebnis ist dieser hintere Teil der kodierten Zahl minus 1.

Es zeigt sich, dass eine separate Speicherung von <math>p</math> nicht notwendig ist, da es selbst Teil der kodierten Zahl ist.

==== Verallgemeinerung zu beliebiger Ordnung ====
Die Kodierung kann mithilfe des Konzepts der ''Ordnung'' <math>k</math> verallgemeinert werden. Das obige Schema entspricht der Ordnung <math>k=0</math>. Bei höheren Ordnungen geschieht eine Aufteilung der Zahl <math>n</math> (nicht <math>n+1</math>!) in Quotient <math>q</math> und Rest <math>r</math> ähnlich zum normalen Rice-Code. Der Dividend ist nun <math>2^k</math>, d.&nbsp;h. <math>q = n \gg k</math> und <math>r = n \land (k-1)</math>. Bildlich gesprochen werden die Bits der Zahl in den (festen) unteren Teil <math>r</math>, der immer <math>k</math> Bits hat, und den (variablen) Teil <math>q</math> aufgeteilt.

Für die finale Kodierung wird <math>q</math> im gewöhnlichen exponentiellen Golomb-Code kodiert, d.&nbsp;h. Ordnung 0 wie oben, und <math>r</math> wird mit <math>k</math> Bits (die laut Definition immer ausreichen) an das so kodierte <math>q</math> angehängt. Eine kodierte Zahl umfasst also drei Teile, hier dargestellt anhand <math>k=5</math> und der kodierten Zahl 489:

<math>489 \longmapsto \underset{\text{Bittiefe von }q\text{ unär}}{\underbrace{0000}} \underset{q}{\underbrace{10000}}\quad \underset{r}{\underbrace{01001}}</math>

Der Vorteil dieser Kodierung besteht darin, dass der benötigte Speicherplatz für große Zahlen weniger als die beim Rice-Code benötigten <math>2\left\lceil \log_2 n+1 \right\rceil</math> („doppelt so viele Bits wie die Zahl selbst hat“) beträgt.

Der Parameter <math>k</math> muss separat gewählt und gespeichert werden. Bei großen Datensätzen eignet sich häufig nicht ein <math>k</math> für alle Daten, daher gibt es verschiedene Verfahren, ein variables <math>k</math> zu wählen. Als einfachen Ansatz verwendet [[FLAC]] die Möglichkeit, mehrere Blöcke variabler Größe mit einem jeweils eigenen <math>k</math> zu kodieren. Der Melcode-Algorithmus und seine Varianten passen <math>k</math> automatisch anhand eines einfachen Algorithmus an, welcher symmetrisch auf Enkodier- und Dekodierseite angewandt wird und ohne explizite Speicherung von <math>k</math> auskommt.<ref>{{Literatur |Autor=Walter D. Leon-Salas, Sina Balkir, Khalid Sayood, Nathan Schemm, Michael W. Hoffman |Titel=A CMOS Imager With Focal Plane Compression Using Predictive Coding |Sammelwerk=IEEE Journal of Solid-State Circuits |Band=42 |Nummer=11 |Datum=2007-11 |ISSN=0018-9200 |DOI=10.1109/JSSC.2007.907191 |Seiten=2555–2572 |Online=https://ieeexplore.ieee.org/document/4362102/ |Abruf=2023-08-16}}</ref><ref>{{Literatur |Autor=M.J. Weinberger, G. Seroussi, G. Sapiro |Titel=The LOCO-I lossless image compression algorithm: principles and standardization into JPEG-LS |Sammelwerk=IEEE Transactions on Image Processing |Band=9 |Nummer=8 |Datum=2000-08 |DOI=10.1109/83.855427 |Seiten=1309–1324 |Online=http://ieeexplore.ieee.org/document/855427/ |Abruf=2023-08-16}}</ref>

=== Verallgemeinerung für negative Zahlen ===
Rice-Code und allgemeiner exponentieller Golomb-Code können zwar 0, aber keine negativen Zahlen kodieren. Dies wird durch eine der ''Zickzackkodierungen'' möglich gemacht, welche die negativen auf die positiven Zahlen abbilden, aber die Eigenschaften der Entropiekodierung erhalten; d.&nbsp;h. betragsmäßig kleine Zahlen werden weiterhin auf kleine Zahlen abgebildet. Konkret bildet man eine Hälfte der ganzen Zahlen auf die geraden natürlichen Zahlen ab und die andere Hälfte auf die ungeraden natürlichen Zahlen:

<math>n = \begin{cases}2x & \text{ falls } x \ge 0\\-2x-1 & \text{ falls } x < 0\end{cases} \quad \text{(FLAC)} \quad \quad n = \begin{cases}-2x & \text{ falls } x \le 0\\2x-1 & \text{ falls } x > 0\end{cases} \quad \text{(H.264)}</math>

Danach folgt normale Rice-Kodierung oder exponentielle Golomb-Kodierung. In der Praxis lassen sich sowohl De- als auch Enkodierung dieses Formats durch Benutzung von Bitmasken und Shifts beschleunigen.

== Einzelnachweise ==
<references>
<ref name="golomb1">
{{Internetquelle
 |autor=Solomon W. Golomb
 |url=https://urchin.earth.li/~twic/Golombs_Original_Paper/
 |titel=Run-Length Encodings
 |werk=IEEE Transactions on Information Theory IT-12 (3)
 |datum=1966
 |seiten=399–401
 |zugriff=2013-04-19}}
</ref>
<ref name="rice1">
{{Literatur
 |Autor=Robert F. Rice, J. Plaunt
 |Hrsg=IEEE Transactions on Communication Technology
 |Titel=Adaptive Variable-Length Coding for Efficient Compression of Spacecraft Television Data
 |Band=19
 |Nummer=6
 |Verlag=California Institute of Technology
 |Ort=Pasadena
 |Datum=1971
 |Seiten=889–897
 |DOI=10.1109/TCOM.1971.1090789}}
</ref>
</references>

[[Kategorie:Datenkompression]]
[[Kategorie:Kodierungstheorie]]