Faltungs-Code

Faltungscodes (engl. Convolutional Code) - ein Begriff der Codierungstheorie - werden, wie auch Blockcodes, in der Nachrichtentechnik zur Kanalkodierung eingesetzt, denn sie bieten eine Vorwärtsfehlerkorrektur. Dabei wird durch zusätzlich eingebrachte Redundanz ein höherer Schutz gegen Übertragungs- beziehungsweise Speicherfehler erreicht. Durch das namensgebende, mathematische Verfahren der Faltung wird der Informationsgehalt der einzelnen Nutzdatenstellen über mehrere Stellen des Codewortes verteilt.

Faltungscodes haben nichts mit der ähnlich klingenden Code-Faltung zu tun.

Bedeutung

Faltungscodes werden beispielsweise im Mobilfunk und bei Satellitenübertragungen zur digitalen Datenübertragung eingesetzt. Sie finden aber auch bei Speichermedien wie Festplatten Anwendung und dienen dort zum Schutz gegen Lesefehler. Eine Kombination aus Faltungscodierung und digitaler Modulation ist die Trellis-Coded Modulation.

Ein Faltungscodierer bildet dabei im Regelfall eingangsseitig k Informationsbits (Nutzdatenbits) auf ein n Bit langes Codewort ab, wobei aufeinanderfolgende Codewörter voneinander abhängig sind. Ein Faltungscodierer besitzt damit im Gegensatz zu Blockcodes ein inneres „Gedächtnis“. Da sich in Praxis allerdings nur endlich lange Datensequenzen bearbeiten lassen, werden diese Sequenzen auf eine bestimmte Anzahl an Codewörter limitiert. Danach wird der Faltungscodierer durch Terminierung wieder in einem definierten Zustand gebracht, der meist gleich dem Ausgangszustand ist. Daher lassen sich übliche Faltungscodes auch als eine Form von speziellen, nicht-systematischen Blockcodes beschreiben.

Bei diesem Code wird die Information welche ein bestimmtes Nutzdatenbit trägt, über mehrere Stellen (Bits) des Codewortes verteilt. Die Verteilung des Informationsgehaltes, man kann sich dies auch als eine Art „Verschmierung“ über einzelne Bits des Codewortes vorstellen, wird durch die mathematische Funktion der Faltung erreicht. Als weiteres Kriterium ist die Anzahl der Nutzdatenbits kleiner als die Anzahl der Bits des Codewortes auf welches diese Information abgebildet wird. Dadurch entstehen Abhängigkeiten zwischen den einzelnen Codebits. Werden durch Fehler einzelne Stellen des Codewortes verfälscht, wobei die Anzahl der Fehler pro Codewort eine bestimmte obere Grenze nicht überschreiten darf, kann der Faltungsdecodierer, durch die über mehrere Stellen verteilte Information, die korrekte Nutzdatenfolge aus den um die Fehlerstelle benachbarten Stellen des Codewortes ermitteln.

Eine wesentliche Besonderheit von Faltungscodes ist, dass es für deren Konstruktion kein bekanntes systematisches Verfahren gibt. Faltungscodes werden primär durch rechenaufwendige Simulationen und das Durchprobieren sehr vieler unterschiedlicher Faltungsstrukturen, oder auch durch zufällige Entdeckungen, gewonnen. Die Mehrzahl der dabei durchprobierten Strukturen liefert so genannte katastrophale Faltungscodes, die bestimmte Übertragungsfehler nicht korrigieren, sondern durch eine theoretisch unendlich lange Folge von Fehlern ersetzen. Daher existieren im Vergleich zu den Blockcodes nur sehr wenige in der Praxis relevante und verwertbare Faltungscodes. Dafür sind für die Decodierung von Faltungscodes mittels so genannter Soft-Decision sehr leistungsfähige Verfahren in Form des Viterbi-Algorithmus bekannt.

Beschreibung

Struktur eines nicht rekursiven Faltungscodierers mit R_c=1/2

Rekursiver Faltungscodierer mit einer Rückkopplung

Ein Faltungscodierer lässt sich durch ein Schieberegister beschreiben, in das seriell die Nutzdatenbits geschoben werden und einer kombinatorischen Struktur aus logischen XOR-Verknüpfungen, die das ausgangsseitige Codeword bilden. Dabei wird zwischen zwei wesentlichen Strukturen unterschieden:

1. Nicht rekursive Faltungscodierer
2. Rekursive Faltungscodierer

