Viterbi Decoder – Wikipedia

decodiert einen Bitstrom mit dem Viterbi-Algorithmus

EIN Viterbi-Decoder verwendet den Viterbi-Algorithmus zum Decodieren eines Bitstroms, der unter Verwendung eines Faltungscodes oder eines Gittercodes codiert wurde.

Es gibt andere Algorithmen zum Decodieren eines Faltungsstroms (zum Beispiel den Fano-Algorithmus). Der Viterbi-Algorithmus ist am ressourcenintensivsten, führt jedoch die Dekodierung mit maximaler Wahrscheinlichkeit durch. Es wird am häufigsten zum Decodieren von Faltungscodes mit Beschränkungslängen k ≤ 3 verwendet, in der Praxis werden jedoch Werte bis zu k = 15 verwendet.

Die Viterbi-Dekodierung wurde von Andrew J. Viterbi entwickelt und in der Veröffentlichung veröffentlicht Viterbi, A. (April 1967). “Fehlergrenzen für Faltungscodes und ein asymptotisch optimaler Decodierungsalgorithmus”. IEEE-Transaktionen zur Informationstheorie. 13 (2): 260–269. doi:10.1109 / tit.1967.1054010.

Es gibt sowohl Hardware- (in Modems) als auch Software-Implementierungen eines Viterbi-Decoders.

Die Viterbi-Decodierung wird im iterativen Viterbi-Decodierungsalgorithmus verwendet.

Hardware-Implementierung[edit]

Ein Hardware-Viterbi-Decoder für Basiscode (nicht punktiert) besteht normalerweise aus den folgenden Hauptblöcken:

• Branch Metric Unit (BMU)
• Pfadmetrikeinheit (PMU)
• Rückverfolgungseinheit (TBU)

Branch Metric Unit (BMU)[edit]

Die Funktion einer Zweigmetrikeinheit besteht in der Berechnung ZweigmetrikenDies sind normierte Abstände zwischen jedem möglichen Symbol im Code-Alphabet und dem empfangenen Symbol.

Es gibt Viterbi-Decoder mit harter und weicher Entscheidung. Ein Viterbi-Decoder mit harter Entscheidung empfängt einen einfachen Bitstrom an seinem Eingang, und ein Hamming-Abstand wird als Metrik verwendet. Ein Viterbi-Decoder mit weicher Entscheidung empfängt einen Bitstrom, der Informationen über den enthält Verlässlichkeit von jedem empfangenen Symbol. Zum Beispiel in einer 3-Bit-Codierung dies Verlässlichkeit Informationen können wie folgt codiert werden:

Wert	Bedeutung
000	am stärksten	0
001	relativ stark	0
010	relativ schwach	0
011	am schwächsten	0
100	am schwächsten	1
101	relativ schwach	1
110	relativ stark	1
111	am stärksten	1

Natürlich ist dies nicht die einzige Möglichkeit, Zuverlässigkeitsdaten zu codieren.

Das kariert Der euklidische Abstand wird als Metrik für Soft Decision Decoder verwendet.

Pfadmetrikeinheit (PMU)[edit]

Eine Pfadmetrikeinheit fasst Zweigmetriken zusammen, für die Metriken abgerufen werden sollen

2K.– –1{ displaystyle 2 ^ {K-1}}

Pfade, wobei K die Einschränkungslänge des Codes ist, von denen einer schließlich als ausgewählt werden kann optimal. Jede Uhr macht es

2K.– –1{ displaystyle 2 ^ {K-1}}

Entscheidungen, die witzig nicht optimale Wege abwerfen. Die Ergebnisse dieser Entscheidungen werden in den Speicher einer Rückverfolgungseinheit geschrieben.

Die Kernelemente einer PMU sind ACS (Add-Compare-Select) Einheiten. Die Art und Weise, wie sie miteinander verbunden sind, wird durch das Gitterdiagramm eines bestimmten Codes definiert.

Da sind Zweigmetriken immer

≥0{ displaystyle geq 0}

Es muss eine zusätzliche Schaltung vorhanden sein (auf dem Bild nicht dargestellt), die einen Überlauf der Metrikzähler verhindert. Eine alternative Methode, die die Überwachung des Pfadmetrikwachstums überflüssig macht, besteht darin, den Pfadmetriken ein “Rollover” zu ermöglichen. Um diese Methode zu verwenden, muss sichergestellt werden, dass die Pfadmetrikakkumulatoren genügend Bits enthalten, um zu verhindern, dass die “besten” und “schlechtesten” Werte innerhalb von 2 liegen^(n-1) von einander. Die Vergleichsschaltung ist im wesentlichen unverändert.

