Viterbi-Decoder - Viterbi decoder
Ein Viterbi-Decoder verwendet den Viterbi-Algorithmus zum Decodieren eines Bitstroms, der unter Verwendung eines Faltungscodes oder Trellis-Codes codiert wurde .
Es gibt andere Algorithmen zum Decodieren eines faltungscodierten Stroms (zum Beispiel der Fano-Algorithmus ). Der Viterbi-Algorithmus ist der ressourcenintensivste, aber er führt die Decodierung mit maximaler Wahrscheinlichkeit durch . Es wird am häufigsten zum Decodieren von Faltungscodes mit Beschränkungslängen k≤3 verwendet, aber in der Praxis werden Werte bis zu k=15 verwendet.
Die Viterbi-Decodierung wurde von Andrew J. Viterbi entwickelt und in der Veröffentlichung Viterbi, A. (April 1967) veröffentlicht. „Fehlergrenzen für Faltungscodes und ein asymptotisch optimaler Dekodierungsalgorithmus“. 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.
Viterbi-Decodierung wird im iterativen Viterbi-Decodierungsalgorithmus verwendet.
Hardwareimplementierung
Ein Hardware-Viterbi-Decoder für einfachen (nicht punktierten) Code besteht normalerweise aus den folgenden Hauptblöcken:
- Metrische Einheit der Branche (BMU)
- Wegmetrikeinheit (PMU)
- Traceback-Einheit (TBU)
Metrische Einheit der Branche (BMU)
Die Funktion einer Verzweigungsmetrikeinheit besteht darin, Verzweigungsmetriken zu berechnen , die normierte Abstände zwischen jedem möglichen Symbol im Codealphabet und dem empfangenen Symbol sind.
Es gibt Viterbi-Decoder mit harter und weicher Entscheidung. Ein Viterbi-Decoder mit harter Entscheidung empfängt einen einfachen Bitstrom an seinem Eingang, und eine Hamming-Distanz wird als Metrik verwendet. Ein Viterbi-Decoder mit weicher Entscheidung empfängt einen Bitstrom, der Informationen über die Zuverlässigkeit jedes empfangenen Symbols enthält. Bei einer 3-Bit-Codierung können diese Zuverlässigkeitsinformationen beispielsweise wie folgt codiert werden:
Wert | Bedeutung | |
---|---|---|
000 | am stärksten | 0 |
001 | relativ stark | 0 |
010 | relativ schwach | 0 |
011 | schwächste | 0 |
100 | schwächste | 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 kodieren.
Die quadrierte euklidische Distanz wird als Metrik für Soft-Decision-Decoder verwendet.
Wegmetrikeinheit (PMU)
Eine Pfadmetrikeinheit fasst Zweigmetriken zusammen, um Metriken für Pfade zu erhalten, wobei K die Beschränkungslänge des Codes ist, von denen schließlich eine als optimal gewählt werden kann . Mit jeder Uhr trifft es Entscheidungen und wirft bewusst nicht optimale Wege ab. Die Ergebnisse dieser Entscheidungen werden in den Speicher einer Traceback-Einheit geschrieben.
Die Kernelemente einer PMU sind ACS- Einheiten (Add-Compare-Select) . Die Art und Weise, wie sie untereinander verbunden sind, wird durch das Trellis-Diagramm eines bestimmten Codes definiert .
Da Verzweigungsmetriken immer sind , muss eine zusätzliche Schaltung (nicht im Bild gezeigt) vorhanden sein, die einen Überlauf der Metrikzähler verhindert. Ein alternatives Verfahren, das die Notwendigkeit beseitigt, das Wachstum der Pfadmetrik zu überwachen, besteht darin, den Pfadmetriken zu erlauben, "überzurollen"; Um dieses Verfahren zu verwenden, muss sichergestellt werden, dass die Pfadmetrik-Akkumulatoren genügend Bits enthalten, um zu verhindern, dass die "besten" und "schlechtesten" Werte innerhalb von 2 (n-1) voneinander liegen. Die Vergleichsschaltung ist im Wesentlichen unverändert.
Es ist möglich, den Rauschpegel des eingehenden Bitstroms zu überwachen, indem die Wachstumsrate der "besten" Pfadmetrik überwacht wird. Ein einfacherer Weg, dies zu tun, besteht darin, einen einzelnen Ort oder "Zustand" zu überwachen und zu beobachten, wie er "aufwärts" durch beispielsweise vier diskrete Pegel innerhalb des Bereichs des Akkumulators geht. Wenn es jeden dieser Schwellenwerte nach oben durchläuft, wird ein Zähler inkrementiert, der das auf dem ankommenden Signal vorhandene "Rauschen" widerspiegelt.
Traceback-Einheit (TBU)
Die Back-Trace-Einheit stellt einen (fast) maximal wahrscheinlichen Pfad aus den von der PMU getroffenen Entscheidungen wieder her. Da er dies in umgekehrter Richtung tut, umfasst ein Viterbi-Decoder einen FILO-Puffer (First-In-Last-Out), um eine korrekte Reihenfolge zu rekonstruieren.
Beachten Sie, dass die im Bild gezeigte Implementierung die doppelte Frequenz erfordert. Es gibt einige Tricks, die diese Anforderung eliminieren.
Umsetzungsfragen
Quantisierung für Soft-Decision-Dekodierung
Um die Vorteile der Soft-Decision-Decodierung voll auszuschöpfen, muss man das Eingangssignal richtig quantisieren. Die optimale Breite der Quantisierungszone wird durch die folgende Formel definiert:
wobei eine spektrale Rauschleistungsdichte und k eine Anzahl von Bits für eine weiche Entscheidung ist.
Berechnung der euklidischen Metrik
Der quadrierte Normabstand ( ) zwischen den empfangenen und den tatsächlichen Symbolen im Codealphabet kann weiter in eine lineare Summen-/Differenzform vereinfacht werden, was ihn weniger rechenintensiv macht.
Betrachten Sie einen 1/2- Faltungscodierer , der 2 Bits ( 00 , 01 , 10 oder 11 ) für jedes Eingangsbit ( 1 oder 0 ) erzeugt. Diese Return-to-Zero- Signale werden in eine nebenstehende Non-Return-to-Zero- Form übersetzt.
Code-Alphabet | Vektor-Mapping |
---|---|
00 | +1, +1 |
01 | +1, -1 |
10 | −1, +1 |
11 | −1, −1 − |
Jedes empfangene Symbol kann in Vektorform als v r = {r 0 , r 1 } dargestellt werden, wobei r 0 und r 1 Soft-Decision-Werte sind, deren Größen die gemeinsame Zuverlässigkeit des empfangenen Vektors v r bezeichnen .
Jedes Symbol im Codealphabet kann ebenfalls durch den Vektor v i = {±1, ±1} dargestellt werden.
Die tatsächliche Berechnung der euklidischen Distanzmetrik ist:
Jeder quadratische Term ist ein normierter Abstand, der die Energie des Symbols darstellt. Zum Beispiel kann die Energie des Symbols v i = {±1, ±1} berechnet werden als
Somit ist der Energieterm aller Symbole im Codealphabet konstant (bei ( normalisiertem ) Wert 2).
Die Operation Add-Compare-Select ( ACS ) vergleicht die metrische Distanz zwischen dem empfangenen Symbol ||v r || und 2 beliebige Symbole im Codealphabet, deren Pfade an einem Knoten im entsprechenden Trellis zusammenlaufen, ||v i (0) || und ||v i (1) || . Dies entspricht einem Vergleich
und
Aber von oben wissen wir, dass die Energie von v i konstant ist (gleich dem (normierten) Wert von 2) und die Energie von v r in beiden Fällen gleich ist. Dies reduziert den Vergleich auf eine Minimafunktion zwischen den 2 (mittleren) Punktprodukttermen ,
da eine Min- Operation bei negativen Zahlen als äquivalente Max- Operation bei positiven Größen interpretiert werden kann.
Jeder Punktproduktbegriff kann erweitert werden als
wobei die Vorzeichen jedes Ausdrucks von den Symbolen v i (0) und v i (1) abhängen , die verglichen werden. Somit kann die quadrierte euklidische Metrikabstandsberechnung zum Berechnen der Verzweigungsmetrik mit einer einfachen Addier-/Subtraktionsoperation durchgeführt werden.
Zurück verfolgen
Der allgemeine Ansatz zur Rückverfolgung besteht darin, Pfadmetriken für das bis zu fünffache der Beschränkungslänge (5 ( K - 1)) zu akkumulieren, den Knoten mit den größten akkumulierten Kosten zu finden und die Rückverfolgung von diesem Knoten aus zu beginnen.
Die allgemein verwendete Faustregel einer Abschneidetiefe von dem Fünffachen des Speichers (Einschränkungslänge K –1) eines Faltungscodes ist nur für Codes mit der Rate 1/2 genau. Für eine beliebige Rate ist eine genaue Faustregel 2,5( K – 1)/(1 – r ), wobei r die Coderate ist.
Das Berechnen des Knotens, der die größten Kosten (entweder die größte oder die kleinste integrale Pfadmetrik) angesammelt hat, beinhaltet jedoch das Finden der Maxima oder Minima mehrerer (normalerweise 2 K –1 ) Zahlen, was zeitaufwendig sein kann, wenn sie auf eingebetteten Hardwaresystemen implementiert wird.
Die meisten Kommunikationssysteme verwenden eine Viterbi-Decodierung, die Datenpakete fester Größe mit einem festen Bit / Byte- Muster entweder am Anfang oder/und am Ende des Datenpakets beinhaltet. Durch Verwenden des bekannten Bit / Byte- Musters als Referenz kann der Startknoten auf einen festen Wert gesetzt werden, wodurch ein perfekter Maximum-Likelihood-Pfad während der Rückverfolgung erhalten wird.
Einschränkungen
Eine physikalische Implementierung eines Viterbi - Decoder wird nicht einen Ausbeute genauen Maximum-Likelihood - Stromes aufgrund der Quantisierung der Eingangssignal, Ast und Pfadmetriken und finite Rückverfolgungslänge . Praktische Implementierungen nähern sich dem Ideal innerhalb von 1 dB.
Die Ausgabe eines Viterbi-Decoders weist beim Decodieren einer durch einen additiven Gaußschen Kanal beschädigten Nachricht Fehler auf, die in Fehlerbursts gruppiert sind. Einzelfehler-korrigierende Codes allein können solche Bursts nicht korrigieren, daher müssen entweder der Faltungscode und der Viterbi-Decoder leistungsfähig genug ausgelegt sein, um Fehler auf eine akzeptable Rate herunterzufahren, oder es müssen Burst-Fehlerkorrekturcodes verwendet werden.
Durchstochene Codes
Ein Hardware-Viterbi-Decoder von punktierten Codes wird üblicherweise so implementiert:
- Ein Depunktierer, der den Eingangsstrom in einen Strom umwandelt, der wie ein originaler (nicht punktierter) Strom aussieht, mit ERASE-Markierungen an den Stellen, an denen Bits gelöscht wurden.
- Ein grundlegender Viterbi-Decoder, der diese ERASE-Markierungen versteht (dh sie nicht für die Berechnung der Verzweigungsmetrik verwendet).
Softwareimplementierung
Eine der zeitaufwendigsten Operationen ist ein ACS-Schmetterling, der normalerweise unter Verwendung einer Assemblersprache und geeigneter Befehlssatzerweiterungen (wie SSE2 ) implementiert wird, um die Decodierzeit zu beschleunigen.
Anwendungen
Der Viterbi-Decodierungsalgorithmus wird häufig in den folgenden Bereichen verwendet:
- Funkkommunikation: Digitalfernsehen ( ATSC , QAM , DVB-T usw.), Richtfunk , Satellitenkommunikation , PSK31 Digitalmodus für Amateurfunk .
- Decoding Trellis-coded Modulation (TCM), die Technik, die in Telefonleitungsmodems verwendet wird, um eine hohe spektrale Effizienz aus analogen Telefonleitungen mit einer Bandbreite von 3 kHz herauszuholen.
- Computerspeichergeräte wie Festplattenlaufwerke .
- Automatische Spracherkennung
Verweise
Externe Links
- Forney, G. David, Jr. (29. April 2005). „Der Viterbi-Algorithmus: Eine persönliche Geschichte“. arXiv : cs/0504020 .
- Details zur Viterbi-Decodierung sowie eine Bibliographie .
- Erläuterung des Viterbi-Algorithmus mit Schwerpunkt auf Hardware-Implementierungsproblemen .
- r =1/6 k =15 Codierung für die Cassini-Mission zum Saturn .
- Online Generator von optimierten Software Viterbi Decodern (GPL) .
- GPL Viterbi Decoder-Software für vier Standardcodes .
- Beschreibung eines k = 24 Viterbi-Decoders, von dem angenommen wird, dass er der größte ist, der jemals in der Praxis verwendet wurde .
- Generische Viterbi-Decoder-Hardware (GPL) .