Faltungscode - Convolutional code

In der Telekommunikation ist ein Faltungscode eine Art von Fehlerkorrekturcode , der Paritätssymbole über die gleitende Anwendung einer Booleschen Polynomfunktion auf einen Datenstrom erzeugt. Die Gleitanwendung stellt die „Faltung“ des Codierers über die Daten dar, was zu dem Begriff „Faltungscodierung“ führt. Die Gleitnatur der Faltungscodes erleichtert die Trellis- Decodierung unter Verwendung eines zeitinvarianten Trellis. Die zeitinvariante Trellis-Decodierung ermöglicht es, dass Faltungscodes mit maximaler Wahrscheinlichkeit weiche Entscheidungen mit angemessener Komplexität decodiert werden.

Die Fähigkeit, eine wirtschaftliche Soft-Decision-Decodierung mit maximaler Wahrscheinlichkeit durchzuführen, ist einer der Hauptvorteile von Faltungscodes. Dies steht im Gegensatz zu klassischen Blockcodes, die im Allgemeinen durch ein zeitvariantes Trellis repräsentiert werden und daher typischerweise hart entscheidungsdecodiert werden. Faltungscodes werden oft durch die Basiscoderate und die Tiefe (oder Speicher) des Codierers gekennzeichnet . Die Basiscoderate wird typischerweise als angegeben , wobei n die rohe Eingangsdatenrate und k die Datenrate des ausgangskanalcodierten Stroms ist. n ist kleiner als k, weil die Kanalcodierung Redundanz in die Eingangsbits einfügt. Der Speicher wird oft als "Beschränkungslänge" K . bezeichnet${\displaystyle [n,k,K]}$${\displaystyle n/k}$, wobei die Ausgabe eine Funktion der aktuellen Eingabe sowie der vorherigen Eingaben ist. Die Tiefe kann auch als Anzahl der Speicherelemente v im Polynom oder als maximal mögliche Anzahl von Zuständen des Codierers (typischerweise: ) angegeben werden. ${\displaystyle K-1}$${\displaystyle 2^{v}}$

Faltungscodes werden oft als kontinuierlich beschrieben. Es kann jedoch auch gesagt werden, dass Faltungscodes eine beliebige Blocklänge haben, anstatt kontinuierlich zu sein, da die meisten Faltungscodierungen in der realen Welt an Datenblöcken durchgeführt werden. Faltungscodierte Blockcodes verwenden typischerweise eine Terminierung. Die beliebige Blocklänge von Faltungscodes kann auch klassischen Blockcodes gegenübergestellt werden , die im Allgemeinen feste Blocklängen aufweisen, die durch algebraische Eigenschaften bestimmt werden.

Die Coderate eines Faltungscodes wird üblicherweise durch Symbolpunktierung modifiziert . Beispielsweise kann ein Faltungscode mit einer "Mutter" -Coderate auf eine höhere Rate von beispielsweise einfach dadurch punktiert werden, dass ein Teil von Codesymbolen nicht übertragen wird. Die Leistung eines punktierten Faltungscodes skaliert im Allgemeinen gut mit der übertragenen Paritätsmenge. Die Fähigkeit, eine wirtschaftliche Soft-Decision-Decodierung von Faltungscodes durchzuführen, sowie die Blocklängen- und Coderatenflexibilität von Faltungscodes machen sie für die digitale Kommunikation sehr beliebt. ${\displaystyle n/k=1/2}$${\displaystyle 7/8}$

Geschichte

Faltungscodes wurden 1955 von Peter Elias eingeführt . Es wurde angenommen, dass Faltungscodes mit beliebiger Qualität auf Kosten von Berechnung und Verzögerung decodiert werden könnten. 1967 stellte Andrew Viterbi fest, dass Faltungscodes mit angemessener Komplexität mit zeitinvarianten Trellis-basierten Decodern – dem Viterbi-Algorithmus – mit maximaler Wahrscheinlichkeit decodiert werden können . Später wurden andere trellisbasierte Decoderalgorithmen entwickelt, einschließlich des BCJR- Decodierungsalgorithmus.

