Grundlegendes zu den Turbocodes

Aus LNTwww
Wechseln zu:Navigation, Suche

Grundstruktur eines Turbocodes (1)


Alle heute (2016) aktuellen Kommunikationssysteme wie UMTS (3. Mobilfunkgeneration) und LTE (4. Mobilfunkgeneration) verwenden das in Kapitel 4.1 dargelegte Konzept der symbolweisen iterativen Decodierung. Dass dies so ist, steht unmittelbar mit der Erfindung der Turbocodes im Jahre 1993 durch C. Berrou, A. Glavieux und P. Thitimajshima in Zusammenhang, denn erst mit diesen Codes konnte man sich der Shannon–Grenze mit vertretbarem Decodieraufwand annähern.

Turbocodes ergeben sich durch die parallele oder serielle Verkettung von Faltungscodes. Die Grafik zeigt die parallele Verkettung zweier Codes mit den Parametern k = 1, n = 2  ⇒  Rate R = 1/2.

Parallele Verkettung zweier Rate–1/2–Codes

In dieser Darstellung bezeichnet:

  • u das aktuell betrachtete Bit der Informationssequenz u,
  • xi,j das aktuell betrachtete Bit am Ausgang j von Coder i   (mit 1 ≤ i ≤ 2, 1 ≤ j ≤ 2),
  • X = (x1,1, x1,2, x2,1, x2,2) das Codewort für das aktuelle Informationsbit u.

Die resultierende Rate des verketteten Codiersystems ist somit R = 1/4.

Verwendet man systematische Komponentencodes, so ergibt sich das folgende Modell:

Rate–1/3–Turbocodierer (parallele Verkettung zweier Rate–1/2–Faltungscodes)

Die Modifikationen gegenüber der oberen Grafik lassen sich wie folgt begründen:

  • Bei systematischen Codes C1 und C2 ist sowohl x1,1 = u als auch x2,1 = u. Deshalb kann man auf die Übertragung eines redundanten Bits (zum Beispiel x2,2) verzichten.
  • Mit dieser Reduktion ergibt sich ein Rate–1/3–Turbocode mit den Parametern k = 1 und n = 3. Das Codewort lautet mit den Paritybits p1 und p2 von Coder 1 bzw. Coder 2:
\[\underline{X} = \left (u, p_1, p_2 \right )\hspace{0.05cm}.\]

Auf der nächsten Seite wird unser Turbocode–Modell nochmals geringfügig modifiziert.

Grundstruktur eines Turbocodes (2)


Im Folgenden gehen wir stets von einem noch weiter modifizierten Turbocoder–Modell aus:

  • Wie es für die Beschreibung von Faltungscodes erforderlich ist, liegt nun am Eingang anstelle des isolierten Informationsbits u die Informationssequenz u = (u1, u2, ... , ui, ... ) an.
  • Die Codewortsequenz wird mit x = (X1, X2, ... , Xi, ... ) bezeichnet. Um Verwechslungen zu vermeiden, wurden vorne die Codeworte Xi = (u, p1, p2)i mit Großbuchstaben eingeführt.

Rate–1/3–Turbocodierer mit Interleaver

  • Die Coder C1 und C1 werden (gedanklich) als Digitale Filter konzipiert und sind somit durch die Übertragungsfunktionen G1(D) und G2(D) darstellbar.
  • Aus verschiedenen Gründen  ⇒  siehe übernächste Seite sollte die Eingangssequenz des zweiten Coders  ⇒  uπ gegenüber der Sequenz u durch einen Interleaver (Π) verwürfelt sein.
  • Somit spricht nichts dagegen, die beiden Coder gleich zu wählen: G1(D) = G2(D) = G(D). Ohne Interleaver würde dies die Korrekturfähigkeit extrem einschränken.

: Die Grafik zeigt die verschiedenen Sequenzen in angepassten Farben. Anzumerken ist:
  1.    Für uπ ist eine 3×4–Interleaver–Matrix entsprechend Aufgabe Z4.8 berücksichtigt.
  2.    Die Paritysequenzen ergeben sich gemäß G1(D) = G2(D) = 1 + D2  ⇒  siehe Aufgabe A4.8.
Beispielhafte Sequenzen beim Rate–1/3–Turbocodierer


