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

Beschreibung

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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

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