Turbo-Code - Turbo code

In der Informationstheorie sind Turbocodes (ursprünglich in Französisch Turbocodes ) eine Klasse von Hochleistungs- Vorwärtsfehlerkorrekturcodes (FEC), die um 1990-91 entwickelt, aber erstmals 1993 veröffentlicht wurden. Sie waren die ersten praktischen Codes, die sich dem maximalen Kanal näherten maximum Kapazität oder Shannon-Limit , ein theoretisches Maximum für die Coderate, bei der bei einem bestimmten Rauschpegel noch eine zuverlässige Kommunikation möglich ist. Turbo - Codes werden in verwendet 3G / 4G Mobilfunk (zB in UMTS und LTE ) und in ( Weltraum ) Satellitenkommunikation sowie andere Anwendungen , bei denen Designer suchen zuverlässige Informationsübertragung über Bandbreiten- zu erreichen oder Latenz beschränkten Kommunikationsverbindungen in dem Vorhandensein von datenverfälschendem Rauschen. Turbo-Codes konkurrieren mit Low-Density-Parity-Check- (LDPC)-Codes, die eine ähnliche Leistung bieten.

Der Name "Turbo-Code" entstand aus der Rückkopplungsschleife, die während der normalen Turbo-Code-Decodierung verwendet wurde, die der Abgasrückführung für die Motorturboaufladung analog war . Hagenauer hat argumentiert, dass der Begriff Turbo-Code eine falsche Bezeichnung ist, da beim Codierungsprozess keine Rückkopplung stattfindet.

Geschichte

Die grundlegende Patentanmeldung für Turbocodes wurde am 23. April 1991 eingereicht. Die Patentanmeldung führt Claude Berrou als alleinigen Erfinder von Turbocodes auf. Die Patentanmeldung führte zu mehreren Patenten, darunter das US-Patent 5.446.747 , das am 29. August 2013 abgelaufen ist.

Das erste öffentliche Papier über Turbo-Codes war „ Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes “. Dieses Papier wurde 1993 in den Proceedings of IEEE International Communications Conference veröffentlicht. Das Papier von 1993 wurde aus drei separaten Einreichungen gebildet, die aus Platzgründen kombiniert wurden. Die Fusion führte dazu, dass das Papier drei Autoren aufführte: Berrou, Glavieux und Thitimajshima (von Télécom Bretagne, ehemals ENST Bretagne , Frankreich). Aus der ursprünglichen Patentanmeldung geht jedoch klar hervor, dass Berrou der einzige Erfinder von Turbo-Codes ist und dass die anderen Autoren des Papiers anderes Material als die Kernkonzepte beigesteuert haben.

Turbo-Codes waren zum Zeitpunkt ihrer Einführung so revolutionär, dass viele Experten auf dem Gebiet der Codierung den berichteten Ergebnissen nicht glaubten. Als die Leistung bestätigt wurde, fand eine kleine Revolution in der Welt der Codierung statt, die zur Untersuchung vieler anderer Arten der iterativen Signalverarbeitung führte.

Die erste Klasse von Turbocode war der parallel verkettete Faltungscode (PCCC). Seit der Einführung der ursprünglichen parallelen Turbocodes im Jahr 1993 wurden viele andere Klassen von Turbocodes entdeckt, einschließlich serieller Versionen verketteter Faltungscodes und Wiederholungsakkumulationscodes . Iterative Turbodecodierverfahren wurden auch auf konventionellere FEC-Systeme angewendet, einschließlich Reed-Solomon-korrigierte Faltungscodes, obwohl diese Systeme für praktische Implementierungen von iterativen Decodierern zu komplex sind. Auch die Turboentzerrung entstammte dem Konzept der Turbocodierung.

Zusätzlich zu Turbocodes hat Berrou auch rekursive systematische Faltungscodes (RSC) erfunden, die in der im Patent beschriebenen beispielhaften Implementierung von Turbocodes verwendet werden. Turbo-Codes, die RSC-Codes verwenden, scheinen eine bessere Leistung zu erbringen als Turbo-Codes, die keine RSC-Codes verwenden.