Erste Voraussetzung für Turbocodes: Rekursive Komponentencodes


Nichtrekursive Übertragungsfunktionen zur Erzeugung der Paritysequenzen bewirken einen Turbocode mit unzureichend kleiner Minimaldistanz. Grund für diese Unzulänglichkeit ist die endliche Impulsantwort g = (1, g2, ... , gm, 0, 0, ... ) mit g2, ... , gm ∈ {0, 1}. Hierbei bezeichnet m das Codegedächtnis.

Die Grafik zeigt das Zustandsübergangsdiagramm für das Beispiel G(D) = [1, 1 + D2]. Die Übergänge sind mit „ui | ui pi” beschriftet. Die Abfolge S0S1S2S0S0S0 → ... führt bezüglich des Eingangs zur Informationssequenz u = (1, 0, 0, 0, 0, ... ) und bezüglich des jeweils zweiten Codesymbols zur Paritysequenz   p = (1, 0, 1, 0, 0, ... )  ⇒  identisch mit der Impulsantwort g  ⇒  Gedächtnis m = 2.

Nichtrekursiver Turbocode und Zustandsübergangsdiagramm

Die untere Grafik gilt für einen sog. RSC–Code (Recursive Systematic Convolutional) entsprechend G(D) = [1, (1 + D2)/(1 + D + D2)]. Hier führt die Folge S0S1S3S2S1S3S2 → ... zur Impulsantwort g = (1, 1, 1, 0, 1, 1, 0, 1, 1, ... ). Diese Impulsantwort setzt sich aufgrund der Schleife S1S3S2S1 bis ins Unendliche fort. Dies ermöglicht bzw. erleichtert die iterative Decodierung.

RSC-Turbocode und Zustandsübergangsdiagramm

Mehr Details zu den Beispielen auf dieser Seite finden Sie in Aufgabe A4.8 und Aufgabe A4.9.

Zweite Voraussetzung für Turbocodes: Interleaving


Es ist offensichtlich, dass bei G1(D) = G2(D) ein Interleaver (Π) unerlässlich ist. Ein weiterer Grund ist, dass die Apriori–Information als unabhängig vorausgesetzt wird. Somit sollten benachbarte (und somit möglicherweise stark abhängige) Bits für den jeweils anderen Teilcode weit auseinander liegen.

Für jeden RSC–Code  ⇒  unendliche Impulsantwort g  ⇒  gebrochen–rationale Übertragungsfunktion G(D) gibt es nämlich gewisse Eingangssequenzen u, die zu sehr kurzen Paritysequenzen p = ug mit geringem Hamming–Gewicht wH(p) führen. Eine solche Sequenz ist beispielsweise in der unteren Grafik auf der letzten Seite angegeben:   u = (1, 1, 1, 0, 0, ...). Dann gilt für die Ausgangssequenz:

\[P(D) = U(D) \cdot G(D) = (1+D+D^2) \cdot \frac{1+D^2}{1+D+D^2}= 1+D^2\]

\[\Rightarrow\hspace{0.3cm} \underline{p}= (\hspace{0.05cm}1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 1\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} 0\hspace{0.05cm},\hspace{0.05cm} ...\hspace{0.05cm})\hspace{0.05cm}. \]

Durch Interleaving (deutsch: Verwürfelung) wird nun mit großer Wahrscheinlichkeit sichergestellt, dass diese Sequenz u = (1, 1, 1, 0, 0, ...) in eine Sequenz uπ gewandelt wird,

  • die zwar ebenfalls nur drei Einsen beinhaltet,
  • deren Ausgangssequenz aber durch ein großes Hamming–Gewicht wH(p) gekennzeichnet ist.

Somit gelingt es dem Decoder, solche „Problemsequenzen” iterativ aufzulösen.

Zur Beschreibung der Interleaver verwendet man die Zuordnung IInIOut. Diese Bezeichnungen stehen für die Indizes von Ausgangs– bzw. Eingangsfolge. Die Interleavergröße wird mit Imax benannt.

Zur Verdeutlichung von Block–Interleaving


Es gibt mehrere, grundsätzlich verschiedene Interleaver–Konzepte:

