Algoritmul de decodare convoluțional Viterbi

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 14 ianuarie 2020; verificarea necesită 1 editare .

În 1967, Andrew Viterbi a dezvoltat și analizat un algoritm de decodare bazat pe principiul probabilității maxime . Algoritmul este optimizat prin utilizarea caracteristicilor structurale ale unei anumite rețele de cod. Avantajul decodării Viterbi față de decodificarea cu forță brută este că complexitatea decodorului Viterbi nu este o funcție de numărul de simboluri din secvența cuvintelor de cod .

Algoritmul implică calcularea unei măsuri de similitudine (sau distanță ) între semnalul primit la momentul t și toate căile de rețea care intră în fiecare stare la momentul t . Algoritmul Viterbi nu ia în considerare acele căi de rețea care, conform principiului maximului de probabilitate, nu pot fi optime. Dacă două căi intră în aceeași stare, se alege cea cu cea mai bună metrică ; o astfel de cale se numește supraviețuire . Selecția căilor de supraviețuire este efectuată pentru fiecare stare. Astfel, decodorul intră mai adânc în rețea, luând decizii prin eliminarea căilor mai puțin probabile. Respingerea preliminară a căilor improbabile simplifică procesul de decodificare. În 1969, Jim Omura a arătat că baza algoritmului Viterbi este estimarea probabilității maxime . Rețineți că problema de selecție a căii optime poate fi exprimată ca alegerea unui cuvânt de cod cu o metrică a probabilității maxime sau o metrică a distanței minime . $t_{I)$ $t_{i}$

Esența metodei

Cea mai bună schemă de decodare pentru codurile de corecție este decodarea cu probabilitate maximă , când decodorul determină un set de probabilități condiționate corespunzătoare tuturor vectorilor de cod posibili și decide în favoarea cuvântului de cod corespunzător maximului . Pentru un canal binar simetric fără memorie (un canal în care probabilitățile de transmisie 0 și 1, precum și probabilitățile de eroare de forma 0 -> 1 și 1 -> 0 sunt aceleași, erorile din j-th și i- Simbolurile codului sunt independente), decodorul de probabilitate maximă este redus la decodorul de distanță de emisie minimă . Acesta din urmă calculează distanța Hamming dintre secvența primită r și toți vectorii de cod posibili și ia o decizie în favoarea vectorului care este mai aproape de cel primit. Desigur, în cazul general, un astfel de decodor se dovedește a fi foarte complicat chiar și pentru dimensiuni mari de cod și practic irealizabil. Structura caracteristică a codurilor convoluționale (repetabilitate a structurii în afara ferestrei de lungime ) face posibilă crearea unui decodor de probabilitate maximă care este destul de acceptabil din punct de vedere al complexității. $P(r/U_{i})$ $U_{i}$ $P(r/U_{i})$ $U_{i}$ $n$ $k$ $n$

Principiul de funcționare al decodorului

Intrarea decodorului primește un segment al secvenței cu o lungime care depășește lungimea codului blocului . Să -i spunem fereastra de decodare. Să comparăm toate cuvintele de cod ale codului dat (în cadrul unui segment de lungime ) cu cuvântul primit și să selectăm cuvântul de cod cel mai apropiat de cel primit. Primul cadru de informații al cuvântului de cod selectat este primit ca o estimare a cadrului de informații al cuvântului decodat. După aceea, simbolurile noi sunt introduse în decodor , iar cele mai vechi simboluri introduse mai devreme sunt aruncate, iar procesul se repetă pentru a determina următorul cadru de informații. Astfel, decodorul Viterbi procesează cadru cu cadru secvenţial, deplasându-se de-a lungul unei reţele similare cu cea utilizată de encoder. La un moment dat, decodorul nu știe în ce nod se află codificatorul și nu încearcă să-l decodeze. În schimb, decodorul determină calea cea mai probabilă către fiecare nod din secvența primită și determină distanța dintre fiecare astfel de cale și secvența primită. Această distanță se numește măsura divergenței căii. Ca o estimare a secvenței primite, este selectat segmentul cu cea mai mică măsură a divergenței. Calea cu cea mai mică măsură de divergență se numește calea de supraviețuire. $r$ $b$ $n$ $b$ $b$ $n_{0}$ $n_{0}$

Exemplu

