Kod Golomba

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Kod Golomba - kod binarny zmiennej długości, służący kodowaniu liczb całkowitych nieujemnych, o potencjalnie nieograniczonej wartości. Został opracowany w 1960 roku przez Solomona W. Golomba.

W kodowaniu Golomba zbiór liczb jest dzielony na rozłączne podprzedziały o długości , tzn. , zaś liczba jest przedstawiana za pomocą pary (numer przedziału do którego należy, odległość od jego początku). Wartość jest nazywana rzędem kodu; jeśli rząd jest potęgą dwójki, taki kod nazywany jest kodem Rice'a (od nazwiska pomysłodawcy, Roberta F. Rice'a).

Kod jest optymalny dla źródeł o geometrycznym rozkładzie prawdopodobieństwa, tzn. prawdopodobieństwo i-tej wartości wynosi (np. dla będą to ).

Kodowanie Rice'a z adaptacyjnym dobieraniem rzędu jest stosowane w m.in. algorytmie kompresji bezstratnej JPEG-LS oraz FLAC.

Kodowanie[edytuj kod]

Kodowanie liczby wymaga znalezienia dwóch wartości:

  1. przedziału do którego należy liczba: ,
  2. odległości od początku przedziału: .

Ogólnie .

Słowo kodowe składa się z dwóch części:

  1. liczby zapisanej w kodzie unarnym
  2. liczby zapisanej w kodzie binarnym (o prawie stałej długości, patrz następna sekcja)

Słowa kodowe nie są krótsze niż .

Dla kodów rzędu kod Golomba redukuje się do kodów unarnych, nie pojawia się zakodowane .

W przypadku kodów Rice'a ( jest potęgą dwójki) kodowanie jest uproszczone, ponieważ większość działań realizowana jest za pomocą szybkich operacji bitowych (koniunkcja, przesunięcie bitowe): wartość jest zapisana na pewnej liczbie młodszych bitów, na starszych.

Kod binarny o prawie stałej długości[edytuj kod]

Jeśli liczba wartości jest potęgą dwójki , wówczas kod binarny ma stałą długość - składa się z bitów; niech oznacza -bitowy zapis wartości .

Gdy liczba kodowanych wartości nie jest potęgą dwójki, można skonstruować kod prefiksowy, w którym początkowych wartości zostanie zapisanych na bitach, a pozostałe bitach.

Kodowanie rozpoczyna się od określenia wartości granicznej :

  • jeśli liczba otrzymuje kod -bitowy -
  • jeśli liczba otrzymuje kod -bitowy liczby o większej -
liczba kod
0 00
1 01
2 10
3 110
4 111

Np. przy kodowaniu pięciu symboli i , liczba . Zatem trzy pierwsze liczby (, i ) otrzymają kody bitowe dla swoich wartości:

  • ,
  • ,
  • .

Natomiast pozostałe (, ) otrzymają kody bitowe dla liczb o większych:

  • ,
  • .


Przykład kodowania[edytuj kod]

Liczba 27 zostanie zakodowana w kodzie Golomba rzędu .

  1. przedział:
  2. odległość od początku przedziału:

Liczba zakodowana unarnie ma postać (6 bitów), natomiast przedział to (2 bity, kod wyznaczony we wcześniejszym przykładzie). Ostatecznie słowo kodowe jest złożeniem obu kodów: .

Tabela liczb od 0 do 16 dla kodów różnego rzędu[edytuj kod]

 
0 0 0 0 0 0 0 00 0 00 0 00 0 00 0 000
1 10 0 1 0 10 0 01 0 01 0 01 0 010 0 001
2 110 10 0 0 11 0 10 0 10 0 100 0 011 0 010
3 1110 10 1 10 0 0 11 0 110 0 101 0 100 0 011
4 11110 110 0 10 10 10 00 0 111 0 110 0 101 0 100
5 111110 110 1 10 11 10 01 10 00 0 111 0 110 0 101
6 1111110 1110 0 110 0 10 10 10 01 10 00 0 111 0 110
7 11111110 1110 1 110 10 10 11 10 10 10 01 10 00 0 111
8 111111110 11110 0 110 11 110 00 10 110 10 100 10 010 10 000
9 1111111110 11110 1 1110 0 110 01 10 111 10 101 10 011 10 001
10 11111111110 111110 0 1110 10 110 10 110 00 10 110 10 100 10 010
11 111111111110 111110 1 1110 11 110 11 110 01 10 111 10 101 10 011
12 1111111111110 1111110 0 11110 0 1110 00 110 10 110 00 10 110 10 100
13 11111111111110 1111110 1 11110 10 1110 01 110 110 110 01 10 111 10 101
14 111111111111110 11111110 0 11110 11 1110 10 110 111 110 100 110 00 10 110
15 1111111111111110 11111110 1 111110 0 1110 11 1110 00 110 101 110 010 10 111
16 11111111111111110 111111110 0 111110 10 11110 00 1110 01 110 110 110 011 110 000

Bibliografia[edytuj kod]

  • Artur Przelaskowski: Kompresja danych: podstawy, metody bezstratne, kodery obrazów. Warszawa: BTC, 2005, s. 95,97,101. ISBN 83-60233-05-5.