Vorwärtsfehlerkorrektur

Wunderbar, jetzt haben wir alles zusammen, um enorme Datenmengen per Funk zu übertragen. Es gibt da nur ein Problem: Sobald die Übertragung gestört wird, gehen die übertragenen Daten schnell kaputt. Wenn, wie es so schön heißt, ein Bit kippt, bekommt der Empfänger nicht, was der Sender ihm übertragen wollte.

Das Schlimmste ist, dass der Empfänger es nicht einmal merken würde. Zum Glück gibt es aber statistische Methoden, um Fehler zu erkennen und sogar zu korrigieren - solange es nicht zu viele sind. Für die Fehlererkennung kommt meist die zyklische Redundanzprüfung (Cyclic Redundancy Check, CRC) zum Einsatz. Der Sender berechnet damit aus dem Datenstrom einen Prüfwert, der mit übertragen wird. Der Empfänger macht das auch und vergleicht die Werte. Stimmen sie überein, wurden die Daten korrekt übertragen.

Werden weitere redundante Daten mitgesendet, können Fehler sogar korrigiert werden. Das Ziel dabei ist, möglichst wenig Redundanz für eine gewünschte Korrekturleistung zu erzeugen. Mittels statistischer Analyse können verschiedene Verfahren verglichen werden. Dazu wird ein Fehlermodell genutzt, das beschreibt, wie Fehler auftreten. Neben Gaußschem Rauschen existieren auch Modelle, die Mehrwegeeffekte betrachten, wie das Rayleigh-Fading.

Sauber gefaltet ist halb korrigiert

Bis zum 802.11n-Standard unterstützte WLAN nur sogenannte Faltungscodes zur Fehlerkorrektur. Sie nutzen das mathematische Konzept der Faltung, das zwei Signalfolgen kombiniert. Sie sind recht einfach zu verstehen und auch technisch mit geringem Aufwand umsetzbar. Die Information jedes Bits wird mittels einer vorgegebenen Funktion über mehrere der ausgegebenen Bits verteilt. Außerdem werden pro Datenbit zwei sogenannte Code-Bits erzeugt, in die das aktuelle und die k - 1 vorhergehenden einfließen. Der Parameter k wird als Einflusslänge bezeichnet und gibt an, wie viele Code-Bit-Paare jedes Datenbit beeinflusst. Im 802.11-Standard ist k sieben.

Anstatt der eigentlichen Datenbits werden die Code-Bits übertragen. Das bedeutet, dass die Datenrate auf die Hälfte sinkt. Bei guten Kanalbedingungen ist es übertrieben, die Hälfte der Datenrate für eine selten erforderliche Fehlerkorrektur aufzuwenden. Daher kann der Sender Teile der Code-Bits verwerfen und so die Redundanz bis auf 20 Prozent senken (sechs Code-Bits pro fünf Datenbits). Das geschieht nach einem vorgegebenen Muster und wird Punktierung genannt.

So wird korrigiert

Der Empfänger füllt die punktierten Stellen wieder auf, wobei er zwangsläufig Fehler macht. Dadurch sinkt die Korrekturleistung des Codes, also die Anzahl korrigierbarer Fehler. Anschließend leitet er aus dem codierten Datenstrom ab, was wahrscheinlich der ursprüngliche Datenstrom war. Oft kommt hierzu der Viterbi-Decoder (hier erklärt vom Entwickler) zum Einsatz.

Hierzu bildet der Viterbi-Decoder den Codierungsprozess nach. Für jedes verarbeitete Code-Bit-Paar hat er k - 1 Zustände. Sie entsprechen den zuletzt decodierten Bits, die das aktuell verarbeitete codierte Paar noch beeinflussen. Die Codierung sorgt dafür, dass von vier möglichen Paaren von Code-Bits nur zwei gültig sind. Jedes dieser Paare führt zu einem Nachfolgezustand, der aus den k - 2 vorherigen Verarbeitungsschritten sowie einer 0 oder 1 besteht - dem im aktuellen Schritt vom Encoder verarbeiteten Datenbit.

So entsteht ein Graph, den der Decoder durchläuft. Dabei werden die gültigen Code-Bits mit den empfangenen verglichen. Für jeden Übergang zu einem Nachfolgezustand berechnet er aus den erwarteten und den empfangenen Code-Bits einen Fehlerwert - es entstehen Pfade mit unterschiedlich großen Fehlern. Führen zwei Pfade zum selben Zustand, wird nur derjenige mit dem geringeren Fehlerwert weiterverfolgt. Wurden alle Code-Bits verarbeitet, wird der Pfad mit dem geringsten Fehlerwert ausgewählt. Seine Übergänge geben die wahrscheinlichste Sequenz an Datenbits an, wie unten dargestellt.

• 

Der Viterbi-Decoder decodiert ein gestörtes Signal. Zwischen zwei Übergängen steht der aktuelle Fehlerwert, ganz oben das empfangene Code-Wort. Die Einflusslänge ist k=3, der Encoder nutzt ein 2-Bit-Schieberegister, dessen Inhalt bildet die Zeilen. Der Pfad mit dem geringsten Fehler wird zurückverfolgt; geht er nach oben, wird 1 decodiert, sonst 0. (Bild: Golem.de)