Przekazywanie informacji multimedialnych

Algorytmy kodowania wykorzystujące opisane wyżej modele źródeł informacji pozwalają tworzyć wyjściową reprezentację kodową, która jest sekwencją bitową o skończonej długości, utworzoną z bitowych słów kodowych charakterystycznych dla danej metody. Realizację algorytmu kodowania, np. w określonym języku programowania lub sprzętową, nazwiemy koderem. Analogicznie realizację algorytmu dekodowania -- dekoderem. Algorytm kodowania realizuje kod, czyli wspomnianą regułę (zasadę, funkcję, przekształcenie) przyporządkowującą ciągowi symboli wejściowych (opisanych modelem źródła informacji o zdefiniowanym alfabecie $A_S$) bitową sekwencję kodową (wyjściową). 

Kodowanie binarne jest metodą wykorzystania określonego kodu do kompresji sekwencji danych wejściowych źródła informacji $A_S$. Kod ten bazuje na określonym modelu źródła informacji, który steruje procesem kodowania binarnego. Podstawowy algorytm kodowania składa się więc z dwóch zasadniczych elementów: modelowania oraz binarnego kodowania.

Kody jednoznacznie dekodowalne

W metodach kompresji, w przeciwieństwie np. do technik szyfrowania, istnieje warunek konieczny, aby reprezentacja kodowa (tj. bitowa sekwencja wyjściowa powstała w wyniku realizacji reguły kodu na strumieniu wejściowym) była jednoznacznie dekodowalna. Oznacza to, iż na podstawie wyjściowej sekwencji bitowej kodera realizującego ustalony kod opisany funkcją kodowania $\mathcal{K}$ można jednoznacznie odtworzyć oryginalny zbiór symboli wejściowych. 

Kodowanie jest więc przekształceniem różnowartościowym 'jeden w jeden', czyli bijekcją. Jeśli dla ciągów symboli wejściowych $s"_{1},s"_{2},\ldots,s"_{t}$ oraz $s""_{1},s""_{2},\ldots,s""_{r}$o wartościach z alfabetu $A_{S}=\{a_{1},\ldots,a_{n}\}$} przyporządkowano bitową sekwencję kodową $z\in Z$ ($Z$ - zbiór wszystkich sekwencji bitowych generowanych przez $\mathcal{K}$):

Oznaczmy przez $A_S^+$  zbiór wszystkich niepustych i skończonych sekwencji symboli alfabetu $A_S$ o $N$ symbolach. Wtedy ogólna postać funkcji kodowania $\mathcal{K}:\ A_S^+ \rightarrow A_{\{0,1\}}^+$ z binarnym alfabetem sekwencji wyjściowych $\{0,1\}$. 

Przykładem kodu jednoznacznie dekodowalnego jest prosty kod dwójkowy stałej długości $B_4$ (zobacz punkt ) z czteroelementowym alfabetem $A_S$. Każdemu z symboli alfabetu przypisano słowo kodowe w postaci binarnego zapisu liczby naturalnej od 0 do 3, będącej indeksem (wskazującej pozycję) danego symbolu w $A_S$ na $k=\log_2 4=2$ bitach. Zbiór słów kodowych jest więc następujący: $A_{B_4}=\{\texttt{00},\texttt{01},\texttt{10},\texttt{11}\}$}, a kod $\mathcal{K}=B_4$ jest odwzorowaniem różnowartościowym (co wynika z unikatowej postaci binarnej reprezentacji indeksu kolejnych symboli $A_S$). 

Kodowanie według $B_4$ polega na przypisaniu kolejnym symbolom sekwencji wejściowej $s_i,\ s_i \in A_S,\ i=1,2\ldots$ odpowiednich binarnych słów kodowych $B_4(s_i)$, takich że $B_4(s_i=a_1)=\texttt{00},\ B_4(s_i=a_2)=\texttt{01},\ B_4(s_i=a_3)=\texttt{10}$ i $B_4(s_i=a_4)=\texttt{11}$, dołączając je do wyjściowej sekwencji bitów (konkatenacja bitów słów kodowych symboli źródła $S$ według porządku ich występowania na wejściu kodera). Praca dekodera tego kodu  polega na odtwarzaniu symboli z $A_S$ według czytanych kolejno 2 bitowych indeksów, co pozwala jednoznacznie zdekodować sekwencję kodową i wiernie zrekonstruować postać źródłowej sekwencji $\mathbf{s}^t$.