Bei einem Block–Interleaver füllt man eine Matrix mit S Spalten und Z Zeilen spaltenweise und liest die Matrix zeilenweise aus. Damit wird ein Informationsblock mit Imax = S · Z Bit deterministisch verwürfelt.

Die Grafik verdeutlicht das Prinzip für Imax = 64  ⇒  1 ≤ IIn < 65 und 1 ≤ IOut < 65. Die Reihenfolge der Ausgangsbits lautet dann:

          1, 9, 17, 25, 33, 41, 49, 57, 2, 10, 18, ... , 48, 56 , 64.

Mehr Informationen zum Block–Interleaving gibt es in Aufgabe Z4.8.

Zur Verdeutlichung von S–Random–Interleaving

Turbocodes verwenden oft den S–Random–Interleaver. Dieser pseudozufällige Algorithmus mit dem Parameter „S” garantiert, dass zwei am Eingang weniger als S auseinander liegende Indizes am Ausgang mindestens im Abstand S + 1 auftreten. Die linke Grafik zeigt die S–Random–Kennlinie IOut(IIn) für Imax = 640.

Auch dieser Algorithmus ist deterministisch, und man kann die Verwürfelung im Decoder rückgängig machen ⇒ De–Interleaving. Die Verteilung wirkt trotzdem „zufälliger” als bei Block–Interleaving.

Symbolweise iterative Decodierung eines Turbocodes


Die Decodierung eines Turbocodes geschieht grundsätzlich wie in Kapitel 4.1 beschrieben. Aus der folgenden Grafik erkennt man aber einige nur für den Turbodecoder zutreffende Besonderheiten.

Iterativer Turbodecoder für die Rate R = 1/3

Vorausgesetzt ist ein Rate–1/3–Turbocode entsprechend der Beschreibung auf der ersten Seite dieses Abschnitts. Auch die Farbgebung für die Informationssequenz u und die beiden Paritysequenzen p1 und p2 sind an die früheren Grafiken angepasst. Weiter ist zu bemerken:

  • Die Empfangsvektoren y0, y1 und y2 sind reellwertig und liefern die jeweilige Soft–Information bezüglich der Sequenzen u (Information), p1 (Parity für Coder 1) und p2 (Parity für Coder 2).
  • Der Decoder 1 erhält die erforderliche intrinsische Information in Form der L–Werte LK,0 (aus y0) und LK,1 (aus y1) über jedes einzelne Bit der Sequenzen u und p1.
  • Beim zweiten Decoder ist auch die Verwürfelung der Informationssequenz u durch den Interleaver zu berücksichtigen. Die zu verarbeitenden L–Werte sind somit π(LK,0) und LK,2.
  • Beim allgemeinen SISO–Decoder am Ende von Kapitel 4.1 wurde der Informationsaustausch zwischen den beiden Komponentendecodern mit LA,2 = LE,1 sowie LA,1 = LE,2 angegeben. Ausgeschrieben auf Bitebene bedeuten diese Gleichungen mit 1 ≤ in:
\[L_{\rm A, \hspace{0.01cm}2}(i) = L_{\rm E, \hspace{0.01cm}1}(i) \hspace{0.5cm}{\rm bzw.}\hspace{0.5cm} L_{\rm A, \hspace{0.01cm}1}(i) = L_{\rm E, \hspace{0.01cm}2}(i) \hspace{0.03cm}.\]
  • Beim Turbodecoder muss bei diesem Informationsaustausch auch der Interleaver berücksichtigt werden. Dann gilt wieder für i = 1, ..., n:
\[L_{\rm A, \hspace{0.01cm}2}\left ({\rm \pi}(i) \right ) = L_{\rm E, \hspace{0.01cm}1}(i) \hspace{0.5cm}{\rm bzw.}\hspace{0.5cm} L_{\rm A, \hspace{0.01cm}1}(i) = L_{\rm E, \hspace{0.01cm}2}\left ({\rm \pi}(i) \right ) \hspace{0.05cm}.\]
  • Der Aposteriori–L–Wert wird in obigem Modell (willkürlich) vom Decoder 1 abgegeben. Dies lässt sich damit begründen, dass eine Iteration für einen zweifachen Informationsaustausch steht.

Leistungsfähigkeit der Turbocodes (1)


