Exercise 1.13Z: Binary Erasure Channel Decoding again

• Return to book

Codetabelle des vorgegebenen Hamming–Codes $(7, 4, 3)$

Wir betrachten wieder wie in der Aufgabe 1.13 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.

Hinweise :

• Die Aufgabe bezieht sich auf das Kapitel Decodierung linearer Blockcodes.
• Im Gegensatz zur Aufgabe 1.13 soll hier die Lösung nicht formal, sondern intuitiv gefunden werden.
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

1

Wie groß ist die minimale Distanz $\ d_{\rm min}$ des vorliegenden Codes?

$\ d_{\rm min} \ = \ $

2

Ist der Code systematisch?

	JA.
	NEIN.

3

Bis zu wie vielen Erasures (Anzahl $e_{\rm max}$) ist die erfolgreiche Decodierung gewährleistet?

$\ e_{\rm max} \ = \ $

4

Wie lautet das gesendete Informationswort $\underline{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

Solution

(1)  Betrachtet wird hier 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 $\underline{x}$ stimmen mit dem Informationswort $\underline{u}$ überein. Richtig ist somit JA.

(3)  Werden nicht mehr als $e_{\rm max} = d_{\rm min} – 1 \underline{ = 2}$ Bit ausgelöscht,so ist eine Decodierung mit Sicherheit möglich.

• 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 Codetabelle 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).