Kodowanie według $B_k$ jest przykładem tzw. kodowania przyrostowego:  $\mathcal{K}(s_1,s_2,\ldots,s_{t})=\mathcal{K}(s_1)\mathcal{K}(s_2) \cdots \mathcal{K}(s_t)$, gdzie $s_i \in A_S$, a $\mathcal{K}(s_i) \in A_{\mathcal{K}}=\{\varsigma_1,\varsigma _2,\ldots,\varsigma _n\}$ ($A_{\mathcal{K}}$ nazwiemy alfabetem kodu $\mathcal{K}$). Ogólniej kodowanie przyrostowe polega na kolejnym dołączaniu sekwencji bitowych, przypisywanych czytanym sekwencjom symboli wejściowych według określonej reguły (tj. kodu), tworząc jedną sekwencję kodową. Kod może przypisywać sekwencje kodowe pojedynczym symbolom (jak wyżej) lub całym wieloelementowym grupom (blokom) symboli. 

Dany jest alfabet $A_S=\{a_1,a_2,a_3\}$ oraz zbiór wszystkich niepustych sekwencji nad tym alfabetem $A_S^+$. Trywialnym przykładem kodowania, które po rozszerzeniu nie jest jednoznacznie dekodowalne, jest funkcja $\mathcal{K}_1(a_i)=\beta$, która dowolnemu symbolowi z $A_S$ przypisuje to samo słowo kodowe $\beta \in A_{\{0,1\}}^+$. Dekoder odczytując $\beta$ nie jest w stanie podjąć jednoznacznej decyzji:  $\mathcal{K}_1^{-1}(\beta)=a_1 \ \lor \dots$ $\ldots \ \lor \ \mathcal{K}_1^{-1}(\beta)=a_2 \ \lor \ \mathcal{K}_1^{-1}(\beta)=a_3$.

Innym przykładem kodu niejednoznacznie dekodowalnego przy dwuelementowym alfabecie źródła jest: $\mathcal{K}_2(a_1)=\texttt{0}$ i $\mathcal{K}_2(a_2)=\texttt{00}$, kiedy to sekwencję $\texttt{00}$ można zdekodować jako ciąg symboli $(a_1,a_1)$ lub też jako pojedynczy symbol $a_2$. Przy większym alfabecie źródła, np. $A_S=\{a_1,a_2,a_3,a_4\}$ określmy $\mathcal{K}_3$ jako: $\mathcal{K}_3(a_1)=\texttt{0}$, $\mathcal{K}_3(a_2)=\texttt{1}$, $\mathcal{K}_3(a_3)=\texttt{01}$ i $\mathcal{K}_3(a_4)=\texttt{10}$. Dekodowanie sekwencji bitowych $\beta_1=\texttt{01}$ lub $\beta_2=\texttt{10}$ nie jest jednoznaczne, gdyż $\mathcal{K}_3^{-1}(\beta_1)=a_3$ lub też $\mathcal{K}_3^{-1}(\beta_1)=(a_1,a_2)$, a w przypadku $\beta_2$ mamy $\mathcal{K}_3^{-1}(\beta_2)=a_4=(a_2,a_1)$. 

Koder $\mathcal{K}_4$ przyporządkuje czterem symbolom alfabetu źródła informacji $A_S$ następujące słowa kodowe: $A_{\mathcal{K}_4}=\{\mathcal{K}_4(a_1),\mathcal{K}_4(a_2),\mathcal{K}_4(a_3)\mathcal{K}_4(a_4) \}=$$=\{\varsigma _1^{(\mathcal{K}_4)},\varsigma _2^{(\mathcal{K}_4)},\varsigma _3^{(\mathcal{K}_4)},\varsigma _4^{(\mathcal{K}_4)}\}=\{\texttt{0},\texttt{01},\texttt{001},\texttt{0011}\}$. Rozpatrzmy krótką sekwencję kodową $\beta$ = 00} utworzoną ze słów kodowych alfabetu $A_{\mathcal{K}_4}$, która może być interpretowana jako połączenie słów 0 i 0} ($\varsigma _1\varsigma _2$) lub też 001 (czyli $\varsigma _3$). Kod realizowany przez ten koder również nie jest kodem jednoznacznie dekodowalnym, a można to stwierdzić na podstawie analizy alfabetu postaci (zbioru) słów kodowych danego kodu. Dla koderów wykorzystujących inne zbiory binarnych słów kodowych można w analogiczny sposób stwierdzić, że:

• kod $A_{\mathcal{K}_5}=\{\texttt{1},\texttt{01},\texttt{001},\texttt{0001}\}$ jest jednoznacznie dekodowalny, 
• kod $A_{\mathcal{K}_6}=\{\texttt{0},\texttt{10},\texttt{110},\texttt{111}\}$ jest jednoznacznie dekodowalny,
•  kod $A_{\mathcal{K}_7}=\{\texttt{0},\texttt{10},\texttt{11},\texttt{111}\}$ nie jest jednoznacznie dekodowalny, 
• kod $A_{\mathcal{K}_8}=\{\texttt{0},\texttt{01},\texttt{11}\}$ jest jednoznacznie dekodowalny,
• kod $A_{\mathcal{K}_9}=\{\texttt{001},\texttt{1},\texttt{100}\}$ nie jest jednoznacznie dekodowalny.

