Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
A.Drozdek"Wprowadzeniedokompresjidanych",Warszawa2007,wyd.2,ISBN978-83-204-3309-8©byWNT
Rozdział1.Informacjaikodowanie
zwyprzedzeniem;np.dekodującsłowokodu0111:najpierw0możemyzdekodo-
waćjakoA;następującapotymzerzejedynkamożewskazywać,żeAzostałonie-
poprawniewybrane,a01powinnobyćzdekodowanejakoC,alboteż,żeAbyło
właściwymwyborem,jeślitrzecimsymbolemjest1;ponieważrzeczywiściejestto1,
ABzostajenarazieuznanezazdekodowanączęśćprzekazu;czwartymsymbolem
jestrównież1,zatempierwszadecyzjabyłaniewłaściwaiAzostałoniewłaściwie
wybrane;właściwiezdekodowanymprzekazemjestCB.Zatemkod2jestjedno-
znaczniedekodowalny,leczniemawłaściwościprzedrostkowej.Wreszciekod3
ikod4,będąckodamiprzedrostkowymi,umożliwiajądekodowaniewtrakciewczy-
tywania,leczkod3niejestkodemoptymalnym,gdyżzredukowaniesłowakodudla
literyCz10do1redukujeLśrbeznaruszaniawłaściwościprzedrostkowejkodu.
Zauważmy,żewłaściwośćprzedrostkowaprzejawiasięwdrzewachkodowychtym,
żesłowakoduznajdująsiętylkowliściachdrzewa,jaknarys.1.6c–d,anigdy
wwęzłachwewnętrznych,jaknarys.1.6a–b.
Rys.1.6.CzteryróżnekodydlatrzechliterA,BiC
1.2.1.NierównośćKrafta
Naszymcelemjestwygenerowanieoptymalnegokoduprzedrostkowego.Musimy
najpierwokreślić,wjakiejsytuacjijesttomożliwe,byniepróbowaćkonstruować
gowówczas,gdytakapróbajestskazanananiepowodzenie.Danedotyczącetej
możliwościmożemyuzyskaćnapodstawietwierdzeniadowiedzionegoprzezLeona
G.Kraftaw1949r.wpracymagisterskiej.
TWIERDZENIE1.1.(TwierdzenieKrafta).Binarnykodprzedrostkowyzłożonyze
słówkodu{c1,…,cn}odługościach{l1,…,ln}istniejewtedyitylkowtedy,gdy
∑
i
=
n
1
2
−
li
<
1
Dowód.Umieśćmywszystkiesłowakoduwdrzewiebinarnymiuzupełnijmyto
drzewododrzewapełnego,tj.drzewao2lmaxwęzłach(liściach)naostatnimpozio-
mielmax+1,przyczymlmax=max{l1,…,ln}(liczeniepoziomówzaczynamyod1,
20
