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 m, tzn. \{\underbrace{0, \ldots, m-1}_{0}, \underbrace{m, \ldots, 2m-1}_{1}, \ldots\}, zaś liczba jest przedstawiana za pomocą pary (numer przedziału do którego należy, odległość od jego początku). Wartość m 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 p^i(1-p) (np. dla p=0.5 będą to 0.5, 0.25, 0.125, 0.0625, \ldots).

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

Kodowanie[edytuj | edytuj kod]

Kodowanie liczby x wymaga znalezienia dwóch wartości:

  1. przedziału do którego należy liczba: q = \lfloor x/m \rfloor,
  2. odległości od początku przedziału: k = x \mod m.

Ogólnie x = qm+k.

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

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

Słowa kodowe nie są krótsze niż \lfloor \log_2{m} \rfloor + 1.

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

W przypadku kodów Rice'a (m 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ść k jest zapisana na pewnej liczbie młodszych bitów, q na starszych.

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

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

Gdy liczba kodowanych wartości nie jest potęgą dwójki, można skonstruować kod prefiksowy, w którym p początkowych wartości zostanie zapisanych na n = \lfloor \log_2 m \rfloor bitach, a pozostałe n+1 bitach.

Kodowanie rozpoczyna się od określenia wartości granicznej p = 2^{\lceil \log_2 m \rceil} - m:

  • jeśli liczba k < p otrzymuje kod n-bitowy - B_n(k)
  • jeśli liczba k \geqslant p otrzymuje kod n+1-bitowy liczby o p większej - B_{n+1}(k+p)
liczba kod
0 00
1 01
2 10
3 110
4 111

Np. przy kodowaniu pięciu symboli i m=5, liczba p = 2^{\lceil \log_2{5} \rceil} - 5 = 2^3 - 5 = 3. Zatem trzy pierwsze liczby (0, 1 i 2) otrzymają kody n = \lfloor \log_2{5} \rfloor = 2 bitowe dla swoich wartości:

  • 0 \rightarrow 00_2,
  • 1 \rightarrow 01_2,
  • 2 \rightarrow 10_2.

Natomiast pozostałe (3, 4) otrzymają kody n+1 = 3 bitowe dla liczb o p=3 większych:

  • 3+3 \rightarrow 110_2,
  • 4+3 \rightarrow 111_2.


Przykład kodowania[edytuj | edytuj kod]

Liczba 27 zostanie zakodowana w kodzie Golomba rzędu m=5.

  1. przedział: n = \lfloor 27/5 \rfloor = 5
  2. odległość od początku przedziału: k = 27 \mod 5 = 2

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

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

  m=1 m=2 m=3 m=4 m=5 m=6 m=7 m=8
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 | edytuj kod]

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