Luați în considerare funcționarea decodorului Viterbi folosind un exemplu simplu. Credem că codarea se realizează folosind un cod convoluțional (7,5) . Folosind diagrama trellis a codificatorului, să încercăm, luând un segment , să urmărim calea cea mai probabilă a codificatorului. În acest caz, pentru fiecare secțiune a diagramei trellis, vom nota măsura divergenței căii către fiecare dintre nodurile sale. Să presupunem că secvența de cod U = (00000000…) este transmisă, iar secvența primită are forma r = (10001000…), adică erori apărute în primul și al treilea cadru al cuvântului de cod. După cum am văzut deja, procedura de decodificare și rezultatul nu depind de cuvântul cod transmis și sunt determinate doar de eroarea conținută în secvența primită. Prin urmare, este cel mai ușor să presupunem că secvența zero este transmisă, adică U = (00000000 ...). După ce a primit prima pereche de simboluri (10), decodorul determină măsura divergenței pentru prima secțiune a rețelei, după ce a primit următoarea pereche de simboluri (00), pentru a doua secțiune etc. În același timp, de la căile incluse în fiecare nod, părăsim calea cu divergență mai mică, deoarece calea cu o divergență curentă mai mare nu mai poate deveni mai scurtă în viitor. Rețineți că, pentru exemplul luat în considerare, începând de la al patrulea nivel, metrica (sau măsura divergenței) căii zero este mai mică decât orice altă metrică. Deoarece nu au mai existat erori în canal, este clar că în final această cale va fi aleasă ca răspuns. Acest exemplu arată, de asemenea, că căile supraviețuitoare pot diferi unele de altele pentru o perioadă destul de lungă. Cu toate acestea, la al șaselea sau al șaptelea nivel, primele șapte margini ale tuturor căilor supraviețuitoare vor coincide unele cu altele. În acest moment, conform algoritmului Viterbi, se ia o decizie cu privire la simbolurile transmise, deoarece toate căile supraviețuitoare ies din același vârf, adică corespund unui simbol informațional. $r$

Adâncimea la care se îmbină căile supraviețuitoare nu poate fi calculată în avans; este o variabilă aleatoare în funcție de multiplicitatea și probabilitatea apariției erorilor în canal. Prin urmare, în practică, de obicei nu se așteaptă îmbinarea căilor, ci stabilește o adâncime fixă de decodare.

La pasul i), gradul de diferență dintre metricile căilor corecte și incorecte este suficient de mare ( , ), adică, în acest caz, ar fi posibil să se limiteze adâncimea de decodificare la . Dar, uneori, calea care este mai lungă către o anumită secțiune se poate dovedi a fi cea mai scurtă în cele din urmă, așa că nu ar trebui să vă lăsați dus în mod special de reducerea dimensiunii ferestrei de decodare b pentru a simplifica munca decodorului. În practică, adâncimea de decodare este de obicei aleasă în intervalul , unde este numărul de erori corectate de un anumit cod. În ciuda prezenței a două erori în fragmentul primit, decodificarea acestuia a avut loc fără eroare, iar secvența zero transmisă va fi acceptată ca răspuns. $d_{corect}=2$ $d_{eroare}=4$ $b<=6$ $n<b<n+l$ $l$

Vezi și

algoritmul Viterbi

Literatură

„Eroare Bounds for Convolutional Codes and an Asymptotic Optimum Decoding Algorithm”, IEEE Transactions on Information Theory, volumul IT-13, pp. 260-269, aprilie 1967.
Viterbi A. D., Omura J. K. Principles of digital communication and coding / Per. din engleza. ed. K. Sh. Zigangirova. - M .: Radio și comunicare, 1982. - 536 p.
Zolotarev V. V., Ovechkin G. V. Codare anti-zgomot. Metode și algoritmi: Manual / Under. ed. Membru corespondent RAS Yu. B. Zubarev. - M .: Hotline-Telecom, 2004.
Kartashevsky V. G., Mishin D. V. Recepția semnalelor codificate în canale cu memorie - Radio și comunicare, 2004.
Morelos-Zaragoza R. Arta codificării corectoare de erori. Metode, algoritmi, aplicație / per. din engleza. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 p. — (Lumea comunicării). - 2000 de exemplare. — ISBN 5-94836-035-0 .
Bernard Sklar. Comunicare digitală. Fundamente teoretice și aplicare practică = Digital Communications: Fundamentals and Applications. - Ed. a II-a. - M . : „Williams” , 2007. - S. 1104. - ISBN 0-13-084788-7 .