Treść książki

Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
36
Elementyteoriiinformacji
kodowykoduDjestbowiemprzedrostkiemciąguprzyporządkowanegowiadomościa3.
WreszciekodEniespełniawarunkuKrafta-McMillana,więczarównoonjakijakikol-
wiekinnyotakimzestawiedługościniebędziekodemjednoznaczniedekodowalnymbez
opóźnienia.
Skoroistniejewielemożliwychkodówźródłowychozestawiedługscispełnia-
jącymnierównsćKrafta-McMillana,zktórychczęśćniejestkodamijednoznacznie
dekodowalnymibezopóźnienia,topowstajeproblem,jakznaleźćnajlepszykod,który
będziemiałnajniższąśredniądługsćciagukodowegospsródwszystkichr-narnych
kodówjednoznaczniedekodowalnychbezopóźnieniazastosowanychdoreprezentacji
wiadomscidanegoźródłabezpamięciowegoX.Takikodjestnazywanykodemzwię-
złym.
Wpierwszymkrokunaszychposzukiwańkodówzwięzłychznajdziemymini-
malnąwartsćśredniejdługsciciągukodowegodlakodujednoznaczniedekodowal-
negobezopóźnienia.
Jakpoprzednio,rozważmybezpamięcioweźródłowiadomościXscharakteryzo-
waneprzezalfabetX={a1,a2,...,aK}orazodpowiadająceposzczególnymwiado-
msciomprawdopodobieństwaichwystąpieniaP(ai)=Pi(ż=1,2,...,K).Symbole
kodowe,zktórychutworzonesąciągikodowe,sąwybieranezr-narnegoalfabetuY.
OznaczmydługsćciągukodowegoprzyporządkowanegowiadomsciaijakoZi.Jak
pamiętamy,entropiatakegoźródłajestdanawzorem(1.2).Przypomnijmyrównież,
żeudowodniliśmyjużprawdziwsćnierównsci
Σ
i=1
K
Pilog
Qi
Pi
≤0,
(1.25)
gdziezarównoPijakiQimająsensprawdopodobieństw,tzn.Pi≥0,Qi≥0,
K
K
(ż=1,2,...,K),
Σ
Pi=1,
Σ
Qi=1.Znierównsci(1.25)wynika,że
i=1
i=1
Σ
i=1
K
Pilog
Pi
1
≤
Σ
i=1
K
Pilog
Qi
1
(1.26)
Zauważmy,żerównsćwwyrażeniu(1.25)zachodzitylkowtedy,gdyPi=Qi(ż=
1,2,...,K).Takwięc,znającdefinicjęentropiiźródłabezpamięciowegomamy
H(X)≤
Σ
i=1
K
Pilog
Qi
1
Przyjmijmyobecnie,że
Qi=
j=1
Σ
K
r1lz
r1lj
(1.27)
(1.28)