Vor Turbocodes waren die besten Konstruktionen serielle verkettete Codes basierend auf einem äußeren Reed-Solomon-Fehlerkorrekturcode kombiniert mit einem inneren Viterbi-decodierten Faltungscode mit kurzer Beschränkungslänge , auch als RSV-Codes bekannt.

In einer späteren Arbeit würdigte Berrou die Intuition von "G. Battail, J. Hagenauer und P. Hoeher, die Ende der 80er Jahre das Interesse der probabilistischen Verarbeitung betonten." Er fügt hinzu: „ R. Gallager und M. Tanner hatten sich bereits Codierungs- und Decodierungstechniken ausgedacht, deren allgemeine Prinzipien eng miteinander verwandt sind“, obwohl die notwendigen Berechnungen damals unpraktisch waren.

Ein Beispiel-Encoder

Es gibt viele verschiedene Instanzen von Turbocodes, die verschiedene Komponentencodierer, Eingabe-/Ausgabeverhältnisse, Verschachteler und Punktierungsmuster verwenden. Diese beispielhafte Codiererimplementierung beschreibt einen klassischen Turbocodierer und demonstriert das allgemeine Design von parallelen Turbocodes.

Diese Codiererimplementierung sendet drei Unterblöcke von Bits. Der erste Unterblock ist der m- Bit-Block von Nutzdaten. Der zweite Unterblock besteht aus n/2 Paritätsbits für die Nutzdaten, die unter Verwendung eines rekursiven systematischen Faltungscodes (RSC-Code) berechnet werden . Der dritte Unterblock besteht aus n/2 Paritätsbits für eine bekannte Permutation der Nutzdaten, die wiederum unter Verwendung eines RSC-Codes berechnet werden. Somit werden zwei redundante, aber unterschiedliche Unterblöcke von Paritätsbits mit der Nutzlast gesendet. Der vollständige Block hat m + n Datenbits mit einer Coderate von m /( m + n ) . Die Permutation der Nutzdaten wird von einem sogenannten Interleaver durchgeführt .

Hardwaremäßig besteht dieser Turbo-Code-Encoder aus zwei identischen RSC-Codierern, C ₁ und C ₂ , wie in der Abbildung dargestellt, die über ein Verkettungsschema, die sogenannte parallele Verkettung, miteinander verbunden sind :

In der Figur ist M ein Speicherregister. Die Verzögerungsleitung und der Interleaver zwingen die Eingangsbits d _k dazu, in unterschiedlichen Sequenzen zu erscheinen. Bei der ersten Iteration erscheint die Eingangssequenz d _k an beiden Ausgängen des Codierers, x _k und y _1k oder y _2k aufgrund der systematischen Natur des Codierers. Wenn die Codierer C ₁ und C ₂ in n ₁ und n ₂ Iterationen verwendet werden, sind ihre Raten jeweils gleich

${\displaystyle {\begin{aligned}~R_{1}&={\frac {n_{1}+n_{2}}{2n_{1}+n_{2}}}\\~R_{2}& ={\frac {n_{1}+n_{2}}{n_{1}+2n_{2}}}\end{ausgerichtet}}}$

Der Decoder

Der Decoder ist ähnlich aufgebaut wie der obige Encoder. Zwei elementare Decoder sind miteinander verschaltet, jedoch in Reihe, nicht parallel. Der Decoder arbeitet mit niedrigerer Geschwindigkeit (dh ), daher ist er für den Codierer bestimmt und ist dementsprechend für . ergibt eine weiche Entscheidung, die eine Verzögerung verursacht . Die gleiche Verzögerung wird durch die Verzögerungsleitung im Encoder verursacht. Die Operation von ' verursacht eine Verzögerung. ${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle R_{1}}$${\displaystyle \textstyle C_{1}}$${\displaystyle \textstyle DEZ_{2}}$${\displaystyle \textstyle C_{2}}$${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle L_{1}}$${\displaystyle \textstyle DEZ_{2}}$${\displaystyle \textstyle L_{2}}$