Rekursive systematische Faltungscodes wurden um 1991 von Claude Berrou erfunden . Diese Codes erwiesen sich als besonders nützlich für die iterative Verarbeitung einschließlich der Verarbeitung von verketteten Codes wie Turbo-Codes .

Unter Verwendung der "Faltungs"-Terminologie könnte ein klassischer Faltungscode als Filter mit endlicher Impulsantwort (FIR) betrachtet werden, während ein rekursiver Faltungscode als Filter mit unendlicher Impulsantwort (IIR) betrachtet werden könnte.

Wo Faltungscodes verwendet werden

Stufen der Kanalcodierung in GSM. Blockcodierer und Paritätsprüfung - Fehlererkennungsteil. Faltungscodierer und Viterbi-Decoder - Fehlerkorrekturteil. Interleaving und Deinterleaving - Codeworttrennung nimmt im Zeitbereich zu und verhindert stoßartige Verzerrungen.

Faltungscodes werden in großem Umfang verwendet, um eine zuverlässige Datenübertragung in zahlreichen Anwendungen zu erreichen, wie z. B. digitales Video , Funk, mobile Kommunikation (z. B. in GSM-, GPRS-, EDGE- und 3G-Netzen (bis 3GPP Release 7)) und Satellitenkommunikation . Diese Codes werden oft in Verkettung mit einem Code für harte Entscheidungen implementiert , insbesondere Reed-Solomon . Vor Turbo-Codes waren solche Konstruktionen die effizientesten und kamen der Shannon-Grenze am nächsten .

Faltungskodierung

Um Daten faltungskodierend zu kodieren, beginnen Sie mit k Speicherregistern , die jeweils ein Eingangsbit enthalten. Sofern nicht anders angegeben, beginnen alle Speicherregister mit einem Wert von 0. Der Encoder hat n Modulo-2- Addierer (ein Modulo-2-Addierer kann mit einem einzelnen booleschen XOR-Gatter implementiert werden , wobei die Logik lautet: 0+0 = 0 , 0+ 1 = 1 , 1+0 = 1 , 1+1 = 0 ) und n Generatorpolynome — eines für jeden Addierer (siehe Abbildung unten). Ein Eingabebit m ₁ wird in das ganz linke Register eingespeist. Unter Verwendung der Generatorpolynome und der vorhandenen Werte in den verbleibenden Registern gibt der Encoder n Symbole aus. Diese Symbole können je nach gewünschter Coderate übertragen oder punktiert werden. Jetzt Bit verschieben alle Registerwerte auf der rechten Seite ( m ₁ bewegt sich zu m ₀ , m ₀ bewegt sich in m _-1 ) und warten auf die nächste Eingabe - Bit. Wenn keine verbleibenden Eingangsbits vorhanden sind, fährt der Encoder mit dem Verschieben fort, bis alle Register in den Nullzustand zurückgekehrt sind (Flush-Bit-Beendigung).

Abb.1. Rate 1/3 nicht-rekursiver, nicht-systematischer Faltungscodierer mit Beschränkungslänge 3

Die Abbildung unten ist ein Encoder mit einer Rate 1 ⁄ 3 ( m ⁄ n ) mit einer Beschränkungslänge ( k ) von 3. Generatorpolynome sind G ₁ = (1,1,1), G ₂ = (0,1,1) und G ₃ = (1,0,1) . Daher werden Ausgangsbits (Modulo 2) wie folgt berechnet:

n ₁ = m ₁ + m ₀ + m ₋₁

n ₂ = m ₀ + m ₋₁

n ₃ = m ₁ + m _–1 .

Faltungscodes können systematisch und nicht-systematisch sein:

• systematisch wiederholt die Struktur der Nachricht vor der Codierung

