Decodierregel

Eine Decodierregel bezeichnet in der Informationstheorie und Codierungstheorie, genauer bei der Kanalcodierung, eine Vorschrift, welches gesendete Wort einem empfangenen Wort zugeordnet werden soll.

Beschreibung

Die Problemstellung dabei ist folgende: Ein Sender (Quelle) S sendet ein Wort c mit n Zeichen, bestehend aus Buchstaben eines Alphabets A mit q Buchstaben. Die Übertragung geht dabei über einen gestörten Kanal. Dadurch können durch Übertragungsfehler einzelne Buchstaben verändert werden. Der Empfänger erhält also ein möglicherweise verändertes Wort. Sein Ziel ist es, das richtige Wort herauszufinden.

Zur mathematischen Betrachtung werden fast immer vereinfachende Annahmen getroffen:

  • der Kanal ist diskret, das Ausgangssignal kann nur endlich viele verschiedene Werte annehmen
  • der Kanal ist gedächtnislos, die Fehlerwahrscheinlichkeit für einen Buchstaben hängt nicht von den zuvor gesendeten Buchstaben ab.
  • der Kanal ist symmetrisch, die Wahrscheinlichkeit, dass ein Buchstabe, der gesendet wurde, auch richtig ankommt ist für alle Buchstaben gleich groß und die Wahrscheinlichkeit für alle Fehler ist gleich groß. In Formeln: und mit . ist dabei die Wahrscheinlichkeit, dass empfangen wird, falls gesendet wurde.

Damit eine einigermaßen fehlerfreie Decodierung gewährleistet ist, wird den Worten meistens gezielt Redundanz hinzugefügt, indem fehlerkorrigierende Codes verwendet werden.

Minimum-Error-Decodierung

Bei der Minimum-Error-Decodierung wird versucht das Wort zu finden, welches am wahrscheinlichsten gesendet wurde. Dies hängt von zwei wesentlichen Faktoren ab. Zum einen von der Fehlerwahrscheinlichkeit des Kanals, zum anderen von der Entropie der Quelle; sprich, ob die gesendeten Worte gleichverteilt und voneinander abhängig sind. Die Minimum-Error-Decodierung ist immer die optimale Decodierregel, sie ist aber im Allgemeinen schwer zu bestimmen.

Beispiel: Sei das Alphabet binär: , der diskrete gedächtnislose symmetrische Kanal habe die Fehlerwahrscheinlichkeit von , als Code wird der binäre Wiederholungscode verwendet: . Dann ist die Wahrscheinlichkeit

  • für keinen Übertragungsfehler:
  • für einen Übertragungsfehler:
  • für zwei Übertragungsfehler:
  • für drei Übertragungsfehler:

Die werde im statistischen Mittel dreimal so oft wie die gesendet. Es wird jetzt das Wort empfangen. Betrachte die entsprechenden Wahrscheinlichkeiten:

Andererseits ist die Wahrscheinlichkeit, dass gesendet wurde:

Dabei steht die Zufallsvariable für das gesendete Wort und die Zufallsvariable für das empfangene Wort. Damit ist die Wahrscheinlichkeit, dass gesendet wurde:

und die Wahrscheinlichkeit für :

Also wird in diesem Fall nach decodiert.

Maximum-Likelihood-Decodierung

Bei der Maximum-Likelihood-Decodierung wird ein empfangenes Wort zu dem (Code-)Wort decodiert, welches am wahrscheinlichsten erzeugt hat. Im Gegensatz zur Minimum-Error-Decodierung ist die Maximum-Likelihood-Decodierung relativ einfach zu implementieren. Unter der Standardvoraussetzung eines diskreten gedächtnislosen Kanals mit einer Fehlerwahrscheinlichkeit von , wird das Codewort gewählt, das sich am geringsten von unterscheidet, sprich das mit dem geringsten Hammingabstand zu .

Die Maximum-Likelihood-Decodierung wird in der Codierungstheorie am häufigsten verwendet.

Unter den Voraussetzungen, dass die Quelle ihre Zeichen/Wörter gedächtnislos und gleichverteilt sendet und der Kanal diskret, symmetrisch und gedächtnislos ist, ist die Maximum-Likelihood-Decodierung eine Minimum Error Decodierung. Aus diesem Grund wird oftmals vor der Blockcodierung zu Fehlerkorrektur eine Entropiecodierung durchgeführt, indem die zu sendenden Daten beispielsweise gepackt werden.

Beispiel: Bei dem obigen Beispiel wird bei der Maximum-Likelihood-Decodierung das Wort nach decodiert. Sendet die Quelle und gleich oft, ist die Decodierung nach Maximum Likelihood auch eine nach Minimum Error.

Literatur

  • Rudolf Mathar: Informationstheorie. Diskrete Modelle und Verfahren. Teubner, Stuttgart 1996, ISBN 3-519-02574-4 (Teubner-Studienbücher – Mathematik).