Aufgabe 1.07: Prüf- und Generatormatrix des HC (7, 4, 3)

Prüfgleichungen des
Hamming–Codes $(7, 4, 3)$

Die Grafik zeigt die Prüfgleichungen des $(7, 4, 3)$–Hamming–Codes, der bereits in der "Aufgabe 1.6" eingehend betrachtet und anhand der Codetabelle beschrieben wurde.

In dieser Aufgabe wird dieser Code – wie in der Kanalcodierung allgemein üblich – nun durch zwei Matrizen charakterisiert:

Die Prüfmatrix $\boldsymbol{\rm H}$ ist eine Matrix mit $m = n - k$ Zeilen und $n$ Spalten. Sie beschreibt die $m = 3$ Prüfgleichungen, wobei sich die erste Zeile auf die Elemente des roten Kreises und die zweite Zeile auf die des grünen Kreises bezieht. Die letzte Zeile gibt die Modulo–2–Summe des blauen Kreises wieder.

Eine zweite Beschreibungsmöglichkeit bietet die Generatormatrix $ \boldsymbol{\rm G}$ mit $k$ Zeilen und $n$ Spalten. Sie gibt den Zusammenhang zwischen den Informationsworten $ \underline{u}$ und den Codeworten $\underline{x}$ an:

$$ \underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \hspace{0.05cm}.$$

Daraus und aus der Gleichung $ \boldsymbol{\rm H} · \underline{x}^{\rm T} = \underline{0}$ kann der Zusammenhang zwischen der Prüfmatrix $ \boldsymbol{\rm H}$ und der Generatormatrix $\boldsymbol{\rm G}$ hergestellt werden:

$$\underline{x}^{\rm T} = { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T} = \underline{0}\hspace{0.5cm} \forall \hspace{0.15cm}\underline{u} \in {\rm GF}(2^k)\hspace{0.3cm} \Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = { \boldsymbol{\rm 0}} \hspace{0.05cm}.$$

Anzumerken ist, dass in diesen Gleichungen "$\underline{0}$" einen Zeilenvektor mit $k$ Elementen bezeichnet und "$\boldsymbol{\rm 0}$" eine Matrix mit $m$ Zeilen und $k$ Spalten. Alle Elemente von "$\underline{0}$" bzw. "$\boldsymbol{\rm 0}$" sind Null.

Handelt es sich um einen systematischen Code, so können die Beschreibungsgrößen $\boldsymbol{\rm H}$ und $\boldsymbol{\rm G}$ unter Zuhilfenahme von "Einheitsmatrizen" wie folgt geschrieben werden:

$${ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_k \: ; \: { \boldsymbol{\rm P}}\right) \hspace{0.5cm} \Rightarrow \hspace{0.5cm} { \boldsymbol{\rm H}} = \left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.05cm}.$$

$\boldsymbol{\rm P}$ ist dabei eine Matrix mit $k$ Zeilen und $m$ Spalten. Dementsprechend besteht die transponierte Matrix ${ \boldsymbol{\rm P}}^{\rm T}$ aus $m$ Zeilen und $k$ Spalten.

Hinweise:

Die Aufgabe gehört zum Kapitel "Allgemeine Beschreibung linearer Blockcodes".
Bezug genommen wird insbesondere auf die Seiten "Codefestlegung durch die Prüfmatrix" sowie "Codefestlegung durch die Generatormatrix".

Fragebogen

Musterlösung

(1) Die Anzahl der Spalten der Prüfmatrix $\boldsymbol{\rm H}$ ist gleich der Codelänge $\underline{n = 7}$.

Die Zeilenzahl ist gleich der Anzahl der Prüfgleichungen, im vorliegenden Fall gilt $\underline{m = 3} = n - k$.

(2) Ein Vergleich mit der Grafik auf der Angabenseite zeigt, dass alle Aussagen zutreffen. Mit

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

ergeben sich folgende Prüfgleichungen:

$$x_1 \oplus x_2 \oplus x_4 \oplus x_5 \hspace{-0.1cm}\ = \ \hspace{-0.1cm} 0 \hspace{0.3cm}{\rm (roter\hspace{0.15cm}Kreis)}\hspace{0.05cm},$$