• unsystematische Änderungen der Ausgangsstruktur

Nicht-systematische Faltungscodes sind aufgrund der besseren Rauschimmunität beliebter. Sie bezieht sich auf den freien Abstand des Faltungscodes.

• 

  Eine kurze Illustration des nicht-systematischen Faltungscodes.

• 

  Eine kurze Illustration des systematischen Faltungscodes.

Rekursive und nicht-rekursive Codes

Der Encoder im obigen Bild ist ein nicht-rekursiver Encoder. Hier ist ein Beispiel für eine rekursive Struktur, die als solche eine Rückkopplungsstruktur zulässt:

Abb.2. Rate 1/2 rekursiver systematischer Faltungscodierer mit 8 Zuständen. Wird als Bestandteilscode im 3GPP 25.212 Turbo Code verwendet.

Der Beispiel-Encoder ist systematisch, da die Eingangsdaten auch in den Ausgangssymbolen (Ausgang 2) verwendet werden. Codes mit Ausgabesymbolen, die die Eingabedaten nicht enthalten, werden als nicht systematisch bezeichnet.

Rekursive Codes sind typischerweise systematisch und umgekehrt sind nicht-rekursive Codes typischerweise nicht-systematisch. Es ist keine strenge Anforderung, sondern eine gängige Praxis.

Der Beispiel-Encoder in Abb. 2. ist ein 8-State-Encoder, da die 3 Register 8 mögliche Encoder-Zustände (2 ³ ) erzeugen . Ein entsprechendes Decoder-Trellis verwendet typischerweise auch 8 Zustände.

Rekursive systematische Faltungscodes (RSC) sind aufgrund ihrer Verwendung in Turbocodes populärer geworden. Rekursive systematische Codes werden auch als pseudo-systematische Codes bezeichnet.

Andere RSC-Codes und Beispielanwendungen umfassen:

Bild 3. Rekursiver, systematischer Faltungscode (RSC) mit zwei Zuständen. Auch „Akkumulator“ genannt.

Nützlich für die Implementierung von LDPC- Code und als innerer konstituierender Code für serielle verkettete Faltungscodes (SCCCs).

Bild 4. Vier-Zustands-rekursiver systematischer Faltungscode (RSC).

Nützlich für SCCCs und mehrdimensionale Turbocodes.

Bild 5. Rekursiver systematischer Faltungscode (RSC) mit 16 Zuständen.

Nützlich als Bestandteilscode in Turbocodes mit niedriger Fehlerrate für Anwendungen wie Satellitenverbindungen. Auch als SCCC-Außencode geeignet.

Impulsantwort, Übertragungsfunktion und Beschränkungslänge

Ein Faltungscodierer wird so genannt, weil er eine Faltung des Eingangsstroms mit den Impulsantworten des Encoders durchführt :

${\displaystyle y_{i}^{j}=\sum_{k=0}^{\infty}h_{k}^{j}x_{ik}=(x*h^{j})[i] ,}$

wobei x eine Eingangssequenz ist, y ^j eine Sequenz von der Ausgabe j ist , h ^j eine Impulsantwort für die Ausgabe j ist und eine Faltung bezeichnet. ${\displaystyle {*}}$

Ein Faltungscodierer ist ein diskretes lineares zeitinvariantes System . Jeder Ausgang eines Encoders kann durch eine eigene Übertragungsfunktion beschrieben werden , die eng mit dem Generatorpolynom verwandt ist. Eine Impulsantwort wird durch Z-Transform mit einer Übertragungsfunktion verbunden .

Übertragungsfunktionen für den ersten (nicht-rekursiven) Geber sind:

• ${\displaystyle H_{1}(z)=1+z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{2}(z)=z^{-1}+z^{-2},\,}$
• ${\displaystyle H_{3}(z)=1+z^{-2}.\,}$

Übertragungsfunktionen für den zweiten (rekursiven) Geber sind:

