Kodowanie Eliasa

Kodowanie Eliasa

Rodzaj	kompresja
Złożoność
Pamięciowa	zależnie od implementacji

Kodowanie Eliasa – sposób kodowania liczb całkowitych większych od zera, za pomocą słów kodowych o zmiennej długości; liczba bitów jest proporcjonalna do kodowanej wartości. Istnieją trzy sposoby kodowania: gamma $(\gamma ),$ delta $(\delta )$ oraz omega $(\omega ).$

Kodowanie jest używane m.in. w różnych metodach kompresji, wymagających zapisywania liczb z szerokiego przedziału wartości (np. przesunięć w metodzie LZR, pochodnej LZ77).

Kodowanie gamma

Algorytm kodowania

• Liczba $x$ jest zapisywana w naturalnym kodzie binarnym.
• $n$ – liczba cyfr znaczących w zapisie dwójkowym.
• Słowo kodowe składa się:
  1. z bitu o wartości zero powtórzonego $n-1$ razy,
  2. liczby dwójkowej.

Liczba bitów słowa kodowego zależy od wartości $x$ i wynosi $2\cdot \lceil \log _{2}{x}\rceil -1.$

Algorytm dekodowania

• Policzenie bitów o wartości 0 – daje to liczbę $n-1.$
• Kolejne $n$ bitów to zapisana binarnie liczba $x.$

Przykład kodowania

Niech $x=113_{10}=1110001_{2}$ – składa się z $n=7$ bitów.

Słowo kodowe ma długość 13 bitów: $\underbrace {000000} _{(n-1)\times 0}\underbrace {1110001} _{x}.$

Kodowanie delta

Algorytm kodowania

Podobnie jak w kodowaniu gamma pierwszym krokiem jest reprezentacja $x$ w kodzie binarnym, o $n$ bitach znaczących. Z liczby dwójkowej jest usuwana najbardziej znacząca cyfra (jedynka). Następnie liczba $n$ jest przedstawiana w kodzie gamma. Jeśli przez $k$ oznaczymy liczbę bitów znaczących $n,$ wówczas słowo kodowe składa się z pól:

• $k-1$ zer,
• liczba $n$ przedstawiona binarnie,
• liczba $x$ przedstawiana binarnie z usuniętą najbardziej znaczącą cyfrą.

Liczba bitów słowa kodowego zależy od wartości $x$ i wynosi $\underbrace {\lceil \log _{2}x\rceil -1} _{x}+\underbrace {2\cdot \lceil \log _{2}(\lceil \log _{2}{x}\rceil )\rceil -1} _{n\ {\textrm {oraz}}\ k-1}.$

Algorytm dekodowania

• Zdekodowanie liczby $n.$
• Odczytanie słowa $n$-bitowego.
• Wstawienie bitu o wartości 1 na początek słowa – liczba $x.$

Przykład kodowania

Niech $x=113_{10}=1110001_{2}$ – składa się z $n=7$ bitów. Z kolei $n$ przedstawione w postaci binarnej to $111_{2},$ składa się z $k=3$ bitów.

Pamiętając, że najbardziej znaczący bit jest usuwany z reprezentacji $x,$ słowo kodowe ma postać $\underbrace {00} _{(k-1)\times 0}\underbrace {111} _{n}\underbrace {110001} _{x'}.$

Kodowanie omega

Algorytm kodowania

Kodowanie jest nieco bardziej złożone i przeprowadzane iteracyjnie, w kolejnych krokach podsłowa binarne są doklejane na początek słowa kodowego.

Algorytm przebiega następująco:

1. zapisz bit 0 (znacznik końca),
2. $k:=x,$
3. dopóki $k>1.$
   • zapisz dwójkowo liczbę $k$
   • $k\leftarrow$ liczba bitów zapisana krok wcześniej, pomniejszona o 1

Liczba bitów również zależy od wartości $x.$ W $i$-tym kroku zapisywane jest $k_{i}=\lceil \log _{2}{k_{i-1}}\rceil -1$ bitów, $k_{0}=\lceil \log _{2}{x}\rceil .$ A więc $1+\sum _{i=0}^{n}k_{i}=1+\lceil \log _{2}{x}\rceil +\lceil \log _{2}{(\lceil \log _{2}{x}\rceil -1)}\rceil +\lceil \log _{2}{(\lceil \log _{2}{(\lceil \log _{2}{x}\rceil -1)}\rceil }-1)\rceil +\ldots$

Algorytm dekodowania

Dekodowanie przebiega według schematu:

1. $n:=1$
2. dopóki kolejny bit nie ma wartości 0:
   • $n\leftarrow$ wartość zapisana na $n+1$ kolejnych bitach
3. $x:=n$ – ostatnia odczytana wartość.

Przykład kodowania

Również zostanie zakodowana liczba $x=113.$

Krok	k	Słowo binarne	Liczba bitów
1		0
2	113	1110001	7
3	6	110	3
4	2	10	2
5	1	koniec kodowania

Po połączeniu słów binarnych w odwrotnej kolejności, słowo kodowe będzie miało postać $\underbrace {10} _{4.}\underbrace {110} _{3.}\underbrace {1110001} _{2.\ \mathrm {krok} }0.$

Kody dla liczb od 1 do 32

	Gamma		Delta		Omega
x	kod	liczba bitów	kod	liczba bitów	kod	liczba bitów
1	1	1	1	1	0	1
2	010	3	0100	4	100	3
3	011	3	0101	4	110	3
4	00100	5	01100	5	101000	6
5	00101	5	01101	5	101010	6
6	00110	5	01110	5	101100	6
7	00111	5	01111	5	101110	6
8	0001000	7	00100000	8	1110000	7
9	0001001	7	00100001	8	1110010	7
10	0001010	7	00100010	8	1110100	7
11	0001011	7	00100011	8	1110110	7
12	0001100	7	00100100	8	1111000	7
13	0001101	7	00100101	8	1111010	7
14	0001110	7	00100110	8	1111100	7
15	0001111	7	00100111	8	1111110	7
16	000010000	9	001010000	9	10100100000	11
17	000010001	9	001010001	9	10100100010	11
18	000010010	9	001010010	9	10100100100	11
19	000010011	9	001010011	9	10100100110	11
20	000010100	9	001010100	9	10100101000	11
21	000010101	9	001010101	9	10100101010	11
22	000010110	9	001010110	9	10100101100	11
23	000010111	9	001010111	9	10100101110	11
24	000011000	9	001011000	9	10100110000	11
25	000011001	9	001011001	9	10100110010	11
26	000011010	9	001011010	9	10100110100	11
27	000011011	9	001011011	9	10100110110	11
28	000011100	9	001011100	9	10100111000	11
29	000011101	9	001011101	9	10100111010	11
30	000011110	9	001011110	9	10100111100	11
31	000011111	9	001011111	9	10100111110	11
32	00000100000	11	0011000000	10	101011000000	12

Zobacz też

• kod Golomba
• kod Tunstalla
• kod unarny
• kodowanie Huffmana