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
Przykład1.4.Załóżmy,żealfabetźródłowyskładasięztrzechliter,S={a,b,
c},dlaktórychprawdopodobieństwaP={0,1,0,45,0,45}.Używająctabelzp.1.4,
obliczmy,żeentropiaźródłaH(S)=−0,1lg0,1−0,45lg0,45−0,45lg0,45=1,369.
DługościShannonasłówkodusąf−lg0,11=4,f−lg0,451=2orazf−lg0,451=2,
takwięcLśr=0,1⋅4+0,45⋅2+0,45⋅2=2,2bitów/literę.Jeślijednakwybraliby-
śmynadługościsłówliczby2,2i1,totetrzyliczbyrównieżspełniałybynierówność
Krafta,tj.istniałbykodprzedrostkowydlatychdługości,aśredniadługośćzmniej-
szyłabysięwznacznysposób,gdyżterazLśr=0,1⋅2+0,45⋅2+0,45⋅1=1,55.
Azatemsposóbkonstruowaniakoduprzedrostkowegosugerowanyprzeztotwier-
dzenienieprowadzidooptymalnejkompresji.Zauważmyrównież,żechociaż
średnia1,55jestowielelepszaniżśrednia2,2,towciążmożemytęśredniąulep-
szyć,gdyżograniczeniedolnerównasię1,369bitów/literę.
Π
Powyższetwierdzeniemożemywzmocnićtak,byodnosiłosiędokodowaniacią-
gówliter,anietylkoposzczególnychliter.Wtensposóbmożemyrozwiązaćproblem
zasygnalizowanywostatnimprzykładzie:gdykodowanieposzczególnychliterpro-
wadzidoprzeciętnejdługościznaczniewiększejniżentropiaźródła,wówczasdłu-
gośćtęmożemyzredukować,kodującciągiliterzamiastkażdąliteręzosobna.
TWIERDZENIE1.4.(PodstawowetwierdzenieShannonaodyskretnymkodowaniu
bezszumowym).DlaźródłaSoentropiiH(S)jestmożliweprzypisaniesłówkodo-
wychciągomkliterźródłatak,żejestspełnionawłaściwośćprzedrostkowaorazdla
średniejdługościLkotrzymujemy
H
(
S
)
<
L
k
k
<
H
(
S
)
+
1
k
Dowód.Prawdopodobieństwociągu
s
=
x
i
1
x
i
2
K
x
i
k
kliterspośródnliterźró-
dłazalfabetemS={xi,x2,…,xn}równasię
p
(
s
)
=
p
(
x
i
1
)
⋅
K
⋅
p
(
x
i
k
),
gdyżźródło
jestźródłembezpamięci,tj.literysąwysyłaneniezależniejednaoddrugiej.Roz-
ważmyterazźródłoużywającealfabetuzłożonegozmakrosymboli,przyczymkaż-
dymakrosymboljestciągiemkliterpierwotnegoźródła.Entropianowegoalfabetu
źródłowego
S
k
=
{
s
1
,
s
2
,
K
,
s
n
k
}
wszystkichciągówk-literowychrównasiękH(S)
(por.ćwiczenie7),azatem,namocytwierdzenia1.3
kH
(
S
)
<
L
k
<
kH
(
S
)
+
1
skądwypływapodstawowetwierdzenie.Zauważmy,żezewzrostemk,tj.zewzro-
stemdługościciągówwnowymalfabecieźródłowym,stosunekśredniejdługości
słowakodudodługościkjestzbieżnydoentropiipierwotnegoźródła,czyli
k
lim
→
∞
L
k
k=
H
(
S
),
ponieważ
k
lim1=
→
∞
k
0
.
Π
26
