Exercise 2.16: Bounded Distance Decoding: Decision Regions

Betrachtete Codierraumschemata

Wir gehen von einem Blockcode der Länge $n$ mit Symbolen $c_i ∈ {\rm GF}(2^m)$ aus, der bis zu $t$ Symbole korrigieren kann. Jedes mögliche Empfangswort $\underline{y}_i$ kann dann als ein Punkt in einem hochdimensionalen Raum angesehen werden. Geht man von der Basis ${\rm GF}(2) = \{0, \, 1\}$ aus, so beträgt die Dimension $n \cdot m$.

Die Grafik zeigt einen solchen Raum in vereinfachender, schematischer 2D–Darstellung.

Die Abbildung ist wie folgt zu interpretieren:

Gesendet wurde der rote Punkt $\underline{c}_j$. Alle rot umrandeten Punkte $\underline{y}_i$ in einer Hyperkugel um diesen Punkt $\underline{c}_j$ mit dem Parameter $t$ als Radius können korrigiert werden. Mit der Nomenklatur gemäß der Grafik im Theorieteil gilt dann $\underline{z}_i = \underline{c}_j$
⇒ „Die Fehlerkorrektur ist erfolgreich".

Bei sehr vielen Symbolfehlern kann $\underline{c}_j$ in einen blauen (oder weißblauen) Punkt $\underline{y}_j$ verfälscht werden, der zur Hyperkugel eines anderen Codewortes $\underline{c}_{k ≠ j}$ gehört. In diesem Fall trifft der Decoder eine falsche Entscheidung
⇒ „Das Empfangswort $\underline{y}_j$ wird falsch decodiert".

Schließlich kann es wie in der unteren Skizze auch noch gelbe Punkte geben, die zu keiner Hyperkugel gehören
⇒ „Das Empfangswort $\underline{y}_j$ ist nicht decodierbar".

In dieser Aufgabe sollen Sie entscheiden, welches der beiden Coderaumschemata geeignet ist zur Beschreibung von

Hinweise:

Die Aufgabe ergänzt die Thematik des Kapitels Fehlerwahrscheinlichkeit und Anwendungsgebiete.
Sie soll signifikante Unterschiede bei der Decodierung von Reed–Solomon–Codes und Hamming–Codes verdeutlichen.

Fragebogen

Musterlösung

Solution

(1) Richtig ist der Lösungsvorschlag 1, da das Codierraumschema $\rm A$ einen perfekten Code beschreibt und jeder Hamming–Code $(n, \, k, \, 3)$ ein perfekter Code ist:

Bei einem jeden Hamming–Code $(n, \, k, \, 3)$ gibt es insgesamt $2^n$ mögliche Empfangsworte $\underline{y}_i$, die bei der Syndromdecodierung einem von $2^k$ möglichen Codeworten $\underline{c}_j$ zugeordnet werden.
Aufgrund der HC–Eigenschaft $d_{\rm min} = 3$ haben alle Kugeln im $n$–dimensionalen Raum den Radius $t = 1$. In allen Kugeln gibt es somit $2^{n-k}$ Punkte, zum Beispiel

$\text{HC (7, 4, 3)}$: einen Punkt für die fehlerfreie Übertragung und sieben Punkte für einen Bitfehler ⇒ $1 + 7 = 8 = 2^3 = 2^{7-4}$.
$\text{HC (15, 11, 3)}$: einen Punkt für die fehlerfreie Übertragung und nun 15 Punkte für einen Bitfehler ⇒ $1 + 15 = 16 = 2^4 = 2^{15-11}$.

Hinweis: Da der Hamming–Code ein Binärcode ist, hat hier der Coderaum die Dimension $n$.

(2) Richtig ist die Antwort 1:

Im grauen Bereich außerhalb von „Kugeln" gibt es bei einem perfekten Code keinen einzigen Punkt.
Dies wurde auch in der Rechnung zur Teilaufgabe (1) gezeigt.

(3) Die Reed–Solomon–Codes werden durch das Codierraumschema $\rm B$ beschrieben ⇒ Antwort 2.

Hier gibt es zahlreiche gelbe Punkte im grauen Bereich, also Punkte die bei Bounded Distance Decoding (BDD) keiner Kugel zugeordnet werden können.
Betrachten wir beispielweise den $\rm RSC \, (7, \, 3, \, 5)_8$ mit den Codeparametern $n = 7, \, k = 3$ und $t = 2$, so gibt es hier insgesamt $8^7 = 2097152$ Punkte und $8^3 = 512$ Hyperkugeln.
Wäre dieser Code perfekt, so müsste es also innerhalb jeder Kugel $8^4 = 4096$ Punkte geben. Es gilt aber:

$${\rm Pr}(\underline{\it y}_{\it i} {\rm \hspace{0.1cm}liegt\hspace{0.1cm} innerhalb\hspace{0.1cm} der\hspace{0.1cm} roten\hspace{0.1cm} Kugel)} = {\rm Pr}(f \le t) = {\rm Pr}(f = 0)+ {\rm Pr}(f = 1)+{\rm Pr}(f = 2) =1 + {7 \choose 1} \cdot 7 + {7 \choose 2} \cdot 7^2 = 1079 \hspace{0.05cm}.$$

Für ${\rm Pr}(f = 1)$ ist berücksichtigt, dass es „$7 \rm \ über \ 1$" $= 7$ Fehlerpositionen geben kann, und für jede Fehlerposition auch sieben unterschiedliche Fehlerwerte. Entsprechendes ist auch für ${\rm Pr}(f = 2)$ berücksichtigt.

(4) Richtig ist die Antwort 3:

Ein Punkt im grauen Niemandsland wird mit weniger Symbolfehlern erreicht als ein Punkt in einer anderen Hyperkugel.
Für lange Codes wird in der Literatur eine obere Schranke für die Verfälschungswahrscheinlichkeit angegeben:

$${\rm Pr}(\underline{y}_{i} {\rm \hspace{0.15cm}wird\hspace{0.15cm} falsch\hspace{0.15cm} decodiert)} = {\rm Pr}(\underline{z} \ne \underline{c}) \le \frac{1}{t\hspace{0.05cm}!} \hspace{0.05cm}.$$

Für den ${\rm RSC} \, (225, \, 223, \, 33)_{256} \ \Rightarrow \ t = 16$ liefert diese obere Schranke den Wert $1/(16!) < 10^{-14}$.

	Die Wahrscheinlichkeit ${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$ ist exakt Null.
	${\rm Pr}(\underline{y} \rm \ ist \ nicht \ decodierbar)$ ist ungleich Null, aber vernachlässigbar.
	Es gilt ${\rm Pr}(\underline{y} {\rm \ ist \ nicht \ decodierbar}) > {\rm Pr}(\underline{y} \rm \ wird \ falsch \ decodiert)$.