Aby kod był jednoznacznie dekodowalny musi mieć $N$ różnych słów kodowych (w przypadku $\mathcal{K}_1$ warunek ten nie jest spełniony). Jeśli w danym kodzie jedno ze słów kodowych jest konkatenacją innych słów, wówczas kod nie jest jednoznacznie dekodowalny (zobacz przypadki kodów  $\mathcal{K}_2$ i $\mathcal{K}_3$). Uogólniając tę zasadę, jeśli połączenie kilku słów kodowych daje taki sam efekt, jak połączenie innych słów z alfabetu kodu, wówczas także mamy do czynienia z brakiem jednoznaczności dekodowania. Tak jest w przypadku kodu $\mathcal{K}_7$, gdzie połączenie słów $\varsigma_3\varsigma_2=\varsigma_4\varsigma_1$, jak również w przypadku kodu $\mathcal{K}_9$, ponieważ $\varsigma_2\varsigma_1=\varsigma_3\varsigma_2$. 

Kody przedrostkowe

W przypadku kodów o liczniejszych alfabetach źródeł informacji trudno jest nieraz zweryfikować kod pod względem jednoznaczności dekodowania. Można jednak zauważyć, że we wszystkich przypadkach przedstawionych powyżej kodów, które nie są jednoznacznie dekodowalne, jedno ze słów kodowych jest przedrostkiem innego. Słowo   $\varsigma_i \in A_{\mathcal{K}}$ jest przedrostkiem słowa $\varsigma_j\in A_{\mathcal{K}},i \neq j$, jeśli $\varsigma_j=\varsigma_i \beta$, gdzie $\beta \in A_{\{0,1\}}^+$. Dla kodów $\mathcal{K}_4, \mathcal{K}_5$ oraz $\mathcal{K}_7$ żadne ze słów nie jest przedrostkiem innego. Są to więc kody przedrostkowe, tj. dla dowolnej pary różnych symboli $a_i ,a_j \in A_S$ zachodzi relacja $\mathcal{K}(a_i) \npreceq \mathcal{K}(a_j)$ (gdzie $\preceq$ oznacza relację początku w sekwencji bitowej). Relacja ta przenosi się na sekwencje symboli źródła $A_S$. Skoro żaden element z $A_{\mathcal{K}}$ nie jest przedrostkiem innego słowa tego zbioru, to sekwencja kodowa $\alpha$ dowolnego ciągu  symboli z $A_S$ także nie może być przedrostkiem sekwencji słów kodowych $\beta$ innego ciągu symboli alfabetu źródła. Efektem wystąpienia choćby jednego różnego symbolu w sekwencji wejściowej jest pojawienie się słowa, który nie jest przedrostkiem innego, co powoduje utratę cechy przedrostkowości sekwencji: $\alpha=\gamma_1\mathcal{K}(a_i)\gamma _2,\beta=\gamma _1\mathcal{K}(a_j)\gamma _2,\ i \neq j,\ \gamma _1,\gamma _2 \in A_{\mathcal{K}}^+ \cup\emptyset \Rightarrow \alpha\npreceq \beta$, ponieważ $\mathcal{K}(a_i)\npreceq \mathcal{K}(a_j)$. Ta właściwość pozwala jednoznacznie zdekodować sekwencję kodową ciagu symboli wejściowych.

Kody przedrostkowe (prefix codes) w literaturze angielskojęzycznej nazywane są także prefix condition codes}, prefix-free codes lub też comma-free code. Wydaje się, że nazwa kody bezprzedrostkowe lepiej oddaje istotę zagadnienia.

Ze względu na możliwość dekodowania od razu kolejnych słów kodowych (od lewej do prawej, co daje prostą budowę kodera), kody przedrostkowe znane są także jako instantaneous codes, czyli kody z natychmiastowym dekodowaniem, bez konieczności odczytywania dalszych bitów w celu poprawnej interpretacji sekwencji bitów. Prosty algorytm dekodera kodu przedrostkowego $\mathcal{K}$ który polega na odczytywaniu kolejnych słów kodowych i dekodowaniu odpowiadających im symboli źródła, jest następujący:

Algorytm 1.3 Dekodowanie sekwencji kodu przedrostkowego 

1. Wyzeruj zmienną $\alpha$ przechowującą wejściową sekwencję bitów;
2. Czytaj do $\alpha$ tyle bitów, ile wynosi minimalna długość słowa kodowego w $A_{\mathcal{K}}$ a wobec braku danych wejściowych zakończ;
3. Porównanie $\alpha$ ze słowami kodu $\mathcal{K}$: dla $i=0,\ldots,n-1$ sprawdź, jeśli $\alpha=\varsigma_i$ (gdzie $\varsigma _i \in A_{\mathcal{K}}$), to emituj na wyjście symbol $a_i=\mathcal{K}^{-1}(\varsigma _i),\ a_i\in A_S$ i kontynuuj krok 1;
4. Czytaj bit z wejścia i dopisz go do $\alpha$, a wobec braku danych wejściowych zakończ;
5. Przejdź do kroku 3.

