Przekazywanie informacji multimedialnych

Kod Golomba należy do szerszej rodziny kodów przedziałowych, które znalazły zastosowanie w standardach multimedialnych, m.in. w JPEG-LS  i H.264. Wyróżnikiem kodów przedziałowych jest potencjalnie nieograniczony alfabet źródła informacji dzielony na przedziały. Słowa kodowe symboli konstruowane są jako  konkatenacja (zlepienie) przedrostka wskazującego na przedział z wyróżnikiem konkretnego elementu danego przedziału. W przypadku kodu Golomba jest to zlepienie odpowiedniego słowa kodu unarnego ze słowem kodu dwójkowego prawie stałej długości. 

Kod dwójkowy prawie stałej długości

Aby uzyskać oszczędniejszą reprezentację kodu dwójkowego (niż za pomocą kodu z p. 1.2.4) przy lic$\lfloor \log_2 n\rfloor$bitów kodu binarnego prawie stałej długości, pozostałym zaś -- $\lceil \log_2 n\rceil$ bitów, zachowując jednoznaczną dekodowalność kodu.

Dokładniej, w kodzie dwójkowym prawie stałej długości $\hat{B}_n$ (dla n-elementowego alfabetu $A_S=\{a_0,\ldots,a_{n-1}\}$pierwszym r symbolom (o indeksie $0\leq i <  r$) przypisywane są słowa $k=\lfloor \log_2 n \rfloor$ bitowe postaci $\hat{B}_n(a_i)=B_k(i)$, a pozostałym - słowa o długości $k+1$ bitów postaci $\hat{B}_n(a_i)=B_{k+1}(r+i)$, gdzie$r=2^{\lceil \log_2 n \rceil}-n$.

Oczywiście, dla źródeł o alfabecie zawierającym $n=2^i,\ i=1,2,\ldots$ symboli, otrzymujemy  $\hat{B}_n=B_{\log_2 n}$, podczas gdy $r=0$. Oznacza to, że kod dwójkowy prawie stałej długości przyjmuje postać kodu stałej długości. 

Przykład 2.2 Kod dwójkowy prawie stałej długości

Ustalmy postać słów kodu  $\hat{B}_n$ dla symboli dwóch alfabetów o odpowiednio $n=3$ oraz $n=5$, sprawdzając jednoznaczną dekodowalność takiego kodu. 
W pierwszym przypadku mamy:  $r=2^{\lceil \log_2 3 \rceil}-3=1$ oraz długość krótszego słowa$k=\lfloor \log_2 3\rfloor=1$. Wtedy  pierwszy symbol alfabetu otrzyma jednobitowe słowo kodowe $\varsigma _0=\hat{B}_3(a_0)=B_1(0)=\texttt{0}$, dwa pozostałe zaś słowa dwubitowe, odpowiednio $\varsigma _1=\hat{B}_3(a_1)=B_2(1+1)=\texttt{10}$ i $\varsigma _2=\hat{B}_3(a_2)=B_2(3)=\texttt{11}$. $\hat{B}_3$ jest  kodem przedrostkowym, jest więc jednoznacznie dekodowalny. Analogicznie, dla $n=5$ otrzymujemy : $r=2^{\lceil \log_2 5 \rceil}-5=3$ oraz $k=\lfloor \log_2 5\rfloor = 2$. Trzy krótsze, dwubitowe słowa kodowe to $\varsigma _0=\hat{B}_5(a_0)=B_2(0)=\texttt{00}$, $\varsigma _1=\hat{B}_5(a_1)=B_2(1)=\texttt{01}$ i $\varsigma _2=\hat{B}_5(a_2)=B_2(2)=\texttt{10}$, a pozostałe: $\varsigma _3=\hat{B}_5(a_3)=B_3(3+3)=\texttt{110}$ i $\varsigma _4=\hat{B}_5(a_4)=B_3(7)=\texttt{111}$. $\hat{B}_5$ jest także kodem przedrostkowym.

W kodzie $\hat{B}_n$ słowa kodowe tworzone są jedynie na podstawie pozycji (indeksu) danego symbolu w alfabecie, bez analizy rozkładu wag poszczególnych symboli. Długość tych słów jest minimalnie zróżnicowana, a więc ich efektywne wykorzystanie w algorytmach kodowania jest możliwe szczególnie w przypadku źródeł o stosunkowo równomiernym (tj. zrównoważonym) rozkładzie prawdopodobieństw symboli. Pokazuje to następujący przykład.

Przyklad 2.3 Efektywność kodu dwójkowego

Wyznaczmy słowa kodu Huffmana dla źródła opisanego zbiorem prawdopodobieństw: $P_S=\{p_0,\ldots,p_5\}=\{1/5,\ 1/5,\ 3/20,\ 3/20,\ 3/20,\ 3/20\}$.
Stosując algorytm 2.1 można skonstruować drzewo Huffmana jak na rys. 2.5. Postać tego drzewa jest \emph{znormalizowana}, tj. liście są uszeregowane w porządku od lewej do prawej według niemalejącej głębokości (każde drzewo Huffmana można znormalizować zamieniając odpowiednio miejscami węzły tego samego poziomu, jeśli relacja maksymalnej głębokości liści ich poddrzew nie jest zgodna z porządkiem uszeregowania -- mechanizm wykorzystywany w algorytmach adaptacyjnych). 
Odczytane z drzewa słowa kodowe kolejnych symboli są następujące: $\varsigma _0=\texttt{00}$, $\varsigma _0=\texttt{01}$, $\varsigma _2=\texttt{100}$, $\varsigma _3=\texttt{101}, \varsigma _4=\texttt{110}$ i $\varsigma _5=\texttt{111}$. Są one identyczne ze słowami kodu $\hat{B}_6$ pod warunkiem uporządkowania symboli alfabetu zgodnie z nierosnącym ich prawdopodobieństwem. Oznacza to, że w tym przypadku kod dwójkowy prawie stałej długości jest równoważny znormalizowanemu kodowi Huffmana, optymalnemu w kategorii kodów symboli.

Rys. 2.5 Znormalizowane drzewo Huffmana konstruowane dla zrównoważonego rozkładu prawdopodobieństwa symboli alfabetu z przykładu 2.3, z typowym etykietowaniem gałęzi; drzewo to daje słowa kodowe jak w kodzie dwójkowym prawie stałej długości.

Okazuje się, że rozkład prawdopodobieństw symboli źródła z przykładu 2.3 jest zrównoważony, tj. suma dwóch najmniejszych prawdopodobieństw rozkładu jest większa od prawdopodobieństwa największego. Dla takich źródeł, po uporządkowaniu symboli alfabetu zgodnie z nierosnącym ich prawdopodobieństwem, kod dwójkowy prawie stałej długości jest optymalnym kodem symboli. 

Kod unarny

Kod unarny wykorzystuje prostą regułę tworzenia kolejnych słów kodowych symboli alfabetu o potencjalnie nieograniczonej długości. Każde ze słów ustalane jest niezależnie, jedynie na podstawie wskazania pozycji symbolu (lub całego przedziału symboli) w hipotetycznym alfabecie.

Według przedrostkowego kodu unarnego, kolejnym symbolom alfabetu przypisywane są słowa postaci: 1, 01, 001, 0001, $\ldots$ lub w logice odwróconej: 0, 10, 110, 1110, $\ldots$. Definicja kodu unarnego $U(i)$ dla dowolnej, całkowitej $i\geq 0$, będącej elementem alfabetu liczb lub indeksem symbolu alfabetu niesprecyzowanej postaci, jest następująca: $U(i)\triangleq \underbrace{\texttt{0\ldots0}}_{i\ \text{razy}}\texttt{1}$ lub $\bar{U}(i)\triangleq \underbrace{\texttt{1\ldots1}}_{i\ \text{razy}}\texttt{0}$.

Za pomocą $U(i)$ można szybko określić słowa dowolnie rozszerzanego alfabetu. Kod ten można wykorzystać do efektywnej kompresji strumienia danych z liczbami naturalnymi (z zerem), przy założeniu: $\forall_i \ i$ jest nie mniej prawdopodobna niż $i-1$. Długość kolejnych słów kodowych $\varsigma _i$ różni się o jeden: $L_i=|\varsigma _i|=L_{i-1}+1$. Ponieważ w kodzie efektywnym długość słowa powinna być równa (proporcjonalna do) informacji własnej danego symbolu $L_i=-\log_2{p_i}$, to kod unarny jest najbardziej efektywny w przypadku, gdy wartości prawdopodobieństw symboli $p_i$ maleją z potęgą dwójki.

Wyobraźmy sobie, że kodowany strumień danych pochodzi ze źródła informacji o alfabecie $A_S=\{0,1,2,\ldots\}$, czyli $a_i=i$, zaś rozkład prawdopodobieństw symboli alfabetu wynosi $P_S=\{\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\ldots\}$, czyli p$p_i=2^{-(i+1)}$. Słowa kodu unarnego przypisane kolejnym symbolom tego źródła mają długości odpowiednio$L_0=1$, $L_1=2$, $L_2=3,\ldots$, czyli $L_i=i+1$. Obliczając średnią bitową takiego kodu mamy:

czyli rozkład długości słów dokładnie odpowiada rozkładowi entropii źródła informacji.
Kod unarny jest więc w tym przypadku kodem optymalnym.

Zależność na  $p_i=2^{-(i+1)},\ i=0,1,2,\ldots$ jest szczególnym przypadkiem rozkładu geometrycznego $p_i=(1-\rho )\rho ^i$ dla $\rho =\frac{1}{2}$. Kod unarny jest optymalny dla wszystkich rozkładów geometrycznych z $\rho \leq \frac{1}{2}$, tj. pozwala uzyskać w tym przypadku rozkład długości słów jak w kodzie Huffmana. Ponieważ przy $\rho$ przyrost informacji własnej kolejnych symboli jest większy od 1 bit/symbol, to zróżnicowane o jeden bit słowa są również optymalne.  Warunkiem koniecznym jest jednak uporządkowanie symboli alfabetu według nierosnących prawdopodobieństw ich występowania.

Jednak dla rozkładów geometrycznych z $\rho >\frac{1}{2}$ informacja własna kolejnych symboli alfabetu narasta wolniej niż 1 bit/symbol, czyli wolniej od wydłużanego o 1 bit słowa kolejnych symboli. Znaczy to, że kod unarny przestaje być wówczas rozwiązaniem optymalnym. Średni przyrost długości słowa kodowego na symbol mniejszy od 1 bita  można uzyskać za pomocą kodu Golomba, łączącego kod unarny (z szybszym przyrostem długości słowa o nieograniczonej precyzji) z kodem dwójkowym prawie stałej długości (o znacznie wolniejszym przyroście długości słowa o ograniczonej precyzji). Okazuje się, że dla rozkładów geometrycznych z $\rho >\frac{1}{2}$ kod Golomba z odpowiednio dobranym parametrem (rzędem) jest optymalnym kodem symboli.

Konstrukcja kodu Golomba 

Rząd kodu Golomba $m \in \mathbb{Z}^+$ określa stały rozmiar przedziału przy podziale potencjalnie nieskończonego alfabetu według zasady:

Słowo kodowe kodu Golomba $G_m(a_i)$ symbolu $a_i \in \pi^{(m)}_u$ składa się z wskaźnika tego przedziału $u=\lfloor i/m \rfloor$, zapisanego w kodzie unarnym, oraz względnego miejsca symbolu w przedziale $k=i\mod m$, $k\in \{0,1,\ldots,m-1\}$. Mamy więc $G_m(a_i)=U(u)\hat{B}_m(a_k)$ lub alternatywnie $\bar{G}_m(a_i)=\bar{U}(u)\hat{B}_m(a_k)$.

Efektywność kodu Golomba warunkowana jest uporządkowaniem realnego alfabetu kodowanych symboli, tak że $p_i \geq p_{i+1}$ oraz właściwym doborem wartość $m$. Ustalenie tego parametru związane jest bezpośrednio z wartością $\rho$, charakteryzującą rozkład geometryczny (zobacz rys. 2.6), możliwie wiernie aproksymujący rozkład prawdopodobieństw uporządkowanego alfabetu źródła. Szybsze opadanie funkcji rozkładu (mniejsze $\rho$) wymaga krótszych przedziałów, wolniejsze - dłuższych. 

Rys. 2.6  Rozkład geometryczny (jednostronny) dla wartości $\rho$: 0,5, 0,7, 0,9.

Wyznaczanie poszczególnych słow kodu Golomba jest proste obliczeniowo. Postać drzew binarnych kodu różnego rzędu ukazuje ich zasadnicze właściwości. Widać to w przykładzie 2.4.

Przyklad 2.4 Kod Golomba
Wyznaczmy słowo kodowe Golomba rzędu m=3 dla i=14. Ustalając wartość $u=\lfloor 14/3 \rfloor=4$ uzyskujemy przedrostek $U(4)=\texttt{00001}$, zaś przy $k=14\mod 3=2$ musimy wyznaczyć słowo kodu dwójkowego $\hat{B}_3(2)$ Obliczmy więc $r=2^{\lceil \log_2 3\rceil}-3=1$, czyli $k\geq r$, stąd $\hat{B}_3(2)=B_{\lceil \log_{2}{3}\rceil}(2+1)=B_2(3)=\texttt{11}$. Poprzez konkatenację otrzymujemy $G_3(a_{13})=U(4)\hat{B}_3(1)=\texttt{00001}\ \texttt{11}$.

Zestawienie słów kodu Golomba dla kolejnych liczb całkowitych nieujemnych przedstawiono w tab. 2.3. Z kolei  binarne drzewa pierwszych słów kodów $G_1, G_2, G_3$ i $G_4$ zamieszczono na rys.2.7. W pierwszym drzewie (dla $m=1$) od ścieżki prawych synów odchodzą tylko liście (jako lewi synowie kolejnych węzłów wewnętrznych). 

Rys. 2.7 Wybrane drzewa Golomba dla kodów rzędu: a) m=1, b) m=2, c) m=3, d) m=4.