Rekursive Faltungscodierer besitzen interne Rückkopplungsstellen welche zu unendlich langen Ausgabefolgen führen können. Rekursive Faltungsstrukturen lassen sich systematisch aus den nicht rekursiven Faltungsstrukturen gewinnen. Diese Kodierer werden in der Literatur als RCS-Encoder (Recursive Systematic Convolutional-Encoder) bezeichnet.

Die Unterteilung ist ähnlich motiviert wie bei den digitalen Filter mit endlicher Impulsantwort (FIR) mit einer nicht rekursiven Struktur und den Filter mit unendlicher Impulsantwort (IIR) mit rekursiven Strukturen. Allerdings haben Faltungscodierer außer groben Ähnlichkeiten in der Struktur nichts mit digitalen Filtern im Speziellen zu tun.

Parameter

Aus der Struktur eines Faltungscodierers ergibt sich die Einflusslänge oder auch Gedächtnisordnung L_c. Sie beschreibt die Anzahl der Takte die ein Eingangsbit (Nutzdatenbit) benötigt um alle Stellen des Schieberegisters zu durchlaufen und somit ein Einfluss eines bestimmten Nutzdatenbits auf das ausgangsseitige Codewort vorliegt. Bei nicht rekursiven Faltungscodierern entspricht sie der Anzahl der Speicherelemente des Faltungscodierers.

Ein weiterer Parameter von Faltungscode ist die Coderate R_c. Sie gibt das Verhältnis von der ganzzahligen Anzahl k der eingangsseitige Informationsbits zu der ganzzahligen Anzahl n der ausgangsseitigen erzeugten Codebits an:

$R_c = \frac{k}{n}$

R_c ist dabei immer kleiner gleich 1. Dabei kann die Anzahl k der eingangsseitigen Informationsbit auch größer 1 sein. In diesem Fall werden pro Takt mehrere Nutzdatenbits parallel an den Encoder geschickt. Die ebenfalls parallel abzugreifenden ausgangsseitigen n Codebits werden durch einen Multiplexer in einen seriellen Datenstrom mit entsprechend höherer Taktrate umgewandelt.

Bei bestimmten Faltungscodes können einzelne eingangsseitige Nutzdatenbits auch direkt bestimmten ausgangsseitigen Codebits ohne einer Faltungscodierung zugeordnet werden. In diesem Fall spricht man von asymmetrischen Faltungscodes. Diese Verfahren werden beispielsweise bei der Trellis-Codierter-Modulation als wesentlicher Bestandteil verwendet. Werden hingegen alle Nutzdatenbits jeweils eigenen Schieberegisterketten der Gedächtnisordnung L_c zugeordnet, spricht man von symmetrischen Faltungscodes.

Terminierung

In praktischen Anwendungen sind nur Nutzdatensequenzen mit endlicher Länge von Bedeutung. Diese Beschränkung, auch Terminierung (engl: Truncation) genannt, wirkt sich wesentlich auf die Korrekturfähigkeit bei der Decodierung von Faltungscodes aus. Ist dem Decodierer der Endzustand einer Sequenz nicht bekannt, kann er die letzten Informationsbits nur sehr unsicher abschätzen und eine gesteigerte Fehlerwahrscheinlichkeit ist die Folge. Ist der Endzustand und die Sequenzlänge N bekannt und zwischen Encoder und Decoder vereinbart, kann die Bestimmung der letzten Stellen einer Nutzdatensequenz auf Decoderseite sicher erfolgen.

Typischerweise werden an das Ende einer Nutzdatensequenz eine Folge von logisch-0 Bits angehängt. Diese führen den Encoder in einen definierten Endzustand über, in der Regel in den so genannten Nullzustand, der aufgrund der Vereinbarung auch dem Decoder bekannt ist. Durch diese zusätzlichen Terminierungsstellen am Ende verlängert sich allerdings die Nutzdatensequenz, und die Coderate reduziert sich auf den Wert:

$R_c^{tail} = R_c \cdot \frac{1}{k} \cdot \left(1 - \frac{L_c - 1}{N}\right)$

Grafische Darstellung

Zustandsübergangsdiagramm eines nicht rekursiven Faltungscode mit zwei Speichern

Trellis-Diagramm mit vier Zuständen über fünf Zeitpunkte. Rot eingezeichnet ist ein möglicher Entscheidungsweg.

Ein Faltungscodierer kann als endlicher Automat mittels Zustandsübergangsdiagramm interpretiert werden, wie er in nebenstehender Abbildung für zwei Speicher mit vier Zuständen abgebildet ist. Die Anzahl der Zustände ergibt sich allgemein bei binärem Code aus der Anzahl z der Zustandsspeicher zu 2^z.