Ein zwischen den beiden Decodern installierter Interleaver wird hier verwendet, um vom Ausgang kommende Fehlerbursts zu streuen . DI- Block ist ein Demultiplex- und Einfügemodul. Es funktioniert wie ein Schalter, der Eingangsbits zu einem Zeitpunkt und zu einem anderen umleitet . Im AUS-Zustand speist es sowohl als auch Eingänge mit Füllbits (Nullen). ${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle DEZ_{2}}$${\displaystyle \textstyle y_{1k}}$${\displaystyle \textstyle y_{2k}}$

Betrachten Sie einen speicherlosen AWGN- Kanal und nehmen Sie an , dass der Decoder bei der k- ten Iteration ein Paar Zufallsvariablen empfängt:

${\displaystyle {\begin{ausgerichtet}~x_{k}&=(2d_{k}-1)+a_{k}\\~y_{k}&=2(Y_{k}-1)+b_{ k}\end{ausgerichtet}}}$

wobei und sind unabhängige Rauschkomponenten mit der gleichen Varianz . ist ein k- tes Bit von der Encoderausgabe. ${\displaystyle \textstyle a_{k}}$${\displaystyle \textstyle b_{k}}$${\displaystyle \textstyle \sigma ^{2}}$${\displaystyle \textstyle Y_{k}}$${\displaystyle \textstyle y_{k}}$

Redundante Informationen werden demultiplexiert und über DI an (when ) und an (when ) gesendet . ${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle y_{k}=y_{1k}}$${\displaystyle \textstyle DEZ_{2}}$${\displaystyle \textstyle y_{k}=y_{2k}}$

${\displaystyle \textstyle DEC_{1}}$ergibt eine weiche Entscheidung; dh:

${\displaystyle \Lambda(d_{k})=\log {\frac {p(d_{k}=1)}{p(d_{k}=0)}}}$

und liefert es an . heißt Logarithmus des Likelihood-Quotienten (LLR). ist die A-posteriori-Wahrscheinlichkeit (APP) des Datenbits, die die Wahrscheinlichkeit der Interpretation eines empfangenen Bits als anzeigt . Unter der LLR berücksichtigt, ergibt sich eine harte Entscheidung; dh ein decodiertes Bit. ${\displaystyle \textstyle DEZ_{2}}$${\displaystyle \textstyle \Lambda(d_{k})}$${\displaystyle \textstyle p(d_{k}=i),\,i\in \{0,1\}}$${\displaystyle \textstyle d_{k}}$${\displaystyle \textstyle d_{k}}$${\displaystyle \textstyle i}$${\displaystyle \textstyle DEZ_{2}}$

Es ist bekannt, dass der Viterbi-Algorithmus APP nicht berechnen kann, daher kann er nicht in verwendet werden . Stattdessen wird ein modifizierter BCJR-Algorithmus verwendet. Für ist der Viterbi-Algorithmus ein geeigneter. ${\displaystyle \textstyle DEC_{1}}$${\displaystyle \textstyle DEZ_{2}}$

Die dargestellte Struktur ist jedoch nicht optimal, da nur ein richtiger Bruchteil der verfügbaren redundanten Informationen verwendet wird. Um die Struktur zu verbessern, wird eine Rückkopplungsschleife verwendet (siehe gestrichelte Linie in der Abbildung). ${\displaystyle \textstyle DEC_{1}}$

Weicher Entscheidungsansatz

Das Frontend des Decoders erzeugt eine ganze Zahl für jedes Bit im Datenstrom. Diese ganze Zahl ist ein Maß dafür, wie wahrscheinlich es ist, dass das Bit eine 0 oder 1 ist und wird auch als Soft-Bit bezeichnet . Die ganze Zahl könnte aus dem Bereich [−127, 127] gezogen werden, wobei:

