Exercise 1.11: Syndrome Decoding

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 $\underline{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 \, ({\rm Codewort}) + \underline{e} \, ({\rm Fehlervektor})$ ein Element von ${\rm 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 $\underline{e}$ führen zum gleichen Syndrom $\underline{s}$. Man fasst nun diejenigen Fehlermuster mit dem gleichen Syndrom $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 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.

Hinweise:

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

Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

Fragebogen

$N_{0} \ = \ $

$N_{7} \ = \ $

	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.

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

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

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

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

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

Musterlösung

Solution

(1) Es gibt insgesamt $2^7 = 128$ verschiedene Codeworte $\underline{x}$ und entsprechend dem BSC–Modell auch $2^7$ unterschiedliche Empfangsworte $y$ und ebenso viele Fehlervektoren $\underline{e}$. Mit $m = 3$ Prüfbits gibt es $2^3 = 8$ unterschiedliche Werte für das Syndrom,

$$\underline{s} \hspace{0.05cm} \in \hspace{0.05cm} \{ \underline{s}_0, \underline{s}_1, ... \hspace{0.05cm} , \underline{s}_7\} = \{ \underline{s}_{\mu} \}\hspace{0.05cm}, \hspace{0.2cm} \mu = 0, ... \hspace{0.05cm} , 7 \hspace{0.05cm},$$

und ebenso viele Nebenklassen. Da beim Hamming–Code, der ja perfekt ist, alle Fehlervektoren zu einer der 8 Nebenklassen ${\it \Psi}_{\mu}$ gehören und zudem die Anzahl aller Vektoren in allen Nebenklassen gleich ist („Warum sollte es anders sein?” Genügt Ihnen das als Beweis?), erhält man

$$ N_0 = \frac{2^n}{2^m} = 2^k \hspace{0.15cm} \underline{= 16} \hspace{0.05cm}.$$

Zur Nebenklasse ${\it \Psi}_{0}$ gehören beispielsweise – siehe Musterlösung zur Aufgabe 1.11Z – die Vektoren

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

(2) Entsprechend den Kommentaren des letzten Teilergebnisses gilt gleichermaßen $N_{7} \ \underline{= 16}$.

(3) Richtig ist Antwort 3: Der Nebenklassenanführer $\underline{e}_{\mu}$ ist derjenige Fehlervektor $\underline{e}$ mit dem geringsten Hamming–Gewicht $w_{\rm H}(\underline{e})$, der zum Syndrom $\underline{s}_{\mu}$ führt. Der hier betrachtete Hamming–Code (7, 4, 3) ist perfekt. Das heißt: Alle 8 Nebenklassenanführer beinhalten deshalb

keine „Eins” ($\underline{e}_{0}$ ⇒ es ist keinerlei Korrektur erforderlich), oder
genau eine einzige „Eins” ($\underline{e}_{1}, ... , \underline{e}_{7}$ ⇒ es muss ein Informations– oder Prüfbit korrigiert werden).

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

$$\underline{s} = \begin{pmatrix} 1 &0 &0 &0 &0 &0 &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} 1 &0 &1 \end{pmatrix} = \underline{s}_5 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} \hspace{0.15cm} \underline{ \mu= 5} \hspace{0.05cm}.$$

(5)

Nebenklassenanführer des $(7, \, 4, \, 3)$–Hamming–Codes

Ein Vergleich mit der Lösung zur letzten Teilaufgabe zeigt, dass $(0, 1, 0, 0, 0, 0, 0) · \boldsymbol{\rm H}^{\rm T}$ als Syndrom die zweite Zeile der transponierten Matrix ergibt:

$$\begin{pmatrix} 0 &0 &1 &0 &0 \hspace{0.2cm}... \end{pmatrix} \cdot { \boldsymbol{\rm H}}^{\rm T} = \begin{pmatrix} 0 &1 &1 \end{pmatrix} = \underline{s}_3$$

$$\Rightarrow\hspace{0.45cm} \underline{ \mu= 3} \hspace{0.05cm}, \hspace{0.2cm} \underline{e}_3 = \begin{pmatrix} 0 &0 &1 &0 &0 &0 &0 \end{pmatrix}\hspace{0.05cm}.$$

$$\begin{pmatrix} 0 &0 &0 &1 &0 \hspace{0.2cm}... \end{pmatrix} \cdot { \boldsymbol{\rm H}}^{\rm T} = \begin{pmatrix} 1 &1 &1 \end{pmatrix} = \underline{s}_7$$

$$\Rightarrow\hspace{0.45cm} \underline{ \mu= 7} \hspace{0.05cm}, \hspace{0.2cm} \underline{e}_7 = \begin{pmatrix} 0 &0 &0 &1 &0 &0 &0 \end{pmatrix}\hspace{0.05cm}.$$

Die nebenstehende Grafik fasst das Ergebnis der Teilaufgaben (3) und (4) nochmals zusammen.

(6) Beim betrachteten $(7, \, 4, \, 3)$–Hamming–Code wird dann für das richtige Informationswort entschieden, wenn bei der Übertragung höchstens ein Bit innerhalb des Codewortes verfälscht wird. Daraus folgt:

$${ \rm Pr(Blockfehler)} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} { \rm Pr(zwei\hspace{0.15cm}Bitfehler\hspace{0.15cm} oder\hspace{0.15cm} mehr)} =$$

$$\hspace{2.875cm}\ = \ \hspace{-0.15cm} 1 - { \rm Pr(kein\hspace{0.15cm}Bitfehler)} - { \rm Pr(ein\hspace{0.15cm}Bitfehler)} =$$

$$\hspace{2.875cm}\ = \ \hspace{-0.15cm} 1 - 0.9^7 - 7 \cdot 0.1 \cdot 0.9^7 \hspace{0.15cm} \underline{ = 0.15} \hspace{0.05cm}.$$

Bei uncodierter Übertragung eines Blocks mit $n = k = 4$ Bit ergäbe sich beim gleichen BSC–Kanal:

$${ \rm Pr(Blockfehler)}= 1 - 0.9^4 \approx 0.344 \hspace{0.05cm}.$$

Der Vergleich ist allerdings nicht ganz fair, da mit $n = 4$ eine kleinere Verfälschungswahrscheinlichkeit $\epsilon$ anzusetzen wäre als mit $n = 7$ (kleinere Symbolrate ⇒ kleinere Bandbreite ⇒ kleinere Rauschleistung).