Exercise 1.2Z: Three-dimensional Representation of Codes

Raum $\rm GF(2^3)$ und Code der Länge $n = 3$

Codes zur Fehlererkennung bzw. Fehlererkorrektur lassen sich sehr anschaulich im $n$–dimensionalen Raum darstellen. Wir beschränken uns hier auf binäre Codes der Länge $n = 3$:

$$\underline{x} = (x_{1}, x_{2}, x_{3}) \hspace{0.1cm} \in \hspace{0.1cm}{\rm GF}(2^3) \hspace{0.05cm},\hspace{0.5cm} x_i = \{0, 1 \}\hspace{0.05cm},\hspace{0.2cm} i = 1, 2, 3\hspace{0.05cm}.$$

Allgemein gilt bei der Blockcodierung:

Das Informationswort $\underline{u} = (u_{1}, u_{2}, \ \text{...} , \ u_{k})$ wird eindeutig in das Codewort $\underline{x} =(x_{1}, x_{2}, \ \text{...} , \ , x_{n})$ überführt.
Die Coderate beträgt $R = k/n$.
Die Hamming–Distanz $d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')$ zwischen zwei Codeworten $x ∈ \mathcal{C}$ und $x\hspace{0.05cm}' ∈ \mathcal{C}$ gibt die Anzahl der Bitpositionen an, in denen sich $x$ und $x\hspace{0.05cm}'$ unterscheiden.
Die Minimaldistanz $d_{\rm min} = {\rm min}[d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')]$ ist ein Maß für die Korrekturfähigkeit eines Codes.
Es können $e =d_{\rm min} – 1$ Fehler erkannt und $t =(d_{\rm min} – 1)/2$ Fehler korrigiert werden. Die letzte Aussage gilt allerdings nur für ungerades $d_{\rm min}$.

Hinweise:

Die Aufgabe gehört zum Kapitel Zielsetzung der Kanalcodierung.
Zusätzlich werden einige einfache Fragen zum Kapitel Beispiele binärer Blockcodes vorweg genommen.
Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

Musterlösung

Solution

(1) Richtig sind die Aussagen 1 und 3:

Bei dieser Belegung werden $k = 3$ Informationsbits auf $n = 3$ Codebits abgebildet ⇒ $R = k/n = 1$.
Die Aussage $\underline{x} = \underline{u} $ würde nur bei systematischer Codierung gelten.
Prinzipiell möglich wäre zum Beispiel auch $(0, 0, 0)$ → $(0, 1, 1)$.
Die letzte Aussage ist mit Sicherheit falsch: Aus der Grafik erkennt man die Minimaldistanz $d_{\rm min} = 1$.

Zwei (3, 2, 2)–Blockcodes

(2) Richtig sind die Aussagen 1 und 3:

$\mathcal{C}_{1}$ und $\mathcal{C}_{2}$ beschreiben tatsächlich Codes mit der Rate $R = 2/3$ und der Minimaldistanz $d_{\rm min} = 2$.
In der Grafik markieren die grünen Punkte den Code $\mathcal{C}_{1}$ und die blauen Punkte den Code $\mathcal{C}_{2}$.
Beim Code $\mathcal{C}_{3}$ – ebenfalls mit Rate $R = 2/3$ – ist die minimale Distanz zwischen zwei Codeworten $d_{\rm min} = 1$, zum Beispiel zwischen $(0, 0, 0)$ und $(1, 0, 0)$ oder zwischen $(0, 1, 1)$ und $(1, 1, 1)$.

(3) Richtig ist nur die Aussage 1:

Mit der Minimaldistanz $d_{\rm min} = 2$ kann lediglich ein Bitfehler erkannt werden.
In der oberen Grafik kennzeichnen die grünen Punkte zulässige Codeworte von $\mathcal{C}_{1}$. Wird ein blauer Punkt empfangen, so weist dies auf einen Übertragungsfehler hin.
Eine Fehlerkorrektur ist mit $d_{\rm min} = 2$ dagegen nicht möglich.
Der Code $\mathcal{C}_{1}$ entspricht dem Single Parity–check Code (3, 2, 2).

(3, 1, 3)–Blockcode

(4) Richtig sind die Antworten 2, 3 und 4:

$C_{4}$ beschreibt den (3, 1, 3)–Wiederholungscode.
Bei diesem Code sind zwar zwei der insgesamt acht möglichen Punkte belegt, woraus man fälschlicherweise auf die Coderate $R = 1/4$ schließen könnte. Die Coderate berechnet sich aber gemäß $R = k/n = 1/3$.
Aus der unteren Grafik erkennt man, dass wegen $d_{\rm min} = 3$ nun auch ein Bitfehler korrigiert werden kann.
Bei der Decodierung werden alle hellgrünen Punkte (mit schwarzer Umrahmung) in den grünen Punkt $(0, 0, 0)$ überführt und alle hellblauen in den blauen Punkt $(1, 1, 1)$.
Gleichzeitig können bis zu zwei Bitfehler erkannt werden (einer natürlich auch).

	Es gilt die Zuordnung $\underline{u} = (u_{1}, u_{2}, u_{3})$ → $\underline{u} = (x_{1}, x_{2},x_{3})$.
	Es gilt die Identität $\underline{x} = \underline{u}$.
	Die Coderate ist $R = 1$.
	Die Minimaldistanz zwischen zwei Codeworten ist $d_{\rm min} = 2$.

	Die Coderate beträgt $R = 1/4$.
	Die Coderate beträgt $R = 1/3$.
	Ein Bitfehler lässt sich erkennen.
	Ein Bitfehler kann korrigiert werden.

	Code $\mathcal{C}_{1} = \{(0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0)\}$ ist möglich.
	Code $\mathcal{C}_{2} = \{(0, 0, 1), (0, 1, 0), (1, 0, 0), (1, 1, 1)\}$ ist möglich.
	Code $\mathcal{C}_{3} = \{(0, 0, 0), (0, 1, 1), (1, 0, 0), (1, 1, 1)\}$ ist möglich.