Viterbi Convolutional Decoding Algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 14 januari 2020; verifiering kräver 1 redigering .

1967 utvecklade och analyserade Andrew Viterbi en avkodningsalgoritm baserad på principen om maximal sannolikhet . Algoritmen optimeras genom att använda de strukturella egenskaperna hos ett visst kodgitter. Fördelen med Viterbi-avkodning framför brute-force-avkodning är att komplexiteten hos Viterbi-avkodaren inte är en funktion av antalet symboler i kodordssekvensen .

Algoritmen innebär att man beräknar ett mått på likhet (eller avstånd ) mellan signalen som tas emot vid tidpunkten t och alla gittervägar som går in i varje tillstånd vid tidpunkten t . Viterbi-algoritmen beaktar inte de gittervägar som enligt principen om maximal sannolikhet inte kan vara optimala. Om två vägar går in i samma tillstånd, väljs den som har bäst måttenhet ; en sådan väg kallas att överleva . Valet av överlevande vägar utförs för varje stat. Således går avkodaren djupare in i gittret och fattar beslut genom att eliminera mindre troliga vägar. Preliminär avvisning av osannolika vägar förenklar avkodningsprocessen. 1969 visade Jim Omura att grunden för Viterbi-algoritmen är den maximala sannolikhetsuppskattningen . Observera att det optimala vägvalsproblemet kan uttryckas som valet av ett kodord med ett mått för maximal sannolikhet eller ett minimiavståndsmått . ${\displaystyle t_{I))$ $t_{i}$

Essensen av metoden

Det bästa avkodningsschemat för korrigeringskoder är maximal sannolikhetsavkodning , när avkodaren bestämmer en uppsättning villkorade sannolikheter som motsvarar alla möjliga kodvektorer , och beslutar till förmån för kodordet som motsvarar maximum . För en minneslös binär symmetrisk kanal (en kanal där överföringssannolikheterna 0 och 1, såväl som felsannolikheterna för formen 0 -> 1 och 1 -> 0 är desamma, är felen i j-th och i- kodens symboler är oberoende), reduceras maximal sannolikhetsavkodaren till avkodaren för minsta hammingsavstånd . Den senare beräknar Hamming-avståndet mellan den mottagna sekvensen r och alla möjliga kodvektorer och fattar ett beslut till förmån för den vektor som är närmare den mottagna. Naturligtvis, i det allmänna fallet, visar sig en sådan avkodare vara mycket komplicerad även för stora kodstorlekar och praktiskt taget orealiserbar. Den karakteristiska strukturen av faltningskoder (strukturupprepbarhet utanför längdfönstret ) gör det möjligt att skapa en maximal sannolikhetsavkodare som är helt acceptabel när det gäller komplexitet. $P(r/U_{i})$ $U_{i}$ $P(r/U_{i})$ $U_{i}$ $n$ $k$ $n$

Funktionsprincipen för avkodaren

Avkodaringången tar emot ett segment av sekvensen med en längd som överstiger blockets kodlängd . Låt oss kalla det för avkodningsfönstret. Låt oss jämföra alla kodord för den givna koden (inom ett längdsegment ) med det mottagna ordet och välj det kodord som är närmast det mottagna. Den första informationsramen för det valda kodordet tas emot som en uppskattning av informationsramen för det avkodade ordet. Därefter matas nya symboler in i avkodaren , och de äldsta symbolerna som matats in tidigare kasseras, och processen upprepas för att bestämma nästa informationsram. Sålunda bearbetar Viterbi-avkodaren ram för ram sekventiellt och rör sig längs ett gitter liknande det som används av kodaren. Vid varje given tidpunkt vet inte avkodaren vilken nod kodaren är i och försöker inte avkoda den. Istället bestämmer avkodaren den mest sannolika vägen till varje nod från den mottagna sekvensen och bestämmer avståndet mellan varje sådan väg och den mottagna sekvensen. Detta avstånd kallas måttet på divergensen för banan. Som en uppskattning av den mottagna sekvensen väljs segmentet med det minsta måttet på divergens. Vägen med det minsta måttet av divergens kallas den överlevande vägen. $r$ $b$ $n$ $b$ $b$ $n_{0}$ $n_{0}$

Exempel

