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

Aus LNTwww
Wechseln zu:Navigation, Suche

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 beiden 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 :



Fragebogen

1

Welches Format hat die Prüfmatrix $\boldsymbol{\rm H}$?

${\rm Spaltenzahl} \ = \ $

${\rm Zeilenzahl} \ = \ $

2

Welche Aussagen hinsichtlich der Prüfmatrix $\boldsymbol{\rm H}$ sind zutreffend?

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

3

Woran erkennt man, dass ein systematischer Code vorliegt?

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.

4

Geben Sie die Generatormatrix $\boldsymbol{\rm G}$ an. Welche Aussagen stimmen?

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

5

Welches Codewort $x_{11}$ ergibt sich für $u_{11} = (1, 0, 1, 1)$?

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


Musterlösung

(1)  Die Anzahl der Spalten der Prüfmatrix 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 H ist nicht eindeutig. Würde man die Reihenfolge der Prüfgleichungen vertauschen, so 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)  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 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}.$$

Richtig sind demnach die Aussagen 1 und 3.

(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. Und schließlich: (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.