• −127 bedeutet "sicher 0"
• −100 bedeutet "sehr wahrscheinlich 0"
• 0 bedeutet "es könnte entweder 0 oder 1 sein"
• 100 bedeutet "sehr wahrscheinlich 1"
• 127 bedeutet "sicher 1"

Dies führt einen wahrscheinlichkeitstheoretischen Aspekt in den Datenstrom vom Front-End ein, übermittelt jedoch mehr Informationen über jedes Bit als nur 0 oder 1.

Beispielsweise muss das Front-End eines herkömmlichen drahtlosen Empfängers für jedes Bit entscheiden, ob eine interne analoge Spannung über oder unter einem bestimmten Schwellenspannungspegel liegt. Für einen Turbo-Code-Decoder würde das Front-End ein ganzzahliges Maß dafür liefern, wie weit die interne Spannung von der gegebenen Schwelle entfernt ist.

Um den m + n- Bit-Datenblock zu decodieren , erzeugt das Decoder-Front-End einen Block von Wahrscheinlichkeitsmaßen mit einem Wahrscheinlichkeitsmaß für jedes Bit im Datenstrom. Es gibt zwei parallele Decoder, einen für jeden der n ⁄ 2- Bit-Paritätsunterblöcke. Beide Decoder verwenden den Unterblock von m Likelihoods für die Nutzdaten. Der an dem zweiten Paritätsunterblock arbeitende Decodierer kennt die Permutation, die der Codierer für diesen Unterblock verwendet hat.

Lösen von Hypothesen, um Bits zu finden

Die Schlüsselinnovation von Turbo-Codes besteht darin, wie sie die Wahrscheinlichkeitsdaten verwenden, um Unterschiede zwischen den beiden Decodern auszugleichen. Jeder der beiden Faltungsdecodierer erzeugt eine Hypothese (mit abgeleiteten Wahrscheinlichkeiten) für das Muster von m Bits im Nutzlast-Unterblock. Die Hypothesen-Bitmuster werden verglichen, und wenn sie sich unterscheiden, tauschen die Decoder die abgeleiteten Wahrscheinlichkeiten aus, die sie für jedes Bit in den Hypothesen haben. Jeder Decoder enthält die abgeleiteten Wahrscheinlichkeitsschätzungen des anderen Decoders, um eine neue Hypothese für die Bits in der Nutzlast zu erzeugen. Dann vergleichen sie diese neuen Hypothesen. Dieser iterative Prozess wird fortgesetzt, bis die beiden Decodierer die gleiche Hypothese für das m- Bit-Muster der Nutzlast aufstellen, typischerweise in 15 bis 18 Zyklen.

Eine Analogie kann zwischen diesem Prozess und dem Lösen von Querverweisrätseln wie Kreuzworträtseln oder Sudoku gezogen werden . Betrachten Sie ein teilweise abgeschlossenes, möglicherweise verstümmeltes Kreuzworträtsel. Zwei Rätsellöser (Decoder) versuchen, es zu lösen: Einer besitzt nur die "unten"-Hinweise (Paritätsbits) und der andere besitzt nur die "über"-Hinweise. Zu Beginn erraten beide Löser die Antworten (Hypothesen) zu ihren eigenen Hinweisen und notieren, wie sicher sie sich in jedem Buchstaben (Nutzlastbit) sind. Dann vergleichen sie Notizen, indem sie Antworten und Vertrauensbewertungen miteinander austauschen und feststellen, wo und wie sie sich unterscheiden. Basierend auf diesem neuen Wissen erstellen beide aktualisierte Antworten und Vertrauensbewertungen und wiederholen den gesamten Prozess, bis sie zu derselben Lösung konvergieren.

Leistung

