Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2020Kompresjainformacji
2.2.Kompresjainformacji
11
Jednymzcelówkodowaniajestzwięzłereprezentowanieinformacji,czyli
kompresja.ProstąmetodękompresjizaproponowałC.Shannonwdowodzie
podstawowegotwierdzeniaokodowaniu0
Kompresjaciągówbitowychpowinnabyćodwracalna(bezstratna).Możnają
realizowaćnakilkasposobów.Wyróżniasię:
kodowaniegrupowe(ang0run-length)zwykłeiwzględne(ang0relative),
kodowaniezależneodczęstościwystąpień(ang.frequency-dependent),
kodowaniezesłownikiemadaptacyjnym(ang0adaptivedictionary)0
Kompresjasygnałów(dźwiękuiobrazu)możebyćstratna,leczpowinnabyć
takrealizowana,abyprzekodowanieniepowodowałoutratytychcechsygnału,
któresąistotnedlajegopercepcjiprzezużytkownika.
2.2.1.Kodyarytmetyczne
Kodowaniearytmetycznetometodakodowaniadyskretnychźródełsygnałów,
bedącajednymzesposobówkompresjibezstratnej.Jejideąjestprzedstawienie
ciąguwiadomościjakoodcinkaprzedziału[0,1)(P.Elias,1960).Ciągbinarny
reprezentującywiadomośćjednoznaczniewskazujetenodcinek(współrzędna
początku,końcalubichśrednia).Odwzorowaniewyznaczasięrekurencyjniena
podstawieprawdopodobieństwwystąpieniawiadomościwciągupochodzącym
zeźródłainformacji.
Możnawykazać,żedlaodpowiedniodługiegociąguwiadomości,średnia
liczbatakwytworzonychsymbolinazakodowanąwiadomośćjestniemniejsza
odentropiiźródłaH(X),alemniejszaodH(X)+20
Algorytmykodowaniaidekodowaniaarytmetycznego
DanyjestzbiórsymboliS={x1,x2,ł}iprzypisaneimprawdopodobieństwa
p1,p2,ł.Jedenzsymbolijestwyróżniony–jegowystąpienieoznaczakoniec
komunikatu,cozapobieganiejednoznaczności.Zamiastdodatkowegosymbolu
możnaprzesyłaćdługośćkodowanegociągu.
PrzedziałP=[0,1)dzielisięnaodcinkioszerokościachrównychkolejnym
prawdopodobieństwompi,otrzymującciągR1=[0,p1),R2=[p1,p1+p2),R3=[p1+p2,
p1+p2+p3),R4=[p1+p2+p3,p1+p2+p3+p4),itd.PodprzedziałomRiodpowiadają
symbolexizezbioruS.Teraz,ażdowyczerpanialisty,dlakolejnychsymboli:
podprzedziałRibieżącegoprzedziałuP,odpowiadającysymbolowixi
potraktujjakoprzedziałpierwotnydlakolejnegopodziału,P:=Ri,
podzielnowy(zawężony)przedziałPnapodprzedziaływproporcjach
prawdopodobieństwpi,tworzącwtensposóbnowepodprzedziałyRi0
Uzyskanaliczbajednoznaczniewskazujeodcinekzbioru[0,1),odpowiadający
ciągowikodowanychsymboli(dolnelubgórneograniczenie,alboichśrednia).
Przebiegalgorytmupokazująponiższeprzykłady.Jegoulepszona,szybsza
wersjajestopartawcałościnadziałaniachnaliczbachcałkowitych.
