Golomb-Code

Der Golomb-Code ist eine Darstellungsform für alle positiven ganzen Zahlen, im Gegensatz zu anderen Codes, die nur einen begrenzten Bereich (z. B. 0-255) darstellen können. Er wurde 1966 von Solomon W. Golomb vorgestellt.

Der Code verwendet wenige Bits für kleine und viele Bits für größere Zahlen. Dabei kann er über einen Parameter gesteuert werden. Je größer der Parameter, um so langsamer wächst die Anzahl der zur Darstellung benötigten Bits, aber um so größer ist die Anzahl der minimal benötigten Bits für die kleinen Zahlen.

Aufgrund dieser Eigenschaften kann der Code für Entropiekodierungen verwendet werden, bei denen die Wahrscheinlichkeiten der zu kodierenden Zeichen (näherungsweise) eine geometrische Verteilung bilden.

Arbeitsweise

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

Mit den in diesem Artikel vorgestellten Formeln ist es nicht möglich, die 0 darzustellen. Um das zu ermöglichen, muss der zu kodierende Wert um 1 erhöht, oder die Subtraktion der 1 aus den Formeln entfernt werden.

Die Zahl $n$, mit $n>0$ wird durch

$q=\left\lfloor {\frac {n-1}{b}}\right\rfloor$

und

$r=n-qb-1\,$

beschrieben. Zur besseren Beschreibung wird noch die Zahl

$c=\left\lfloor \log _{2}b\right\rfloor$

benötigt.

Der Quotient wird dann unär ausgegeben, d. h. es werden $q$ "1" Bits gefolgt von einer "0" abgelegt.

Der Rest wird dann in einer "abgeschnittenen binären Darstellung" (en:Truncated_binary_encoding) genannten Codierung abgelegt. Diese Darstellung legt einen Teil der Werte, falls möglich, mit $\lceil \log _{2}b\rceil -1$ und den anderen Teil, mit $\lceil \log _{2}b\rceil$ Bit ab. Die Anzahl der Werte, die mit $\lceil \log _{2}b\rceil -1$ Bits abgelegt werden kann ist $2^{\lceil \log _{2}b\rceil }-b$

Beispiele

Die Darstellung der Zahl 10 mit einem Parameter 4:

$q=\left\lfloor {\frac {10-1}{4}}\right\rfloor =2$

$r=10-2\times 4-1=1$

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

Ein paar weitere Beispiele:

n	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
b=4	0 00	0 01	0 10	0 11	10 00	10 01	10 10	10 11	110 00	110 01
b=5	0 00	0 01	0 10	0 110	0 111	10 00	10 01	10 10	10 110	10 111
b=7	0 00	0 010	0 011	0 100	0 101	0 110	0 111	10 00	10 010	10 011

Anwendung

Der Golomb-Code kann angewendet werden, wenn Zahlen unbekannter Größe abspeichert werden sollen.

Das eigentliche Anwendungsgebiet liegt in der Datenkompression. Wenn die Wahrscheinlichkeiten der Zahlen eine bestimme Verteilung (exponentielle 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.

Datei:GolombRedundancy 2007 07 08.png

Die beiden Grafiken zeigen die Redundanz des Golomb-Code pro Symbol. Auf der Abszisse ist die Auftretenswahrscheinlichkeit des häufigeren Symbols ablesbar.

Rice-Code

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

Angenommen, es gilt $b=2^{p}$. Dann ist

$q=(n-1)\gg p$

und

$r=(n-1)\land (b-1)$

$\gg$ steht dabei für bitweises Verschieben nach rechts und $\land$ für bitweise Und-Verknüpfung.

$r$ wird dabei immer mit genau $p$ Bits dargestellt.

Literatur

Golomb S. W. Run Length Encodings, IEEE Transactions on Information Theory IT-12(3):399-401