Grundlagen der Faltungscodierung

Voraussetzungen und Definitionen

Wir betrachten in diesem Kapitel eine unendlich lange binäre Informationssequenz u und unterteilen diese in Informationsblöcke u_i zu je k Bit. Man kann diesen Sachverhalt wie folgt formalisieren:

\[\underline{\it u} = \left ( \underline{\it u}_1, \underline{\it u}_2, ... \hspace{0.1cm}, \underline{\it u}_i , ... \hspace{0.1cm}\right ) \hspace{0.3cm}{\rm mit}\hspace{0.3cm} \underline{\it u}_i = \left ( u_i^{(1)}, u_i^{(2)}, ... \hspace{0.1cm}, u_i^{(k)}\right )\hspace{0.05cm},\]

\[u_i^{(j)}\in {\rm GF(2)}\hspace{0.3cm}{\rm f\ddot{u}r} \hspace{0.3cm}1 \le j \le k \hspace{0.5cm}\Rightarrow \hspace{0.5cm} \underline{\it u}_i \in {\rm GF}(2^k)\hspace{0.05cm}.\]

Im Englischen bezeichnet man eine solche Sequenz ohne negative Indizes als semi–infinite.

: Bei einem binären Faltungscode (englisch: Binary Convolutional Code) wird zu dem Taktzeitpunkt i ein Codewort x_i bestehend aus n Codebits ausgegeben:

\[\underline{\it x}_i = \left ( x_i^{(1)}, x_i^{(2)}, ... \hspace{0.1cm}, x_i^{(n)}\right )\in {\rm GF}(2^n)\hspace{0.05cm}.\]

Dieses ergibt sich entsprechend

den k Bit des aktuellen Informationsblockes u_i, und

den m vorherigen Informationsblöcken u_i–1, ... , u_i–m.

Die folgende Grafik verdeutlicht diesen Sachverhalt für die Parameter k = 4, n = 7, m = 2 und i = 4. Die n = 7 zum Zeitpunkt i = 4 erzeugten Codebits x₄⁽¹⁾, ... , x₄⁽⁷⁾ können (direkt) von den k · (m + 1) = 12 rot markierten Informationsbits abhängen und werden durch Modulo–2–Additionen erzeugt.

Gelb eingezeichnet ist zudem ein (n, k)–Faltungscodierer. Zu beachten ist, dass sich der Vektor u_i und die Sequenz u⁽ⁱ⁾ grundlegend unterscheiden. Während u_i = (u_i⁽¹⁾, u_i⁽²⁾, ... , u_i^(k)) die k zum Zeitpunkt i parallel anliegenden Informationsbits zusammenfasst, bezeichnet u⁽ⁱ⁾ = (u₁⁽ⁱ⁾, u₂⁽ⁱ⁾, ...) die (horizontale) Sequenz am i–ten Eingang des Faltungscodierers. Für den Faltungscode gelten folgende Definitionen:

Die Coderrate ergibt sich wie bei den Blockcodes zu R = k/n.

Man bezeichnet m als das Gedächtnis (englisch: Memory) des Codes und den Convolutional Code selbst mit CC(n, k, m).

Daraus ergibt sich die Einflusslänge (englisch: Constraint Length) zu ν = m + 1.

Für k > 1 gibt man diese Parameter oft auch in Bit an: m_Bit = m · k bzw. ν_Bit = (m + 1) · k.

Gemeinsamkeiten und Unterschiede gegenüber Blockcodes

Aus der Definition auf der letzten Seite ist ersichtlich, dass ein binärer Faltungscode mit m = 0 (also ohne Gedächtnis) identisch wäre mit einem binären Blockcode wie in Kapitel 1 beschrieben. Wir schließen diesen Grenzfall aus und setzen deshalb für das Folgende stets voraus:

Das Gedächtnis m sei größer oder gleich 1.

Die Einflusslänge ν sei größer oder gleich 2.

: Bei einem (7, 4)–Blockcode hängt das Codewort x₄ nur vom Informationswort u₄ ab, nicht jedoch von u₂ und u₃, wie bei dem beispielhaften Faltungscodes (mit m = 2) auf der letzten Seite.

Gilt beispielsweise x₄⁽¹⁾ = u₄⁽¹⁾, x₄⁽²⁾ = u₄⁽²⁾, x₄⁽³⁾ = u₄⁽³⁾, x₄⁽⁴⁾ = u₄⁽⁴⁾ sowie

\[x_4^{(5)} = u_4^{(1)}+ u_4^{(2)}+u_4^{(3)}\hspace{0.05cm} ,\hspace{0.3cm} x_4^{(6)} = u_4^{(2)}+ u_4^{(3)}+u_4^{(4)}\hspace{0.05cm} ,\hspace{0.3cm} x_4^{(7)} = u_4^{(1)}+ u_4^{(2)}+u_4^{(4)}\hspace{0.05cm} ,\]

so handelt es sich um einen so genannten systematischen Hamming–Code (7, 4, 3) entsprechend Kapitel 1.3. In der Grafik sind diese speziellen Abhängigkeiten für x₄⁽¹⁾ und x₄⁽⁷⁾ rot eingezeichnet.

In gewisser Weise könnte man auch einen (n, k)–Faltungscode mit Gedächtnis m ≥ 1 als Blockcode interpretieren, dessen Codeparameter n' >> n und k' >> k allerdings sehr viel größere Werte annehmen müssten als die des vorliegenden Faltungscodes. Aufgrund der großen Unterschiede in der Beschreibung, in den Eigenschaften und insbesondere bei der Decodierung betrachten wir aber Faltungscodes in diesem Lerntutorial als etwas völlig Neues. Hierfür sprechen folgende Gründe:

Ein Blockcodierer setzt Informationsworte der Länge k Bit blockweise in Codeworte mit n Bit um. Der Blockcode ist dabei um so leistungsfähiger, je größer seine Codewortlänge n ist. Bei gegebener Coderate R = k/n erfordert dies auch eine große Informationswortlänge k.

Dagegen wird die Korrekturfähigkeit eines Faltungscodes im wesentlichen durch sein Gedächtnis m bestimmt. Die Codeparameter k und n werden hier meist sehr klein gewählt (1, 2, 3, ...). Von praktischer Bedeutung sind somit nur ganz wenige und zudem sehr einfache Faltungscodes.

Auch schon bei kleinen Werten für k und n überführt ein Faltungscoder eine ganze Sequenz von Informationsbits (k' → ∞) in eine sehr lange Sequenz von Codebits (n' = k'/R). Ein solcher Code bietet somit oft ebenfalls eine große Korrekturfähigkeit.

Es gibt effiziente Faltungsdecoder ⇒ Viterbi–Algorithmus bzw. BCJR–Algorithmus. Diese können Soft–Decision–Input (Zuverlässigkeitsinformationen über den Kanal) einfach verarbeiten und liefern auch Soft–Decision–Output (Zuverlässigkeitsinformation über das Decodierergebnis).