Aufgaben:Exercise 4.7: Product Code Decoding

• Return to book

Syndromtabellen der betrachteten Komponenten –Codes

Wir betrachten wie in Aufgabe A4.6 einen Produktcode, basierend auf

• dem Hammingcode (7, 4, 3)  ⇒ Code $C_1$,
• dem verkürzten Hammingcode (6, 3, 3)  ⇒  $C_2$.

Die Prüfmatrizen dieser Codes lauten:

$${ \boldsymbol{\rm H}}_1 = \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},$$

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

Die Hard Decision Decodierung dieses Codes geschieht vorzugsweise iterativ, indem abwechselnd alle Zeilen und anschließend alle Spalten syndromdecodiert werden.

Hinweis: Die Syndromdecodierung soll entsprechend der zweiten Theorieseite von Kapitel 4.2 erfolgen.

Die folgende Grafik zeigt drei verschiedene Coder– und Empfangsmatrizen, die in den Teilaufgaben (1), (2) und (3) zu analysieren sind. Wir benennen diese mit Konstellation (A), (B) und (C). Gelb markiert sind die Unterschiede der Empfangsmatrix von Konstellation (B) gegenüber (A). In beiden Fällen besteht die Codermatrix nur aus Nullen. Die Codematrix von (C) wurde in Aufgabe A4.6 ermittelt.

Vorgegebene Coder– und Empfangsmatrizen

Die Syndromdecodierung (eindimensionaler) Blockcodes wurde bereits im Kapitel Decodierung linearer Blockcodes behandelt. Hier eine kurze Zusammenfassung und eine Adaption an den zweidimensionalen Fall:

• Aus dem Empfangswort $\underline{y}$ (einer Zeile bzw. einer Spalte der vorgegebenen Empfangsmatrix) wird das Syndrom entsprechend $\underline{s} = \underline{y} \cdot \mathbf{H}_1^{\rm T}$ bzw. $\underline{s} = \underline{y} \cdot \mathbf{H}_2^{\rm T}$ gebildet.
• Mit dem Ergebnis $\underline{s} = \underline{s}_{\mu}$ kann man in obigen Tabellen den so genannten Nebenklassenanfüherer $\underline{e}_{\mu}$ ablesen. Das korrigierte Codewort ist dann $\underline{y} + \underline{e}_{\mu}$.

Fragebogen

1

Ist die 2D–Empfangsmatrix $\mathbf{A}$ decodierbar?

	Ja, nach der ersten Decodierung in horizontaler Richtung.
	Ja, nach der ersten Decodierung in vertikaler Richtung.
	Ja, nach der zweiten Decodierung in horizontaler Richtung.
	Ja, nach der zweiten Decodierung in vertikaler Richtung.
	Nein.

2

Ist die 2D–Empfangsmatrix $\mathbf{B}$ decodierbar?

	Ja, nach der ersten Decodierung in horizontaler Richtung.
	Ja, nach der ersten Decodierung in vertikaler Richtung.
	Ja, nach der zweiten Decodierung in horizontaler Richtung.
	Ja, nach der zweiten Decodierung in vertikaler Richtung.
	Nein.

3

Ist die 2D–Empfangsmatrix $\mathbf{C}$ decodierbar? Versuchen Sie, die Lösung über eine Äquivalenz zur Aufgabe (1) oder (2) zu finden.

	Ja, nach der ersten Decodierung in horizontaler Richtung.
	Ja, nach der ersten Decodierung in vertikaler Richtung.
	Ja, nach der zweiten Decodierung in horizontaler Richtung.
	Ja, nach der zweiten Decodierung in vertikaler Richtung.
	Nein.

Musterlösung

Solution

(1)  Der Decodiervorgang der Empfangsmatrix $\mathbf{A}$ wird durch die folgende Grafik verdeutlicht.

Zur Syndromdecodierung der 2D–Empfangsmatrix $\mathbf{A}$

• Die Einzelfehler in den Zeilen 1, 3, 5 und 6 werden vom (7, 4, 3)–Hammingcode erkannt und können korrigiert werden  ⇒  grüne Markierungen in der Grafik „1. Iteration horizontal”.
• Für die zweite Zeile ergibt sich das Syndrom

