Aufgaben:Exercise 1.11: Syndrome Decoding

• Return to book

Syndrom und Nebenklassenanführer des betrachteten Hamming–Codes (unvollständige Liste)

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 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 genau die gleiche Konstellation wie in der vorliegenden Aufgabe betrachtet wird.
• Verwenden Sie in der letzten Teilaufgabe (6) den BSC–Parameter $ \varepsilon = 0.1$.
• Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.

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

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) \text{:} \hspace{0.4cm} {\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) \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 \ = \ $

6

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

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