Es ist möglich, den Rauschpegel im eingehenden Bitstrom zu überwachen, indem die Wachstumsrate der “besten” Pfadmetrik überwacht wird. Eine einfachere Möglichkeit, dies zu tun, besteht darin, einen einzelnen Ort oder “Zustand” zu überwachen und zu beobachten, wie er “aufwärts” durch beispielsweise vier diskrete Ebenen innerhalb des Bereichs des Akkumulators läuft. Wenn es durch jeden dieser Schwellenwerte nach oben geht, wird ein Zähler inkrementiert, der das auf dem eingehenden Signal vorhandene “Rauschen” widerspiegelt.

Rückverfolgungseinheit (TBU)[edit]

Die Rückverfolgungseinheit stellt einen (fast) Maximum-Likelihood-Pfad aus den von der PMU getroffenen Entscheidungen wieder her. Da dies in umgekehrter Richtung erfolgt, umfasst ein Viterbi-Decoder einen FILO-Puffer (First-In-Last-Out), um eine korrekte Reihenfolge zu rekonstruieren.

Beachten Sie, dass die auf dem Bild gezeigte Implementierung eine doppelte Frequenz erfordert. Es gibt einige Tricks, die diese Anforderung beseitigen.

Umsetzungsfragen[edit]

Quantisierung für die weiche Entscheidungsdecodierung[edit]

Um die Vorteile der Soft Decision Decodierung voll auszuschöpfen, muss das Eingangssignal richtig quantisiert werden. Die optimale Breite der Quantisierungszone wird durch die folgende Formel definiert:

