Aufgaben:Aufgabe 1.07: Prüf- und Generatormatrix des HC (7, 4, 3): Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(13 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2390__KC_A_1_7.png|right|frame|Prüfgleichungen des (7, 4, 3)–Hamming–Code]]
+
[[Datei:P_ID2390__KC_A_1_7.png|right|frame|Prüfgleichungen des <br>Hamming–Codes &nbsp; $(7, 4, 3)$]]
  
Die Grafik zeigt die Prüfgleichungen des (7, 4, 3)–Hamming–Codes, der bereits in der [[Aufgaben:1.6_Zum_(7,_4)–Hamming–Code|Aufgabe 1.6]] eingehend betrachtet und anhand der Codetabelle beschrieben wurde.
+
Die Grafik zeigt die Prüfgleichungen des&nbsp; $(7, 4, 3)$–Hamming–Codes,&nbsp; der bereits in der&nbsp; [[Aufgaben:1.6_Zum_(7,_4)–Hamming–Code|"Aufgabe 1.6"]]&nbsp; 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 '''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.
+
In dieser Aufgabe wird dieser Code &ndash; wie in der Kanalcodierung allgemein üblich &ndash; nun durch zwei Matrizen charakterisiert:
  
*Eine zweite Beschreibungsmöglichkeit bietet die Generatormatrix '''G''', mit ''k'' Zeilen und ''n'' Spalten. Sie gibt den Zusammenhang zwischen den Informationsworten <u>''u''</u> und den Codeworten <u>''x''</u> an:
+
*Die Prüfmatrix&nbsp; $\boldsymbol{\rm H}$&nbsp; ist eine Matrix mit&nbsp; $m = n - k$&nbsp; Zeilen und&nbsp; $n$&nbsp; Spalten.&nbsp;  Sie beschreibt die&nbsp; $m = 3$&nbsp; Prüfgleichungen,&nbsp;  wobei sich die erste Zeile auf die Elemente des roten Kreises und die zweite Zeile auf die des grünen Kreises bezieht.&nbsp;  Die letzte Zeile gibt die Modulo–2–Summe des blauen Kreises wieder.
 +
 
 +
*Eine zweite Beschreibungsmöglichkeit bietet die Generatormatrix&nbsp; $ \boldsymbol{\rm G}$&nbsp; mit&nbsp; $k$&nbsp; Zeilen und&nbsp; $n$&nbsp; Spalten.&nbsp;  Sie gibt den Zusammenhang zwischen den Informationsworten&nbsp; $ \underline{u}$&nbsp; und den Codeworten&nbsp;  $\underline{x}$&nbsp; an:
 
:$$ \underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \hspace{0.05cm}.$$
 
:$$ \underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \hspace{0.05cm}.$$
  
Daraus und aus der Gleichung '''H''' $· x^{\rm T} = $'''0''' kann der Zusammenhang zwischen der Prüfmatrix '''H''' und der Generatormatrix '''G''' hergestellt werden:
+
Daraus und aus der Gleichung&nbsp;  $ \boldsymbol{\rm H} · \underline{x}^{\rm T} = \underline{0}$&nbsp; kann der Zusammenhang zwischen der Prüfmatrix&nbsp; $ \boldsymbol{\rm H}$&nbsp; und der Generatormatrix&nbsp; $\boldsymbol{\rm G}$&nbsp; 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)$$
+
:$$\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,&nbsp;  dass in diesen Gleichungen&nbsp; "$\underline{0}$"&nbsp; einen Zeilenvektor mit&nbsp; $k$&nbsp; Elementen bezeichnet und&nbsp; "$\boldsymbol{\rm 0}$"&nbsp; eine Matrix mit&nbsp; $m$&nbsp; Zeilen und&nbsp; $k$&nbsp; Spalten.&nbsp;  Alle Elemente von&nbsp; "$\underline{0}$"&nbsp; bzw.&nbsp; "$\boldsymbol{\rm 0}$"&nbsp; sind Null.
 +
 
 +
Handelt es sich um einen&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|systematischen Code]],&nbsp;  so können die Beschreibungsgrößen&nbsp; $\boldsymbol{\rm H}$&nbsp; und&nbsp; $\boldsymbol{\rm G}$&nbsp; unter Zuhilfenahme von&nbsp; "Einheitsmatrizen"&nbsp; wie folgt geschrieben werden:
  
:$$\Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = { \boldsymbol{\rm 0}} \hspace{0.05cm}.$$
+
:$${ \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}.$$
  
Anzumerken ist, dass in diesen Gleichungen <u>0</u> einen Zeilenvektor mit ''k'' Elementen bezeichnet und '''0''' eine Matrix mit ''m'' Zeilen und ''k'' Spalten. Alle Elemente von <u>0</u> bzw. '''0''' sind identisch 0.
+
$\boldsymbol{\rm P}$&nbsp; ist dabei eine Matrix mit&nbsp; $k$&nbsp; Zeilen und&nbsp; $m$&nbsp; Spalten.&nbsp;  Dementsprechend besteht die transponierte Matrix&nbsp; ${ \boldsymbol{\rm P}}^{\rm T}$&nbsp; aus&nbsp; $m$&nbsp; Zeilen und&nbsp; $k$&nbsp; Spalten.
 +
  
Handelt es sich um einen [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|systematischen Code]], so können die beiden Beschreibungsgrößen '''H''' und '''G''' unter Zuhilfenahme von ''Einheitsmatrizen'' wie folgt geschrieben werden:
 
  
:$${ \boldsymbol{\rm G}} \hspace{-0.15cm}\ = \ \hspace{-0.15cm}\left({ \boldsymbol{\rm I}}_k \: ; \: { \boldsymbol{\rm P}}\right) \hspace{0.05cm},$$
 
:$$ { \boldsymbol{\rm H}} \hspace{-0.15cm}\ = \ \hspace{-0.15cm}\left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.05cm}.$$
 
  
'''P''' ist dabei eine Matrix mit ''k'' Zeilen und ''m'' Spalten. Dementsprechend besitzt die transponierte Matrix ${ \boldsymbol{\rm P}}^{\rm T} \ m$ Zeilen und ''k'' Spalten.
+
Hinweise:
 +
 
 +
*Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|"Allgemeine Beschreibung linearer Blockcodes"]].
 +
*Bezug genommen wird insbesondere auf die Seiten&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Pr.C3.BCfmatrix|"Codefestlegung durch die Prüfmatrix"]]&nbsp; sowie&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix|"Codefestlegung durch die Generatormatrix"]].
 
   
 
   
''Hinweis'' :
 
  
Die Aufgabe bezieht sich auf das Kapitel [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer Blockcodes]].
+
 
  
  
Zeile 36: Zeile 43:
 
<quiz display=simple>
 
<quiz display=simple>
  
{Welches Format hat die Prüfmatrix?
+
{Welches Format hat die Prüfmatrix&nbsp; $\boldsymbol{\rm H}$?
 
|type="{}"}
 
|type="{}"}
${ \boldsymbol{\rm H}}\ {\rm: Spaltenzahl}$ = { 7 3% }
+
${\rm Spaltenzahl} \ = \ $ { 7 }
${ \boldsymbol{\rm H}}\ {\rm: Zeilenzahl}$ = { 3 3% }
+
${\rm Zeilenzahl} \ = \ $ { 3 }
  
  
{Welche Aussagen hinsichtlich der Prüfmatrix '''H''' sind zutreffend?
+
{Welche Aussagen sind  hinsichtlich der Prüfmatrix&nbsp; $\boldsymbol{\rm H}$&nbsp; zutreffend?
 
|type="[]"}
 
|type="[]"}
  
+ Die erste Zeile lautet: 1101100.
+
+ Die erste Zeile lautet: &nbsp; "$1101100$".
+ Die zweite Zeile lautet: 0111010.
+
+ Die zweite Zeile lautet: &nbsp; "$0111010$".
+ Die dritte Zeile lautet: 1011001.
+
+ Die dritte Zeile lautet: &nbsp; "$1011001$".
  
{Woran erkennt man, dass ein systematischer Code vorliegt?
+
{Woran erkennt man,&nbsp;  dass ein systematischer Code vorliegt?
 
|type="[]"}
 
|type="[]"}
  
 
- In jeder Zeile gibt es eine gerade Anzahl von Einsen.
 
- In jeder Zeile gibt es eine gerade Anzahl von Einsen.
+ Am Ende von '''H''' erkennt man eine Einheitsmatrix.
+
+ Am Ende von&nbsp; $\boldsymbol{\rm H}$&nbsp; erkennt man eine Einheitsmatrix.
- Die mittlere Spalte von '''H''' ist mit Einsen besetzt.
+
- Die mittlere Spalte von&nbsp; $\boldsymbol{\rm H}$&nbsp; ist mit Einsen besetzt.
  
{Geben Sie die Generatormatrix '''G''' an. Welche Aussagen stimmen?
+
{Geben Sie die Generatormatrix&nbsp; $\boldsymbol{\rm G}$&nbsp; an.&nbsp;  Welche Aussagen stimmen?
 
|type="[]"}
 
|type="[]"}
  
+ Die erste Zeile lautet: 1000101,
+
+ Die erste Zeile lautet: &nbsp; "$1000101$",
- Die zweite Zeile lautet: 0111010,
+
- Die zweite Zeile lautet: &nbsp; "$0111010$",
+ Die letzte Zeile lautet: 0001111.
+
+ Die letzte Zeile lautet: &nbsp; "$0001111$".
  
{Welches Codewort $x_{11}$ ergibt sich für $u_{11}$ = (1, 0, 1, 1)?
+
{Welches Codewort&nbsp; $x_{11}$&nbsp; ergibt sich für&nbsp; $u_{11} = (1, 0, 1, 1)$?
 
|type="[]"}
 
|type="[]"}
  
 
- $x_{11} = (1, 1, 1, 1, 0, 0, 0),$
 
- $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, 0),$
 
+ $x_{11} = (1, 0, 1, 1, 0, 0, 1).$
 
+ $x_{11} = (1, 0, 1, 1, 0, 0, 1).$
  
Zeile 74: Zeile 81:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; 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$.
+
'''(1)'''&nbsp; Die Anzahl der Spalten der Prüfmatrix&nbsp;  $\boldsymbol{\rm H}$&nbsp;  ist gleich der Codelänge&nbsp;  $\underline{n = 7}$.  
 +
:Die Zeilenzahl ist gleich der Anzahl der Prüfgleichungen,&nbsp;  im vorliegenden Fall gilt&nbsp;  $\underline{m = 3} = n - k$.
  
'''(2)'''&nbsp;  Ein Vergleich mit der Grafik auf der Angabenseite zeigt, dass <u>alle Aussagen</u> zutreffen. Mit
+
 
 +
 
 +
'''(2)'''&nbsp;  Ein Vergleich mit der Grafik auf der Angabenseite zeigt,&nbsp;  dass&nbsp;  <u>alle Aussagen</u>&nbsp;  zutreffen.&nbsp;  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)$$
 
:$$\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)$$
Zeile 90: Zeile 100:
 
:$${ \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}.$$
 
:$${ \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:
+
Die Angabe von &nbsp;$\boldsymbol{\rm H}$&nbsp; ist nicht eindeutig.&nbsp;  Bei anderer Reihenfolge der Prüfgleichungen ergäbe sich beispielsweise eine zweite,&nbsp;  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}.$$
 
:$${ \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)'''&nbsp; Richtig ist die <u>Aussage 2</u>. Bei einem systematischen Code lässt sich die Prüfmatrix in folgender Form darstellen:
+
 
 +
 
 +
