Kodowanie arytmetyczne

Kodowanie arytmetyczne – metoda kodowania źródłowego dyskretnych źródeł sygnałów, stosowana jako jeden z systemów w bezstratnej kompresji danych. Została wynaleziona przez Petera Eliasa około 1960 roku. Od roku 2014 było zastępowane kodowaniem Asymmetric Numeral Systems, które pozwala na szybsze implementacje przy podobnym stopniu kompresji.

Ideą tego kodu jest przedstawienie ciągu wiadomości jako podprzedziału przedziału jednostkowego  wyznaczonego rekursywnie na podstawie prawdopodobieństw wystąpienia tychże wiadomości generowanych przez źródło. Ciąg kodowy reprezentujący kodowane wiadomości jest binarnym zapisem wartości z wyznaczonego w ten sposób przedziału.

Można udowodnić, że przy wyborze odpowiednio długiego ciągu wiadomości do zakodowania, średnia liczba symboli na wiadomość jest mniejsza od  gdzie  jest entropią źródła, lecz co najmniej równa samej entropii.

Algorytm kodowania 
Dany jest zbiór symboli  oraz stowarzyszony z nim zbiór prawdopodobieństw  Jeden z symboli jest wyróżniony – jego wystąpienie oznacza koniec komunikatu, co zapobiega wystąpieniu niejednoznaczności; ewentualnie zamiast wprowadzenia dodatkowego symbolu można przesyłać długość kodowanego ciągu.

Na początku dany jest przedział  który dzielony jest na podprzedziały o szerokościach równych kolejnym prawdopodobieństwom  czyli otrzymywany jest ciąg podprzedziałów  Kolejnym podprzedziałom (ozn. ) odpowiadają symbole ze zbioru 

Algorytm kodowania:
 Dla kolejnych symboli c:
 Określ, który podprzedział bieżącego przedziału  odpowiada literze c – wynikiem jest 
 Weź nowy przedział  – następuje zawężenie przedziału
 Podziel ten przedział  na podprzedziały w sposób analogiczny do tego, jak to miało miejsce na samym początku (chodzi o zachowanie proporcji szerokości podprzedziałów).
 Zwróć liczbę jednoznacznie wskazującą przedział  (najczęściej dolne ograniczenie, albo średnia dolnego i górnego ograniczenia).

Przykład 1 
Na rysunku pokazano, jak zmienia się aktualny przedział  w trzech pierwszych krokach kodowania. Kodowane są trzy symbole z czteroelementowego zbioru o prawdopodobieństwach  w kolejności: pierwszy, trzeci, czwarty.

Przykład 2 
Niech  ( – koniec komunikatu), prawdopodobieństwa 

Zakodowany zostanie ciąg 
 Początkowo przedział  jest on dzielony na podprzedziały 
 Pierwszym kodowanym symbolem jest  któremu odpowiada 3. podprzedział, zatem  Nowy przedział znów jest dzielony: 
 Kolejnym kodowanym symbolem jest  któremu odpowiada 1. podprzedział, zatem  Nowy przedział znów jest dzielony: 
 Kolejnym kodowanym symbolem jest  któremu odpowiada 2. podprzedział, zatem  Nowy przedział znów jest dzielony: 
 Kolejnym kodowanym symbolem jest (ponownie)  któremu odpowiada 1. podprzedział, zatem  Nowy przedział znów jest dzielony: 
 Kolejnym kodowanym symbolem jest  kończący kodowanie, któremu odpowiada 4. podprzedział, zatem 
 Na wyjście zostaje zapisana liczba identyfikująca ten przedział – może to być, jak wspomniano, jego dolne ograniczenie, czyli 0,802042.

Dekodowanie 
Dekodowanie przebiega prawie tak samo. Różnica polega na tym, że przy kodowaniu kolejne litery jednoznacznie określały podprzedziały, przy dekodowaniu natomiast wybierany jest ten podprzedział, do którego należy kodująca liczba. Wybranie podprzedziału powoduje wypisanie powiązanego z nim symbolu.

Formalnie algorytm przebiega następująco:
  – liczba (kod)
 
 Wykonuj w pętli:
 Podziel  na podprzedziały 
 Znajdź podprzedział  do którego należy 
 
 Wypisz i-ty symbol na wyjście
 Jeśli i-ty symbol był symbolem końcowym, zakończ pętlę

Przykład 
Na rysunku poniżej pokazano pierwsze trzy kroki dekodowania liczby 0,538 (zaznaczonej kropką na osi liczbowej); prawdopodobieństwa symboli:  W pierwszej iteracji  – liczba 0,538 znajduje się w pierwszym przedziale, a zatem wypisany zostanie pierwszy symbol, a  Teraz 0,538 znajduje się w przedziale 3., wypisany zostanie symbol 3., a  itd.

Zobacz też 
 kompresja danych (informatyka)
 Program do kompresji plików
 kodowanie Huffmana
 kodowanie Shannona
 kodowanie Shannona-Fano

Bibliografia 
 Adam Drozdek, Wprowadzenie do kompresji danych, WNT 1999.

Linki zewnętrzne 
  (materiały dydaktyczne AGH)

Algorytmy kompresji bezstratnej