Aufgabe 1.13Z: Nochmals BEC–Decodierung

• Zurück zum Buch

Codetabelle des vorgegebenen Hamming–Codes

Wir betrachten wieder wie in der vorherigen Aufgabe die Decodierung eines Hamming–Codes nach der Übertragung über einen Auslöschungskanal ⇒ Binary Erasure Channel (abgekürzt BEC). Der (7, 4, 3)–Hamming–Code wird durch die nebenstehende Codetabelle $\underline{u}_{i} → \underline{x}_{i}$ vollständig beschrieben, anhand derer alle Lösungen gefunden werden können.

Hinweis :

Die Aufgabe bezieht sich auf das Kapitel Decodierung linearer Blockcodes. Im Gegensatz zur Aufgabe 1.13 soll hier die Lösung nicht streng formal, sondern eher intuitiv gefunden werden.

Fragebogen

1

Wie groß ist die minimale Distanz des vorliegenden Codes?

$\ d_{\rm min}$ =

2

Ist der Code systematisch?

	JA.
	NEIN.

3

Bis zu wie vielen Erasures ist die erfolgreiche Decodierung gewährleistet?

$\ e_{\ max}$ =

4

Wie lautet das gesendete Informationswort u für $\underline{y} = (1, 0, {\rm E}, {\rm E}, 0, 1, 0)$?

	$\underline{u} = (1, 0, 0, 0),$
	$\underline{u}= (1, 0, 0, 1),$
	$\underline{u} = (1, 0, 1, 0),$
	$\underline{u} = (1, 0, 1, 1).$

5

Welche der nachfolgenden Empfangsworte können decodiert werden?

	$\underline{y}_{\rm A }= (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E}),$
	$\underline{y}_{\rm B} = ({\rm E}, {\rm E }, 0, {\rm E}, 0, 1, 0),$
	$\underline{y}_{\rm C} = ({\rm E}, {\rm E}, {\rm E}, 1, 0, 1, 0),$
	$\underline{y}_{\rm D} = (1, 0, {\rm E}, {\rm E}, {\rm E}, {\rm E}, 0).$

Musterlösung

Musterlösung

(1)  Betrachtet wird der (7, 4, 3)–Hamming–Code. Dementsprechend ist die minimale Distanz $d_{\rm min} \underline{= 3}$.

(2)  Die ersten $k = 4$ Bit eines jeden Codewortes x stimmen mit dem Informationswort u überein. Richtig ist somit JA.

(3)  Es können bis zu $e_{\rm max} = d_{\rm min} – 1 \underline{ = 2}$ Bit ausgelöscht sein, damit eine Decodierung mit Sicherheit möglich ist. Jedes Codewort unterscheidet sich von jedem anderen in mindestens drei Bitpositionen. Bei nur zwei Auslöschungen kann deshalb das Codewort in jedem Fall rekonstruiert werden.

(4)  In der Tabelle auf der Angabenseite findet man ein einziges Codewort, das mit „10” beginnt und mit „010” endet, nämlich $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$. Da es sich um einen systematischen Code handelt, beschreiben die ersten $k = 4$ Bit das Informationswort $\underline{u} = (1, 0, 0, 1)$ ⇒ Antwort 2.

(5)  Richtig sind die Lösungsvorschläge 1 und 2.

• $\underline{y}_{\rm D} = (1, 0, {\rm E}, {\rm E}, {\rm E}, {\rm E}, 0)$ kann nicht decodiert werden, da weniger als $k = 4$ Bit (Anzahl der Informationsbit) ankommen.

• $\underline{y}_{\rm C} = ( {\rm E}, {\rm E}, {\rm E}, 1, 0, 1, 0)$ ist ebenfalls nicht decodierbar, da sowohl $\underline{x} = (0, 1, 1, 1, 0, 1, 0)$ als auch $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$ als mögliches Ergebnis in Frage kommen.

• $\underline{y}_{\rm B} = ( {\rm E}, {\rm E}, 0, {\rm E}, 0, 1, 0)$ ist dagegen decodierbar, da von allen 16 möglichen Codeworten nur $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$ mit $\underline{y}_{\rm B}$ in den (richtigen) Bitpositionen 3, 5, 6 und 7 übereinstimmt.

• $\underline{y}_{\rm A} = (1, 0, 0, 1, {\rm E}, {\rm E}, {\rm E})$ ist decodierbar. Es fehlen nur die $m = 3$ Prüfbit. Damit liegt das Informationswort $\underline{u} = (1, 0, 0, 1)$ ebenfalls fest (systematischer Code).