• ${\displaystyle H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}}, \,}$
• ${\displaystyle H_{2}(z)=1.\,}$

Definiere m durch

${\displaystyle m=\max_{i}\operatorname {polydeg} (H_{i}(1/z))\,}$

wobei für jede rationale Funktion , ${\displaystyle f(z)=P(z)/Q(z)\,}$

${\displaystyle \operatorname {polydeg} (f)=\max(\deg(P),\deg(Q))\,}$.

Dann ist m das Maximum der Polynomgrade von , und die Randbedingungslänge ist definiert als . Im ersten Beispiel beträgt die Beschränkungslänge beispielsweise 3 und im zweiten die Beschränkungslänge 4. ${\displaystyle H_{i}(1/z)\,}$${\displaystyle K=m+1\,}$

Gitterdiagramm

Ein Faltungscodierer ist eine endliche Zustandsmaschine . Ein Codierer mit n binären Zellen hat 2 ⁿ Zustände.

Stellen Sie sich vor, dass der Codierer (in Bild 1 oben gezeigt) '1' in der linken Speicherzelle ( m ₀ ) und '0' in der rechten ( m _–1 ) hat. ( m ₁ ist nicht wirklich eine Speicherzelle, da sie einen Stromwert darstellt). Wir werden einen solchen Zustand als "10" bezeichnen. Entsprechend einem Eingangsbit kann der Encoder bei der nächsten Umdrehung entweder in den Zustand "01" oder in den Zustand "11" übergehen. Man sieht, dass nicht alle Übergänge möglich sind (zB kann ein Decoder nicht vom Zustand "10" in den Zustand "00" konvertieren oder sogar im Zustand "10" bleiben).

Alle möglichen Übergänge können wie folgt dargestellt werden:

Abb.6. Ein Trellis-Diagramm für den Encoder auf Bild1. Ein Pfad durch das Spalier wird als rote Linie angezeigt. Die durchgezogenen Linien zeigen Übergänge, bei denen eine "0" eingegeben wird, und die gestrichelten Linien, bei denen eine "1" eingegeben wird.

Eine tatsächliche codierte Sequenz kann als Pfad in diesem Graphen dargestellt werden. Als Beispiel ist ein gültiger Pfad rot dargestellt.

Dieses Diagramm gibt uns eine Idee über die Dekodierung : Wenn eine empfangene Sequenz nicht in diesen Graphen passt, wurde sie mit Fehlern empfangen, und wir müssen die nächste korrekte (in den Graphen passende) Sequenz wählen . Die echten Decodierungsalgorithmen nutzen diese Idee.

Freier Abstand und Fehlerverteilung

Theoretische Bitfehlerratenkurven von codiertem QPSK (rekursiv und nicht-rekursiv, weiche Entscheidung), additiver weißer Gaußscher Rauschkanal. Kurven zeichnen sich durch annähernd gleiche freie Abstände und Gewichte aus.

Die freie Distanz ( d ) ist die minimale Hamming-Distanz zwischen verschiedenen kodierten Sequenzen. Die Korrekturfähigkeit ( t ) eines Faltungscodes ist die Anzahl von Fehlern, die durch den Code korrigiert werden können. Es kann berechnet werden als

${\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .}$

Da ein Faltungscode keine Blöcke verwendet, sondern einen kontinuierlichen Bitstrom verarbeitet, gilt der Wert von t für eine Menge von Fehlern, die relativ nahe beieinander liegen. Das heißt, mehrere Gruppen von t- Fehlern können normalerweise behoben werden, wenn sie relativ weit voneinander entfernt sind.

