Aufgabe 1.13Z: Nochmals BEC–Decodierung

From LNTwww

Codetabelle des  $\rm HC \ (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 :


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 Auslöschungen ("Erasures";   maximale Anzahl:  $e_{\rm max})$  ist eine 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

(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.
  • Auch  $\underline{y}_{\rm C} = ( {\rm E}, {\rm E}, {\rm E}, 1, 0, 1, 0)$  kann nicht decodierbar, da  $\underline{x} = (0, 1, 1, 1, 0, 1, 0)$  und   $\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 decodierbar, da von den 16 möglichen Codeworten nur  $\underline{x} = (1, 0, 0, 1, 0, 1, 0)$  mit  $\underline{y}_{\rm B}$  in den Positionen 3, 5, 6, 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).