Wir betrachten wieder wie auf den letzten Seiten den Rate–1/3–Turbocode

  • mit gleichen Filterfunktionen G1(D) = G2(D) = (1 + D2)/(1 + D + D2)  ⇒  Gedächtnis m = 2,
  • mit der Interleavergröße K; zunächst gelte K = 10000,
  • eine ausreichende Anzahl an Iterationen (I = 20), hier nahezu gleichzusetzen mit „I → ∞”.

Die beiden RSC–Komponentencodes sind jeweils auf K Bit terminiert. Deshalb gruppieren wir

  • die Informationssequenz u zu Blöcken mit je K Informationsbits, und
  • die Codesequenz x zu Blöcken mit je N = 3 · K Codebits.

Die Grafik zeigt als grüne Kurve in doppelt–logarithmischer Darstellung die Blockfehlerwahrscheinlichkeit ⇒  Pr(Blockfehler) beim AWGN–Kanal in Abhängigkeit der Kenngröße 10 · lg(EB/N0). Man erkennt:

Bit– und Blockfehlerwahrscheinlichkeit von Turbodecodes
  • Die Daten entstammen dem Vorlesungsskript [Liv15][1]. Die mit Kreuzen markierten Punkte ergaben sich aus den Gewichtsfunktionen des Turbocodes mit Hilfe der Union Bound.
  • Simulationsergebnisse aus [Liv15] sind in der Grafik durch Kreise markiert. Sie sind nahezu deckungsgleich mit den berechneten Werten.
  • Die Union Bound ist nur eine obere Schranke, basierend auf ML–Decodierung. Der iterative Decoder ist suboptimal (also schlecher als ML). Diese beiden Effekte heben sich scheinbar auf.
  • Etwa bei 10 · lg(EB/N0) = 1 dB ist ein Knick im (grünen) Kurvenverlauf festzustellen, der mit der Steigungsänderung von Pr(Bitfehler)  ⇒  blaue Kurve korrespondiert. Die Erklärung folgt unten.

Die blauen Kreuze (Berechnung) und die blauen Kreise (Simulation) bezeichnen die Bitfehlerwahrscheinlichkeit. Als Vergleichskurve ist die (strichpunktierte) Kurve für uncodierte Übertragung eingezeichnet. Anzumerken ist:

  • Bei kleinen Abszissenwerten ist der Kurvenabfall in der gewählten Darstellung nahezu linear und ausreichend steil. Für Pr(Bitfehler) = 10–5 benötigt man 10 · lg(EB/N0) ≈ 0.8 dB.
  • Im Vergleich zur Shannon–Grenze, die sich für die Coderate R = 1/3 zu 10 · lg(EB/N0) ≈ –0.55 dB ergibt, liegt unser Standard–Turbocode (mit Gedächtnis m = 2) nur etwa 1.35 dB entfernt.
  • Ab 10 · lg(EB/N0) ≈ 0.5 dB verläuft die Kurve flacher. Ab ca. 1.5 dB ist der Verlauf wieder (fast) linear mit geringerer Steigung. Für Pr(Bitfehler) = 10–7 benötigt man etwa 10 · lg(EB/N0) = 3 dB.

Die Bildbeschreibung wird auf der nächsten Seite fortgesetzt.

Leistungsfähigkeit der Turbocodes (2)


Wir betrachten weiter die (blaue) Bitfehlerwahrscheinlichkeit für die Interleavergröße K = 10000 und versuchen, den flacheren Abfall bei größerem EB/N0 zu erklären. Man spricht von einem Error Floor.