Der freie Abstand kann als minimale Länge eines fehlerhaften "Bursts" am Ausgang eines Faltungsdecoders interpretiert werden. Die Tatsache, dass Fehler als "Bursts" auftreten, sollte berücksichtigt werden, wenn ein verketteter Code mit einem inneren Faltungscode entworfen wird. Die beliebte Lösung für dieses Problem besteht darin, Daten vor der Faltungscodierung zu verschachteln , damit der Code des äußeren Blocks (normalerweise Reed-Solomon ) die meisten Fehler korrigieren kann.

Dekodierung von Faltungscodes

Bitfehlerverhältniskurven für Faltungscodes mit verschiedenen Möglichkeiten digitaler Modulationen ( QPSK, 8-PSK , 16-QAM, 64-QAM ) und LLR- Algorithmen. (Genau und Ungefähr) über additivem weißen Gaußschen Rauschkanal.

Es gibt mehrere Algorithmen zum Decodieren von Faltungscodes. Für relativ kleine Werte von k wird der Viterbi-Algorithmus universell verwendet, da er eine maximale Wahrscheinlichkeitsleistung bereitstellt und hochgradig parallelisierbar ist. Viterbi-Decoder sind somit leicht in VLSI- Hardware und in Software auf CPUs mit SIMD- Befehlssätzen zu implementieren .

Codes mit längerer Einschränkungslänge werden praktischer mit einem von mehreren sequentiellen Decodieralgorithmen decodiert , von denen der Fano- Algorithmus der bekannteste ist. Im Gegensatz zur Viterbi-Decodierung ist die sequentielle Decodierung keine maximale Wahrscheinlichkeit, aber ihre Komplexität nimmt mit der Beschränkungslänge nur geringfügig zu, was die Verwendung starker Codes mit langer Beschränkungslänge ermöglicht. Solche Codes wurden im Pioneer-Programm der frühen 1970er Jahre für Jupiter und Saturn verwendet, wichen aber kürzeren, Viterbi-dekodierten Codes, die normalerweise mit großen Reed-Solomon-Fehlerkorrekturcodes verkettet sind , die die gesamte Bitfehlerratenkurve steiler machen und produzieren extrem niedrige unentdeckte Fehlerquoten.

Sowohl Viterbi- als auch sequentielle Decodierungsalgorithmen geben harte Entscheidungen zurück: die Bits, die das wahrscheinlichste Codewort bilden. Ein ungefähres Vertrauensmaß kann jedem Bit unter Verwendung des Viterbi-Algorithmus für weiche Ausgabe hinzugefügt werden . Maximale a posteriori (MAP) weiche Entscheidungen für jedes Bit können durch Verwendung des BCJR-Algorithmus erhalten werden .

Beliebte Faltungscodes

Schieberegister für das (7, [171, 133]) Faltungscode-Polynom. Zweige: , . Alle mathematischen Operationen sollten mit Modulo 2 ausgeführt werden.${\displaystyle h^{1}=171_{o}=[1111001]_{b}}$${\displaystyle h^{2}=133_{o}=[1011011]_{b}}$

Theoretische Bitfehlerratenkurven von codiertem QPSK (Soft Decision), additiver weißer Gaußscher Rauschkanal. Längere Beschränkungslängen erzeugen leistungsfähigere Codes, aber die Komplexität des Viterbi-Algorithmus nimmt mit Beschränkungslängen exponentiell zu, wodurch diese leistungsfähigeren Codes auf Weltraummissionen beschränkt werden, bei denen die zusätzliche Leistung die erhöhte Decodiererkomplexität leicht wert ist.

Tatsächlich werden in der Industrie vordefinierte Faltungscodestrukturen verwendet, die während wissenschaftlicher Forschungen erhalten wurden. Dies bezieht sich auf die Möglichkeit, katastrophale Faltungscodes auszuwählen (verursacht eine größere Anzahl von Fehlern).

Ein besonders beliebter Viterbi-dekodierter Faltungscode, der mindestens seit dem Voyager-Programm verwendet wird, hat eine Beschränkungslänge K von 7 und eine Rate r von 1/2.

