Kod Golomba

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.

KodowanieEdytuj

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ściEdytuj

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 kodowaniaEdytuj

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ęduEdytuj

                 
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

BibliografiaEdytuj

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