Faltungscode und Viterbi-Decodierung

Alle bisherigen Fehlerkorrekturcodes dieser Serie — Hamming, BCH, Golay — sind Blockcodes: Ein fester Block von $k$ Nutzdatenbits wird zu einem festen Codewort von $n$ Bits kodiert, unabhängig von allen anderen Blöcken davor oder danach. Der Faltungscode (Convolutional Code) verfolgt einen grundsätzlich anderen Ansatz: Er hat ein Gedächtnis. Jedes Ausgangsbit hängt nicht nur vom aktuellen Eingangsbit ab, sondern auch von den letzten paar vorangegangenen — der Coder "faltet" die Eingangsfolge kontinuierlich mit einer festen Regel, daher der Name.

1. Aufbau eines Faltungscoders

Ein Faltungscoder besteht aus einem Schieberegister, durch das die Eingangsbits laufen, und mehreren Generatorpolynomen, die per XOR-Verknüpfung aus dem aktuellen Registerinhalt die Ausgangsbits berechnen. Zwei Kenngrößen bestimmen den Code:

• Rate $r = k/n$: Für jedes Eingangsbit werden $n$ Ausgangsbits erzeugt (bei Rate $1/2$: zwei Ausgangsbits pro Eingangsbit — mehr Redundanz, mehr Fehlerschutz).
• Constraint Length $K$: Die Anzahl der Bits (aktuelles Bit plus Vorgeschichte), die jedes Ausgangsbit beeinflussen. Mit $K-1$ Speicherbits ergeben sich $2^{K-1}$ mögliche Zustände des Coders.

Für diesen Artikel dient der klassische Lehrbuch-Code mit $K=3$, Rate $1/2$ und den Generatorpolynomen $G_1=111_2$ (oktal 7) sowie $G_2=101_2$ (oktal 5) als durchgängiges Beispiel — bekannt dafür, unter allen $K{=}3$-Rate-$1/2$-Codes die größtmögliche freie Distanz $d_{\text{frei}}=5$ zu erreichen (ein Maß für die Fehlerkorrekturfähigkeit, das beim Blockcode der Minimaldistanz $d_{\min}$ entspricht).