Kody przedrostkowe mogą być reprezentowane za pomocą struktury binarnych drzew kodowych (są kodami drzew binarnych), gdzie etykietowane gałęzie ustalają kolejne bity słów symboli alfabetu źródła, przypisanych liściom tego drzewa. Przejście od liścia do korzenia ze spisaniem dwójkowych etykiet kolejnych gałęzi daje słowo kodowe danego symbolu (w odwrotnej kolejności, tj. od najmłodszego bitu do nastarszego). Przy dekodowaniu symbolu, odczytywane kolejno bity słowa kodowego (od najstarszego do najmłodszego) prowadzą od korzenia do odpowiedniego liścia. Wykorzystanie struktury drzewa umożliwia wygodną realizację kodera i dekodera danego kodu przedrostkowego.

Przedrostkowość kodu jest warunkiem wystarczającym jego jednoznacznej dekodowalności. Nie jest jednak warunkiem koniecznym, co pokazuje przykład kodu $\mathcal{K}_8$. Kody jednoznacznie dekodowalne, nie będące kodami przedrostkowymi, są jednak trudniejsze w dekodowaniu (komplikuje się nieco budowa dekodera, a interpretacja sekwencji bitów odbywa się z opóźnieniem). Po odczytaniu słowa kodowego wymagają niekiedy odczytania kilku dodatkowych bitów, aby dokonać poprawnej jego interpretacji. Weźmy sekwencję kodową utworzoną według kodu $\mathcal{K}_8$ postaci: $\beta=\texttt{001110}=\varsigma_1\varsigma_2\varsigma_3\varsigma_1$. Zdekodowanie pierwszego symbolu $a_1=\mathcal{K}_8^{-1}(\varsigma _1)$ trójelementowego alfabetu $A_S$ wymaga odczytania dwóch pierwszych bitów (drugi bit sekwencji kodowej równy 0 wskazuje, że pierwsze 0 to $\varsigma_1$ a nie pierwszy bit słowa $\varsigma_2$). Aby poprawnie zdekodować bit drugi i trzeci sekwencji $\beta$(jako $\varsigma_2$) koniecznym jest odczytanie wszystkich pozostałych bitów $\beta$ (tj. czwartego, piątego i szóstego). Bowiem po odczytaniu piątego bitu jeszcze nie wiadomo, czy 0111 (bity od 2 do 5 sekwencji $\beta$) to złączone słowa $\varsigma_2\varsigma_3$, czy też konkatenacja słów $\varsigma_1 \varsigma_3$ z pierwszym bitem kolejnego słowa $\varsigma_3$. Dopiero po odczytaniu ostatniego 0 (szóstego bitu z $\beta$) wszystko się wyjaśnia (gdyby nie był to ostatni bit sekwencji kodowej, nie byłoby wiadomo czy należy dekodować $\varsigma_1$ czy też jest to pierwszy bit $\varsigma_2$).

Kody drzew binarnych

Wykorzystanie struktury drzewa w projektowaniu kodu przedrostkowego pozwala w wygodny sposób realizować założenia dotyczące konstrukcji kodu efektywnego w kompresji danych o określonej charakterystyce. Utworzenie drzewa binarnego dla definiowanego kodu przedrostkowego ułatwia analizę kodu, pozwala wykazać ewentualną jego nadmiarowość, umożliwia prostą jego modyfikację poprzez zmianę sposobu etykietowania drzewa (wpływającego na postać poszczególnych słów) lub dodanie  liści (rozszerzenie alfabetu kodu o nowe słowa).

Właściwości kodu drzewa binarnego są określane na etapie konstruowania struktury drzewa dla założonej liczby liści, przy ustalaniu jego głębokości, poziomu zrównoważenia w skali całego drzewa lub wybranych poddrzew, sposobu rozmieszczenia symboli w liściach oraz zasad etykietowania. Głębokość umieszczenia poszczególnych liści decyduje o długości słów kodowych. Poziom zrównoważenia drzewa wpływa na zróżnicowanie długości słów symboli.
 
Formowanie słów kodowych poszczególnych liści odbywa się poprzez spisywanie etykiet gałęzi przejścia od korzenia do liścia, nigdy w kierunku odwrotnym (wynika to z naturalnego kierunku przejścia od rodzica do dzieci, pozwala rozróżnić potomstwo, choć nieco komplikuje budowę kodera wymuszając konieczność odwrócenia bitów). Idąc od korzenia na kolejnych poziomach formowany jest, w zależności od drogi, przedrostek słów kodowych. Przykładowo, przy ustalaniu słowa liścia z symbolem $b$w drzewie na rys. 1.4a, w węźle wewnętrznym pierwszego poziomu określony jest przedrostek 0, a następnie idąc do prawego syna-liścia otrzymujemy słowo $\varsigma _b=\texttt{01}$ W zależności od wybranego sposobu etykietowania gałęzi, binarne drzewo kodowe (tj. służące do realizacji danego kodu) o określonej strukturze wyznacza wiele kodów o takiej samej długości słów. Słowa te w sposób jednoznaczny opisują drogę przejścia od korzenia do symboli alfabetu $A_S$ przypisanych poszczególnym liściom.

