Viterbin konvoluutiodekoodausalgoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 14. tammikuuta 2020 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Vuonna 1967 Andrew Viterbi kehitti ja analysoi dekoodausalgoritmin, joka perustuu suurimman todennäköisyyden periaatteeseen . Algoritmi optimoidaan käyttämällä tietyn koodihilan rakenteellisia ominaisuuksia. Viterbi-dekoodauksen etuna brute force -dekoodaukseen verrattuna on, että Viterbi-dekooderin monimutkaisuus ei ole funktio koodisanasekvenssin symbolien lukumäärästä .

Algoritmi sisältää samankaltaisuuden (tai etäisyyden ) mittauksen laskemisen hetkellä t vastaanotetun signaalin ja kaikkien hilareittien välillä, jotka saapuvat kuhunkin tilaan hetkellä t . Viterbi-algoritmi ei ota huomioon niitä hilapolkuja, jotka maksimaalisen todennäköisyyden periaatteen mukaan eivät voi olla optimaalisia. Jos kaksi polkua siirtyy samaan tilaan, valitaan se, jolla on paras metriikka ; tällaista polkua kutsutaan selviytymiseksi . Selviytyvien polkujen valinta suoritetaan jokaiselle osavaltiolle. Siten dekooderi menee syvemmälle hilaan ja tekee päätöksiä eliminoimalla vähemmän todennäköisiä polkuja. Epätodennäköisten polkujen alustava hylkääminen yksinkertaistaa dekoodausprosessia. Vuonna 1969 Jim Omura osoitti, että Viterbi-algoritmin perusta on maksimitodennäköisyysarvio . Huomaa, että optimaalisen polun valintaongelma voidaan ilmaista koodisanan valintana, jolla on maksimitodennäköisyysmetriikka tai vähimmäisetäisyysmetriikka . ${\displaystyle t_{I))$ $t_{i}$

Metodin olemus

Paras dekoodausmenetelmä korjauskoodeille on suurimman todennäköisyyden dekoodaus , kun dekooderi määrittää joukon ehdollisia todennäköisyyksiä, jotka vastaavat kaikkia mahdollisia koodivektoreita , ja päättää maksimiarvoa vastaavan koodisanan hyväksi . Muistittomalla binäärisymmetrisellä kanavalla (kanava, jossa lähetystodennäköisyydet 0 ja 1 sekä virhetodennäköisyydet muodossa 0 -> 1 ja 1 -> 0 ovat samat, j:nnen ja i- koodin symbolit ovat riippumattomia), maksimitodennäköisyyden dekooderi pienennetään minimihamming- etäisyyden dekooderiin . Jälkimmäinen laskee Hamming-etäisyyden vastaanotetun sekvenssin r ja kaikkien mahdollisten koodivektoreiden välillä ja tekee päätöksen sen vektorin hyväksi, joka on lähempänä vastaanotettua. Luonnollisesti yleisessä tapauksessa tällainen dekooderi osoittautuu erittäin monimutkaiseksi jopa suurille koodikokoille ja käytännössä mahdottomaksi. Konvoluutiokoodien ominaisrakenne (rakenteen toistettavuus pituusikkunan ulkopuolella ) mahdollistaa maksimitodennäköisyyden dekooderin luomisen, joka on varsin hyväksyttävä monimutkaisuuden suhteen. $P(r/U_{i})$ $U_{i}$ $P(r/U_{i})$ $U_{i}$ $n$ $k$ $n$

Dekooderin toimintaperiaate

Dekooderin tulo vastaanottaa sekvenssin segmentin, jonka pituus ylittää lohkon koodipituuden . Kutsutaan sitä dekoodausikkunaksi. Verrataan kaikkia annetun koodin koodisanoja (pituisen segmentin sisällä ) vastaanotettuun sanaan ja valitaan vastaanotettua lähinnä oleva koodisana. Valitun koodisanan ensimmäinen informaatiokehys vastaanotetaan arviona dekoodatun sanan informaatiokehyksestä. Sen jälkeen uudet symbolit syötetään dekooderiin ja vanhimmat aiemmin syötetyt symbolit hylätään ja prosessi toistetaan seuraavan informaatiokehyksen määrittämiseksi. Siten Viterbi-dekooderi prosessoi kehys kehykseltä peräkkäin liikkuen pitkin hilaa, joka on samanlainen kuin kooderi käyttää. Dekooderi ei tiedä milloin tahansa, missä solmussa kooderi on, eikä yritä purkaa sitä. Sen sijaan dekooderi määrittää todennäköisimmän polun jokaiseen solmuun vastaanotetusta sekvenssistä ja määrittää kunkin tällaisen polun ja vastaanotetun sekvenssin välisen etäisyyden. Tätä etäisyyttä kutsutaan polun hajaantumisen mittaksi. Vastaanotetun sekvenssin estimaatiksi valitaan segmentti, jolla on pienin eron mitta. Polkua, jolla on pienin ero, kutsutaan selviytymispoluksi. $r$ $b$ $n$ $b$ $b$ $n_{0}$ $n_{0}$

Esimerkki

