Rice-Code


Rice-Code

Der Golomb-Code ist eine Darstellungsform für alle positiven ganzen Zahlen einschließlich der Null, im Gegensatz zu anderen Codes, die nur einen endlichen 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, 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.

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.

Inhaltsverzeichnis

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.

Die Zahl n, mit n > 0 wird durch

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

und

r = n - qb\,

beschrieben. Zur besseren Beschreibung wird noch die Zahl

c = \left\lceil\log_2 b\right\rceil

benötigt.

Als erstes wird q + 1 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 c − 1 Bits und den anderen Teil, mit c Bits ab. Die Anzahl der Werte, die mit c − 1 Bits abgelegt werden kann ist 2cb

Beispiele

Die Darstellung der Zahl 10 mit einem Parameter 4:

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

r = 10 - 2 \cdot 4  = 2

c = \left\lceil\log_2 4\right\rceil = 2

Abhängig von c wird die Codierung vervollständigt:

  • falls r < 2cb ist, wird r als Binärcode mit der Länge c − 1 geschrieben.
  • falls r2cb ist, wird r + 2cb als Binärcode mit der Länge c 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

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

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 (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 b eine Potenz von 2 ist. Diese Codes lassen sich sehr einfach mit Bitshiften und logischen Bitoperationen umsetzen.

Angenommen, es gilt b = 2p. Dann ist

q = n \gg p

und

r = n \and (b-1)

\gg steht dabei für bitweises Verschieben nach rechts und \and 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


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Rice code — Der Golomb Code ist eine Darstellungsform für alle positiven ganzen Zahlen einschließlich der Null, im Gegensatz zu anderen Codes, die nur einen endlichen Bereich (z. B. 0 255) darstellen können. Er wurde 1966 von Solomon W. Golomb vorgestellt.… …   Deutsch Wikipedia

  • Rice, California — is a vacant town site in the southern tip of the Mojave Desert in unincorporated San Bernardino County, California, United States.The town, located on present day State Route 62 approximately midway between Twentynine Palms and the Arizona state… …   Wikipedia

  • Rice — Rice, TX U.S. city in Texas Population (2000): 798 Housing Units (2000): 371 Land area (2000): 2.705666 sq. miles (7.007642 sq. km) Water area (2000): 0.091787 sq. miles (0.237728 sq. km) Total area (2000): 2.797453 sq. miles (7.245370 sq. km)… …   StarDict's U.S. Gazetteer Places

  • Rice Lake — Rice Lake, WI U.S. city in Wisconsin Population (2000): 8320 Housing Units (2000): 3799 Land area (2000): 8.631421 sq. miles (22.355278 sq. km) Water area (2000): 1.033227 sq. miles (2.676045 sq. km) Total area (2000): 9.664648 sq. miles… …   StarDict's U.S. Gazetteer Places

  • Rice Lake, MN — U.S. Census Designated Place in Minnesota Population (2000): 226 Housing Units (2000): 65 Land area (2000): 7.690786 sq. miles (19.919044 sq. km) Water area (2000): 0.182559 sq. miles (0.472825 sq. km) Total area (2000): 7.873345 sq. miles… …   StarDict's U.S. Gazetteer Places

  • Rice Lake, WI — U.S. city in Wisconsin Population (2000): 8320 Housing Units (2000): 3799 Land area (2000): 8.631421 sq. miles (22.355278 sq. km) Water area (2000): 1.033227 sq. miles (2.676045 sq. km) Total area (2000): 9.664648 sq. miles (25.031323 sq. km)… …   StarDict's U.S. Gazetteer Places

  • Rice, MN — U.S. city in Minnesota Population (2000): 711 Housing Units (2000): 250 Land area (2000): 5.985750 sq. miles (15.503020 sq. km) Water area (2000): 0.111547 sq. miles (0.288906 sq. km) Total area (2000): 6.097297 sq. miles (15.791926 sq. km) FIPS… …   StarDict's U.S. Gazetteer Places

  • Rice, TX — U.S. city in Texas Population (2000): 798 Housing Units (2000): 371 Land area (2000): 2.705666 sq. miles (7.007642 sq. km) Water area (2000): 0.091787 sq. miles (0.237728 sq. km) Total area (2000): 2.797453 sq. miles (7.245370 sq. km) FIPS code:… …   StarDict's U.S. Gazetteer Places

  • Rice University — Infobox University name = William Marsh Rice University image size = 200px motto = Letters, Science, Art established = 1891 (opened 1912) type = Private calendar= Semester president = David Leebron city = Houston state = TX country = U.S.… …   Wikipedia

  • Rice Video — Infobox Software name = Rice Video caption = The interface of Rice Video developer = Rice (Beta 10 and before) Mudlord (post beta 10) latest release version = 6.1.4 latest release date = December 31, 2007 operating system = MS Windows, Linux… …   Wikipedia