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.2.Kodowaniebezszumoweibezpamięciowe
TWIERDZENIE1.3.(A)Dladowolnegobinarnegokoduprzedrostkowego,dlaktó-
regośredniadługośćsłowakodowegoLśr=Σpili,zachodzinierówność
Lśr>H(S)
(B)Istniejebinarnykodprzedrostkowy,dlaktórego
Lśr<H(S)+1
Dowód(A).
cowynikaznierówności(1.2)
cowynikaznierównościKraftaiztego,żeΣpi=1.
całkowitą,cozkoleijestmożliwewówczas,gdypijestodwrotnościąpotęgidwójki.
Zachodzitoraczejrzadko,dlategośredniadługośćsłowakodujestzazwyczaj
większaniżentropiaźródła,tj.większaniżidealnaśrednia.
Zauważmy,żejeśli−lgpi=li,toLśr=H(S),cowymaga,by−lgpibyłoliczbą
H
=
(
=
lg
S
)
−
e
−
Σ
Σ
L
(
(
śr
p
2
i
−
=
lg
l
i
−
−
p
Σ
i
p
2
i
p
l
)
i
i
)
=
lg
=
lg
p
Σ
i
e
−
p
(
Σ
Σ
i
lg
2
p
−
i
l
p
i
l
i
1
i
2
−
l
=
i
Σ
<
−
p
Σ
Σ
i
)
p
p
<
i
i
(
(lg
p
lg
i
1
2
l
e
i
p
(
−
i
1
+
1
−
)
lg
1
lg
)
2
=
e
l
i
,
)
0,
=
Dowód(B).ZdefiniujmydługośćShannona
l
i
=
[
−
lg
p
i
]
dlakażdegoi,przy
czymfx1jestnajmniejsząwartościącałkowitąniemniejsząniżx,tj.
l
i
>
−
lgi
p
,
skąd
p
i
>
2i
−
l
.
Pozsumowaniupoiotrzymujemy
Σ
2
−
l
i<
Σ
p
i
=
1
cojestnierównościąKraftagwarantującąistnieniekoduprzedrostkowegodlatych
długości.Ponadto
l
i
<
−
lg
p
i
+
1
lubpopomnożeniuprzezpi
p
i
l
i
<
p
i
(
−
lg
p
i
+
1
)
cozkoleipozsumowaniupoidaje
L
śr
=
Σ
p
i
l
i
<
Σ
p
i
(
−
lg
p
i
+
1
)
=
−
Σ
p
i
lg
p
i
+
Σ
p
i
=
H
(
S
)
+
1
Π
25