Rys. .4 Etykietowanie drzew binanych: a) drzewo o dwóch wierzchołkach wewnętrznych i trzech liściach z symbolami $a,b,c$ z zaznaczoną relacją rodzic-dzieci oraz ustalonymi słowami kodowymi $\varsigma _a,\varsigma _b,\varsigma _c$; b) trzy inne sposoby etykietowania tego samego drzewa.
 

Przy etykietowaniu drzewa binarnego gałęzie łączące wierzchołek rodzica z dziećmi muszą mieć różne etykiety. Dwa możliwe sposoby etykietowania gałęzi każdego elementarnego poddrzewa (rodzic-dwójka dzieci) to 0 dla połączenia z lewym synem i 1 - z prawym lub odwrotnie (zobacz rys. 1.4a). Skoro istnieją dwie możliwości ustalania przedrostka dzieci każdego wierzchołka wewnętrznego (rodzica), to przy $M$ wierzchołkach wewnętrznych w drzewie mamy $2^M$ różnych sposobów utworzenia słów kodowych. Przykład różnych sposobów etykietowania drzewa o $M=2$ przedstawiono na rys. 1.4. 

W związku z tym, w przypadku budowy drzewa określonego kodu przedrostkowego możliwych jest $2^M$ różnych postaci drzewa binarnego, w zależności od przyjętego sposobu etykietowania. Długość słów poszczególnych symboli alfabetu tego kodu jest określona, czyli odpowiednie liście muszą zawsze znajdować się na tej samej głębokości, chociaż kształt struktury drzewa może być różny.

Długość słowa symbolu danego liścia drzewa jest równa głębokości (numerowi poziomu, licząc od zerowego poziomu korzenia), na jakiej znajduje się liść. Dla drzew z rysunku 1.4 liście $a$i $b$znajdują się na 2 poziomie (na głębokości równej 2), więc mają słowa dwubitowe, zaś liściowi $c$z pierwszego poziomu przypisano słowo jednobitowe. Zmiana sposobu etykietowania nie wpływa na długość poszczególnych słów.

Efektywna postać kodu drzewa binarnego Podstawowy warunek zapewniający efektywność kodu sprowadza się do konstrukcji drzewa, które nie ma zdegenerowanych elementarnych poddrzew, tj. rodzica tylko z jednym dzieckiem. Stąd każdy wierzchołek takiego drzewa, zwanego drzewem lokalnie pełnym, z wyjątkiem korzenia, ma brata. Puste miejsce w zdegenerowanym poddrzewie jest niewykorzystane - brakuje gałęzi z etykietą, dla której zarezerwowano miejsce w drzewie. Zawsze wtedy można zlikwidować wierzchołek rodzica takiego poddrzewa przesuwając na jego miejsce jedyne dziecko (wraz z poddrzewem) i skracając w ten sposób o jeden długość związanego z dzieckiem przedrostka słów liści z jego poddrzewa.

Drzewo lokalnie pełne o zadanej liczbie liści można zbudować, zaczynając np. od struktury z jednym wierzchołkiem, korzeniem, dodając nowe liście zgodnie z poniższą regułą.

Reguła rozbudowy drzewa lokalnie pełnego: wybrany węzeł aktualnej postaci drzewa przenosimy wraz z poddrzewem o jeden poziom niżej, zaś na jego miejsce wstawiamy nowy węzeł wewnętrzny, którego drugim dzieckiem jest nowo dołączany liść.

Drzewo o $N=2$ liściach ma jeden węzeł wewnętrzny, tj. korzeń. Dodanie nowego liścia według tej reguły powoduje, że uzyskujemy drzewo z $N=3$ liśćmi przy dwóch wierzchołkach wewnętrznych. W każdym kolejnym kroku rozbudowy drzewa dochodzi jeden liść i jeden wierzchołek wewnętrzny, a więc liczba wierzchołków wewnętrznych drzewa lokalnie pełnego jest zawsze równa: $M=N-1$. Wszystkich wierzchołków drzewa jest $K=2N-1$. Przykłady drzew przedstawiono na rys.1.5. 

Rys. 1.5 Przykłady drzew: a) lokalnie pełnych; b) nie będących lokalnie pełnymi.

