Exercise 1.11: Syndrome Decoding

Syndrom und Nebenklassenanführer (unvollständige Liste) des $\rm HC \ (7, \, 4, \, 3)$

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 $\underline{y} = \underline{x} \, ({\rm Codewort}) + \underline{e} \, ({\rm Fehlervektor})$ ein Element aus ${\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 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. Gibt es hiervon mehrere, so wählt man willkürlich einen davon aus.

Die obige Grafik zeigt die unvollständige Liste der Nebenklassenanführer $\underline{e}_{\mu}$ für die einzelnen $\underline{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 gehört zum Kapitel Decodierung linearer Blockcodes.
Zugrunde liegt ein Hamming–Code mit den Parametern $n = 7$ und $k = 4$ ⇒ $m = 3$. Alle Codeworte haben das folgende 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 die gleiche Konstellation wie in der vorliegenden Aufgabe betrachtet wird.
Verwenden Sie in der letzten Teilaufgabe (6) den BSC–Parameter $ \varepsilon = 0.1$.

Fragebogen

$N_{0} \ = \ $

$N_{7} \ = \ $

	Die letzten drei 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.4cm} {\rm Index} \ \mu \ = \ $

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

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

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

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

$\ \%$

Musterlösung

Solution

(1) Es gibt insgesamt $2^7 = 128$ verschiedene Codeworte $\underline{x}$ und gemäß 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} \text{...} \hspace{0.05cm} , \underline{s}_7\} = \{ \underline{s}_{\mu} \}\hspace{0.05cm}, \hspace{0.2cm} \mu = 0, \hspace{0.05cm} \text{...} \hspace{0.05cm} , 7 \hspace{0.05cm},$$

und ebenso viele Nebenklassen.

Da beim Hamming–Code, der ja perfekt ist, alle Fehlervektoren zu einer der acht 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 acht Nebenklassenanführer beinhalten deshalb

entweder keine „Eins” ($\underline{e}_{0}$ ⇒ es ist keinerlei Korrektur erforderlich), oder
genau eine einzige „Eins” ($\underline{e}_{1}, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \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}.$$

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

(5) 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 &1 &0 &0 &0 \hspace{0.2cm}\text{... }\end{pmatrix} \cdot { \boldsymbol{\rm H}}^{\rm T} = \begin{pmatrix} 1 &1 &0 \end{pmatrix} = \underline{s}_6$$

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

$$\begin{pmatrix} 0 &0 &1 &0 &0 \hspace{0.2cm}\text{... }\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}\text{... } \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 die Ergebnisse der Teilaufgaben (4) und (5) 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(\ge 2\hspace{0.15cm}Bitfehler\hspace{0.15cm})} =1 - { \rm Pr(0\hspace{0.15cm}Bitfehler)} - { \rm Pr(1\hspace{0.15cm}Bitfehler)} =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 $\varepsilon$ anzusetzen wäre als mit $n = 7$ (kleinere Symbolrate ⇒ kleinere Bandbreite ⇒ kleinere Rauschleistung).