$$x_2 \oplus x_3 \oplus x_4 \oplus x_6 \hspace{-0.1cm}\ = \ \hspace{-0.1cm} 0 \hspace{0.3cm}{\rm (gr\ddot{u}ner\hspace{0.15cm}Kreis)}\hspace{0.05cm},$$

$$ x_1 \oplus x_3 \oplus x_4 \oplus x_7 \hspace{-0.1cm}\ = \ \hspace{-0.1cm} 0 \hspace{0.3cm}{\rm (blauer\hspace{0.15cm}Kreis)}\hspace{0.05cm}.$$

Damit erhält man für die Prüfmatrix:

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

Die Angabe von $\boldsymbol{\rm H}$ ist nicht eindeutig. Bei anderer Reihenfolge der Prüfgleichungen ergäbe sich beispielsweise eine zweite, ebenfalls richtige Prüfmatrix:

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

(3) Richtig ist die Aussage 2:

Bei einem systematischen Code lässt sich die Prüfmatrix in folgender Form darstellen:

$${ \boldsymbol{\rm H}} =\left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.05cm}.$$

Im vorliegenden Beispiel gilt mit $m = 3$:

$${ \boldsymbol{\rm P}}^{\rm T} = \begin{pmatrix} 1 &1 &0 &1\\ 0 &1 &1 &1\\ 1 &0 &1 &1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm I}}_3 = \begin{pmatrix} 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$

(4) Richtig sind die Aussagen 1 und 3:

Allgemein lautet der Zusammenhang zwischen der $m×n$–Prüfmatrix und der $k×n$–Generatormatrix:

$${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = { \boldsymbol{\rm 0}} \hspace{0.05cm}$$

Die Matrix "$ \boldsymbol{\rm 0}$" ist nur mit Nullen belegt und hat $m$ Zeilen und $k$ Spalten. Bei einem systematischen Code – wie hier – besteht folgender Zusammenhang:

$${ \boldsymbol{\rm H}} =\left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.3cm}\Leftrightarrow \hspace{0.3cm}{ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_k \: ; \:{ \boldsymbol{\rm P}} \right) \hspace{0.05cm}.$$

Im vorliegenden Fall erhält man:

$${ \boldsymbol{\rm I}}_4 = \begin{pmatrix} 1 &0 &0 &0\\ 0 &1 &0 &0\\ 0 &0 &1 &0\\ 0 &0 &0 &1 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} { \boldsymbol{\rm P}} = \begin{pmatrix} 1 &0 &1\\ 1 &1 &0\\ 0 &1 &1\\ 1 &1 &1 \end{pmatrix}\hspace{0.3cm}\Rightarrow \hspace{0.3cm} { \boldsymbol{\rm G}} = \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}.$$

(5) Die anzuwendende Gleichung lautet:

$$\underline{x}_{11} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} \underline{u}_{11} \cdot { \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &1 &1 \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 &0 &1 &1 &0 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$

Ein Vergleich mit der Tabelle von Aufgabe 1.6 zeigt die Richtigkeit dieser Berechnung ⇒ Antwort 3.

Die Antwort 1 kann schon deshalb nicht richtig sein, weil das keiner systematischen Codierung entspricht.
$(1, 0, 1, 1, 0, 0, 0)$ gemäß Vorschlag 2 ist kein gültiges Codewort. Hiermit wird die in der Grafik auf der Angabenseite blau markierte Prüfgleichung nicht erfüllt.

	Die erste Zeile lautet: "$1101100$".
	Die zweite Zeile lautet: "$0111010$".
	Die dritte Zeile lautet: "$1011001$".

	In jeder Zeile gibt es eine gerade Anzahl von Einsen.
	Am Ende von $\boldsymbol{\rm H}$ erkennt man eine Einheitsmatrix.
	Die mittlere Spalte von $\boldsymbol{\rm H}$ ist mit Einsen besetzt.

	Die erste Zeile lautet: "$1000101$",
	Die zweite Zeile lautet: "$0111010$",
	Die letzte Zeile lautet: "$0001111$".

	$x_{11} = (1, 1, 1, 1, 0, 0, 0),$
	$x_{11} = (1, 0, 1, 1, 0, 0, 0),$
	$x_{11} = (1, 0, 1, 1, 0, 0, 1).$