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
1.3.Dodatek:OgraniczeniafunkcjientropiiH
Przykład1.5.Użyjmyźródłazprzykładu1.4.Alfabetźródłowyzawieratrzyli-
tery,S=(a,b,c),wysyłanezprawdopodobieństwamiP={0,1,0,45,0,45}.
UtwórzmynowyalfabetźródłowyS2={aa,ab,ac,ba,bb,bc,ca,cb,cc}złożony
zparliterwysyłanychzprawdopodobieństwami(0,01,0,045,0,045,0,045,0,2025,
0,2025,0,045,0,2025,0,2025},przyczymentropiaH(S2)=2H(S)=2,738.Długości
Shannonasłówkodudlamakrosymbolisąrównef−lg0,011=7,f−lg0,0451=5,
f−lg0,20251=3.ŚredniadługośćsłowakodunamakrosymbolL2=0,01⋅7+4⋅
⋅0,045⋅5+4⋅0,2025⋅3=3,4,takwięc
L
2
2=
1
,
7
bitów/literę,cojestowielebliżej
optymalnejdługości1,369niżprzeciętnadługośćznalezionadlapierwotnegoźró-
dła,tj.2,2.
Π
1.3.Dodatek:OgraniczeniafunkcjientropiiH
1.3.Dodatek:OgraniczeniafunkcjientropiiH
PodamyterazdowódokreślającyograniczeniadolneigórnefunkcjiH
0
=
H
(
1
,
0
,
K
,
0
)
<
H
(
p
1
,
K
,
p
n
)
<
H
(
1
n
,
K
,
1
n
)
=
lg
n
Wceluokreśleniaograniczeniadolnegozauważmy,żedlakażdegowyrazu
funkcjiH,−pilgpi>0,ponieważprawdopodobieństwonigdyniejestujemne,
algpi<0dla0<pi<1.
Zauważmyrównież,że,ponieważprawdopodobieństwadająwsumiejeden,
∑
i
n
=
1
p
i
=
1
,
jedno
z
prawdopodobieństw
zależy
od
pozostałych,
p
n
=
=
1
−
∑
n
i
=
−
1
1
pzatem
i
;
∂
∂
p
p
n
i
=
−
1
.
Funkcja
F
(
p
1
,
K
,
p
n
−
1
)
=
−
∑
n
i
=
−
1
1
p
i
lg
p
i
−
(
|
|
\
1
−
∑
n
i
=
−
1
1
p
i
\
|
|
)
lg
(
|
|
\
1
−
∑
n
i
=
−
1
1
p
i
\
|
|
)
maekstremumwpunkciep,jeśliwszystkiepochodnecząstkowe
∂
∂
F
p
i
=
0
.
Ekstre-
mumtojestmaksimum,jeślidlawyznacznikamacierzydrugichpochodnych
F
i
,
j
=
∂
∂
p
2
ip
∂
F
j
det
n
−=
1
F
F
n
1
−
,
1
1
,
1
F
n
−
1
,
2
L
F
n
−
1
,
n
−
1
F
1
,
2
L
L
F
1
,
n
−
1
dlakażdegoi=1,…,n−1,zachodzi(−1)idet
i>0,tj.wyznacznikdeti+1otrzymany
przezdodaniejednegowierszaijednejkolumnydowyznacznikadetizmieniarów-
nieżznak[10].
27