T.=N.02k,{ displaystyle , ! T = { sqrt { frac {N_ {0}} {2 ^ {k}}},}

wo

N.0{ displaystyle N_ {0}}

ist eine spektrale Rauschleistungsdichte und k ist eine Anzahl von Bits für eine weiche Entscheidung.

Euklidische Metrikberechnung[edit]

Die quadratische Norm (

ℓ2{ displaystyle ell _ {2}}

) Der Abstand zwischen den empfangenen und den tatsächlichen Symbolen im Code-Alphabet kann weiter vereinfacht werden, um eine lineare Summen- / Differenzform zu erhalten, die es weniger rechenintensiv macht.

Stellen Sie sich einen 1/2 Faltungscodierer vor, der 2 Bits erzeugt (00, 01, 10 oder 11) für jedes Eingangsbit (1 oder 0). Diese Rückkehr zu Null Signale werden in a übersetzt Non-Return-to-Zero nebenstehende Form.

Code Alphabet	Vektorabbildung
00	+1, +1
01	+1, -1
10	−1, +1
11	−1, −1

Jedes empfangene Symbol kann in Vektorform als dargestellt werden v_r = {r₀, r₁}, wo r₀ und r₁ sind weiche Entscheidungswerte, deren Größen die gemeinsame Zuverlässigkeit des empfangenen Vektors, v_r.

Jedes Symbol im Code-Alphabet kann ebenfalls durch den Vektor dargestellt werden v_ich = {± 1, ± 1}.

Die tatsächliche Berechnung der euklidischen Distanzmetrik lautet:

D.=((vr→– –vich→)2=vr→2– –2vr→vich→+vich→2{ displaystyle , ! D = ({ overrightarrow {v_ {r}}} – { overrightarrow {v_ {i}}}) ^ {2} = { overrightarrow {v_ {r}}} ^ {2 } -2 { overrightarrow {v_ {r}}} { overrightarrow {v_ {i}}} + { overrightarrow {v_ {i}}} ^ {2}}

Jeder quadratische Term ist eine normierte Entfernung, die die Energie des Symbols. Zum Beispiel die Energie des Symbols v_ich = {± 1, ± 1} kann berechnet werden als

vich→2=((±1)2+((±1)2=2{ displaystyle , ! { overrightarrow {v_ {i}}} ^ {2} = ( pm 1) ^ {2} + ( pm 1) ^ {2} = 2}

Somit ist der Energieterm aller Symbole im Code-Alphabet konstant (at (normalisiert) Wert 2).

Das Add-Compare-Select ((ACS) Operation vergleicht den metrischen Abstand zwischen dem empfangenen Symbol || v_r|| und 2 beliebige Symbole im Code-Alphabet, deren Pfade an einem Knoten im entsprechenden Gitter zusammengeführt werden. || v_ich⁽⁰⁾|| und || v_ich⁽¹⁾||. Dies entspricht einem Vergleich

D.0=vr→2– –2vr→vich0→+vich0→2{ displaystyle , ! D_ {0} = { overrightarrow {v_ {r}}} ^ {2} -2 { overrightarrow {v_ {r}}} { overrightarrow {v_ {i} ^ {0} }} + { overrightarrow {v_ {i} ^ {0}}} ^ {2}}

und

D.1=vr→2– –2vr→vich1→+vich1→2{ displaystyle , ! D_ {1} = { overrightarrow {v_ {r}}} ^ {2} -2 { overrightarrow {v_ {r}}} { overrightarrow {v_ {i} ^ {1} }} + { overrightarrow {v_ {i} ^ {1}}} ^ {2}}

Aber von oben wissen wir, dass die Energie von v_ich ist konstant (gleich (normalisierter) Wert von 2) und die Energie von v_r ist in beiden Fällen gleich. Dies reduziert den Vergleich mit einer Minima-Funktion zwischen der 2 (Mitte) Skalarprodukt Begriffe,

Mindest((– –2vr→vich0→,– –2vr→vich1→)=max((vr→vich0→,vr→vich1→){ displaystyle , ! min (-2 { overrightarrow {v_ {r}}} { overrightarrow {v_ {i} ^ {0}}}, – 2 { overrightarrow {v_ {r}}} { overrightarrow {v_ {i} ^ {1}}}) = max ({ overrightarrow {v_ {r}}} { overrightarrow {v_ {i} ^ {0}}}, { overrightarrow {v_ {r }}} { overrightarrow {v_ {i} ^ {1}}})}

seit einem Mindest Die Operation mit negativen Zahlen kann als äquivalent interpretiert werden max Betrieb mit positiven Größen.

Jeder Skalarprodukt Begriff kann erweitert werden als

max((±r0±r1,±r0±r1){ displaystyle , ! max ( pm r_ {0} pm r_ {1}, pm r_ {0} pm r_ {1})}

wo die Zeichen jedes Begriffs von Symbolen abhängen, v_ich⁽⁰⁾ und v_ich⁽¹⁾verglichen werden. Und so kam es dass der kariert Euklidische metrische Entfernungsberechnung zur Berechnung der Zweigmetrik kann mit einer einfachen Additions- / Subtraktionsoperation durchgeführt werden.

Zurück verfolgen[edit]

Der allgemeine Ansatz für das Traceback besteht darin, Pfadmetriken für das bis zu Fünffache der Einschränkungslänge (5 () zu akkumulieren.K. – 1)), finden Sie den Knoten mit den größten kumulierten Kosten und beginnen Sie mit der Rückverfolgung von diesem Knoten.

Die häufig verwendete Faustregel für eine Kürzungstiefe, die das Fünffache des Speichers beträgt (Einschränkungslänge) K.-1) eines Faltungscodes ist nur für Codes der Rate 1/2 genau. Für eine beliebige Rate lautet eine genaue Faustregel 2,5 (K. – 1) / (1−r) wo r ist die Coderate.^[1]

Das Berechnen des Knotens, der die größten Kosten (entweder die größte oder die kleinste integrale Pfadmetrik) angehäuft hat, umfasst jedoch das Finden des Maxima oder Minima von mehreren (normalerweise 2^K.-1) Zahlen, die bei der Implementierung auf eingebetteten Hardwaresystemen zeitaufwändig sein können.

Die meisten Kommunikationssysteme verwenden eine Viterbi-Decodierung mit Datenpaketen fester Größe mit einem festen Bit / Byte-Muster entweder am Anfang oder / und am Ende des Datenpakets. Unter Verwendung des bekannten Bit / Byte-Musters als Referenz kann der Startknoten auf einen festen Wert gesetzt werden, wodurch während des Tracebacks ein perfekter Maximum-Likelihood-Pfad erhalten wird.

Einschränkungen[edit]

Eine physikalische Implementierung eines Viterbi-Decoders ergibt keine genau Maximum-Likelihood-Stream aufgrund der Quantisierung des Eingangssignals, der Verzweigungs- und Pfadmetriken und der Endlichkeit Traceback-Länge. Praktische Implementierungen nähern sich innerhalb von 1 dB des Ideals.

Die Ausgabe eines Viterbi-Decoders weist beim Decodieren einer durch einen additiven Gauß-Kanal beschädigten Nachricht Fehler auf, die in Fehlerbursts gruppiert sind.^[2][3]Einzelfehlerkorrekturcodes allein können solche Bursts nicht korrigieren. Daher müssen entweder der Faltungscode und der Viterbi-Decoder so leistungsfähig sein, dass Fehler auf eine akzeptable Rate reduziert werden, oder es müssen Burst-Fehlerkorrekturcodes verwendet werden.

Durchstochene Codes[edit]

Ein Hardware-Viterbi-Decoder von durchstochene Codes wird üblicherweise so implementiert:

• Ein Depuncturer, der den Eingabestream in einen Stream umwandelt, der an den Stellen, an denen Bits gelöscht wurden, wie ein ursprünglicher (nicht punktierter) Stream mit ERASE-Markierungen aussieht.
• Ein grundlegender Viterbi-Decoder, der diese ERASE-Markierungen versteht (dh sie nicht für die Berechnung der Verzweigungsmetrik verwendet).

Software-Implementierung[edit]

Eine der zeitaufwändigsten Operationen ist ein ACS-Butterfly, der normalerweise unter Verwendung einer Assemblersprache und geeigneter Befehlssatzerweiterungen (wie SSE2) implementiert wird, um die Decodierungszeit zu beschleunigen.

Anwendungen[edit]

Der Viterbi-Decodierungsalgorithmus wird in den folgenden Bereichen häufig verwendet:

Verweise[edit]

Externe Links[edit]