Treść książki

Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Źródławiadomościiichkodowanie
25
Przykład1.3.RozważmyźródłobezpamięcioweXoalfabecieX={a1,a2,a3}isko-
jarzonymznimrozkłademprawdopodobieństwa{P(a1),P(a2),P(a3)}={1
2,1
4,1
4}.
PoniżejokreślimydrugierozszerzenieX2źródłaXprzezpodaniejegowiadomościele-
mentarnychiodpowiadającegoimrozkładuprawdopodobieństwa,atakżewyliczymy
jegoentropięiporównamyzentropiąźródłaX.WłasnościźródłaX2określonowta-
beliprzedstawionejponiżej.
NajejpodstawiemożnawyznaczyćentropięźródłaX2.EntropiaźródłaXwynosi
Wiad.X2
Wiad.X
P(bj)
a1a1
b1
1
4
a1a2
b2
1
8
a1a3
b3
1
8
a2a1
b4
1
8
a2a2
16
b5
1
a2a3
b6
16
1
a3a1
b7
1
8
a3a2
b8
16
1
a3a3
b9
16
1
H(X)=
1
2
log2+
1
4
log4+
1
4
log4=
3
2
NatomiastentropiadrugiegorozszerzeniaX2źródłaXwynosi
H(X2)=
1
4
log4+4i
1
8
log8+4i
16
1
log16=3
AzatemrzeczywiścieH(X2)=2H(X).
1.5.4.ŹródłaciągówMarkowa
Modeldyskretnegoźródłabezpamięciowegojestbardzoprostyiczęstonieodzwiercie-
dlasposobugeneracjiprzezźródłoposzczególnychwiadomsciwichciągu.Jużcho-
ciażbyprzykładtekstuwokreślonymjęzyku,wktórymjakoposzczególnewiadomości
elementarnesątraktowneznakialfanumeryczne,uzmysławianam,żekolejneznaki
niesąstatystycznieniezależneodsiebie.Istniejąbowiemtypowekombinacjezna-
kówtworzącesłowawdanymjęzyku,innezaśniewystepują.Takwięc,zdającsobie
sprawęzfaktycznejstatystycznejzależnsciodsiebiekolejnychwiadomsci,wprowa-
dzonomodelźródłaciągówMarkowa,któryuwzględniatęzależnsć.Poniżejpodamy
jegoformalnądefinicję.
Definicja1.6.NiechbędziedaneźródłoXoalfabecieX={a1,...,aK}.Źródło
tojestźródłemciągówMarkowam-tegorzędu,gdyprawdopodobieństwowygenerowa-
niawż-tejchwiliwiadomościxi∈{a1,...,aK}zależyodsekwencjimwiadomości
wygenerowanychpoprzednioprzezźródło.Oznaczato,żeźródłociągówMarkowajest
określoneprzezpodaniealfabetuXorazzbioruprawdopodobieństw{P(xi|xi11,...
,
xi1m)},gdziexi1j∈X,(j=0,...,m).
Blokwiadomsci(xi11,...,xi1m)określastan,wktórymznajdujesięźró-
dłociągówMarkowa.Ponieważwchwiliż−jźródłomożewygenerowaćjednązK
wiadomscinależącychdojegoalfabetu,liczbamożliwychstanówwynosiwięcKm.
Źródłoprzechodziodokreślonegowchwiliż-tejstanu(xi11,...,xi1m)podwpływem
wygenerowanejwiadomscixidostanu(xi,...,xi1m+1)wchwilinastępnej.
DogodnąmetodąopisuźródłaciągówMarkowajestpodaniejegodiagramu
stanów,podobniejaksiętoczyniopisującautomaty.Takwięcdiagramstanówprzed-
stawiawszystkieKmstanówźródłapołączonychodpowiedniozesobąprzejściamiwy-