imported>Joschi71: /* Bedeutung */ Stil

2026-04-23T00:34:26Z

Bedeutung: Stil

Neue Seite

'''Faltungscodes''' (auch '''konvolutioneller Code'''; engl. ''Convolutional Code'') – ein Begriff der [[Kodierungstheorie|Codierungstheorie]] – werden, wie auch [[Blockcode]]s, in der [[Nachrichtentechnik]] zur [[Kanalkodierung]] eingesetzt, denn sie bieten eine [[Vorwärtsfehlerkorrektur]]. Dabei wird durch zusätzlich eingebrachte [[Redundanz (Informationstheorie)|Redundanz]] ein höherer Schutz gegen Übertragungs- bzw. Speicherfehler erreicht. Durch das namensgebende mathematische Verfahren der [[Faltung (Mathematik)|Faltung]] (auch Konvolution genannt) wird der Informationsgehalt der einzelnen [[Nutzdaten]]<nowiki/>stellen ü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 [[Satellit (Raumfahrt)|Satellitenübertragungen]] zur digitalen Datenübertragung eingesetzt. Sie finden aber auch bei Speichermedien wie [[Festplattenlaufwerk|Festplatten]] Anwendung und dienen dort dem Schutz gegen Lesefehler. Eine Kombination aus Faltungscodierung und digitaler [[Modulation (Technik)|Modulation]] ist die [[Trellis-Coded Modulation]].

Ein Faltungscodierer bildet dabei im Regelfall eingangsseitig ''k'' Informationsbits (Nutzdatenbits) auf ein ''n'' Bit langes [[Code]]wort 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 [[Faltungscode#Terminierung|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 [[Informationsgehalt]]es – man kann sich dies auch als eine Art „Verschmierung“ über einzelne Bits des Codewortes vorstellen – wird durch die mathematische Funktion der [[Faltung (Mathematik)|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 für deren Konstruktion kein systematisches Verfahren bekannt ist. 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 ==
[[Datei:Convolutional encoder 5 7 non recursive 2.svg|mini|Struktur eines nicht-rekursiven Faltungscodierers mit Rc = 1/2]]
[[Datei:Convolutional encoder recursive 2.svg|mini|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 Codewort bilden. Dabei wird zwischen zwei wesentlichen Strukturen unterschieden:

# Nicht-rekursive Faltungscodierer
# [[Rekursion|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 [[Filter mit endlicher Impulsantwort|Filtern mit endlicher Impulsantwort]] (FIR) mit nicht-rekursiver Struktur bzw. den [[Filter mit unendlicher Impulsantwort|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 ''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:

:<math>R_c = \frac{k}{n}</math>

''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-Code|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.

=== 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:

:<math>R_c^\text{tail} = R_c \cdot \frac{1}{k} \cdot \left(1 - \frac{L_c - 1}{N}\right)</math>

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

=== Grafische Darstellung ===
[[Datei:Trellis state.svg|mini|Zustandsübergangsdiagramm eines nicht-rekursiven Faltungscode mit zwei Speichern]]
[[Datei:Convolutional code trellis diagram.svg|mini|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 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-Algorithmus|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 [[Binary Symmetric Channel|binäre]], sondern auch [[Kanalkapazität#AWGN-Kanal|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 [[BCJR-Algorithmus|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 ''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.

=== 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-Code]]s. 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 ==
* {{Literatur
|Autor = [[Martin Bossert]]
|Titel = Kanalcodierung
|Reihe = Informationstechnik
|Verlag = B. G. Teubner|Ort= Stuttgart |Auflage=2. vollständig neubearbeitete und erweiterte |Jahr = 1998 |ISBN = 3-519-16143-5
}}
* {{Literatur
|Autor = [[Karl-Dirk Kammeyer]], Volker Kühn
|Titel = MATLAB in der Nachrichtentechnik
|Verlag = J. Schlembach Fachverlag |Ort=Weil der Stadt |Jahr = 2001 |ISBN = 3-935340-05-2
}}
* {{Literatur
|Autor = Todd K. Moon
|Titel = Error Correction Coding. Mathematical Methods and Algorithms
|Verlag = Wiley-Interscience |Ort=Hoboken NJ |Jahr = 2005 | ISBN = 0-471-64800-0
}}

== Weblinks ==
* [http://home.netcom.com/~chip.f/Viterbi.html Erklärung des Faltungscodes mit Viterbi-Algorithmus] (englisch)
* {{Webarchiv|url=http://www.tu-chemnitz.de/informatik/ThIS/downloads/courses/ss03/kv/Faltungscodes.pdf|text=Erklärung des Faltungscodes mit Viterbi-Algorithmus mit detailliertem Beispiel|wayback=20160418104609|format=PDF; 548 kB}}

[[Kategorie:Theoretische Informatik]]
[[Kategorie:Kodierungstheorie]]

Faltungscode - Versionsgeschichte

imported>Joschi71: /* Bedeutung */ Stil