Aby uzyskać postać drzewa, które utraci cechę lokalnej pełności można zmodyfikować opisaną wyżej metodę konstrukcji drzewa lokalnie pełnego w sposób następujący. Wybrany liść przesuwamy poziom niżej, zaś w jego poprzednim miejscu tworzymy wierzchołek wewnętrzny (bez dołączania nowego liścia). W ten sposób powstaje zdegenerowane elementarne poddrzewo, rośnie o jeden liczba węzłów wewnętrznych przy niezmiennej liczbie liści równej $N$. W drzewach  nie będących lokalnie pełnymi o $N$ liściach liczba węzłów wewnętrznych jest więc równa $N$ lub większa, a liczba wszystkich wierzchołków $K>2N-1$.
  
W mniejszym drzewie na rysunku 1.5a liczba wierzchołków $N=2,\ K=3$. Wersja tego drzewa po utracie cechy lokalnej pełności z rys. 1.5b  ma odpowiednio $N=2,\ K=4$ (dwa wierzchołki wewnętrzne plus dwa liście), czyli $K>2N-1$. Nastąpiło wydłużenie długości słowa kodowego symbolu $b$ o jeden bit. Analogicznie większe drzewo z rys. 1.5a ma $N=6,\ K=11$ jego modyfikacja na rys. 1.5b odpowiednio $N=6,\ K=13$ oraz wydłużone słowa symboli $a$i $b$ o jeden bit. 

Każdy wewnętrzny wierzchołek $T$ drzewa lokalnie pełnego o lokalizacji jednoznacznie określonej jego przedrostkiem $\alpha$ ma zawsze dwóch synów: lewego i prawego o przedrostkach $\alpha\texttt{0}$ i $\alpha\texttt{1}$. Przedrostki te muszą pojawić się jako przedrostki słów wszystkich liści występujących w poddrzewie wierzchołka $T$. Stąd w kodzie takiego drzewa każdy przedrostek właściwy $\alpha$ (mający przedłużenie w słowie) dowolnego słowa kodowego $\varsigma _i$ ma przedłużenia $\alpha\texttt{0}$ i $\alpha\texttt{1}$ będące przedrostkami tego słowa oraz innego $\varsigma _j \neq \varsigma _i$. Kod drzewa lokalnie pełnego nazywany jest kodem przedrostkowym pełnym. 

W większym drzewie z rys. 1.5a widać, że dowolny przedrostek związany z wierzchołkiem wewnętrznym ma przedłużenia z dołączonym bitem 0 oraz 1 w przedrostkach dzieci tego wierzchołka, a ostatecznie w słowach liści należących do jego poddrzewa. Z kolei słowa $\varsigma _a = \texttt{0}$ i $\varsigma _b = \texttt{10}$ mniejszego drzewa z rys. 1.5b świadczą o tym, że nie jest on przedrostkowo pełny: przedrostek właściwy $\alpha=\texttt{1}$ słowa $\varsigma _b$ nie ma przedłużenia $\alpha\texttt{1}$ a jedynie przedłużenie $\alpha\texttt{0}$ w słowie symbolu $b$.  

Kody symboli i kody strumieniowe

Kod dwójkowy stałej długości, jak również inne wzmiankowane wyżej przykłady kodów pozwalające lub nie na jednoznaczne dekodowanie tworzonych sekwencji, należą do klasy tzw. kodów symboli (symbol codes). W kodach symboli sekwencja wyjściowa powstaje poprzez przypisanie kolejnym symbolom pojawiającym się na wejściu odpowiednich słów kodowych w schemacie ,,jeden symbol - jedno słowo''. Aby uzyskać efekt kompresji potrzebne jest zróżnicowanie długości poszczególnych słów (w przeciwieństwie do kodu $B_k$, który ustala zwykle oryginalną reprezentację kodowanych danych). Bardziej praktyczne są więc kody o zmiennej długości bitowej słów kodowych (variable-length symbol codes).

Inną, potencjalnie bardziej efektywną grupę metod kodowania stanowią kody strumieniowe (stream codes). W kodach strumieniowych pojedyncze słowo kodowe przypisywane jest ciągowi symboli wejściowych. Może to być ciąg symboli o stałej lub zmiennej długości (np. w koderach słownikowych), a w skrajnym przypadku wszystkim symbolom strumienia wejściowego odpowiada jedno słowo kodowe, będące jednoznacznie dekodowalną reprezentacją danych źródłowych. Takie słowo tworzone jest w koderze arytmetycznym, stanowiącym automat skończony, który w każdym takcie (a więc po wczytaniu kolejnego symbolu wejściowego) wyprowadza (nieraz pustą) sekwencję bitów w zależności od czytanego symbolu i aktualnego stanu automatu.

Jednoznaczna dekodowalność kodów strumieniowych wynika z różnowartościowości przekształcenia sekwencji symboli wejściowych w słowo kodowe (sekwencję kodową). Decydujący wpływ ma tutaj metoda tworzenia słów kodowych, przystosowana do znacznie większego alfabetu możliwych postaci danych wejściowych, zwykle adaptacyjna i bardziej złożona niż w przypadku kodów symboli.

