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. $\{\underset{0}{\underbrace{0,\dots ,m-1}},\underset{1}{\underbrace{m,\dots ,2m-1}},\dots \},$ 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,\dots$).

Kodowanie Rice’a z adaptacyjnym dobieraniem rzędu jest stosowane m.in. w 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=xmodm.$

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⩾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\to 00_2,$
• $1\to 01_2,$
• $2\to 10_2.$

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

• $3+3\to 110_2,$
• $4+3\to 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=27mod5=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

• Szablon:Cytuj książkę