Faltungscode

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 eines Faltungscodes ist seine Coderate R_c. Sie gibt das Verhältnis von der ganzzahligen Anzahl k der eingangsseitigen Informationsbits zu der ganzzahligen Anzahl n der ausgangsseitig erzeugten Codebits an:

${\displaystyle 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 eine Faltungscodierung zugeordnet werden. In diesem Fall spricht man von asymmetrischen Faltungscodes. Diese Verfahren werden beispielsweise bei der Trellis-Codierten-Modulation als wesentlicher Bestandteil verwendet. Werden hingegen alle Nutzdatenbits jeweils eigenen Schieberegisterketten der Gedächtnisordnung L_c zugeordnet, spricht man von symmetrischen Faltungscodes.

In praktischen Anwendungen sind nur Nutzdatensequenzen mit endlicher Länge von Bedeutung. Dies macht eine sogenannte Terminierung (engl.: Termination) der Sequenz notwendig. Man bezeichnet hiermit das Zurückführen des Encoders in einen definierten Endzustand. Falls keine Terminierung am Ende der Nutzdatensequenz vorgenommen wird, wirkt sich dies wesentlich auf die Korrekturfähigkeit bei der Decodierung aus. Ist dem Decodierer der Endzustand einer Sequenz nämlich nicht bekannt, kann er die letzten Informationsbits nur sehr unsicher abschätzen, was eine gesteigerte Fehlerwahrscheinlichkeit zur Folge hat. Ist der Endzustand und die Sequenzlänge N hingegen bekannt und zwischen Encoder und Decoder vereinbart, kann die Bestimmung der letzten Stellen einer Nutzdatensequenz auf Decoderseite sicher erfolgen.

Im Falle von nicht-rekursiven Faltungscodes werden typischerweise an das Ende einer Nutzdatensequenz eine Folge von logisch-0 Bits angehängt. Dieser sogenannte Tail führt den Encoder in einen definierten Endzustand, den so genannten Nullzustand, zurück, der 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:

${\displaystyle R_{c}^{\text{tail}}=R_{c}\cdot {\frac {1}{k}}\cdot \left(1-{\frac {L_{c}-1}{N}}\right)}$

Im Falle von rekursiven Faltungscodes hängt der Tail von den vorherigen Nutzdaten ab.

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 mit dem Viterbi-Algorithmus anschaulich darstellen: Dabei bekommen die einzelnen Übergänge von einem Zustand in den nächsten verschiedene Wahrscheinlichkeitswerte zugeordnet, wodurch in sich in der Folge ü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.

In der Regel kommt für die Decodierung von Faltungscodes der Viterbi-Decoder zum Einsatz. Dieses Verfahren basiert wie erwähnt auf der Trellis-Darstellung des Codes und bestimmt für eine gestörte Codesequenz die wahrscheinlichste zugehörige Nutzdaten- oder Codesequenz. Der Viterbi-Decoder kann dabei nicht nur binäre, sondern auch kontinuierliche Eingangssequenzen verarbeiten. Man spricht dann von Hard- bzw. Soft-Decision-Decodierung. Generell lassen sich Soft-Decision-Decoder für Faltungs-Codes leichter realisieren als dies bei Block-Codes der Fall ist.

Der klassische Viterbi-Decoder gibt binäre Sequenzen aus – für verschiedene Anwendungen ist es jedoch wichtig, nicht nur die einzelnen decodierten Bits zu kennen, sondern auch deren Zuverlässigkeit. Das Erzeugen dieser Zuverlässigkeiten kann beispielsweise mit Hilfe eines modifizierten Viterbi-Decoders, dem sogenannten Soft-Output-Viterbi-Algorithmus (SOVA), oder dem MAP/BCJR-Algorithmus erfolgen.

Für Codes mit sehr großen Gedächtnisordnungen wird das Trellis sehr komplex und eine trellisbasierte Decodierung mittels Viterbi-Decoder damit sehr aufwendig. In diesem Fall können alternativ sequentielle, suboptimale Decodierer verwendet werden, welche auf der Darstellung des Codebaums arbeiten.

Bei Faltungscodes lässt sich durch eine sogenannte Punktierung des Codewortes gezielt eine bestimmte Coderate R_c wählen. Bei der Punktierung werden bestimmte Bitpositionen des Codewortes weggelassen(„punktiert“) und dadurch die Coderate erhöht. Der Decoder muss dieses sogenannte Punktierungsschema kennen und bei der Decodierung berücksichtigen.

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.

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 die Summe der einzelnen Faltungscodes für sich alleine.

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