'''(3)'''&nbsp; Richtig ist die&nbsp;  <u>Aussage 2</u>:
 +
*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}.$$
 
:$${ \boldsymbol{\rm H}} =\left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.05cm}.$$
  
Im vorliegenden Beispiel gilt mit $m = 3$:
+
*Im vorliegenden Beispiel gilt mit&nbsp;  $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}.$$
 
:$${ \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)'''&nbsp; Allgemein lautet der Zusammenhang zwischen der ''m×n''–Prüfmatrix und der ''k×n''–Generatormatrix:
+
 
 +
 
 +
'''(4)'''&nbsp; Richtig sind  die&nbsp;  <u>Aussagen 1 und 3</u>:
 +
*Allgemein lautet der Zusammenhang zwischen der&nbsp;  $m×n$–Prüfmatrix und der&nbsp;  $k×n$–Generatormatrix:
  
 
:$${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = { \boldsymbol{\rm 0}} \hspace{0.05cm}$$  
 
:$${ \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.
+
*Die Matrix&nbsp;  "$ \boldsymbol{\rm 0}$"&nbsp;  ist nur mit Nullen belegt und hat&nbsp;  $m$&nbsp;  Zeilen und&nbsp;  $k$&nbsp;  Spalten.&nbsp;  Bei einem systematischen Code – wie hier – besteht folgender Zusammenhang:
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}.$$
 
:$${ \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:
+
*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}.$$
 
:$${ \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 <u>Aussagen 1 und 3</u>.
+
 
  
 
'''(5)'''&nbsp; Die anzuwendende Gleichung lautet:
 
'''(5)'''&nbsp; Die anzuwendende Gleichung lautet:
:$$\underline{x}_{11} \hspace{-0.15cm}\ = \ \hspace{-0.15cm} \underline{u}_{11} \cdot { \boldsymbol{\rm G}} =$$
+
:$$\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}.$$
:$$ \ \ = \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 [[Aufgaben:1.6_Zum_(7,_4)–Hamming–Code|Aufgabe 1.6]] zeigt die Richtigkeit dieser Berechnung ⇒ <u>Antwort 3</u>. 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.
+
Ein Vergleich mit der Tabelle von&nbsp;  [[Aufgaben:1.6_Zum_(7,_4)–Hamming–Code|Aufgabe 1.6]]&nbsp;  zeigt die Richtigkeit dieser Berechnung &nbsp; &nbsp; <u>Antwort 3</u>.  
 +
*Die Antwort 1 kann schon deshalb nicht richtig sein,&nbsp;  weil das keiner systematischen Codierung entspricht.  
 +
* $(1, 0, 1, 1, 0, 0, 0)$&nbsp;  gemäß Vorschlag 2 ist kein gültiges Codewort.&nbsp;  Hiermit wird die in der Grafik auf der Angabenseite blau markierte Prüfgleichung nicht erfüllt.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Aktuelle Version vom 10. Juli 2022, 13:43 Uhr

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:



Fragebogen

1

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

${\rm Spaltenzahl} \ = \ $

${\rm Zeilenzahl} \ = \ $

2

Welche Aussagen sind hinsichtlich der Prüfmatrix  $\boldsymbol{\rm H}$  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  $\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.