Aufgaben:Exercise 4.7Z: Principle of Syndrome Decoding

• Return to book

Nebenklassenanführer für HC (7, 4, 3)

Die Syndromdecodierung wurde bereits im Kapitel Decodierung linearer Blockcodes ausführlich behandelt. Bei allen Hammingcodes, die ja bekanntlich perfekt sind, ergibt sich hiermit ein gleich gutes Decodierergebnis wie mit der (im allgemeinen) deutlich komplizierteren Maximum–Likelihood–Detektion.

Bei der Syndromdecodierung geht man wie folgt vor:

• Man bildet aus dem Empfangsvektor $\underline{y}$ der Länge $n$ und der Prüfmatrix $\mathbf{H}$ das Syndrom:

$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}, \hspace{0.5cm}{\rm Anmerkung\hspace{-0.10cm}:} \hspace{0.15cm}m = n-k \hspace{0.05cm}. $$

• Das Empfangswort $\underline{y} = \underline{x} \ {\rm (Codewort)} + \underline{e} \ {\rm (Fehlervektor)}$ ist nicht notwendigermaßen ein Element von ${\rm GF}(2^m)$, sicher aber ein Element von ${\rm GF}(2^n)$ und es gilt wegen $\underline{x} \cdot \mathbf{H}^{\rm T} = \underline{0}$ gleichermaßen:

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

• Viele Fehlermuster $\underline{e}$ führen zum gleichen Syndrom $\underline{s}$. Man fasst nun diejenigen Fehlermuster mit gleichem Syndrom $\underline{s}_{\mu}$ zur Nebenklasse ${\it \Psi}_{\mu}$ zusammen.

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

Die Tabelle oben zeigt die Liste der Nebenklassenanführer $\underline{e}_{\mu}$ für die einzelnen $\underline{s}_{\mu}$ beim Hammingcode (7, 4, 3). Diese Tabelle wird für die Teilaufgabe (1) benötigt.

Eine ähnliche Tabelle soll für den verkürzten Hammingcode (6, 3, 3) erstellt werden. Dieser wurde bereits in Aufgabe A4.6 sowie Aufgabe Z4.6 benutzt und ist durch seine Generatormatrix vorgegeben:

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

Im Gegensatz zum originalen (7, 4, 3)–Hammingcode ist der verkürzte (6, 3, 3)–Hammingcode nicht perfekt, so dass sich nicht für alle möglichen $\underline{s}_{\mu}$ ein Einfehler–Nebenklassenanführer $\underline{e}_{\mu}$ finden lässt.

Hinweise:

• Die Aufgabe bezieht sich auf das Kapitel Grundlegendes zu den Produktcodes und ist als Ergänzung zur Aufgabe A4.7 gedacht.
• Ähnliche Aufgabenstellungen wurden in Aufgabe A1.11 und Aufgabe Z1.11 im Kapitel 1.5 behandelt.
• Der Zusammenhang zwischen der Generatormatrix $\mathbf{G}$ und der Prüfmatrix $\mathbf{H}$ von systematischen Codes ist im Kapitel Allgemeine Beschreibung linearer Blockcodes angegeben.

Fragebogen

1

Das Empfangswort sei $\underline{y} = (0, \, 1, \, 1,\, 0, \, 1, \, 1, \, 0)$, das Syndrom $\underline{s} = (0, \, 1, \, 1)$. Für welches Codewort $\underline{x}$ von $C_1$ entscheidet sich der Syndromdecoder?

	Das wahrscheinlichste Codewort ist $\ \underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0)$.
	Das wahrscheinlichste Codewort ist $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 0)$.
	Das wahrscheinlichste Codewort ist $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 1)$.

2

Welche Aussagen gelten für die Prüfmatrix $\mathbf{H}$ des verkürzten Codes $C_2$?

	Es handelt sich um eine $4 × 6$–Matrix.
	Die erste Zeile dieser Matrix lautet: $\ 110100$.
	Die zweite Zeile dieser Matrix lautet: $\ 101010$.
	Die dritte Zeile dieser Matrix lautet: $\ 011001$.

3

Welches Syndrom $\underline{s}$ ergibt sich für das Fehlermuster $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$?

	$\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{s} = \underline{s}_0 = (0, \, 0, \, 0)$,
	$\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{s} = \underline{s}_1 = (0, \, 0, \, 1)$,
	$\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{s} = \underline{s}_7 = (1, \, 1, \, 1)$.

4

Welche der folgenden Aussagen stimmen bezüglich der Einfehlermuster?

	Einfehlermuster $\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 0)$  ⇒  Syndrom $\underline{s}_6 = (1, \, 1, \, 0)$,
	Einfehlermuster $\underline{e} = (0, \, 1, \, 0, \, 0, \, 0, \, 0)$  ⇒  Syndrom $\underline{s}_5 = (1, \, 1, \, 0)$,
	Einfehlermuster $\underline{e} = (0, \, 0, \, 1, \, 0, \, 0, \, 0)$  ⇒  Syndrom $\underline{s}_3 = (1, \, 1, \, 0)$,
	Einfehlermuster $\underline{e} = (0, \, 0, \, 0, \, 1, \, 0, \, 0)$  ⇒  Syndrom $\underline{s}_4 = (1, \, 1, \, 0)$,
	Einfehlermuster $\underline{e} = (0, \, 0, \, 0, \, 0, \, 1, \, 0)$  ⇒  Syndrom $\underline{s}_2 = (1, \, 1, \, 0)$,
	Einfehlermuster $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 1)$  ⇒  Syndrom $\underline{s}_1 = (1, \, 1, \, 0)$,

5

Welche der folgenden Fehlermuster führen zum Syndrom $\underline{s}_7 = (1, \, 1, \, 1)$?

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

Musterlösung

Solution

(1)  (2)  (3)  (4)  (5)