Grundlegendes zu den Turbocodes

1. Kanalcodierung
2. Iterative Decodierverfahren
3. Grundlegendes zu den Turbocodes

• Vorherige Seite
• Nächste Seite

• Vorherige Seite
• Nächste Seite

Grundstruktur eines Turbocodes (1)

Alle heute (2016) aktuellen Kommunikationssysteme wie UMTS (3. Mobilfunkgeneration) und LTE <nobr>(4. Mobilfunkgeneration)</nobr> 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.

In dieser Darstellung bezeichnet:

• u das aktuell betrachtete Bit der Informationssequenz u,
  

• x_i,j das aktuell betrachtete Bit am Ausgang j von Coder i   (mit 1 ≤ i ≤ 2, 1 ≤ j ≤ 2),
  

• X = (x_1,1, x_1,2, x_2,1, x_2,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:

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

• Bei systematischen Codes C₁ und C₂ ist sowohl x_1,1 = u als auch x_2,1 = u. Deshalb kann man auf die Übertragung eines redundanten Bits (zum Beispiel x_2,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 p₁ und p₂ 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 = (u₁, u₂, ... , u_i, ... ) an.
  

• Die Codewortsequenz wird mit x = (X₁, X₂, ... , X_i, ... ) bezeichnet. Um Verwechslungen zu vermeiden, wurden vorne die Codeworte X_i = (u, p₁, p₂)_i mit Großbuchstaben eingeführt.
  

• Die Coder C₁ und C₁ werden (gedanklich) als Digitale Filter konzipiert und sind somit durch die Übertragungsfunktionen G₁(D) und G₂(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: G₁(D) = G₂(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äß G₁(D) = G₂(D) = 1 + D²  ⇒  siehe Aufgabe A4.8.
   

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, g₂, ... , g_m, 0, 0, ... ) mit g₂, ... , g_m ∈ {0, 1}. Hierbei bezeichnet m das Codegedächtnis.

Die Grafik zeigt das Zustandsübergangsdiagramm für das Beispiel G(D) = [1, 1 + D²]. Die Übergänge sind mit „u_i | u_i p_i” beschriftet. Die Abfolge S₀ → S₁ → S₂ → S₀ → S₀ → S₀ → ... 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.

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

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 G₁(D) = G₂(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 = u ∗ g mit geringem Hamming–Gewicht w_H(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 w_H(p) gekennzeichnet ist.
  
  

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

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

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 I_max = S · Z Bit deterministisch verwürfelt.

Die Grafik verdeutlicht das Prinzip für I_max = 64  ⇒  1 ≤ I_In < 65 und <nobr>1 ≤ I_Out < 65.</nobr> 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.

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 I_Out(I_In) für I_max = 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.