Betrakta funktionen av Viterbi-dekodern med ett enkelt exempel. Vi tror att kodning utförs med en faltningskod (7,5) . Med hjälp av spaljédiagrammet för kodaren, låt oss försöka, med ett segment , för att spåra den mest sannolika vägen för kodaren. I det här fallet, för varje sektion av trellisdiagrammet, kommer vi att notera måttet på divergensen för vägen till var och en av dess noder. Antag att kodsekvensen U = (00000000...) sänds och den mottagna sekvensen har formen r = (10001000...), det vill säga fel inträffade i kodordets första och tredje ram. Som vi redan har sett beror avkodningsproceduren och resultatet inte på det sända kodordet och bestäms endast av felet i den mottagna sekvensen. Därför är det lättast att anta att nollsekvensen sänds, det vill säga U = (00000000 ...). Efter att ha mottagit det första symbolparet (10), bestämmer avkodaren måttet på divergens för den första sektionen av gittret, efter att ha tagit emot nästa symbolpar (00), för den andra sektionen, etc. Samtidigt, från kl. vägarna som ingår i varje nod lämnar vi vägen med mindre divergens, eftersom vägen med en större strömdivergens inte längre kan bli kortare i framtiden. Observera att för exemplet i fråga, från och med den fjärde nivån, är måttet (eller måttet på divergens) för nollbanan mindre än något annat mått. Eftersom det inte fanns fler fel i kanalen är det klart att i slutändan kommer denna väg att väljas som svar. Detta exempel visar också att de överlevande vägarna kan skilja sig från varandra under ganska lång tid. Men på den sjätte eller sjunde nivån kommer de första sju kanterna på alla överlevande vägar att sammanfalla med varandra. I detta ögonblick, enligt Viterbi-algoritmen, fattas ett beslut om de överförda symbolerna, eftersom alla överlevande vägar kommer ut från samma vertex, det vill säga de motsvarar en informationssymbol. $r$

Djupet vid vilket de överlevande vägarna smälter samman kan inte beräknas på förhand; det är en slumpmässig variabel beroende på mångfalden och sannolikheten för att fel uppstår i kanalen. Därför väntar man i praktiken vanligtvis inte på vägsammanslagning, utan ställer in ett fast avkodningsdjup.

I steg i) är graden av skillnad mellan metrikerna för de korrekta och felaktiga vägarna tillräckligt stor ( , ), det vill säga i detta fall skulle det vara möjligt att begränsa avkodningsdjupet till . Men ibland kan vägen som är längre till en viss sektion visa sig vara den kortaste i slutändan, så du bör inte ryckas särskilt med genom att minska storleken på avkodningsfönstret b för att förenkla arbetet med avkodaren. I praktiken väljs avkodningsdjupet vanligtvis i intervallet , där är antalet fel korrigerade av en given kod. Trots närvaron av två fel i det mottagna fragmentet skedde dess avkodning utan ett fel, och den överförda nollsekvensen kommer att accepteras som ett svar. $d_{correct}=2$ $d_{error}=4$ $b<=6$ $n<b<n+l$ $l$

Se även

Viterbi algoritm

Litteratur

"Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm", IEEE Transactions on Information Theory, Volym IT-13, s. 260-269, april 1967.
Viterbi A. D., Omura J. K. Principer för digital kommunikation och kodning / Per. från engelska. ed. K. Sh. Zigangirova. - M .: Radio och kommunikation, 1982. - 536 sid.
Zolotarev V. V., Ovechkin G. V. Anti-bruskodning. Metoder och algoritmer: Handbok / Under. ed. Motsvarande ledamot RAS Yu. B. Zubarev. - M .: Hotline-Telecom, 2004.
Kartashevsky V. G., Mishin D. V. Mottagning av kodade signaler i kanaler med minne - Radio och kommunikation, 2004.
Morelos-Zaragoza R. Konsten att felkorrigera kodning. Metoder, algoritmer, tillämpning / per. från engelska. V. B. Afanasiev . - M . : Technosfera, 2006. - 320 sid. — (Kommunikationens värld). - 2000 exemplar. — ISBN 5-94836-035-0 .
Bernard Sklar. Digital kommunikation. Teoretiska grunder och praktisk tillämpning = Digital kommunikation: Grunder och tillämpningar. - 2:a uppl. - M . : "Williams" , 2007. - S. 1104. - ISBN 0-13-084788-7 .