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 Buchstaben 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: $P(X=c_1|c_1) = P(X=c_2|c_2) \forall c_1,c_2 \in A$ und $P(X=c_2|c_1)=P(X=c_3|c_1) \forall c_1,c_2,c_3 \in A$ mit $c_2 \not= c_1 \not= c_2$. P(X = a | b) ist dabei die Wahrscheinlichkeit, dass a empfangen wird, falls b 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: A = {0,1}, der diskrete gedächtnislose symmetrische Kanal habe die Fehlerwahrscheinlichkeit von $\frac 1 3$, als Code wird der binäre [3,1,3] Wiederholungscode verwendet: $a \mapsto (a,a,a)$. Dann ist die Wahrscheinlichkeit

• für keinen Übertragungsfehler:

$\left(\frac 2 3 \right)^3=\frac{8}{27}$

• für einen Übertragungsfehler:

$3 \cdot \left(\frac 2 3 \right)^2 \cdot \frac 1 3 =\frac{4}{9}=\frac{12}{27}$

• für zwei Übertragungsfehler:

$3 \cdot \frac 2 3 \cdot \left(\frac 1 3 \right)^2 =\frac{2}{9}=\frac{6}{27}$

• für drei Übertragungsfehler:

$\left(\frac 1 3 \right)^3 =\frac{1}{27}$

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

$P_1 := P(X=(110)|(000))P(Y=(000)) = \frac{2}{3} \cdot \left(\frac{1}{3}\right)^2 \cdot \frac{3}{4} = \frac{6}{108}$

Andererseits ist die Wahrscheinlichkeit, dass (111) gesendet wurde:

$P_2 := P(X=(110)|(111))P(Y=(111)) = \left(\frac{2}{3}\right)^2 \cdot \frac{1}{3} \cdot \frac{1}{4} = \frac{4}{108}$

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

$P(Y=(000)|(110))=\frac{P_1}{P_1+P_2}=60%$

und die Wahrscheinlichkeit für (111):

$P(Y=(111)|(110))=\frac{P_2}{P_1+P_2}=40%$

Also wird (110) in diesem Fall nach (000) decodiert.

Maximum Likelihood Decodierung

Bei der Maximum Likelihood Decodierung wird ein empfangenes Wort x zu dem (Code-)Wort c decodiert, welches x 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 $<\frac 1 2$, wird das Codewort c gewählt, das sich am geringsten von x unterscheidet, sprich das c mit dem geringsten Hammingabstand zu x.

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 (110) nach (111) decodiert. Sendet die Quelle (000) und (111) 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).