Kodowanie Eliasa

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 ${\displaystyle (\gamma ),}$ delta ${\displaystyle (\delta )}$ oraz omega ${\displaystyle (\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).

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

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

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

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

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

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

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

Liczba bitów słowa kodowego zależy od wartości ${\displaystyle x}$ i wynosi ${\displaystyle \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}.}$

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

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

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

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. ${\displaystyle k:=x,}$
3. dopóki ${\displaystyle k>1.}$
   • zapisz dwójkowo liczbę ${\displaystyle k}$
   • ${\displaystyle k\leftarrow }$ liczba bitów zapisana krok wcześniej, pomniejszona o 1

Liczba bitów również zależy od wartości ${\displaystyle x.}$ W ${\displaystyle i}$-tym kroku zapisywane jest ${\displaystyle k_{i}=\lceil \log _{2}{k_{i-1}}\rceil -1}$ bitów, ${\displaystyle k_{0}=\lceil \log _{2}{x}\rceil .}$ A więc ${\displaystyle 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 }$

Dekodowanie przebiega według schematu:

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

Również zostanie zakodowana liczba ${\displaystyle x=113.}$

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

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