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 Reihe 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 muß 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.

Die Darstellung des Restes wird in vielen Quellen falsch angegeben als:

Der Rest wird auf eine spezielle Weise abgelegt. Die ersten $c$ Werte werden mit $c$ Bits gespeichert. Wobei das höchstwertige Bit 0 ist. Die anderen Werte werden in $c+1$ Bits abgelegt, wobei das höchstwertige Bit gesetzt ist.

Diese Art der Ablegung funktioniert nicht. Das kann man sich einfach an einem Beispiel mit dem Parameter 7 überlegen. $c$ ist in diesem Fall 2. Das würde bedeuten, dass die ersten 2 Werte für den Rest als '00' und '01' abgelegt werden. Dann stehen noch 4 weitere Kodierungen mit je 3 Bits zur Verfügung '100', '101', '110', '111'. Es stehen somit 6 verschiedene Kodes zur Verfügung. Es werden aber Kodes für insgesamt 7 verschiedene Werte benötigt. Die Anzahl der Kodierungen reicht also nicht aus. In anderen Fällen, z.B. $b=5$ verschwendet diese Darstellung Bits, da mögliche Bitfolgen ungenutzt bleiben würden.

Richtigerweise muss der Rest in einer "abgeschnittenen binären Darstellung" (en:Truncated_binary_encoding) genannten Codierung abgelegt werden. 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 genau so 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 $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