Przejdź do zawartości

Kod Golomba

Z Wikipedii, wolnej encyklopedii

Kod Golombakod 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 m.in. w algorytmie kompresji bezstratnej JPEG-LS oraz FLAC.

Kodowanie

[edytuj | 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 | 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 | 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 | 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 | edytuj kod]
  • Artur Przelaskowski: Kompresja danych: podstawy, metody bezstratne, kodery obrazów. Warszawa: BTC, 2005, s. 95, 97, 101. ISBN 83-60233-05-5.