Exercise 4.6: Product Code Generation

Verwendete Komponentencodes

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

dem Hammingcode (7, 4, 3) $\Rightarrow C_1$,
dem verkürzten Hamming–Code (6, 3, 3) $\Rightarrow 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 Z4.6 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},$$

$${ \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 Ersten Theorieseite:

die Parity–Matrix $\mathbf{P}^{(1)}$ bezüglich des horizontalen Codes $C_1$,
die Parity–Matrix $\mathbf{P}^{(2)}$ bezüglich des vertikalen Codes $C_2$,
die Checks–on–Checks–Matrix $\mathbf{P}^{(12)}$.

Hinweis:

Die Aufgabe gehört zum Kapitel Grundlegendes zu den Produktcode.

Fragebogen

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 jeweils 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 $C_2$ ebenso wie $C_1$ ein systematischer Code ist.
Auch der verkürzte (6, 3, 3)–Hammingcode $C_2$ ist linear, so dass auch ohne Rechnung die Zuordnung $\underline{u} = (0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$ angebbar ist.

(3)

Vollständige Codetabellen

Rechts sind die vollständigen Codetabellen des

Hammingcodes (7, 4, 3),
verkürzten Hammingcodes (6, 3, 3)

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

Die folgende kleine Grafik zeigt das Ergebnis der gesamten Codierung. Unten rechts ist die Checks–on–Checks–Matrix der Dimension $3 × 3$ zu erkennen.

Gesuchter Produktcode

Bezüglich der Teilaufgabe (3) sind nur die Lösungsvorschläge 1 und 2 richtig, wobei es Zufall ist, dass hier in der Checks–on–Checks–Matrix zwei Zeilen und zwei Spalten identisch sind.

Weiter ist anzumerken: Es ist egal, ob man die Zeilen 4 bis 6 der Gesamtmatrix über den Code $C_1$ gewinnt oder die Spalten 5 bis 7 über den Code $C_2$.

	Erste Spalte: $\underline{u} = (0, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 1, \, 0, \, 1, \, 1)$.
	Zweite Spalte: $\underline{u} = (1, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (1, \, 0, \, 1, \, 1, \, 0, \, 1)$.
	Dritte Spalte: $\underline{u} = (1, \, 0, \, 1) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 0, \, 0, \, 1, \, 1)$.
	Vierte Spalte: $\underline{u} = (0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 0, \, 0, \, 0, \,0, \, 0)$.

	Erste Zeile: $\underline{u} = (0, \, 1, \, 1, \, 0) \ \Rightarrow \ \underline{x} = (0, \, 1, \, 1, \, 0, \, 1, \, 0, \, 1)$.
	Zweite Zeile: $\underline{u} = (0, \, 0, \, 0, \, 0) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 1, \, 1, \, 1, \, 1, \, 1)$.
	Dritte Zeile: $\underline{u} = (1, \, 1, \, 1, \, 0) \ \Rightarrow \ \underline{x} = (1, \, 1, \, 1, \, 0, \, 0, \, 0, \, 0)$.

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