Treść książki

Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Kodowanieźródełdyskretnych
39
uzyskanegokoduzawierasięwprzedzialepomiędzyentropiąźródłaajejwartscią
powiększonąojeden.Wyniktenuzyskujemy,mnożącdlakażdegożobustronnienie-
równsć(1.36)przezodpowiednieprawdopodobieństwowygenerowaniawiadomsciPi
isumująctakotrzymanewyrażeniastronami.Mamybowiem
^
i
Pilogr
Pi
1
≤PiZi<Pilogr
Pi
1
+Pi
Sumującstronamiotrzymujemy
Σ
i=1
Pilogr
Pi
1
≤
Σ
i=1
K
PiZi<
Σ
i=1
K
Pilogr
Pi
1
+
Σ
i=1
K
Pi
K
awięc
Hr(X)≤L<Hr(X)+1
(1.38)
Dlamałychwartscientropiiprzedziałtenjestrelatywnieszerokiiokazuje
sięwtedy,żeuzyskaniewysokiejefektywnscikodowaniaźródłowegojestmożliwe,
gdyzamiastreprezentowaćzapomocąciągówkodowychposzczególnewiadomości,
przedmiotemkodowaniabędąn-elementoweblokiwiadomsci.Takwięcefektywnsć
kodowaniaźródłowegowzrasta,gdykodowaniupodlegan-terozszerzenieźródłaX.
OznaczającjakoLnśredniądługsćciągukodowegowprzypadkukodowanian-tego
rozszerzeniaźródłaX,otrzymujemynapodstawie(1.38)nierównsć
Hr(X
n)≤Ln<Hr(Xn)+1
Wiedząc,żeHr(Xn)=nHr(X)otrzymujemyzkolei
nHr(X)≤Ln<nHr(X)+1
awięc
Hr(X)≤
Ln
n
<Hr(X)+
n
1
Zostatniejnierównsciwnioskujemy,że
n→∞
lim
Ln
n
=Hr(X)
(1.39)
(1.40)
Zwróćmyuwagę,żeLn/njestśredniąliczbąsymbolikodowychpotrzebnych
dozakodowaniapojedynczejwiadomościwblokunwiadomsci.Granica(1.40)po-
twierdzajeszczeraztwierdzenieShannona,żeśredniadługsćciągukodowegokodu
jednoznaczniedekodowalnego,użytegodoreprezentacjiwiadomsciźródłabezpamię-
ciowego,niemożebyćmniejszaniżentropiategoźródła(wjednostkachr-narnych).
Rozważaniapodobnedopowyższychmożnaprzeprowadzićdlakodowaniaźró-
dełciągówMarkowa[1].Wnioskipłynąceztychrozważańsątakiesameiprowadzą
dorównsci(1.40).