Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
KODOWANIEKANAŁOWE
1,0,0,1,1
i(x)
+
+
wyjściegórne
wyjściedolne
wykluczeń
Tablica
a
1
2
010
wyjście
0
111
Rys.1.19.KoderRCPCosprawnościR=4/5
Podobniejakwprzypadkudekoderówkodówblokowych,optymalnywsensie
maksimumwiarygodnościdekoderkodusplotowegonapodstawieobserwacjiciągu
odebranegowyszukujetakiciągkodowy,któregoodległośćHamminga(wprzypadku
dekoderatwardodecyzyjnego)lubeuklidesowa(wprzypadkudekoderamiękkodecyzyj-
nego)względemciąguodebranegojestminimalna.
EfektywnąmetodąznajdowaniatakiegociągujestalgorytmViterbiegoopub-
likowanywroku1967przezAndrewJ.Viterbiego[11].Poszukujeonoptymalnego
ciągukodowego,któryodpowiada„najkrótszej”(wsensieprzyjętejmiaryodległości)
drodzenawykresiekratowymodznanegostanupoczątkowegodokażdegozmożliwych
stanówwchwilin-tej.Każdemuprzejściuodstanudostanuodpowiadaokreślonykoszt
przejścia—odległośćpomiędzyciągiemkodowymskojarzonymztymprzejściem
aciągiemodebranym.Kluczowympunktemalgorytmujeststwierdzenie,żenajkrótsza
drogadostanui-tegowchwilin-tejskładasięzprzejściaodjednegozmożliwych
stanówwchwili(n-1)-szej,zktórychosiągalnyjestwnastępnejchwilistani-ty,np.
k-tego,oraznajkrótszejdrogidostanuk-tegowchwili(n-1)-szej.Takwięcposzukiwanie
najkrótszejdrogidojściadokażdegostanuwchwilin-tejmacharakterrekurencyjny
—znajdujemyjąkorzystajączrezultatówwchwilipoprzedniej.Wprzypadkuskończonej
sekwencjikodowejalgorytmpodajedecyzjęonadanymciąguwejściowymśledzącdrogę
dojścia(cojestrównoznacznezsekwencjąstanów)dotegozestanów,dlaktóregokoszt
dojściajestminimalny.Czasami,atakzdarzasięnp.wsystemietelefoniikomórkowej
GSM,ciąginformacyjnyjestuzupełnionynajegokońcukilkomaznanymisymbolami
danych,np.zerami.Dekodermawtedydodatkowąinformacjęonumerzestanu
końcowego,cowykorzystujewwyborzeciągukodowego.Wprzypadkutransmisji
ciągłej,dlaktórejsekwencjakodowamacharakternieskończony,jestkonieczne
podejmowaniedecyzjizeskończonymopóźnieniem.Jesttomożliwedziękitemu,że
zprawdopodobieństwembliskimjedności,najkrótszedrogidojściadokażdegoze
stanówwwynikuproceduryichwyborumająwswoimskładziedrogęwspólnąażdo
chwilioDtaktówwsteczwstosunkudochwiliaktualnej.Takwięcdrogaodchwili
początkowejażdochwilin-Djesttakasama,niezależnieodtego,któryzestanów
wchwilin-tejcharakteryzujesięnajkrótsządrogądojścia.Dekodermożewięc
przekazywaćkolejneostatecznedecyzjedotyczącesymbolinadanychconajmniej
Dkrokówwstecz,czylizopóźnieniemoconajmniejDtaktów.Narysunku1.20
przedstawionoprzykładnajkrótszychdrógdojściadokażdegozestanówkoderazrys.1.18
45
