Kodowanie arytmetyczne.html

Kodowanie arytmetyczne to 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.

Ideą tego kodu jest przedstawienie ciągu wiadomości jako podprzedziału przedziału jednostkowego [0,1) 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 H(X) + 2, gdzie H(X) jest entropią źródła, lecz większa bądź co najwyżej równa samej entropii.

Spis treści

1 Algorytm kodowania
- 1.1 Przykład 1.
- 1.2 Przykład 2.
2 Dekodowanie
- 2.1 Przykład
3 Praktyczne implementacje
4 Bibliografia
5 Zobacz też

edytuj Algorytm kodowania

Dany jest zbiór symboli $S = \{x_1, x_2, \ldots\}$ oraz stowarzyszony z nim zbiór prawdopodobieństw $p = \{p_1, p_2, \ldots\}$ . Jeden z symboli jest wyróżniony - jego wystąpienie oznacza koniec komunikatu, zapobiegając wystąpieniu niejednoznaczności; ewentualnie zamiast wprowadzenia dodatkowego symbolu można przesyłać długość kodowanego ciągu.

Na początku dany jest przedział $P = [0,1)$ , który dzielony jest na podprzedziały o szerokościach równych kolejnym prawdopodobieństwom $p i$ , czyli otrzymywany jest ciąg podprzedziałów $[0, p_1), [p_1, p_1 + p_2), [p_1 + p_2, p_1 + p_2 + p_3), [p_1 + p_2 + p_3, p_1 + p_2 + p_3 + p_4), \ldots$ . Kolejnym podprzedziałom (ozn. $R i$ ) odpowiadają symbole ze zbioru $S$ .

Algorytm kodowania:

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

edytuj Przykład 1.

Na rysunku pokazano, jak zmienia się aktualny przedział $P$ w trzech pierwszych krokach kodowania. Kodowane są cztery symbole o prawdopodobieństwach $p = {0.6,0.2,0.1,0.1}$ w kolejności: pierwszy, trzeci, czwarty.

edytuj Przykład 2.

Niech $S = \{a, b, c, \#\}$ ( $\#$ - koniec komunikatu), prawdopodobieństwa $p = {0.45,0.3,0.2,0.05}$ .

Zakodowany zostanie ciąg $caba\#$ .

Początkowo przedział $P = [0,1)$ , jest on dzielony na podprzedziały $[0,0.45),[0.45,0.75),[0.75,0.95),[0.95,1)$ .
Pierwszym kodowany symbolem jest $c$ , któremu odpowiada 3. podprzedział, zatem $P : = R 3 = [0.75,0.95)$ . Nowy przedział znów jest dzielony: $[0.75,0.84),[0.84,0.9),[0.9,0.94),[0.94,0.95)$ .
Kolejnym kodowanym symbolem jest $a$ , któremu odpowiada 1. podprzedział, zatem $P : = R 1 = [0.75,0.84)$ . Nowy przedział znów jest dzielony: $[0.75,0.7905),[0.7905,0.8175),[0.8175,0.8355),[0.8355,0.84)$ .
Kolejnym kodowanym symbolem jest $b$ , któremu odpowiada 2. podprzedział, zatem $P : = R 2 = [0.7905,0.8175)$ . Nowy przedział znów jest dzielony: $[0.7905,0.80265),[0.80265,0.81075),[0.81075,0.81615),[0.81615,0.8175)$ .
Kolejnym kodowanym symbolem jest (ponownie) $a$ , któremu odpowiada 1. podprzedział, zatem $P : = R 1 = [0.7905,0.80265)$ . Nowy przedział znów jest dzielony: $[0.7905,0.795968),[0.795968,0.799612),[0.799612,0.802042),[0.802042,0.80265)$ .
Kolejnym kodowanym symbolem jest $\#$ , kończący kodowanie, któremu odpowiada 4. podprzedział, zatem $P : = R 4 = [0.802042,0.80265)$ .
Na wyjście zostaje zapisana liczba identyfikująca ten przedział - może to być, jak wspomniano, jego dolne ograniczenie, czyli 0.802042.

edytuj Dekodowanie

Dekodowanie przebiega prawie tak samo. Z tą różnicą, że przy kodowaniu kolejne litery jednoznacznie określała 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:

$x$ - liczba (kod)
$P = [0,1)$
Wykonuj w pętli:
- Podziel $P$ na podprzedziały $R i$
- Znajdź podprzedział $R i$ do którego należy $x$ .
- $P : = R i$
- Wypisz i-ty symbol na wyjście
- Jeśli i-ty symbol był symbolem końcowy, zakończ pętlę

edytuj Przykład

Na rysunku poniżej pokazano pierwsze trzy kroki dekodowania liczby 0.538 (zaznaczona kropką na osi liczbowej); prawdopodobieństwa symboli: $p = {0.6,0.2,0.1,0.1}$ . W pierwszej iteracji $P = [0,1)$ - liczba 0.538 znajduje się w pierwszym przedziale, a zatem wypisany zostanie pierwszy symbol, a $P : = R 1 = [0,0.6]$ . Teraz 0.538 znajduje się w przedziale 3., wypisany zostanie symbol 3. a $P = R 3 = [0.48,0.54]$ . Itd.

edytuj Praktyczne implementacje

Podstawowy algorytm, dość wolny jednak, generuje kolejne bity rozwinięcia dwójkowego. O wiele lepsza realizacja opiera się w całości na działaniach na liczbach całkowitych.

edytuj Bibliografia

Adam Drozdek, Wprowadzenie do kompresji danych, WNT 1999