Bit– und Blockfehlerwahrscheinlichkeit von Turbodecodes
  • Der Grund für dieses asymptotisch schlechtere Verhalten bei besserem Kanal (im Beispiel: ab ca. 10 · lg EB/N0 > 2 dB) ist die Periode P der Coderimpulsantwort g, wie auf der Seite Zweite Voraussetzung: Interleaving nachgewiesen.
  • Im Beispiel (m = 2) ist die Periode P = 2m = 3. Dadurch ist für u = (1, 1, 1)  ⇒  wH(u) = 3 trotz unbegrenzter Impulsantwort g die Paritysequenz begrenzt:   p = (1, 0, 1)  ⇒  wH(p) = 2.
  • Die Sequenz u = (0, ..., 0, 1, 0, 0, 1, 0, ...)  ⇒  U(D) = Dx · (1 + DP) führt ebenfalls zu einem kleinen Hamming–Gewicht wH(p) am Ausgang, was den iterativen Decodierprozess erschwert.
  • Eine gewisse Abhilfe schafft der Interleaver, der dafür sorgt, dass nicht die beiden Sequenzen p1 und p2 gleichzeitig durch sehr kleine Hamming–Gewichte wH(p1) und wH(p2) belastet sind.
  • Aus der Grafik erkennt man, dass Pr(Bitfehler) umgekehrt proportional zur Interleavergröße K ist. Das heißt: Bei großem K funktioniert die Entspreizung ungünstiger Eingangssequenzen besser.
  • Allerdings gilt die Näherung K · Pr(Bitfehler) = const. nur für größere EB/N0–Werte ⇒ kleinere Bitfehlerwahrscheinlichkeiten. Der oben beschriebene Effekt tritt zwar auch bei kleinerem EB/N0 auf, doch sind dann die Auswirkungen auf die Bitfehlerwahrscheinlichkeit geringer.

