Kodowanie arytmetyczne

Z Wikipedii

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 2 Dekodowanie 3 Praktyczne implementacje 4 Bibliografia 5 Zobacz też

[edytuj] 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, 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 . 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

Niech ( - koniec komunikatu), prawdopodobieństwa p = {0.45,0.3,0.2,0.05}.

Zakodowany zostanie ciąg .

• 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₃ = [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₁ = [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₂ = [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₁ = [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₄ = [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] 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

[edytuj] Zobacz też

• kodowanie Shannona
• kodowanie Shannona-Fano
• kodowanie Huffmana