Treść książki

Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
34
Elementyteoriiinformacji
Definicja1.9.Niechci=(ci
1,ci
2,...,ci
m)będzieciągiemkodowymokreślonegokodu.
Ciągsymboli(ci
l,ci
2,...,ci
j),gdziej≤m,jestprzedrostkiemciągukodowegoci.
Zwróćmyuwagę,żewkodzieCkażdyciągkodowywymienionywyżejwtablicy
kodowaniajestprzedrostkiemciągówkodowychwystępującychwtablicypodnim.
Zasadniczymzadaniemjestskonstruowaniekodujednoznaczniedekodowalnego
bezopóźnienia.Wkolejnymprzykładzie[1]zilustrowanoheurystycznepodejściedo
rozwiązaniategoproblemu.
Przykład1.12.Przyjmijmy,żebezpamięcioweźródłowiadomościcharakteryzujesię
pięcioelementowymalfabetemwiadomości{a1,a2,...,a5}.Konstruujemybinarnykod
jednoznaczniedekodowalnywnastępującysposób.
Przyporządkujmywiadomościa1symbol„0”.Jestonwięcpierwszymwybra-
nymciągiemkodowym.Abyniebyłonprzedrostkieminnegociągukodowego,wszystkie
pozostałeciągikodowemusząmiećnapierwszejpozycjisymbol„1”.Niechzkoleiwia-
domościa2zostanieprzyporządkowanyciągsymboli„10”.Wszystkiepozostałeciągi
kodowebędąwięcmusiałyrozpocząćsięodsekwencji„11”.Takwięcwiadomościa3
możnaprzyporządkowaćciąg„110”.Doprzyporządkowaniaciągówkodowychpozostały
jedyniedwiewiadomości.Możnajewięcskojarzyćzciągamikodowymirozpoczynają-
cymisięodsekwencji„111”iuzupełnionychodpowiednioo„0”i„1”.Wtabeliponiżej
przedstawionowyniknaszegodziałaniajakokodA.
a1
a2
a3
a4
a5
KodA
1110
1111
110
10
0
KodB
110
111
00
01
10
Czyjesttojedynysposóbprzyporządkowaniawiadomsciomciągówkodowych?
Zpewnsciąnie!SpójrzmynakolumnęzawierającąciągikodowekoduB.Wtworze-
niutegokodustosowanotęsamąpodstawowązasadęjakwsynteziekoduA,tzn.
żadenciągkodowyniemożebyćprzedrostkieminnegociągukodowego.Rozpoczęto
jednakodprzyporządkowaniawiadomscia1sekwencji„00”.Powstajezatempytanie,
którykodjestlepszyijaktoocenić.Generalniemożemyuważać,żeimmniejsymboli
jestwymaganychśredniodoreprezentacjipojedynczejwiadomsci,tymkodjestlep-
szy.Abyosiągnąćwysokistopieńwykorzystaniasymbolikodowych,intuicyjniejest
jasne,żewiadomsciomwystępującymczęstonawyjściuźródłanależyprzyporząd-
kowaćkrótkieciągikodowe,natomiastwiadomsciomoniskimprawdopodobieństwie
wystąpienia—ciągikodoweowiększejdługsci.
Wceluoszacowaniajaksciprocesukodowaniażródłowegowprowadzasiępo-
jęcieśredniejdługościciągukodowego.
Definicja1.10.NiechbędziedanebezpamięcioweźródłowiadomościXoalfabecie
{a1,...,aK}iodpowiadającymwiadomościomprawdopodobieństwomichwystąpienia
{P1,...,PK}.Poszczególnymwiadomościomprzyporządkowanociągikodoweodłu-