Bei jedem neuen Eingangsbit $b_t$ und den beiden vorangegangenen Bits $b_{t-1}, b_{t-2}$ (dem „Zustand" vor diesem Schritt) berechnen sich die zwei Ausgangsbits als:

$$c_1 = b_t \oplus b_{t-1} \oplus b_{t-2} \qquad c_2 = b_t \oplus b_{t-2}$$

— genau die XOR-Verknüpfungen, die $G_1=111$ (alle drei Bits) und $G_2=101$ (erstes und drittes Bit, mittleres übersprungen) vorschreiben.

2. Das Trellis-Diagramm: Zustände über der Zeit

Mit $K-1=2$ Speicherbits hat dieser Coder $2^2=4$ mögliche Zustände: 00, 01, 10, 11 (die letzten beiden Eingangsbits). Trägt man diese 4 Zustände über der Zeit auf und verbindet sie mit den möglichen Übergängen (ein Übergang pro möglichem nächsten Eingangsbit), entsteht das namensgebende Trellis-Diagramm (engl. trellis = Rankgitter) — von jedem Zustand führen genau zwei Kanten weg (eine für Eingangsbit 0, eine für Eingangsbit 1), jede Kante ist mit dem dabei erzeugten 2-Bit-Ausgangssymbol beschriftet.

Bsp.: Für die 8 Datenbits 10110010 plus 2 angehängte Null-Bits zum „Zurückschieben" des Coders in den Startzustand (Flush-Bits, Standardpraxis, damit der Endzustand bekannt und fest ist) ergibt der Code die 10 Ausgangssymbole 11 10 00 01 01 11 11 10 11 00 — nachgerechnet endet der Coder exakt wieder im Zustand 00.

3. Viterbi-Decodierung: der wahrscheinlichste Pfad durchs Trellis

Der Empfänger kennt die Struktur des Trellis (dieselbe Regel wie der Sender), aber nicht, welchen Pfad der Sender tatsächlich genommen hat — nur die (möglicherweise fehlerhaften) empfangenen Symbole. Die Grundidee des Viterbi-Algorithmus: Finde unter allen möglichen Pfaden durchs Trellis denjenigen, der am wenigsten von den tatsächlich empfangenen Symbolen abweicht (gemessen in Hamming-Distanz, Bitunterschiede pro Symbol). Das ist wie eine Routenplanung, bei der einzelne Wegweiser falsch stehen könnten: Man wählt nicht stur jeden einzelnen Wegweiser, sondern am Ende die Gesamtroute, die zu den meisten Wegweisern passt.

Damit das effizient geht (ohne alle exponentiell vielen möglichen Pfade einzeln durchzuprobieren), verfolgt der Algorithmus pro Zeitschritt nur die jeweils beste Route zu jedem der 4 Zustände weiter (der „Verlierer"-Pfad zu jedem Zustand wird verworfen, da er nie besser als der „Gewinner" werden kann) — die Rechenlast wächst dadurch nur linear mit der Anzahl der Symbole, nicht exponentiell.

4. Simulator: Kodierung, Trellis und Viterbi-Korrektur

5. Praktischer Einsatz

NASA Deep Space Network / Voyager-Missionen: Der De-facto-Standard für Faltungscodes in der Raumfahrtkommunikation ist ein $K{=}7$, Rate-$1/2$-Code mit den Generatorpolynomen $171_8$ und $133_8$ (deutlich größer als das $K{=}3$-Lehrbuchbeispiel oben: $2^6=64$ statt nur 4 Zustände). Dieser Code wurde bereits bei den Voyager-1/2-Missionen eingesetzt, zusammen mit Viterbi-Decodierung am Boden, und ist seither über die CCSDS-Standardisierung (Consultative Committee for Space Data Systems) fester Bestandteil praktisch aller Deep-Space- und vieler Satellitenprotokolle.

Amateurfunksatelliten (AMSAT): Genau dieser CCSDS-Standardcode ($K{=}7$, Rate $1/2$, Generatoren $171_8/133_8$) kommt auch bei Amateurfunksatelliten zum Einsatz — etwa bei den Telemetrie-Downlinks von LilacSat-1/2 und bei AO-40 (Oscar-40). Größere Constraint Length bedeutet höhere Fehlerkorrekturfähigkeit, aber auch exponentiell mehr Trellis-Zustände ($2^{K-1}$) und damit höheren Rechenaufwand beim Decodieren — der Kompromiss, den reale Systeme bei der Wahl von $K$ eingehen müssen.

QPSK31 (Amateurfunk): Wie im Varicode-Artikel erwähnt, ergänzt die QPSK-Variante von PSK31 gegenüber dem einfachen BPSK31 genau einen Faltungscode mit Viterbi-Decodierung als zusätzlichen Fehlerschutz für den Sprachfunk-typischen, stark gestörten Kurzwellenkanal.

Packet Radio mit FEC: Über die reine AX.25-CRC-Prüfsumme hinaus experimentierten Funkamateure (u. a. Phil Karn, KA9Q) schon früh mit Faltungscodierung und Viterbi-Decodierung als zusätzliche Fehlerkorrekturschicht für Packet Radio, um Übertragungsfehler nicht nur zu erkennen, sondern direkt zu korrigieren.

6. Grenzen

• Keine feste Fehlerkorrektur-Garantie wie Blockcodes: Ein Faltungscode garantiert kein festes $t$ wie Hamming, BCH oder Golay. Ob eine Fehlerkonstellation korrigierbar ist, hängt von der Verteilung der Fehler ab, nicht nur von ihrer Anzahl — im Simulator oben lassen sich 2 weit auseinanderliegende Fehler meist problemlos korrigieren, während 4 eng geballte Fehler die Decodierung kippen können (siehe auch die freie Distanz $d_{\text{frei}}$ aus Abschnitt 1 als das eigentliche, subtilere Maß für die Korrekturfähigkeit).
• Rechenaufwand wächst exponentiell mit $K$: Jede zusätzliche Speicherstelle verdoppelt die Anzahl der Trellis-Zustände — der in der Praxis dominante Code mit $K{=}7$ hat bereits 64 Zustände; deutlich größere $K$ werden wegen des Rechenaufwands selten genutzt.
• Hard-Decision vs. Soft-Decision: Der hier gezeigte Simulator vergleicht empfangene Symbole nur als harte 0/1-Bits (Hamming-Distanz). Reale Viterbi-Decoder nutzen meist Soft-Decision-Metriken (wie sicher/unsicher war die 0-oder-1-Entscheidung tatsächlich, basierend auf dem analogen Empfangssignal) und erreichen dadurch einen spürbar besseren Fehlerschutz bei gleichem Code — ein Aspekt, den dieser vereinfachte Simulator bewusst ausklammert.