Aufgabe 1.11Z: Nochmals Syndromdecodierung

Schaubild: Prüfgleichungen

Betrachtet wird die gleiche Konstellation wie in "Aufgabe 1.11", nämlich die Decodierung eines $(7, 4, 3)$ –Hamming–Codes mit der Prüfmatrix

${ \boldsymbol{\rm H}}_{\rm } = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$

Dementsprechend lautet die Generatormatrix:

${ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &0\\ 0 &0 &1 &0 &0 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$

Bei der "Syndromdecodierung" bildet man aus dem Empfangsvektor $\underline{y}$ das Syndrom $\underline{s}$ entsprechend der Gleichung

$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}.$

Mit diesem Ergebnis lässt sich beim betrachteten Hamming–Code ein jeder Einzelfehler im Codewort korrigieren.

Im fehlerfreien Fall gilt $\underline{s} = \underline{s}_{0} = (0, 0, 0)$ .

Aber auch bei drei Übertragungsfehlern kann sich unter Umständen $\underline{s}_{0} = (0, 0, 0)$ ergeben, so dass diese Fehler unerkannt bleiben.

Hinweise:

Die Aufgabe gehört zum Kapitel "Decodierung linearer Blockcodes".

Weitere Informationen zur Syndromdecodierung finden Sie im Angabenblatt zur "Aufgabe 1.11".

Die Grafik verdeutlicht die drei Prüfgleichungen entsprechend der Prüfmatrix:
- erste Zeile: rote Gruppierung,
- zweite Zeile: grüne Gruppierung,
- dritte Zeile: blaue Gruppierung.

Fragebogen

Musterlösung

(1) Die Antwort ist JA, wie man aus der vorgegebenen Prüfmatrix

$\mathbf{H}$ erkennt:

Diese beinhaltet am Ende eine $3×3$ –Diagonalmatrix.

Die Codeworte lauten demzufolge:

$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6, x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_{3}) \hspace{0.05cm}.$

(2) Mit diesem Empfangsvektor $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$ werden alle Prüfgleichungen erfüllt:

$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$

$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \hspace{0.05cm},$

$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm}.$

Richtig ist dementsprechend die Antwort JA.

(3) Es gilt $\underline{s} = \underline{y} · \boldsymbol{\rm H}^{\rm T}$ :

$\underline{s} = \begin{pmatrix} 1 &0 &0 &1 &0 &1 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &1\\ 1 &1 &0\\ 0 &1 &1\\ 1 &1 &1\\ 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} = \begin{pmatrix} 0 &0 &0 \end{pmatrix} = \underline{s}_0 \hspace{0.2cm} \Rightarrow\hspace{0.2cm} \hspace{0.15cm} \underline{ \rm Antwort \hspace{0.15cm}1} \hspace{0.05cm}.$

(4) Man könnte nun für jedes $\underline{y}$ die Gleichung $\underline{y} · \boldsymbol{\rm H}^{\rm T} = (0, 0, 0)$ überprüfen. Hier soll nun das Ergebnis auf anderem Wege gewonnen werden:

$\underline{y}= (1, 1, 0, 1, 0, 1, 0)$ unterscheidet sich von $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$ nur im Bit $u_{2}$ , das nur in den beiden ersten Prüfgleichungen verwendet wird, nicht jedoch in der letzten ⇒ $\underline{s} = \underline{s}_{6} = (1, 1, 0)$ .

Wendet man die Prüfgleichungen auf $\underline{y} = (0, 1, 0, 1, 0, 0, 1)$ an, so erhält man $\underline{s} = \underline{s}_{0} = (0, 0, 0)$ , wie die folgende Rechnung belegt:

$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$

$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$

$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \hspace{0.05cm}.$

Zum gleichen Ergebnis kommt man mit dem Empfangsvektor $\underline{y} = (0, 1, 1, 0, 1, 0, 1),$ der sich vom Vektor $(1, 0, 0, 1, 0, 1, 0)$ in allen sieben Bitpositionen unterscheidet:

$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm},$

$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 1 \oplus 1 \oplus 0 \oplus 0 = 0 \hspace{0.05cm},$

$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm}.$

Richtig sind also die Antworten 2 und 3.

	$\underline{s} = \underline{s}_{0} = (0, 0, 0),$
	$\underline{s} = \underline{s}_{3} = (0, 1, 1),$
	$\underline{s} = \underline{s}_{7} = (1, 1, 1).$

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

	Ja,
	Nein.

	Ja,
	Nein.