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
Rozdział1.Informacjaikodowanie
wystarczywykazać,że
−
∑
j
=
i
1
p
j
lg
p
j
=
−
p
suma
lg
p
suma
−
p
suma
∑
j
=
i
1
p
p
suma
j
lg
p
suma
p
j
Jeżeli
p
suma
∑
j
=
i
1
p
p
suma
j
lg
p
suma
p
j
=
∑
j
=
i
1
p
j
lg
p
p
suma
j
=
∑
j
=
i
1
p
j
lg
p
j
−
∑
j
=
i
1
p
j
lg
p
suma
=
=∑
j
=
i
1
p
j
lg
p
j
−
p
suma
lg
p
suma
(1.1)
torównanie(1.1)jestprawdziwe,cokończydowód.
5.Właściwościzbiorupustego.DodaniedozbioruzdarzeńSniemożliwego
zdarzenia,czyraczejzdarzeniaoprawdopodobieństwiezerowym,niezmieniaen-
tropii,tj.
H(p1,…,pn,0)=H(p1,…,pn)
6.Funkcjaf(n)=
H
(
1
n
,K
,
1
n
)
rośniemonotonicznie,tj.f(n)<f(n+1)dla
każdegon>0.Oznaczato,żeilośćinformacjirośniezewzrostemzdarzeńorów-
nymprawdopodobieństwiezajścia.Dowódwynikanatychmiastzmonotoniczności
logarytmu,gdyżf(n)=lgn.
1.2.Kodowaniebezszumoweibezpamięciowe
1.2.Kodowaniebezszumoweibezpamięciowe
Załóżmy,żeistniejeźródłozalfabetemS={x1,…,xn}iprawdopodobieństwami
P={p1,…,pn}iżeliteromxiodpowiadająciągisymbolilubsłowakodunależące
dozbiorusłówkoduC={c1,…,cn}.KodemnazywamyodwzorowaniezSnaC,tj.
przypisaniesłowakoducikażdejliterzexi.Kodnazywamybinarnym,jeślisłowa
koduskładająsięzzerijedynek.Zakładamyteż,żeźródłoniemapamięci,tj.
przesyłaneliterysąniezależnejednaoddrugiej.Przykompresjidanychinteresuje
naszredukowaniedominimumoczekiwanego(średniego)kosztu
L
śr
=
∑
i
=
n
1
p
i
l
i
przyczymlijestdługościąsłowakoducikodującegoliteręxi.
DEFINICJA1.3.Kodnazywamyjednoznaczniedekodowalnym,jeśliistniejetylko
jedensposóbpodziałuciągusłówkodu
c
i
1
c
i
2
K
c
i
k
naoddzielnesłowakodu.Inny-
misłowy,jeśli
18
