Kod Golomba

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

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

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

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

	$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

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