Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
2.4.ALGORYTMYKODOWANIAOPTYMALNEGO
Dlawprowadzeniawkolejnypodrozdziałrozważmykodowanieźródłazczteremako-
munikatamizidentycznymzestawemkodów,aleprzypisanychinnymkomunikatom,tojest
wkolejnościodpowiednio0,10,110,111.Tymrazemśredniadługośćkodowaniawyniesie:
L
±
1
2
|+|+X|±
1
1
4
22
.
1
8
3
446
++
8
±
7
4
.
Ponieważjestrównaentropii,implikujekodowanieoptymalne.Właśniealgorytmy
optymalnegokodowaniastanowiątematykękolejnegopodrozdziału.
Wdotychczasowymopisieredundancjabyłazjawiskiemnegatywnym,jednakwprak-
tyceinformatycznejwartościowanieredundancjijestniecobardziejzłożone.Kosztowność
zjawiskaniebudziwątpliwości,alemożebyćzamierzonadlaosiągnięciainnychcelów.
Najprostszymzastosowaniemcelowejredundancjijestpowszechnakopiabezpieczeństwa.
Zauważmy,żekopianiczegoinformacyjnieniewnosiwobecpierwowzoru,alekosztuje
podwójnie.Dwukrotniekosztujenośnikinformacjiorazczaskoniecznynawykonanie
kopii,oznaczającredundancjęwynoszącądokładnie2,usprawiedliwionąwzględamibez-
pieczeństwa.Właśniebezpieczeństwojestpodstawowąkorzyściąświadomejredundancji
objawianejwmacierzydyskowej,czyliurządzeniuowielokrotnymzapisiejednejinfor-
macji,czyliowielokrotnejredundancji.Winformatyceniecobardziejpodstawowejza-
stosowaniemasubtelniejsza(niecałkowita)redundancjapolegającanatakzwanymbicie
parzystości,czylidodaniedozestawubitówdodatkowegobituuzupełniającegoliczbę
bitówustawionychna1wcałościzapisudoliczbyparzystej.Tymsamymewentualnybłąd
przesyłania(przekłamanie)objawiasiębrakiemparzystości,pozwalającnaodpowiednią
reakcję.Jeszczeciekawszymzastosowaniemświadomejredundancjijestdodaniewięk-
szejilościdodatkowychbitów,copozwalaosiągnąćprzesyłaniedanychzmożliwościami
samokorekty,jaknaprzykładwkodachHamminga.
2.4.Algorytmykodowaniaoptymalnego
Wpoprzednimpodrozdzialewprowadziliśmypojęcieredundancjiźródłainformacjista-
nowiącejakościowekryteriumkodowania,aponadtopodaliśmykilkaprzykładówopty-
malnychkodowań.Wiemy,żeoptymalnekodowaniasąmożliwe,niewiemyjednak,jak
jeuzyskać.Tenpodrozdziałdotyczywłaśniealgorytmówuzyskaniakoduoptymalnego,
czylionajmniejszejmożliwejredundancji,byćmożenawetzerowej.
Przedstawimydwaalgorytmy.Pierwszy(zwanyalgorytmemShannona-Fano)jestnie-
coprostszywopisie,aledodatkowouwarunkowany.Drugi(zwanyalgorytmemHuffmana)
jestniecotrudniejszy,alezawszedziała,aponadtomadużeznaczeniewpraktycznejin-
formatyce.Podstawaobuprezentowanychalgorytmówjestjednakowa-chodziokodo-
wanieprzypisującekomunikatomowysokichprawdopodobieństwachkrótkichkodów
(zracjiczęstegowystępowaniadużozyskujemy),podczasgdykomunikatomoniskich
prawdopodobieństwachprzypisujemydłuższekody(niewieletracąc,gdyżodpowiednie
komunikatypojawiająsięrzadko).
29