$$\underline{s} = \underline{y}_2 \hspace{-0.03cm}\cdot \hspace{-0.03cm}{ \boldsymbol{\rm H}}_1^{\rm T} = \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0, \hspace{0.03cm}1, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0 \right ) \cdot \hspace{-0.05cm} \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} \hspace{-0.05cm}= \left ( 1, \hspace{0.03cm} 1, \hspace{0.03cm}0 \right ) + \left ( 1, \hspace{0.03cm} 1, \hspace{0.03cm}1 \right )= \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}1 \right ) = \underline{s}_1 \hspace{0.03cm}.$$

Nach der oberen Syndromtabelle auf der Angabenseite wird somit fälschlicherweise das letzte Bit „korrigiert”. Fehlerkorrekturen sind in der oberen Grafik rot eingetragen.

• Entsprechend gilt für die vierte Zeile:

$$\underline{s} = \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}1, \hspace{0.03cm}0 \right ) \cdot { \boldsymbol{\rm H}}_1^{\rm T} = \left ( 1, \hspace{0.03cm} 1, \hspace{0.03cm}0 \right ) + \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0 \right )= \left ( 1, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right )= \underline{s}_4 \hspace{0.05cm}.$$

1. Dies bewirkt eine Fehlkorrektur von Bit 5.

• Die vertikale Decodierung der Spalten 1, 3, 4, 5, 6 und 7 ist problemlos, da höchstens ein Fehler pro Spalte auftritt, der durch den verkürzten Hammingcode (6, 3, 3) korrigiert werden kann.

• In Spalte 2 kommt es dagegen zu einer Fehlkorrektur des letzten Bits entsprechend der unteren Syndromtabelle. Mit der Transponierten der (6, 3)–Prüfmatrix $\mathbf{H}_2$ ergibt sich nämlich:

$$\underline{s}= \underline{y}_{2{\rm S}}\cdot { \boldsymbol{\rm H}}_2^{\rm T} = \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0, \hspace{0.03cm}1, \hspace{0.03cm}0, \hspace{0.03cm}0 \right ) \cdot \begin{pmatrix} 1 &1 &0 \\ 1 &0 &1 \\ 0 &1 &1 \\ 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix}= \left ( 1, \hspace{0.03cm} 0, \hspace{0.03cm}1 \right ) + \left ( 1, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right )= \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}1 \right ) = \underline{s}_1.$$

• Die zweite Horizontaldecodierung ist problemlos, da nun in jeder Zeile maximal ein Fehler auftritt  ⇒  Lösungsvorschlag 3.

(2)  Die folgende Grafik zeigt den Decodiervorgang entsprechend den Vorgaben gemäß $\mathbf{B}$.

Zur Syndromdecodierung der 2D–Empfangsmatrix $\mathbf{B}$

Trotz nur geringfügigen Modifikationen gegenüber $\mathbf{A}$ gibt es nun gravierende Unterschiede:

• Durch die erste Horizontaldecodierung lauten nun die „korrigierten” Zeilen 2 und 4 gleichermaßen: $(0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1)$, das heißt, das letzte Bit dieser Zeilen wird jeweils fehlkorrigiert.
• Die Vertikaldecodierung führt zu gleichlautenden Spalten 2, 4 und 6, nämlich $(0, \, 1, \, 0, \, 1, \, 0, \, 1)$. Danach gibt es in jeder Zeile und in jeder Spalte drei Einsen (oder keine einzige).
• Diese Konstellation bleibt für beliebig weitere (horizontale oder vertikale) Decodierungen erhalten, weil sich für $d_{\rm min} = 3$ stets das Syndrom $\underline{s}_0 (0, \, 0, \, 0)$ ergibt.

Richtig ist also der Lösungsvorschlag 5.

(3)  Vergleicht man die Coder– und Empfangsmatrizen (Unterschiede sind blau markiert), so kann man entsprechend der folgenden Grafik durch Modulo–2–Additionen die Fehlermatrix erstellen.

Matrizendarstellung von Coder, Empfänger und Fehlermuster

Die Fehlermatrix ist gleich der Empfangsmatrix von $\mathbf{A}$  ⇒  auch hier ist der Lösungsvorschlag 3 richtig.