Mars Pathfinder , Mars Exploration Rover und die Cassini-Sonde zum Saturn verwenden einen K von 15 und eine Rate von 1/6; dieser Code ist etwa 2 dB besser als der einfachere Code bei Kosten von 256-facher Decodierungskomplexität (im Vergleich zu Voyager-Missionscodes). ${\displaystyle K=7}$

Der Faltungscode mit einer Beschränkungslänge von 2 und einer Rate von 1/2 wird in GSM als Fehlerkorrekturtechnik verwendet.

Punktierte Faltungscodes

Faltungscodes mit 1/2 und 3/4 Coderaten (und Beschränkungslänge 7, Soft Decision, 4-QAM / QPSK / OQPSK).

Faltungscode mit beliebiger Coderate kann basierend auf Polynomauswahl entworfen werden; in der Praxis wird jedoch häufig ein Punktierungsvorgang verwendet, um die erforderliche Coderate zu erreichen. Punktieren ist eine Technik, die verwendet wird, um einen m / n- Ratencode aus einem "grundlegenden" Code mit niedriger Rate (zB 1/ n ) zu machen. Dies wird durch das Löschen einiger Bits in der Encoderausgabe erreicht. Bits werden gemäß einer Punktierungsmatrix gelöscht . Die folgenden Punktiermatrizen werden am häufigsten verwendet:

Wenn wir zum Beispiel einen Code mit einer Rate von 2/3 unter Verwendung der entsprechenden Matrix aus der obigen Tabelle erstellen möchten, sollten wir einen Basis-Encoder-Ausgang nehmen und jedes erste Bit aus dem ersten Zweig und jedes Bit aus dem zweiten übertragen. Die konkrete Übertragungsreihenfolge wird durch den jeweiligen Kommunikationsstandard festgelegt.

Punktierte Faltungscodes werden in der Satellitenkommunikation weit verbreitet verwendet , beispielsweise in INTELSAT- Systemen und beim digitalen Videorundfunk .

Gelochte Faltungscodes werden auch als "perforiert" bezeichnet.

Turbo-Codes: Ersetzen von Faltungscodes

Ein Turbocode mit Komponentencodes 13, 15. Turbocodes haben ihren Namen, weil der Decoder wie ein Turbomotor Feedback verwendet. Permutation bedeutet dasselbe wie die Verschachtelung. C1 und C2 sind rekursive Faltungscodes. Rekursive und nicht-rekursive Faltungscodes unterscheiden sich in der BER-Leistung nicht so sehr, jedoch wird der rekursive Typ von in Turbo-Faltungscodes aufgrund besserer Verschachtelungseigenschaften implementiert.

Einfache Viterbi-dekodierte Faltungscodes weichen jetzt Turbo-Codes , einer neuen Klasse von iterierten kurzen Faltungscodes, die sich den theoretischen Grenzen des Shannon-Theorems mit viel weniger Dekodierkomplexität als der Viterbi-Algorithmus bei den erforderlichen langen Faltungscodes sehr nahe kommen für die gleiche Leistung. Verkettungs mit einem äußeren algebraischen Code ( zum Beispiel Reed-Solomon ) -Adressen der Ausgabe des Fehlerbodens inhärent Turbocode - Designs.

Siehe auch

• Quantenfaltungscode

Verweise

•  Dieser Artikel enthält  gemeinfreies Material aus dem Dokument General Services Administration : "Federal Standard 1037C" .

Externe Links

• Das Online-Lehrbuch: Information Theory, Inference, and Learning Algorithms von David JC MacKay diskutiert Faltungscodes in Kapitel 48.
• Die Seite mit den Fehlerkorrekturcodes (ECC)
• Matlab-Erklärungen
• Grundlagen von Faltungsdecodern für eine bessere digitale Kommunikation
• Faltungscodes (MIT)
• Informationstheorie und Codierung (TU Ilmenau) behandelt Faltungscodes auf Seite 48.

Weiterlesen