W kolejnych węzłach wewnętrznych ścieżki prawych synów podpięte są poddrzewa, początkowo składające się z pojedynczych liści (dla m=1), aż do pełnych poddrzew przy m=4. Przy rosnącym m daje to efekt stopniowego równoważenia drzewa, czyli lepszego dopasowanie do rozkładów geometrycznych o mniejszych nachyleniach (większym $\rho$). 

Tab. 2.3 Przykładowe słowa kodu Golomba różnych rzędów dla kolejnych liczb całkowitych $i\geq 0$; przy m=1 występują tylko słowa kodu unarnego;  | oznacza miejsce sklejenia słowów kodu unarnego oraz dwójkowego prawie stałej długości.

Kod wykładniczy

Przykładem kodu przedziałowego o zmiennym rozmiarze przedziału jest wykładniczy kod Golomba (exp_Golomb), zastosowany w koderze CAVLC (Context based Adaptive Variable Length Coding) standardu H.264. 

Słowa kodowe kodu exp_Golomb konstruowane są według reguły:  

gdzie $$m=\lfloor \log_2 (i+1)\rfloor$. Przykładowe słowa kodu zebrano w tabeli 2.4.

Tab. 2.4 Pierwsze, kolejne słowa wykładniczego kodu przedziałowego.

Charakterystyczną cechą tej wersji kodu Golomba jest wykładniczo rosnąca długość przedziału, równa $2^m$.