Exercise 4.6: Product Code Generation

• Return to book

Verwendete Komponentencodes

Es soll ein  $\rm Produktcode \ (42, \ 12)$  generiert werden, der auf folgenden Komponentencodes aufbaut:

• dem Hammingcode  $\rm HC \ (7, \ 4, \ 3)$   ⇒   $\mathcal{C}_1$,
• dem verkürzten Hammingcode $\rm HC \ (6, \ 3, \ 3)$   ⇒   $\mathcal{C}_2$.

Die entsprechenden Codetabellen sind rechts angegeben, wobei jeweils drei Zeilen unvollständig sind. Diese sollen von Ihnen ergänzt werden.

Das zu einem Informationsblock  $\underline{u}$  gehörige Codewort ergibt sich allgemein entsprechend der Gleichung  $\underline{x} = \underline{u} \cdot \mathbf{G}$. Wie auch in der  Aufgabe 4.6Z  wird hier von folgenden Generatormatrizen ausgegangen:

$${ \boldsymbol{\rm G}}_1 = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.8cm} { \boldsymbol{\rm G}}_2 = \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}.$$

In der gesamten Aufgabe gelte für den Informationsblock:

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

Gesucht sind entsprechend der Nomenklatur auf der Seite  Grundstruktur eines Produktcodes:

• die Parity–Matrix  $\mathbf{P}^{(1)}$  bezüglich des horizontalen Codes  $\mathcal{C}_1$,
• die Parity–Matrix  $\mathbf{P}^{(2)}$  bezüglich des vertikalen Codes  $\mathcal{C}_2$,
• die Checks–on–Checks–Matrix  $\mathbf{P}^{(12)}$.

Hinweise:

• Die Aufgabe gehört zum Kapitel  Grundlegendes zu den Produktcode.
• Bezug genommen wird insbesondere auf die Seite  Grundstruktur eines Produktcodes.
• Die beiden Komponentencodes werden auch in der  Aufgabe 4.6Z  behandelt.

Fragebogen

1

Welche Ergebnisse liefert die Zeilencodierung mit dem  $(7, \ 4, \ 3)$–Code  $\mathcal{C}_1$?

	1. Zeile:   $\underline{u} = (0, \, 1, \, 1, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 1)$.
	2. Zeile:   $\underline{u} = (0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 1, \, 1, \, 1, \, 1, \, 1)$.
	3. Zeile:   $\underline{u} = (1, \, 1, \, 1, \, 0) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, 0)$.

2

Welche Ergebnisse liefert die Spaltencodierung mit dem  $(6, \ 3, \ 3)$–Code  $\mathcal{C}_2$?

	1. Zeile:   $\underline{u} = (0, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 1, \, 0, \, 1, \, 1)$.
	2. Zeile:   $\underline{u} = (1, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (1, \, 0, \, 1, \, 1, \, 0, \, 1)$.
	3. Zeile:   $\underline{u} = (1, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 0, \, 0, \, 1, \, 1)$.
	4. Zeile:   $\underline{u} = (0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 0, \, 0, \,0, \, 0)$.

3

Welche Aussagen gelten für die Checks–on–Checks–Matrix?

	Die erste Zeile lautet  $(1, \, 0, \, 1)$  und die erste Spalte  $(1, \, 1, \, 0)$.
	Die zweite Zeile lautet  $(1, \, 0, \, 1)$  und die zweite Spalte  $(0, \, 0, \, 0)$.
	Die dritte Zeile lautet  $(0, \, 0, \, 0)$  und die dritte Spalte  $(0, \, 0, \, 0)$.

Musterlösung

Solution

(1)  Richtig sind die Lösungsvorschläge 1 und 3:

Allgemein gilt $\underline{x} = \underline{u} \cdot \mathbf{G}$. Daraus folgt für

• den ersten Zeilenvektor:

$$\begin{pmatrix} 0 &1 &1 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} =\begin{pmatrix} 0 &1 &1 &0 &1 &0 &1 \end{pmatrix} \hspace{0.05cm},$$

• den zweiten Zeilenvektor:

$$\begin{pmatrix} 0 &0 &0 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} =\begin{pmatrix} 0 &0 &0 &0 &0 &0 &0 \end{pmatrix} \hspace{0.05cm},$$

• den dritten Zeilenvektor

$$\begin{pmatrix} 1 &1 &1 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 \\ 0 &1 &0 &0 &1 &1 &0 \\ 0 &0 &1 &0 &0 &1 &1 \\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix} =\begin{pmatrix} 1 &1 &1 &0 &0 &0 &0 \end{pmatrix} \hspace{0.05cm}.$$

(2)  Richtig sind die Lösungsvorschläge 1, 2 und 4:

$$\begin{pmatrix} 0 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &0 &1 &1 \end{pmatrix} =\begin{pmatrix} 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm},$$

$$\begin{pmatrix} 1 &0 &1 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &1 &0 &1 \\ 0 &0 &1 &0 &1 &1 \end{pmatrix} =\begin{pmatrix} 1 &0 &1 &1 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$

Zu dieser Teilaufgabe ist weiter anzumerken:

• Die angegebene erste Spalte ist schon allein deshalb richtig, weil sie mit einer Zeile (der dritten) der Generatormatrix $\mathbf{G}_2$ übereinstimmt.
• Die dritte Spalte des 2D–Codewortes müsste mit der zweiten Spalte identisch sein, da vom gleichen Codewort $(1, \, 0, \, 1)$ ausgegangen wird.
• Der angegebene Vektor $(1, \, 1, \, 0, \, 0, \, 1, \, 1)$ kann aber schon allein deshalb nicht richtig sein, da $\mathcal{C}_2$ ebenso wie $\mathcal{C}_1$ ein systematischer Code ist.
• Auch der verkürzte $(6, \ 3, \ 3)$–Hammingcode $C_2$ ist linear, so dass die Zuordnung $\underline{u} = (0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$ auch ohne Rechnung angebbar ist.

Vollständige Codetabellen

(3)  Rechts angegeben sind die vollständigen Codetabellen

• des Hammingcodes $(7, \ 4, \ 3)$, und
• des verkürzten Hammingcodes $(6, \ 3, \ 3)$.

Man erkennt daraus (ohne dass das für diese Aufgabe von Interesse ist), dass die hier betrachteten Codes jeweils die Hamming–Distanz $d_{\rm min} = 3$ aufweisen.

Gesuchter Produktcode

Die linke Grafik zeigt das Ergebnis der gesamten Codierung. Unten rechts erkennt man die Checks–on–Checks–Matrix der Dimension $3 × 3$.
Bezüglich der Teilaufgabe (3) sind die Lösungsvorschläge 1 und 2 richtig:

• Es ist Zufall, dass hier in der Checks–on–Checks–Matrix zwei Zeilen und zwei Spalten identisch sind.
• Es ist egal, ob man die Zeilen 4 bis 6 der Gesamtmatrix über den Code $\mathcal{C}_1$ gewinnt oder die Spalten 5 bis 7 über den Code $\mathcal{C}_2$.