Viterbi Convolutional Decoding Algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 14. januar 2020; verifikation kræver 1 redigering .

I 1967 udviklede og analyserede Andrew Viterbi en afkodningsalgoritme baseret på princippet om maksimum sandsynlighed . Algoritmen er optimeret ved at bruge de strukturelle funktioner i et bestemt kodegitter. Fordelen ved Viterbi-afkodning frem for brute-force-afkodning er, at kompleksiteten af ​​Viterbi-dekoderen ikke er en funktion af antallet af symboler i kodeordssekvensen .

Algoritmen indebærer beregning af et mål for lighed (eller afstand ) mellem signalet modtaget på tidspunktet t og alle gitterveje, der går ind i hver tilstand på tidspunktet t . Viterbi-algoritmen tager ikke hensyn til de gitterbaner, som ifølge princippet om maksimum sandsynlighed ikke kan være optimale. Hvis to stier går ind i samme tilstand, vælges den med den bedste metrik ; sådan en vej kaldes at overleve . Udvælgelsen af ​​overlevende stier udføres for hver stat. Således går dekoderen dybere ind i gitteret og træffer beslutninger ved at eliminere mindre sandsynlige stier. Foreløbig afvisning af usandsynlige stier forenkler afkodningsprocessen. I 1969 viste Jim Omura , at grundlaget for Viterbi-algoritmen er det maksimale sandsynlighedsestimat . Bemærk, at det optimale vejvalgsproblem kan udtrykkes som valget af et kodeord med en maksimumsandsynlighedsmetrik eller en minimumsafstandsmetrik .

Essensen af ​​metode

Det bedste afkodningsskema for korrektionskoder er maksimal sandsynlighedsafkodning , når dekoderen bestemmer et sæt af betingede sandsynligheder svarende til alle mulige kodevektorer , og beslutter sig for kodeordet svarende til maksimum . For en hukommelsesløs binær symmetrisk kanal (en kanal, hvor transmissionssandsynlighederne 0 og 1, såvel som fejlsandsynlighederne på formen 0 -> 1 og 1 -> 0 er de samme, er fejlene i j-te og i- kodens symboler er uafhængige), er den maksimale sandsynlighed-dekoder reduceret til den minimale hamming-afstandsdekoder . Sidstnævnte beregner Hamming-afstanden mellem den modtagne sekvens r og alle mulige kodevektorer og træffer en beslutning til fordel for den vektor, der er tættere på den modtagne. Naturligvis, i det generelle tilfælde, viser en sådan dekoder sig at være meget kompliceret selv for store kodestørrelser og praktisk talt urealiserbar. Den karakteristiske struktur af foldningskoder (strukturrepeterbarhed uden for længdevinduet ) gør det muligt at skabe en maksimal sandsynlighedsdekoder, der er ganske acceptabel med hensyn til kompleksitet.

Funktionsprincippet for dekoderen

Dekoderinputtet modtager et segment af sekvensen med en længde, der overstiger blokkens kodelængde . Lad os kalde det afkodningsvinduet. Lad os sammenligne alle kodeord i den givne kode (inden for et længdesegment ) med det modtagne ord og vælge det kodeord, der er tættest på det modtagne. Den første informationsramme for det valgte kodeord modtages som et estimat af informationsrammen for det afkodede ord. Derefter indtastes nye symboler i dekoderen , og de ældste symboler, der er indtastet tidligere, kasseres, og processen gentages for at bestemme den næste informationsramme. Viterbi-dekoderen behandler således ramme for ramme sekventielt og bevæger sig langs et gitter svarende til det, der anvendes af koderen. På ethvert givet tidspunkt ved afkoderen ikke, hvilken node indkoderen er i og forsøger ikke at afkode den. I stedet bestemmer dekoderen den mest sandsynlige vej til hver knude fra den modtagne sekvens og bestemmer afstanden mellem hver sådan vej og den modtagne sekvens. Denne afstand kaldes målet for divergensen af ​​stien. Som et estimat af den modtagne sekvens vælges segmentet med det mindste mål for divergens. Stien med det mindste mål for divergens kaldes den overlevende vej.

Eksempel

Overvej betjeningen af ​​Viterbi-dekoderen ved hjælp af et simpelt eksempel. Vi mener, at kodning udføres ved hjælp af en foldningskode (7,5) . Ved at bruge espalierdiagrammet for indkoderen, lad os prøve at tage et segment , for at spore indkoderens mest sandsynlige vej. I dette tilfælde vil vi for hver sektion af trellisdiagrammet bemærke målet for divergensen af ​​stien til hver af dens noder. Antag, at kodesekvensen U = (00000000…) transmitteres, og den modtagne sekvens har formen r = (10001000…), det vil sige, at der opstod fejl i den første og tredje frame af kodeordet. Som vi allerede har set, afhænger afkodningsproceduren og resultatet ikke af det transmitterede kodeord og bestemmes kun af fejlen indeholdt i den modtagne sekvens. Derfor er det nemmest at antage, at nulsekvensen transmitteres, det vil sige U = (00000000 ...). Efter at have modtaget det første symbolpar (10), bestemmer dekoderen divergensmålet for den første sektion af gitteret, efter at have modtaget det næste symbolpar (00), for den anden sektion osv. Samtidig fra kl. de stier, der indgår i hver knude, forlader vi stien med mindre divergens, da stien med en større strømdivergens ikke længere kan blive kortere i fremtiden. Bemærk, at for det undersøgte eksempel, startende fra det fjerde niveau, er metrikken (eller mål for divergens) for nulstien mindre end nogen anden metrik. Da der ikke var flere fejl i kanalen, er det klart, at denne vej i sidste ende vil blive valgt som svaret. Dette eksempel viser også, at de overlevende stier kan adskille sig fra hinanden i ret lang tid. Men på sjette eller syvende niveau vil de første syv kanter af alle overlevende stier falde sammen med hinanden. I dette øjeblik tages der ifølge Viterbi-algoritmen en beslutning om de transmitterede symboler, da alle overlevende stier kommer ud af samme toppunkt, det vil sige, at de svarer til et informationssymbol.

Den dybde, hvor de overlevende stier smelter sammen, kan ikke beregnes på forhånd; det er en tilfældig variabel afhængig af multipliciteten og sandsynligheden for, at der opstår fejl i kanalen. Derfor venter man i praksis normalt ikke på stisammenlægning, men sætter en fast afkodningsdybde.

I trin i) er graden af ​​forskel mellem metrikken for de korrekte og forkerte stier tilstrækkelig stor ( , ), det vil sige, i dette tilfælde ville det være muligt at begrænse afkodningsdybden til . Men nogle gange kan vejen, der er længere til en given sektion, vise sig at være den korteste i sidste ende, så du bør ikke lade dig rive med af at reducere størrelsen af ​​afkodningsvinduet b for at forenkle arbejdet med dekoderen. I praksis vælges afkodningsdybden normalt i området , hvor  er antallet af fejl rettet af en given kode. På trods af tilstedeværelsen af ​​to fejl i det modtagne fragment, skete dets afkodning uden en fejl, og den transmitterede nulsekvens vil blive accepteret som et svar.

Se også

Litteratur