Faltungscode

Faltungscodes (engl. Convolutional Code) sind in der Codierungstheorie eingesetzte Codes zur Kanalkodierung und stellen in der Nachrichtentechnik neben den Blockcodes eine Möglichkeit zur Vorwärtsfehlerkorrektur dar. 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

Faltungscode 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 einer Faltungscodierung und einer digitalen Modulation stellt die Trellis-Coded Modulation dar.

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 befindet sich der Faltungscodierer wieder in einem definierten Zustand welcher 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 weitere Kriterium ist die Anzahl der Nutzdatenbits kleiner als die Anzahl der Bits des Codewortes auf welches diese Information abgebildet wird. Dadurch ergibt sich eine Redundanz. 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 ermittelt.

Ein wesentliche Besonderheit bei Faltungscode besteht darin, dass es für deren Konstruktion kein bekanntes systematisches Verfahren gibt. Faltungscodes werden primär durch rechenaufwendige Simulationen und das Duchprobieren sehr vieler unterschiedlicher Faltungsstrukturen, oder auch durch zufällige Entdeckungen, gewonnen. Die Mehrzahl der dabei durchprobierten Strukturen liefert so genannte katastrophale Faltungscodes welche 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 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 welches seriell die Nutzdatenbits geschoben werden und einer kombinatorischen Struktur aus logischen XOR-Verknüpfungen welche 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. Die damit erzeugten Faltungscodes werden in der Literatur als RCS-Code (Recursive Systematic Convolutional-Code) 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 Faltungscodes ausser groben Ähnlichkeiten in der Struktur nichts mit digitalen Filtern im Speziellen zu tun.

Parameter

Aus der Struktur eines Faltungscodiereres 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.

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össer 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 Faltungscode 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 bespielsweise bei der Trellis-Code-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 Praxis sind nur Nutzdatensequenzen mit endlicher Länge von Bedeutung. Diese Beschränkung, auch Terminierung (engl: Truncating oder Tail-Biting) 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 dem so genannten Nullzustand, welcher 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

Datei:Trellis state.png

Zustandsübergangsdiagramm eines nicht rekursiven Faltungscode mit zwei Zustandsspeichern

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 nebenstehener Abbildung für zwei Zustandsspeicher mit vier Zuständen abgebildet ist. Die Anzahl der Zustände ergibt sich allgemein bei binären Code aus der Anzahl z der Zustandsspeicher zu 2^z.

Der Nachteil der Darstellungsform mittels Zustandsübergangsdiagramm ist der fehlende zeitliche Bezug. Der fehlende zeitliche Bezug bei der seriellen Decodierung kann durch ein Trellis-Diagramm visualisiert werden. Ein Trellis-Diagramm ist die Darstellung eines Zustandsübergangsdiagrammes welches über die Zeitachse „abgerollt“ wird. Im Rahmen des Trellis-Diagrammes lässen sich auch die Decodierungsprozesse von Faltungscode 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, welcher 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.

Bei Faltungscodes mit hoher Einflusslänge wächsen allerdings die Anzahl der Zustände im Trellis-Diagramm exponentiell und diese Darstellung samt dem Übergangskanten wird schnell unübersichtlich. Das Trellis-Diagramm dient daher zur Darstellungen des Decodierungsprozesses mittels Viterbi-Alorithmus bei beispielhaften Faltungscodes mit geringer Einflusslänge zur grafischen Veranschaulichung der Abläufe.

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 mit fix definierten Werten besetzt und daher weggelassen. Der Decoder muss diese bekannten Stellen vor dem Decodierungsprozess dem Codewort wieder 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

Eine Erweiterung stellen so genannte verkettete Faltungscodes dar. 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ässige Verteilung von Fehlern auf die unterschiedlichen Codes ermöglicht und eine Art Entkopplung der Teilcodes ergibt. Damit kann ein grösserer Codegewinn erreicht werden als wie die Summe der einzelnen Faltungscodes für sich alleine.

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

Literatur

• 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)