W charakterystyce kodów symboli o zmiennej długości istotną rolę odgrywa także nierówność Krafta-MacMillana. Dotyczy ona kodów jednoznacznie dekodowalnych zawierających $n$słów kodowych o długościach $L_i=|\varsigma _i|$, dla których zachodzi następująca zależność:

Odwrotnie, mając dany zbiór $n$ dodatnich liczb całkowitych $\mbox{\{L_1,..., L_n\}}$ spełniających (1.11) istnieje jednoznacznie dekodowalny kod symboli o długościach kolejnych słów kodowych równych $L_i$.

Nierówność (1.11) jest prawdziwa dla kodów drzew binarnych, co można wykazać na podstawie właściwości struktury drzewa. Dowolną postać drzewa binarnego daje się uzyskać poprzez rozbudowę drzewa najprostszej postaci. Kolejne liście dołączane są w wolnych miejscach istniejącej struktury węzłów lub też poprzez dodanie nowego węzła wewnętrznego. 

Najprostsza (i najbardziej efektywna) postać drzewa z jednym liściem to korzeń z podpiętym bezpośrednio liściem. Mamy wtedy jedno słowo kodowe o długości $L_1=1$ czyli spełniona jest nierówność (1.11). Wstawienie na wolne miejsce (jako drugie dziecko korzenia) drugiego liścia daje dwa słowa kodowe o długościach $L_1=1$i $L_2=1$ wobec czego zachodzi równość $\sum_{i=1}^{2}2^{-L_i}=1$. 

Uzyskaliśmy w ten sposób drzewo lokalnie pełne. Dodanie nowego liścia z zachowaniem lokalnej pełności drzewa może się odbywać według reguły rozbudowy drzewa lokalnie pełnego  stosowanej do dowolnego liścia. Powoduje to następującą zmianę w alfabecie słów kodowych: słowo $\varsigma _i=\alpha$o długości $L_i$ zastępowane jest dwoma słowami postaci $\varsigma _i'=\alpha0$ i $\varsigma _i''=\alpha1$o długości $L_{i+1}$. Odpowiedni składnik sumy z wyrażenia (1.11) się nie zmienia, gdyż $2^{-L_i}=2^{-L_i+1}+2^{-L_i+1}$. Według tej zasady można uzyskać dowolne drzewo lokalnie pełne. Pozwala to stwierdzić, że dla drzew lokalnie pełnych, czyli dla kodu przedrostkowego pełnego zawsze zachodzi równość: $\sum_{i=1}^{n}2^{-L_i}=1$.