Dagegen gilt der flachere Verlauf der Blockfehlerwahrscheinlichkeit (grüne Kurve weitgehend unabhängig von der Interleavergröße K, also sowohl für K = 1000 als auch für K = 10000. Im Bereich ab 10 · lg EB/N0 > 2 dB dominieren aufgrund der kleinen Bitfehlerwahrscheinlichkeiten (< 10–5) nämlich Einzelfehler, so dass hier die Näherung Pr(Blockfehler) ≈ Pr(Bitfehler) · K gültig ist.

Die hier beispielhaft gezeigten Kurven für Bit– und Blockfehlerwahrscheinlichkeit gelten qualitativ auch für m > 2, zum Beispiel für den Turbocode von UMTS und LTE (jeweils m = 3), der in Aufgabe A4.10 analysiert wird. Es ergeben sich aber einige quantitative Unterschiede:

  • Die Kurve verläuft bei kleinem EB/N0 steiler und der Abstand von der Shannongrenze ist etwas geringer als im hier gezeigten Beispiel für m = 2.
  • Auch für größeres m gibt es einen Error Floor. Der Knick in den dargestellten Kurven erfolgt aber später, also bei kleineren Fehlerwahrscheinlichkeiten.

Seriell verkettete Turbocodes – SCCC


Die bisher betrachteten Turbocodes werden manchmal auch als Parallel Concatenated Convolutional Codes (PCCC) bezeichnet. Einige Jahre nach Berrou's Erfindung wurden von anderen Autoren auch Serial Concatenated Convolutional Codes (SCCC) entsprechend folgender Grafik vorgeschlagen.

  • Die Informationssequenz u liegt am äußeren Faltungscoder C1 an. Dessen Ausgangssequenz sei c.
  • Nach dem Interleaver (Π) folgt der innere Faltungscoder C2. Die Codesequenz wird x genannt.
  • Die resultierende Coderate ist R = R1 · R2. Bei Rate–1/2–Komponentencodes ist R = 1/4.

SCCC–Coder und –Decoder

Die untere Grafik zeigt den SCCC–Decoder und verdeutlicht die Verarbeitung der L–Werte und den Austausch der extrinsischen Information zwischen den beiden Komponentencoder:

  • Der innere Decoder (für den Code C2) erhält vom Kanal die intrinsische Information LK(x) und vom äußeren Decoder (nach Interleaving) die Apriori–Information LA(w) mit w = π(c). An den äußeren Decoder wird die extrinsische Information LE(w) abgegeben.
  • Der äußere Decoder (für C1) verarbeitet die Apriori–Information LA(c), also die extrinsische Information LE(w) nach dem De–Interleaving. Er liefert die extrinsische Information LE(c).
  • Nach hinreichend vielen Iterationen ergibt sich das das gewünschte Decodierergebnis in Form der Aposteriori–L–Werte LAPP(u) der Informationssequenz u.

Wichtig für seriell verkettete Faltungscodes ist, dass der innere Code rekursiv ist (also ein RSC–Code). Der äußere Code C1 kann auch nichtrekursiv sein. Zur Leistungsfähigkeit solcher Codes ist anzumerken:

  • SCCCs sind bei großem EB/N0 besser als PCCCs  ⇒  niedrigerer Error Floor. Die Aussage gilt schon für SCCC–Komponentencodes mit Gedächtnis m = 2 (nur vier Trelliszustände), während bei PCCC das Gedächtnis m = 3 bzw. m = 4 (acht bzw. sechzehn Trelliszustände) sein sollte.
  • Im unteren Bereich (kleines EB/N0) ist dagegen der beste seriell verkettete Faltungscode (SCCC) um einige Zehntel Dezibel schlechter als der vergleichbare Turbocode gemäß Berrou (PCCC). Entsprechend größer ist auch der Abstand von der Shannongrenze.

Einige Anwendungsgebiete für Turbocodes


Einige standardisierte Turbocodes im Vergleich zur Shannon–Grenze

In fast allen neueren Kommunikationssystemen (nach 1993 standardisiert) werden Turbocodes eingesetzt. Die Grafik zeigt deren Leistungsfähigkeit beim AWGN–Kanal im Vergleich zur Shannonschen Kanalkapazität (blaue Kurve).

Der grün hinterlegte Bereich „BPSK” gibt die Shannongrenze für Nachrichtensystemee mit binärem Eingang an, mit der nach dem Kanalcodierungstheorem eine fehlerfreie Übertragung gerade noch möglich ist.

Anzumerken ist, dass hier für die eingezeichneten Kanalcodes von standardisierten Systemen die Fehlerrate 10–5 zugrunde liegt, während die informationstheoretischen Kapazitätskurven (Shannon, BPSK) für die Fehlerwahrscheinlichkeit 0 gelten.

  • Die blauen Rechtecke markieren die Turbocodes für UMTS. Diese sind Rate–1/3–Codes mit Gedächtnis m = 3. Die Leistungsfähigkeit hängt stark von der Interleavergröße ab. Mit K = 6144 liegt dieser Code nur etwa 1 dB rechts von der Shannon–Grenze. LTE verwendet die gleichen Turbocodes. Geringfügige Unterschiede ergeben sich aufgrund des unterschiedlichen Interleavers.
  • Die roten Kreuze markieren die Turbocodes nach CCSDS (Consultative Comittee for Space Data Systems), entwickelt für den Einsatz bei fernen Weltraummissionen. Diese Klasse geht von der einheitlichen Interleavergröße K = 6920 aus und stellt Codes der Rate 1/6, 1/4, 1/3 und 1/2 zur Verfügung. Die niedrigsten Coderaten erlauben einen Betrieb mit 10 · lg (EB/N0) ≈ 0 dB.
  • Der grüne Kreis steht für einen sehr einfachen Repeat–Accumulate (RA) Code, einem seriell–verketteten Turbocode. Der äußere Decoder verwendet einen Wiederholungscode (englisch: Repetition Code), im gezeichneten Beispiel mit der Rate R = 1/3. Nach dem Interleaver folgt ein RSC–Code mit G(D) = 1/(1 + D)  ⇒  Gedächtnis m = 1. Bei systematischer Ausführung ist die Gesamtcoderate R = 1/4 (zu jedem Informationsbit noch drei Paritybits). Aus der oberen Grafik erkennt man, dass dieser einfache RA–Code überraschend gut ist. Mit der Interleavergröße <nobr>K = 300000</nobr> beträgt der Abstand von der Shannon–Grenze lediglich ca. 1.5 dB.

Repeat Accumulate (RA) Code der Rate 1/4

In der oberen Grafik nicht eingetragen sind die Turbocodes für den Standard DVB Return Channel Terrestrial (RCS) sowie für den WiMax–Standard (IEEE 802.16), die ähnliche Turbocodes benutzen.

Aufgaben


A4.8 Wiederholung zu den Faltungscodes

Zusatzaufgaben:4.8 Grundlegendes zum Interleaving

A4.9 Wiederholung zu den RSC-Codes

A4.10 UMTS/LTE–Turbocoder

Quellenverzeichnis

  1. Liva, G.: Channels Codes for Iterative Decoding. Vorlesungsmanuskript, Lehrstuhl für Nachrichtentechnik, TU München und DLR Oberpfaffenhofen, 2015.