Aufgaben:Exercise 1.11: Syndrome Decoding

• Return to book

Syndrom und Nebenklassenanführer eines Hamming–Codes

Zur Decodierung eines (7, 4, 3)–Hamming–Codes, der durch seine 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}$$

gegeben ist, eignet sich auch die Syndromdecodierung. Da alle Hamming–Codes perfekt sind, ergibt sich hiermit ein gleich gutes Ergebnis wie mit der (im allgemeinen Fall) komplizierteren Maximum–Likelihood–Detektion.

Bei der Syndromdecodierung geht man wie folgt vor:

• Man bildet aus dem Empfangsvektor y das Syndrom (es gilt $m = n – k$):

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

• Beim BSC–Kanal ist auch das Empfangswort $y = x$ (Codewort) + e (Fehlervektor) ein Element von GF ($2^n$), und es gilt wegen $ \underline{x} · \boldsymbol {{\rm H} }^{\rm T} = \underline{0}$ gleichermaßen:

$$\underline{s} = \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T} \hspace{0.05cm}.$$

• Viele Fehlermuster e führen zum gleichen Syndrom s. Man fasst nun diejenigen Fehlermuster mit dem gleichen Syndrom $s_{\mu}$ zur Nebenklasse $\Psi_{\mu}$ zusammen.

• Als Nebenklassenanführer $\underline{e}_{\mu}$ bezeichnet man denjenigen Fehlervektor, der innerhalb der Klasse $\Psi_{\mu}$ das geringste Hamming–Gewicht aufweist und dementsprechend am wahrscheinlichsten ist.

Die obige Grafik zeigt die unvollständige Liste der Nebenklassenanführer $\underline{e}_{\mu}$ für die einzelnen $s_{\mu}$ . Die wahrscheinlichsten Fehlervektoren

• $\underline{e}_{3}$ mit Syndrom $\underline{s}_{3} = (0, 1, 1)$,
• $\underline{e}_{5}$ mit Syndrom $\underline{s}_{5} = (1, 0, 1)$,
• $\underline{e}_{6}$ mit Syndrom $\underline{s}_{6} = (1, 1, 0)$,
• $\underline{e}_{7}$ mit Syndrom $\underline{s}_{7} = (1, 1, 1)$

sollen in den Teilaufgaben (4) und (5) ermittelt werden.

Hinweis:

Die Aufgabe bezieht sich auf das Kapitel Decodierung linearer Blockcodes. Zugrunde liegt ein Hamming–Code mit den Parametern $n = 7$ und $k = 4 ⇒ m = 3$. Alle Codeworte haben folgendes Format:

$$\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}.$$

Die Prüfgleichungen sind auf dem Angabenblatt zur Aufgabe 1.11Z veranschaulicht, in der genau die gleiche Konstellation betrachtet wird wie in der vorliegenden Aufgabe. Verwenden Sie in der letzten Teilaufgabe (6) den BSC–Parameter $ \epsilon = 0.1$.

Fragebogen

1

Wie viele Empfangsworte $(N_{0})$ führen zum Syndrom $\underline{s} = \underline{s}_{0} = (0, 0, 0)$?

$\ N_{0}$ =

2

Wie viele Empfangsworte $(N_{7})$ führen zum Syndrom $\underline{s} = \underline{s}_{7} = (1, 1, 1)$?

$\ N_{7}$ =

3

Welche Eigenschaften weisen alle Nebenklassenanführer $\underline{e}_{\mu}$ auf?

	Die letzten 3 Bit von $\underline{e}_{\mu}$ sind identisch mit $\underline{s}_{\mu}$ .
	Alle $\underline{e}_{\mu}$ beinhalten jeweils eine einzige 1.
	Alle $\underline{e}_{\mu}$ beinhalten höchstens eine 1.

4

Zu welchem Syndrom $\underline{s}_{\mu}$ führt der Fehlervektor (1, 0, 0, 0, 0, 0, 0)?

$\ \underline{e} = (1, 0, 0, 0, 0, 0, 0): \ \ {\rm Index} \ \ \mu $ =

5

Berechnen Sie jeweils das Syndrom $\underline{s}_{\mu}$ (Eingabe: Index $\mu$) für

$\ \underline{e} = (0, 1, 0, 0, 0, 0, 0): \ \ {\rm Index} \ \ \mu $ =

$\ \underline{e} = (0, 0, 1, 0, 0, 0, 0): \ \ {\rm Index} \ \ \mu $ =

$\ \underline{e} = (0, 0, 0, 1, 0, 0, 0): \ \ {\rm Index} \ \ \mu $ =

6

Welche Blockfehlerwahrscheinlichkeit ergibt sich für das BSC–Modell mit der Verfälschungswahrscheinlichkeit $\epsilon = 0.1$?

$\ {\rm Pr(Blockfehler)}$ =

Musterlösung

Solution

1. 2. 3. 4. 5. 6. 7.