Der Nachteil der Darstellungsform mittels Zustandsübergangsdiagramm ist der fehlende zeitliche Bezug. Dieser fehlende zeitliche Bezug bei der seriellen Decodierung kann durch ein Trellis-Diagramm (kurz Trellis) visualisiert werden. Ein Trellis-Diagramm ist die Darstellung eines Zustandsübergangsdiagramms, das über die Zeitachse „abgerollt“ wird. Im Rahmen des Trellis-Diagramms lassen sich auch die Decodierungsprozesse von Faltungscodes mittels dem Viterbi-Algorithmus anschaulich darstellen: Dabei bekommen die einzelnen Übergänge von einem Zustand in den nächsten verschiedene Wahrscheinlichkeitswerte zugeordnet, wodurch in Folge sich über mehrere Zustände hinweg meist eindeutig ein einziger Pfad im Trellis herausbildet, der die geringste Summenfehlerwahrscheinlichkeit gegenüber allen anderen Pfaden aufweist. Die diesem Pfad zugeordneten Symbole werden dann vom Decoder als die am wahrscheinlichsten gesendeten Symbole angesehen und die zugeordneten Informationsbits zur weiteren Verarbeitung ausgegeben (MLSE = Maximum Likelihood Sequence Estimation).

Bei Faltungscodes mit hoher Einflusslänge wachsen allerdings die Anzahl der Zustände im Trellis-Diagramm exponentiell und diese Darstellung samt den Übergangskanten wird schnell unübersichtlich. Das Trellis-Diagramm dient daher zur Darstellung des Decodierungsprozesses mittels Viterbi-Algorithmus bei beispielhaften Faltungscodes mit geringer Einflusslänge.

Decodierung

Neben dem schon erwähnten Viterbi-Algorithmus existieren für eine effizientere Soft-Decodierung (engl. soft decision) weitere Algorithmen wie der BCJR-Algorithmus und der Soft-Output-Viterbi-Algorithmus (SOVA). Für sehr große Gedächtnisordnungen können alternativ sequentielle Decodierer verwendet werden welche bereits vor der Terminierung mit der Decodierung beginnen. Dabei sollte eine so genannte Rückgrifftiefe K des sequentiellen Decoders von K ≈ 5*L_c eingehalten werden.

Generell lassen sich Faltungsdecoder, welche mittels Soft-Decodierung arbeiten, also einzelnen Symbolwahrscheinlichkeitswerten arbeiten, leichter realisieren als dies bei den Block-Codes der Fall ist.

Punktierung

Bei Faltungscodes lässt sich durch eine so genannte Punktierung des Codewortes gezielt eine bestimmte Coderate R_c wählen. Bei der Punktierung werden bestimmte Bitpositionen des Codewortes weggelassen. Der Decoder muss diese bekannten Stellen vor dem Decodierungsprozess dem Codewort entsprechend hinzufügen.

Der Grund für Punktierung liegt darin, die Codewortlängen genau auf eine bestimmte Rahmenlänge für die nachfolgende Datenübertragung bzw. Datenspeicherungen auszulegen. Durch das Weglassen einzelner Stellen des Codewortes kommt es allerdings auch zu einer Reduktion der Korrekturleistung.

Erweiterung

Die Erweiterung sind verkettete Faltungscodes. Dabei werden mehrere unterschiedliche oder auch gleiche Faltungscodes seriell oder parallel miteinander verkettet. Die Verkettung der einzelnen Codes erfolgt über eine Funktion die als Interleaver bezeichnet wird und eine gleichmäßige Verteilung von Fehlern auf die unterschiedlichen Codes ermöglicht und eine Art Entkopplung der Teilcodes ergibt. Damit kann ein größerer Codegewinn erreicht werden als wie die Summe der einzelnen Faltungscodes für sich alleine.

Eine spezielle Form der Codeverkettung ist die Turbo-Codes. Eine Untergruppe der Turbo-Codes, die so genannten Turbo-Convolutional-Codes (TCC), basieren auf den rekursiven RCS-Faltungscodes. Nicht rekursive Faltungscodes weisen bei den TCC nicht die gleichen Verbesserung im Codegewinn auf.

Literatur

• Martin Bossert: Kanalcodierung. B.G. Teubner Stuttgart, 1998, ISBN 3-519-16143-5. 
• Karl Dirk Kammeyer: MATLAB in der Nachrichtentechnik. J. Schlembach Fachverlag, 2001, ISBN 3-935340-05-2. 
• Todd K. Moon: Error correction coding: mathematical methods and algorithms. John Wiley & Sons, 2005, ISBN 0-471-64800-0. 

Weblinks

• Erklärung des Faltungscodes mit Viterbi-Algorithmus (englisch)