Sekventiell avkodning

Sekventiell avkodning, erkänd av John Wozencraft , är en begränsad minnesteknik för avkodning av trädkoder. Sekventiell avkodning används huvudsakligen som en ungefärlig avkodningsalgoritm för faltningskoder med långa begränsningslängder . Detta tillvägagångssätt kanske inte är lika exakt som Viterbi-algoritmen men kan spara en betydande mängd datorminne. Den användes för att avkoda en faltningskod i Pioneer 9- uppdraget 1968.

Sekventiell avkodning utforskar trädkoden på ett sådant sätt att försöka minimera beräkningskostnaden och minneskraven för att lagra trädet.

Det finns en rad sekventiella avkodningsmetoder baserade på valet av mått och algoritm. Mätvärden inkluderar:

Fano-mått
Zigangirov metrisk
Gallager-mått

Algoritmer inkluderar:

Stackalgoritm
Fano algoritm
Creeper-algoritm

Fano-mått

Med tanke på ett delvis utforskat träd (representerat av en uppsättning noder som är gräns för utforskning), skulle vi vilja veta den bästa noden att utforska vidare från. Fano-måttet (uppkallat efter Robert Fano ) gör att man kan beräkna från vilken nod som är bäst att utforska vidare. Detta mått är optimalt med tanke på inga andra begränsningar (t.ex. minne).

För en binär symmetrisk kanal (med felsannolikhet $p$ ) kan Fano-måttet härledas via Bayes sats . Vi är intresserade av att följa den mest sannolika vägen $P_{i}$ givet ett utforskat tillstånd för trädet $X$ och en mottagen sekvens ${\mathbf {r} }$ . Med hjälp av sannolikhetsspråket och Bayes sats vill vi välja det maximala över $i$ av :

Pr(P_{i}|X,{\mathbf {r} })\propto

Vi introducerar nu följande notation:

$N$ för att representera den maximala längden för överföring i grenar
$b$ för att representera antalet bitar på en gren av koden (nämnaren för kodhastigheten , R { $displaystyle R} )$ .
$d_{i}$ för att representera antalet bitfel på sökvägen $P_{i}$ ( hammeringavståndet mellan grenetiketterna och den mottagna sekvensen)
$n_{i}$ för att vara längden av $P_{i}$ i grenar.

Vi uttrycker sannolikheten Pr $\displaystyle \Pr({\mathbf {r} }|P_{i},X)$ $p^{d_{i}}(1-p)^{n_{i}b-d_{i}}2^{-(N-n_{i}) b}$ som (genom att använda den binära symmetriska kanalsannolikheten för de första $n_{i}b$ bitarna följt av en enhetlig prior över de återstående bitarna).

Vi uttrycker föregående $\Pr(P_{i}|X)$ i termer av antalet grenval man har gjort, $n_{i}$ , och antal grenar från varje nod, $2^{Rb}$ .

Därför:

{\begin{aligned}\Pr(P_{i}|X,{\mathbf {r} })&\propto p^{d_{i }}(1-p)^{n_{i}b-d_{i}}2^{-(N-n_{i})b}2^{-n_{i}Rb}\\&\propto p ^{d_{i}}(1-p)^{n_{i}b-d_{i}}2^{n_{i}b}2^{-n_{i}Rb}\end{aligned}}

Vi kan på motsvarande sätt maximera loggen för denna sannolikhet, dvs

{\begin{aligned}&d_{i}\log _{2}p+(n_{i}b-d_{i}) \log _{2}(1-p)+n_{i}b-n_{i}Rb\\=&d_{i}(\log _{2}p+1-R)+(n_{i}b -d_{i})(\log _{2}(1-p)+1-R)\end{aligned}}

Detta sista uttryck är Fano-måttet. Det viktiga att se är att vi har två termer här: en baserad på antalet fel bitar och en baserad på antalet rätt bitar. Vi kan därför uppdatera Fano-måttet helt enkelt genom att lägga till $\log _{2}p+1-R$ för varje icke-matchande bit och $\log _{2}(1-p)+1-R$ för varje matchande bit.

Beräkningsmässig cutoff rate

För sekventiell avkodning till ett bra val av avkodningsalgoritm, vill antalet utforskade tillstånd förbli litet (annars kan en algoritm som medvetet utforskar alla tillstånd, t.ex. Viterbi-algoritmen, vara mer lämplig). För en speciell brusnivå finns det en maximal kodningshastighet $R_{0}$ som kallas den beräkningsmässiga cutoff-hastigheten där det finns en ändlig backtracking-gräns. För den binära symmetriska kanalen:

R_{0}=1-\log _{2}(1+2{\sqrt {p(1-p)}} )

Algoritmer

Stackalgoritm

Den enklaste algoritmen att beskriva är "stackalgoritmen" där de bästa $N$ sökvägarna som hittats hittills lagras. Sekventiell avkodning kan introducera ett ytterligare fel ovanför Viterbi-avkodning när den korrekta sökvägen har $N$ eller fler vägar med hög poäng över sig; vid denna tidpunkt kommer den bästa vägen att falla av stapeln och inte längre övervägas.

Fano algoritm

Den berömda Fano-algoritmen (uppkallad efter Robert Fano ) har ett mycket lågt minnesbehov och lämpar sig därför för hårdvaruimplementationer. Denna algoritm utforskar bakåt och framåt från en enda punkt på trädet.

Fano-algoritmen är en sekventiell avkodningsalgoritm som inte kräver en stack.
Fano-algoritmen kan bara fungera över ett kodträd eftersom den inte kan undersöka vägsammanslagning.
Vid varje avkodningssteg behåller Fano-algoritmen informationen om tre vägar: den aktuella vägen, dess närmaste föregångare och en av dess efterföljande vägar.
Baserat på denna information kan Fano-algoritmen flytta från den aktuella vägen till antingen dess omedelbara föregångare eller den valda efterföljaren; därför krävs ingen stack för att köa alla undersökta vägar.
Rörelsen av Fano-algoritmen styrs av en dynamisk tröskel T som är en heltalsmultipel av en fast stegstorlek ¢.
Endast den väg vars banmått inte är mindre än T kan besökas nästa gång. Enligt algoritmen fortsätter processen för kodordssökning att gå framåt längs en kodväg, så länge Fano-måttet längs kodvägen förblir icke-minskande.
När väl alla efterföljande vägmått är mindre än T , flyttas algoritmen bakåt till föregångarens väg om föregångarens vägmått slår T ; därefter kommer tröskelundersökningen att utföras på en annan efterföljande väg till denna återbesökta föregångare.
Om föregångarens vägmått också är mindre än T sänks tröskeln T ett steg så att algoritmen inte fångas på den aktuella vägen.
För Fano-algoritmen, om en sökväg återbesöks, är den för närvarande undersökta dynamiska tröskeln alltid lägre än den momentana dynamiska tröskeln vid föregående besök, vilket garanterar att looping i algoritmen inte inträffar och att algoritmen i slutändan kan nå en terminalnod på kodträdet och stanna.

John Wozencraft och B. Reiffen, Sequential decoding , ISBN 0-262-23006-2
Rolf Johannesson och Kamil Sh. Zigangirov, Fundamentals of convolutional coding (kapitel 6), ISBN 0-470-27683-5

externa länkar

" Korrigeringsträd " - simulator av korrigeringsprocess som använder prioritetskö för att välja maximal metrisk nod (kallad vikt)