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 m.in. w algorytmie kompresji bezstratnej JPEG-LS oraz FLAC.
Kodowanie Kodowanie liczby wymaga znalezienia dwóch wartości: przedziału do którego należy liczba: odległości od początku przedziału:
Ogólnie
Słowo kodowe składa się z dwóch części: liczby zapisanej w kodzie unarnym, 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 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 Liczba 27 zostanie zakodowana w kodzie Golomba rzędu przedział: 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 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
Kategoria:Kompresja