Podręcznik

1.9. Kod dwójkowy stałej długości

Typowa reprezentacja źródłowych danych cyfrowych ma postać kodu dwójkowego stałej długości. Kod dwójkowy $B_k$ jest kodem symboli, nazywanym także kodem naturalnym ponieważ słowa tego kodu są dwójkową reprezentacją kolejnych liczb naturalnych (tj. nieujemnych liczb całkowitych). $B_k$ charakteryzuje stała, $k$ bitowa precyzja słów przypisanych $n$ symbolom alfabetu $A_S$, gdzie $k\triangleq\lceil\log_2 n\rceil$. Przykładowo, przy $n=8$ mamy następujące słowa kodowe o precyzji 3 bitów: $A_{B_3}=\{\texttt{000}, \texttt{001}, \texttt{010}, \texttt{011}, \texttt{100}, \texttt{101}\}$.

Słowa kodowe $B_k$ oznaczmy jako $\varsigma _i = (i)_{2,k}$ (dwójkowy zapis indeksów $i \in \{0,\ldots,n-1\}$ kolejnych symboli w $A_S=\{a_0,\ldots,a_{n-1}\}$). Prosty algorytm zakodowania symboli $A_S$ metodą przyrostową za pomocą kodu dwójkowego wygląda następująco (algorytm \1.1):

Algorytm 1.1  Kodowanie symboli źródła z wykorzystaniem kodu dwójkowego stałej długości

1. Pobierz kolejny symbol do zakodowania $s_i=a_j \in A_S=\{a_0,\ldots,a_{n-1}\}$ lub zakończ;
2. Dołącz do sekwencji wyjściowej bitowy ciąg: $\varsigma _i=(i)_{2,k}$;
3. Kontynuuj krok 1.

Algorytm dekodera kodu dwójkowego o $k$ bitowej długości słów, który sprowadza się do kolejnego odczytywania zapisanej na $k$ bitach pozycji dekodowanego symbolu w alfabecie $A_S$, jest następujący (algorytm 1.2):

Algorytm 1.2 Dekoder kodu dwójkowego o stałej długości 

1. Czytaj ciąg $k$ bitów i zapisz go jako $\alpha $; jeśli liczba bitów możliwych do przeczytania jest mniejsza od $k$ to zakończ;
2. Dla $\alpha =(i)_{2,k}$ jeśli $i<n$, to emituj na wyjście symbol $a_i \in A_S$; w przeciwnym razie sygnalizuj błąd dekodera i zakończ;
3. Kontynuuj krok 1.

Ponadto, zapis danych źródła w kodzie $B_k$ można wykorzystać w procedurze redukcji nadmiarowości oryginalnej reprezentacji danych o dynamice równej $n_o$ możliwych wartości. Odwzorowanie $n$ różnych wartości danych (symboli) źródła, gdzie $n<n_o$ w $n$ kolejnych słów kodowych $B_k$ pozwoli uzyskać stopień kompresji $CR>1$. Podobny eksperyment wykonano w przypadku kompresji danych obrazowych o niewykorzystanej pełnej dynamice bajtowych wartości pikseli.