Treść książki

Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
38
Elementyteoriiinformacji
Zwarunków10i20wnioskujemy,żegranicaefektywnscikodowaniaźródłowegoby-
łabyosiągnięta,gdybydlakażdejwiadomsciźródłabezpamięciowegojejprawdopo-
dobieństwowystąpieniaPibyłowyrażoneprzezzależnsć
^
i
Pi=Qi=
j=1
Σ
K
r1lz
r1lj
=r1lż
(1.33)
Takwięcdlakażdejwiadomsciai,którejprawdopodobieństwojestokreślonewzorem
(1.33),reprezentującyjąciągkodowypowinienmiećdługsć
Zi=logr
Pi
1
(1.34)
Oczywiściedługsćciągówkodowychmusibyćliczbącałkowitą,awięcbyłobytomoż-
liwetylkowtedy,gdybyprawdopodobieństwawystąpieniaposzczególnychwiadomsci
miałypostać
Pi=(
1
r)
oz
(1.35)
iwtedydlakażdegożdługsćciągukodowegobyłabyrównaZi=0i.Jesttooczywiście
szczególnyprzypadek,któryzazwyczajniejestspełniony.
Prawdopodobieństwaposzczególnychwiadomscisąwłasnsciąźródła,awięc
niemożemyichkształtowaćwedługnaszychżyczeń.Zastanówmysięwięc,jakpo-
stępować,gdywarunek(1.35)niejestspełniony.Poniżejzaprezentowanerozwiązanie
zapewniauzyskaniegranicyefektywnościkodowaniaasymptotycznie.
Jeśliwartscilogarytmówzodwrotnsciprawdopodobieństwawystąpieniapo-
szczególnychwiadomsci(1.35)niesąliczbamicałkowitymi,wtedydługsćciąguko-
dowego,będącaliczbącałkowitą,mieścisięzpewnsciąwprzedziale
logr
Pi
1
≤Zi<logr
Pi
1
+1
(1.36)
Wybórdługościciągówkodowychwedługzasady(1.36)zapewniauzyskanie
kodujednoznaczniedekodowalnegobezopóźnienia,ponieważzfaktu,żedlakażdego
żjestspełnionywarunekZi≥log1
Pz,wynikaspełnienienierównsciKrafta-McMillana.
Wnioskujemybowiem,że
^
i
Pi≥r
1lz
zczegozkoleiwynika,że
Σ
i=1
K
r1lz≤
Σ
i=1
K
Pi=1
(1.37)
Możnasięłatwoprzekonać,żedobórciągówkodowychwedługzasady(1.36)
nieprowadzidozbytefektywnegokodu,bowiemśredniadługsćciągukodowegotak