Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
Kodowanieźródełdyskretnych
35
gościachodpowiednio{Z1,...,ZK}.ŚredniądługościąLciągukodowegonazywamy
wartośćoczekiwanądługościciągukodowegoopisanąwzorem
L=
Σ
i=1
K
ZiPi
(1.22)
Abyocenićjaksćkodowania,uprzedniomusimybyćpewni,żeistniejekodjed-
noznaczniedekodowalnybezopóźnieniaposiadającywybranyzestawdługsciciągów
kodowych{Z1,...,ZK}.DosprawdzeniategofaktusłużynierównośćKrafta-McMillana.
Twierdzenie1.2.Warunkiemkoniecznymiwystarczającymistnieniar-narnegokodu
jednoznaczniedekodowalnegobezopóźnienia,charakteryzującegosięzbioremdługości
ciągówkodowych{Z1,...,ZK},jestspełnienienierówności
Σ
i=1
K
r1lz≤1
Dlakodubinarnego(r=2)nierównsćuzyskujepostać
Σ
i=1
K
21lz≤1
(1.23)
(1.24)
NierównsćKrafta-McMillanasłużydosprawdzenia,czyistniejekodjedno-
znaczniedekodowalnybezopóźnieniaozadanychdługsciachciągówkodowych.Nie-
stetypozatymsprawdzeniemnieułatwiaonaznalezieniatakiegokodu.Zilustrujmy
tokolejnymprzykłademzaczerpniętymz[1].
Przykład1.13.Rozpatrzmypięćróżnychkodówźródłowychdlaźródłabezpamięcio-
wegoXoczterechwiadomościachelementarnych{a1,a2,a3,a4}.Przedstawionojew
poniższejtabeli.
Wiad.
a1
a2
a3
a4
A
00
01
10
11
B
0
100
110
111
C
0
10
110
111
D
0
100
110
11
E
0
10
110
11
Gdybyśmyoznaczylilewąstronęwzoru(1.24)jakoW,wtedyprosteoblicze-
niawskazują,żedlakodówA,CiDwartośćW=1,dlakoduBwartośćW=7/8,
natomiastdlakoduEwartośćW=9/8.KodAjestjednoznaczniedekodowalnybez
opóźnienia,ponieważjegociągikodowemająstałądługośćikażdyznichjestinny.Dłu-
gościciągówkodowychkoduBspełniająnierównośćKrafta-McMillanaiżadenzciągów
kodowychniejestprzedrostkieminnegociągukodowego.Zastosowaniejednegociągu
kodowegokrótszegoniżwprzypadkukoduBjestrównieżmożliwe,aleniewszyst-
kiekodyotakimzestawiedługościciągówkodowychsąjednoznaczniedekodowalnebez
opóźnienia.TakimkodemjestkodC,niejestnimnatomiastkodD.Ostatniciąg