Rozbudowa drzewa bez zachowania cechy lokalnej pełności powoduje zmniejszenie efektywności kodu poprzez wydłużenie słów kodowych. Utratę tej cechy powoduje modyfikacja drzewa polegająca na przesunięciu o jeden poziom w dół wierzchołka wraz z całym poddrzewem i ustanowieniu w zwolnionym miejscu nowego węzła wewnętrznego. Operacja ta powoduje wydłużenie długości słów kodowych wszystkich liści tego poddrzewa. Mamy więc $\sum_{i=1}^{n}2^{-L'_i}$ gdzie $L'_i$ to długości słów po modyfikacji. Dla kodu przedrostkowego bez cechy pełności mamy więc zawsze zależność: $\sum_{i=1}^{n}2^{-L_i}$.  

Spełnienie nierówności (1.11) jest warunkiem koniecznym jednoznacznej dekodowalności kodu, nie jest jednak warunkiem wystarczającym (dostatecznym). Potwierdzeniem jest np. kod symboli określony słowami$A_{\mathcal{K}}=\{\texttt{0},\texttt{10},\texttt{110},\texttt{101}\}$ (niewielka modyfikacja kodu $A_{\mathcal{K}_6}$) spełniający(1.11). Przykładowe kody $A_{\mathcal{K}_3}$i $A_{\mathcal{K}_7}$ nie spełniają nierówności (1.11), co dowodzi, że nie są jednoznacznie dekodowalne. Zaś w przypadku kodów $A_{\mathcal{K}_2},A_{\mathcal{K}_4}$i $A_{\mathcal{K}_9}$ zależność ta nie wystarcza do wykazania braku niejednoznacznej dekodowalności.   

Nierówność (1.11) można odnieść do pojęcia informacji własnej związanej z wystąpieniem (z prawdopodobieństwem $p_i$) pojedynczego symbolu kodowanego słowem o długości $L_i$zapisując $L_i=-\log_{2} p_i+\epsilon _i$ gdzie $\epsilon _i$j est nadmiarową|niedomiarową (w stosunku do wartości informacji własnej) długością słowa $L_i$ (wynikającą np. z ograniczenia długości słowa do całkowitej liczby bitów). W wyniku prostych przekształceń $2^{-L_i}=2^{(\log_{2} p_i-\epsilon _i)}=p_i\cdot 2^{-\epsilon _i}$, co pozwala zapisać (1.11) jako $\sum_{i=1}^{n}p_i\cdot 2^{-\epsilon _i}\leq 1$. Jeśli założymy stałą wartość $\epsilon _i=\epsilon$dla wszystkich słów, wtedy $\epsilon \geq 0$. W przypadku, gdy kod dobiera krótsze od informacji własnej słowa kodowe dla wybranych symboli alfabetu, to dla innych symboli słowa muszą być wydłużone (średnio) tak samo lub bardziej. 

Twierdzenia o kodowaniu źródeł

Przy konstruowaniu technik odwracalnej kompresji interesującym jest pytanie o granicę możliwej do uzyskania efektywności kompresji. Intuicyjnie wiadomo, że nie można stworzyć nowej reprezentacji danych o dowolnie małej długości przy zachowaniu pełnej informacji dostarczonej ze źródła. Okazuje się, że entropia łączna $H(S)$ wyznaczona według równań (1.4) dla kodowanego zbioru danych stanowi graniczną (minimalną) wartość średniej bitowej reprezentacji kodowej - jest bowiem miarą ilości informacji pochodzącej ze źródła. Mówią o tym twierdzenia Shannona o kodowaniu źródeł, w tym szczególnie istotne twierdzenie o bezstratnym kodowaniu źródła (tj. z kanałem bezszumnym, z doskonałą rekonstrukcją sekwencji symboli źródła - bez ograniczenia liczby bitów) (noiseless source coding theorem), zwane też pierwszym twierdzeniem Shannona. Według tego twierdzenia, aby zakodować dany proces (sekwencję symboli generowanych przez źródło) o entropii $H(S)$do postaci sekwencji symboli binarnych, na podstawie której możliwe będzie dokładne zdekodowanie (rekonstrukcja) procesu źródłowego, potrzeba co najmniej $H(S)$ symboli binarnych (bitów). Możliwa jest przy tym realizacja schematu kodowania, który pozwoli uzyskać bitową reprezentację informacji z takiego źródła o długości bardzo bliskiej wartości $H(S)$.

Bardziej praktyczna odmiana twierdzenia o bezstratnym kodowaniu źródła dotyczy granicznej efektywności kodowania, osiąganej poprzez kodowanie dużych bloków symboli alfabetu źródła (tj. $N$-tego rozszerzenia źródła, przy zmianie struktury informacji pojedynczej) za pomocą binarnych słów kodowych. Zamiast przypisywania słów kodowych pojedynczym symbolom alfabetu, jak w koderach symboli, koncepcja skuteczniejszego kodera prowadzi w kierunku realizacji kodu strumieniowego, uwzględniając przy tym w możliwie wydajny sposób zależności pomiędzy poszczególnymi symbolami kodowanej sekwencji.

Okazuje się, że zawarta w tym twierdzeniu sugestia o zwiększaniu efektywności kompresji poprzez konstruowanie coraz większych rozszerzeń źródła (rosnące $N$) jest cenną wskazówką, ukazującą kierunek optymalizacji koderów odwracalnych. W dosłownej realizacji tej sugestii występuje jednak problem skutecznego określenia prawdopodobieństw łącznego wystąpienia $N$ symboli źródła na podstawie kodowanego strumienia danych.

Z twierdzenia o bezstratnym kodowaniu źródła jasno wynika, że każde źródło danych może być bezstratnie kodowane przy użyciu kodu jednoznacznie dekodowalnego, którego średnia liczba bitów na symbol źródła jest dowolnie bliska, ale nie mniejsza niż entropia źródła (określona na podstawie prawdopodobieństw występowania poszczególnych symboli i grup symboli źródła) wyrażona w bitach. Jest to naturalne ograniczenie wszystkich metod bezstratnej kompresji odnoszące się do założonych modeli źródeł informacji. Oczywiście użyty model źródła winien jak najlepiej charakteryzować (przybliżać) zbiór danych rzeczywistych. Należy więc podkreślić względność wyznaczanych wartości granicznych wobec przyjętego modelu źródła informacji. Przykładowo, przy konstruowaniu kodera na podstawie modelu źródła bez pamięci, graniczną wartością efektywności tego kodera będzie wartość entropii $H(S_{\mathrm{DMS}})$.

Uzyskanie większej skuteczności kompresji metod bezstratnych jest możliwe poprzez doskonalenie modelu źródła informacji przybliżającego coraz wierniej kompresowany zbiór danych (oryginalnych, współczynników falkowych itp.), nawet kosztem rosnącej złożoności modelu. Potrzeba coraz dokładniej modelować wpływ kontekstu, zarówno za pomocą rozbudowanych, dynamicznych (adaptacyjnych) modeli predykcyjnych, jak też coraz szybciej i pełniej określanych probabilistycznych modeli Markowa nawet wyższych rzędów. Modelowanie musi być skojarzone z efektywnymi rozwiązaniami kodów binarnych (powstających na podstawie tych modeli), pozwalających osiągnąć minimalną długość bitowej sekwencji nowej reprezentacji danych.