Turbocodes arbeiten aufgrund der attraktiven Kombination des zufälligen Auftretens des Codes auf dem Kanal zusammen mit der physikalisch realisierbaren Decodierungsstruktur gut. Turbo-Codes sind von einem Error Floor betroffen .

Praktische Anwendungen mit Turbocodes

Telekommunikation:

• Turbo-Codes werden häufig in 3G- und 4G- Mobilfunkstandards verwendet; zB in HSPA , EV-DO und LTE .
• MediaFLO , terrestrisches mobiles Fernsehsystem von Qualcomm .
• Der Interaktionskanal von Satellitenkommunikationssystemen wie DVB-RCS und DVB-RCS2 .
• Neuere NASA- Missionen wie der Mars Reconnaissance Orbiter verwenden Turbo-Codes als Alternative zur Reed-Solomon-Fehlerkorrektur - Viterbi-Decoder- Codes.
• IEEE 802.16 ( WiMAX ), ein Standard für drahtlose Metropolen, verwendet Block-Turbo-Codierung und Faltungs-Turbo-Codierung.

Bayessche Formulierung

Aus Sicht der Künstlichen Intelligenz können Turbo-Codes als ein Beispiel für eine verworrene Glaubensausbreitung in Bayes-Netzwerken angesehen werden .

Siehe auch

• Faltungscode
• Viterbi-Algorithmus
• Soft-Decision-Dekodierung
• Interleaver
• BCJR-Algorithmus
• Paritätsprüfcode mit niedriger Dichte
• Seriell verkettete Faltungscodes
• Turbo-Equalizer
• Vorwärtsfehlerkorrektur

Verweise

Weiterlesen

Veröffentlichungen

• Battail, Gerhard. "Ein konzeptioneller Rahmen zum Verständnis von Turbo-Codes." IEEE Journal on Selected Areas in Communications 16.2 (1998): 245–254.
• Brejza, Matthew F., et al. "20 Jahre Turbocodierung und energiebewusste Designrichtlinien für energiebeschränkte drahtlose Anwendungen." IEEE Communications Surveys & Tutorials 18.1 (2016): 8–28.
• Garzón-Bohórquez, Ronald, Charbel Abdel Nour und Catherine Douillard. „Verbesserung von Turbo-Codes für 5G mit paritätseinschränkenden Interleavern.“ Turbo Codes and Iterative Information Processing (ISTC), 2016 9. Internationales Symposium zum. IEEE, 2016.

Externe Links

• "Der perfekte Code zum Abschluss" , IEEE Spectrum, März 2004
• "Der UMTS-Turbo-Code und eine effiziente Decoder-Implementierung für Software-Defined Radios" ( International Journal of Wireless Information Networks )
• Dana Mackenzie (2005), "Take it to the limit", New Scientist , 187 (2507): 38–41, ISSN  0262-4079 .( Vorschau , Kopie )
• "Pushing the Limit" , ein Beitrag von Science News über die Entwicklung und Genese von Turbo-Codes
• Internationales Symposium zu Turbocodes
• Coded Modulation Library , eine Open-Source-Bibliothek zur Simulation von Turbo-Codes in Matlab mat
• "Turbo Equalization: Principles and New Results" , ein Artikel von IEEE Transactions on Communications über die Verwendung von Faltungscodes zusammen mit Kanalentzerrung.
• IT++ Home Page Die IT++ ist eine mächtige C++-Bibliothek, die insbesondere Turbo-Codes unterstützt
• Turbocode-Veröffentlichungen von David MacKay
• AFF3CT Home Page (A Fast Forward Error Correction Toolbox) für Hochgeschwindigkeits-Turbocode-Simulationen in Software
• Turbo-Code von Dr. Sylvie Kerouédan und Dr. Claude Berrou (scholarpedia.org).
• 3GPP LTE Turbo-Referenzdesign .
• Schätzen Sie die Turbo-Code-BER-Leistung in AWGN (MatLab).
• Parallel Concatenated Convolutional Coding: Turbo-Codes (MatLab Simulink)