Faltungscode
Faltungscodes (auch konvolutioneller Code; 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- bzw. Speicherfehler erreicht. Durch das namensgebende mathematische Verfahren der Faltung (auch Konvolution genannt) 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 k kleiner als n ist. Aufeinanderfolgende Codewörter sind voneinander abhängig, d. h. ein Faltungscodierer besitzt im Gegensatz zu Blockcodes ein inneres „Gedächtnis“. Da sich in der Praxis allerdings nur endlich lange Datensequenzen bearbeiten lassen, werden diese Sequenzen auf eine bestimmte Anzahl an Codewörtern limitiert. Danach wird der Faltungscodierer durch Terminierung wieder in einen 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 Faltungscodes wird die Information, die 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. 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
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 Codewort bilden. Dabei wird zwischen zwei wesentlichen Strukturen unterschieden:
- Nicht-rekursive Faltungscodierer
- Rekursive Faltungscodierer
Rekursive Faltungscodierer besitzen interne Rückkopplungsstellen, die 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 RSC-Encoder (Recursive Systematic Convolutional-Encoder) bezeichnet.
Die Unterteilung ist ähnlich motiviert wie bei den digitalen Filtern mit endlicher Impulsantwort (FIR) mit nicht-rekursiver Struktur bzw. den Filtern mit unendlicher Impulsantwort (IIR) mit rekursiver Struktur. 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 Lc. 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 Rc. Sie gibt das Verhältnis von der ganzzahligen Anzahl k der eingangsseitigen Informationsbits zu der ganzzahligen Anzahl n der ausgangsseitig erzeugten Codebits an:
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_c = \frac{k}{n}}
Rc 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 Lc zugeordnet, spricht man von symmetrischen Faltungscodes.
Terminierung
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:
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.
Grafische Darstellung
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 2z.
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.
Decodierung
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.
Punktierung
Bei Faltungscodes lässt sich durch eine sogenannte Punktierung des Codewortes gezielt eine bestimmte Coderate Rc 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.
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 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.
Literatur
- Martin Bossert: Kanalcodierung (= Informationstechnik). 2. vollständig neubearbeitete und erweiterte Auflage. B. G. Teubner, Stuttgart 1998, ISBN 3-519-16143-5.
- Karl-Dirk Kammeyer, Volker Kühn: MATLAB in der Nachrichtentechnik. J. Schlembach Fachverlag, Weil der Stadt 2001, ISBN 3-935340-05-2.
- Todd K. Moon: Error Correction Coding. Mathematical Methods and Algorithms. Wiley-Interscience, Hoboken NJ 2005, ISBN 0-471-64800-0.
