Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
40
Elementyteoriiinformacji
Przykład1.14.RozważmyźródłobezpamięcioweXcharakteryzującesięwiadomo-
ściamielementarnymi„0”oraz„1”występującymiodpowiedniozprawdopodobień-
stwamiPO=0,1orazP1=0,9.Łatwomożnaobliczyć,żeentropiategoźródławynosi
H(X)=0,4690.Zakładajączastosowaniebinarnegokoduźródłowego(r=2)iko-
dowaniebezpośredniowiadomości„0”oraz„1”zapomocąjednoelementowychciągów
kodowych0i1otrzymujemy,żeśredniadługośćciągukodowegowynosiwtymprzy-
padkuL=1.Takwięcsprawnsćkodowaniawynosi
η=
Hr(X)
L
=
0,4690
1
=46,9%
RozważmyterazdrugierozszerzenieźródłaX2.Wtabeliponiżejprzedstawionowiado-
mościźródłaX2,ichprawdopodobieństwaorazzwiązaneznimidługościciągówkodo-
wychwynikającezzasady(1.36).
Wiadomość
11
10
01
00
0781
0709
0709
0701
Pi
li
1
4
4
7
Okazujesię,żewtymprzypadkuśredniadługośćciągukodowegowynosiL2=
=1,6,takwięcsprawnośćkodowania
η=
2Hr(X)
L2
=58,6%
Łatwomożnazauważyć,żezastosowaniedoborudługościciągówkodowychwedługza-
sady(1.36)niedoprowadziłowtymprzypadkudoznalezieniakoduzwięzłego.Już
bowiemzestawdługościciągówkodowych(1,2,3,3)przyporządkowanychodpowiednio
wiadomościom11,10,01i00pozwalanakonstrukcjękodujednoznaczniedekodowal-
negobezopóźnienia,któregośredniadługośćciągówkodowychwynosiL2=1,29,
azatemsprawnośćkodowaniaη=72%.Dobórdługościciągówkodowychwedługza-
sady(1.36)stajesięoptymalnyprzykodowaniuwiadomościcorazwyższychrozszerzeń
źródłaX.
Powyższyprzykładwskazuje,żebyłobyinteresującewyznaczeniemetodykodo-
waniadającejwrezultaciekodzwięzłynietylkowsensieasymptotycznymdlarosną-
cychrozszerzeńźródławiadomsciX,alerównieżdladowolnegoźródła.Okazuje
się,żeistniejekilkametodkodowaniadającychwwynikukodzwięzły.Omówimy
najważniejszeznich.
1.6.1.KodowanieHuffmana
W1962rokuHulmanprzedstawiłprocedurę,którawyznaczar-narnykodzwięzłydla
dowolnegobezpamięciowegoźródławiadomsci.Poniżejprzedstawimyjąnaprzykła-
dziekodubinarnego.
RozważmyźródłobezpamięciowemającealfabetX={a1,a2,...,aK}orazod-
powiadającewiadomsciomelementarnymprawdopodobieństwaichwystąpieniarówne
