Aufgaben:Exercise 1.2Z: Three-dimensional Representation of Codes

• Return to book

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} \hspace{-0.15cm} = \hspace{-0.15cm} (x_{1}, x_{2}, x_{3}) \hspace{0.1cm} \in \hspace{0.1cm}{\rm GF}(2^3) \hspace{0.05cm},\\ x_i \hspace{-0.15cm} \in \hspace{-0.15cm} \{0, 1 \}\hspace{0.05cm},\hspace{0.2cm} i = 1, 2, 3\hspace{0.05cm}.$$

Allgemein gilt bei der Blockcodierung:

• Das Informationswort u = $(u_{1}, u_{2}, ... , u_{k})$ wird eindeutig in das Codewort x = $(x_{1}, x_{2}, ... , x_{n})$ überführt.
• Die Coderate beträgt R = k/n.
• Die Hamming–Distanz $d_{\rm H}$(x, x') zwischen zwei Codeworten x ∈ C und x' ∈ C gibt die Anzahl der Bitpositionen an, in denen sich x und x' unterscheiden.
• Die Minimaldistanz $d_{\rm min}$ = min [$d_{\rm H}$(x, x')] 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 korrigiert werden. Die letzte Aussage gilt allerdings nur für ungerades $d_{\rm min}$ .

Hinweis: Die Aufgabe gehört zum Themengebiet von Zielsetzung_der_Kanalcodierung. Zusätzlich werden einige einfache Fragen zu eispiele_binärer_Blockcodes vorweg genommen.

Fragebogen

1

Welche Aussagen gelten, wenn alle Punkte in GF(23) belegt sind?

	Es gilt die Zuordnung u = $ (u_{1}, u_{2}, u_{3})$) → x=$(x_{1}, x_{2},x_{3})$.
	Es gilt die Identität x = 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 $C_{1}$ = {(0, 0, 0), (0, 1, 1), (1, 0, 1), (1, 1, 0)} ist möglich.
	Code $C_{2}$ = {(0, 0, 1), (0, 1, 0), (1, 0, 0), (1, 1, 1)} ist möglich.
	Code $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 $C_{1}$?

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

4

Welche Eigenschaften zeigt der Code $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.

Musterlösung

Solution

(1)  Richtig sind die Aussagen 1 und 3: k = 3 Informationsbits werden bei dieser Belegung auf n = 3 Codebits abgebildet ⇒ R = k/n = 1. Die Aussage <>x = <>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.

(2) 

Zwei (3, 2, 2)–Blockcodes

$C_{1}$ und $C_{2}$ beschreiben tatsächlich Codes mit der Rate R = 2/3 und der Minimaldistanz $d_{\rm min}$ = 2 ⇒ Antwort 1 und 2.

In nebenstehender Grafik markieren die grünen Punkte den Code $C_{1}$ und die blauen Punkte den Code $C_{2}$. Beim angegebenen Code $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 auch zwischen (0, 1, 1) und (1, 1, 1).

(3) 

(4)