Harkitse Viterbi-dekooderin toimintaa yksinkertaisella esimerkillä. Uskomme, että koodaus suoritetaan käyttämällä konvoluutiokoodia (7,5) . Yritetään kooderin ristikkokaavion avulla jäljittää kooderin todennäköisin polku ottamalla jokin segmentti. Tässä tapauksessa jokaiselle ristikkokaavion osalle huomioidaan polun eron mitta jokaiseen sen solmuun. Oletetaan, että koodisekvenssi U = (00000000…) lähetetään ja vastaanotetun sekvenssin muoto on r = (10001000…), eli koodisanan ensimmäisessä ja kolmannessa kehyksessä tapahtui virheitä. Kuten olemme jo nähneet, dekoodausmenettely ja tulos eivät riipu lähetetystä koodisanasta ja ne määräytyvät vain vastaanotetun sekvenssin sisältämän virheen perusteella. Siksi on helpointa olettaa, että nollasekvenssi lähetetään, eli U = (00000000 ...). Vastaanotettuaan ensimmäisen symboliparin (10), dekooderi määrittää divergenssin arvon hilan ensimmäiselle osalle, vastaanotettuaan seuraavan symboliparin (00), toiselle jaksolle jne. Samanaikaisesti alkaen kuhunkin solmuun sisältyvät polut, jätämme polun pienemmällä erolla, koska polku, jolla on suurempi virtadivergentti, ei voi enää lyhentyä tulevaisuudessa. Huomaa, että tarkasteltavassa esimerkissä, neljännestä tasosta alkaen, nollapolun metriikka (tai eron mitta) on pienempi kuin mikään muu mittari. Koska kanavassa ei enää ollut virheitä, on selvää, että tämä polku lopulta valitaan vastaukseksi. Tämä esimerkki osoittaa myös, että säilyneet polut voivat erota toisistaan melko pitkään. Kuitenkin kuudennella tai seitsemännellä tasolla kaikkien säilyneiden polkujen seitsemän ensimmäistä reunaa osuvat toisiinsa. Tällä hetkellä Viterbi-algoritmin mukaan tehdään päätös lähetetyistä symboleista, koska kaikki säilyneet polut tulevat samasta kärjestä, eli ne vastaavat yhtä informaatiosymbolia. $r$

Syvyyttä, jossa säilyneet polut sulautuvat, ei voida laskea etukäteen; se on satunnaismuuttuja, joka riippuu kanavassa esiintyvien virheiden moninkertaisuudesta ja todennäköisyydestä. Siksi käytännössä ei yleensä odoteta polun yhdistämistä, vaan asetetaan kiinteä dekoodaussyvyys.

Vaiheessa i) oikeiden ja väärien polkujen metriikan eron aste on riittävän suuri ( , ), eli tässä tapauksessa dekoodaussyvyys olisi mahdollista rajoittaa arvoon . Mutta joskus tie, joka on pidempi tiettyyn osioon, voi lopulta osoittautua lyhimmäksi, joten sinun ei pitäisi olla erityisen hukassa pienentämällä dekoodausikkunan kokoa b dekooderin työn yksinkertaistamiseksi. Käytännössä dekoodaussyvyys valitaan yleensä alueella , jossa on annetulla koodilla korjattujen virheiden määrä. Huolimatta siitä, että vastaanotetussa fragmentissa oli kaksi virhettä, sen dekoodaus tapahtui ilman virhettä, ja lähetetty nollasekvenssi hyväksytään vastauksena. $d_{correct}=2$ $d_{error}=4$ $b<=6$ ${\näyttötyyli n<b<n+l}$ $l$

Katso myös

Viterbi-algoritmi

Kirjallisuus

"Error Bounds for Convolutional Codes and an Asymptoottically Optimum Decoding Algorithm", IEEE Transactions on Information Theory, Volume IT-13, s. 260-269, huhtikuu 1967.
Viterbi A. D., Omura J. K. Digitaalisen viestinnän ja koodauksen periaatteet / Per. englannista. toim. K. Sh. Zigangirova. - M .: Radio ja viestintä, 1982. - 536 s.
Zolotarev V. V., Ovechkin G. V. Anti-kohinakoodaus. Menetelmät ja algoritmit: Käsikirja / Under. toim. Vastaava jäsen RAS Yu. B. Zubarev. - M .: Hotline-Telecom, 2004.
Kartashevsky V. G., Mishin D. V. Koodattujen signaalien vastaanotto kanavilla, joissa on muisti - Radio ja viestintä, 2004.
Morelos-Zaragoza R. Virheenkorjauskoodauksen taito. Menetelmät, algoritmit, sovellus / per. englannista. V. B. Afanasjev . - M . : Technosfera, 2006. - 320 s. — (Viestintämaailma). - 2000 kappaletta. — ISBN 5-94836-035-0 .
Bernard Sklar. Digitaalinen viestintä. Teoreettiset perusteet ja käytännön sovellus = Digital Communications: Fundamentals and Applications. - 2. painos - M . : "Williams" , 2007. - S. 1104. - ISBN 0-13-084788-7 .