Aufgabe 1.2Z: 3D–Darstellung von Codes

• Zurück zum Buch

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}\big[d_{\rm H}(x, \hspace{0.05cm}x\hspace{0.05cm}')\big]$  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.

Fragebogen

1

Welche Aussagen gelten,  wenn alle Punkte in  $\rm GF(2^3)$  belegt sind?

	Es gilt die Zuordnung  $\underline{u} = (u_{1}, u_{2}, u_{3})$   →   $\underline{x} = (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$.

2

Welche Aussagen gelten für einen  $(3, 2, 2)$–Blockcode?

	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.

3

Welche Eigenschaften zeigt der in Teilaufgabe  (2)  definierte Code  $\mathcal{C}_{1}$?

	Ein Bitfehler lässt sich erkennen.
	Ein Bitfehler kann korrigiert werden.

4

Welche Eigenschaften zeigt der Code  $\mathcal{C}_{4}= \{(0, 0, 0),  (1, 1, 1)\}$?

	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.

Musterlösung

Musterlösung

(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).