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 delta oraz 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 jest zapisywana w naturalnym kodzie binarnym. – liczba cyfr znaczących w zapisie dwójkowym. Słowo kodowe składa się: z bitu o wartości zero powtórzonego razy, liczby dwójkowej.
Liczba bitów słowa kodowego zależy od wartości i wynosi
Algorytm dekodowania Policzenie bitów o wartości 0 – daje to liczbę Kolejne bitów to zapisana binarnie liczba
Przykład kodowania Niech – składa się z bitów.
Słowo kodowe ma długość 13 bitów:
Kodowanie delta Algorytm kodowania Podobnie jak w kodowaniu gamma pierwszym krokiem jest reprezentacja w kodzie binarnym, o bitach znaczących. Z liczby dwójkowej jest usuwana najbardziej znacząca cyfra (jedynka). Następnie liczba jest przedstawiana w kodzie gamma. Jeśli przez oznaczymy liczbę bitów znaczących wówczas słowo kodowe składa się z pól: zer, liczba przedstawiona binarnie, liczba przedstawiana binarnie z usuniętą najbardziej znaczącą cyfrą.
Liczba bitów słowa kodowego zależy od wartości i wynosi
Algorytm dekodowania Zdekodowanie liczby Odczytanie słowa -bitowego. Wstawienie bitu o wartości 1 na początek słowa – liczba
Przykład kodowania Niech – składa się z bitów. Z kolei przedstawione w postaci binarnej to składa się z bitów.
Pamiętając, że najbardziej znaczący bit jest usuwany z reprezentacji słowo kodowe ma postać
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: zapisz bit 0 (znacznik końca),
dopóki zapisz dwójkowo liczbę liczba bitów zapisana krok wcześniej, pomniejszona o 1
Liczba bitów również zależy od wartości W -tym kroku zapisywane jest bitów, A więc
Algorytm dekodowania Dekodowanie przebiega według schematu:
dopóki kolejny bit nie ma wartości 0: wartość zapisana na kolejnych bitach – ostatnia odczytana wartość.
Przykład kodowania Również zostanie zakodowana liczba
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ć
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
Kategoria:Algorytmy kompresji bezstratnej