Kanalcodierung/Allgemeine Beschreibung linearer Blockcodes: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(16 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 8: Zeile 8:
 
== Lineare Codes und zyklische Codes ==
 
== Lineare Codes und zyklische Codes ==
 
<br>
 
<br>
Alle bisher behandelten Codes  
+
Alle bisher behandelten Codes,
*<i>Single Parity&ndash;check Code</i>,  
+
*der&nbsp; "Single Parity&ndash;check Code",  
*<i>Repetition Code</i>,
+
*der&nbsp; "Repetition Code"&nbsp; und
* <i>Hamming&ndash;Code</i>
+
*der&nbsp; Hamming&ndash;Code
 +
 
  
 
sind linear. Nun wird die für binäre Blockcodes gültige Definition von Linearität nachgereicht.<br>
 
sind linear. Nun wird die für binäre Blockcodes gültige Definition von Linearität nachgereicht.<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Ein '''linearer binärer Blockcode''' $\mathcal{C}$ ist ein Satz von $2^k$ Codeworten $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_n)$, wobei die (Modulo&ndash;2)&ndash;Summe zweier beliebiger Codeworte $\underline{x}$ und $\underline{x}'$ wiederum ein gültiges Codewort ergibt:
+
$\text{Definition:}$&nbsp; Ein&nbsp; '''linearer binärer Blockcode'''&nbsp; $\mathcal{C}$ ist ein Satz von&nbsp; $2^k$&nbsp; Codeworten&nbsp; $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_n)$, wobei die (Modulo&ndash;2)&ndash;Summe zweier beliebiger Codeworte&nbsp; $\underline{x}$&nbsp; und&nbsp; $\underline{x}\hspace{0.05cm}'$&nbsp; wiederum ein gültiges Codewort ergibt:
  
 
::<math>\underline{x}, \underline{x}\hspace{0.05cm}' \in {\rm GF}(2^n),\hspace{0.3cm} \underline{x}, \underline{x}\hspace{0.05cm}' \in  \mathcal{C}  
 
::<math>\underline{x}, \underline{x}\hspace{0.05cm}' \in {\rm GF}(2^n),\hspace{0.3cm} \underline{x}, \underline{x}\hspace{0.05cm}' \in  \mathcal{C}  
Zeile 22: Zeile 23:
 
  \hspace{0.05cm}.</math>
 
  \hspace{0.05cm}.</math>
  
Diese Bedingung muss auch für $\underline{x} = \underline{x}'$ erfüllt sein.<br>
+
Diese Bedingung muss auch für&nbsp; $\underline{x} = \underline{x}\hspace{0.05cm}'$&nbsp; erfüllt sein.<br>
  
<i>Hinweis:</i> Die Modulo&ndash;Addition wird für den Rest dieses Buches zur Vereinfachung der Schreibweise nicht mehr durch das Modulo&ndash;Additionszeichen ausgedrückt, sondern mit dem herkömmlichen Pluszeichen.}} <br>
+
<i>Hinweis:</i> &nbsp; Die Modulo&ndash;Addition wird für den Rest dieses Buches zur Vereinfachung der Schreibweise nicht mehr durch das Modulo&ndash;Additionszeichen ausgedrückt, sondern mit dem herkömmlichen Pluszeichen.}} <br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 1:}$&nbsp; Wir betrachten zwei (3, 2)&ndash;Blockcodes:
+
$\text{Beispiel 1:}$&nbsp; Wir betrachten zwei&nbsp; $\text{(3, 2)}$&ndash;Blockcodes:
  
 
::<math>\mathcal{C}_1 = \{ (0, 0, 0) \hspace{0.05cm}, (0, 1, 1) \hspace{0.05cm},(1, 0, 1) \hspace{0.05cm},(1, 1, 0) \}\hspace{0.05cm},</math>
 
::<math>\mathcal{C}_1 = \{ (0, 0, 0) \hspace{0.05cm}, (0, 1, 1) \hspace{0.05cm},(1, 0, 1) \hspace{0.05cm},(1, 1, 0) \}\hspace{0.05cm},</math>
Zeile 34: Zeile 35:
  
 
Man erkennt:
 
Man erkennt:
*Der Code $\mathcal{C}_1$ ist linear, da die Modulo&ndash;2&ndash;Addition zweier beliebiger Codeworte stets auch ein gültiges Codewort ergibt, zum Beispiel $(0, 1, 1) + (1, 0, 1) = (1, 1, 0)$.<br>
+
*Der Code&nbsp; $\mathcal{C}_1$&nbsp; ist linear, da die Modulo&ndash;2&ndash;Addition zweier beliebiger Codeworte stets auch ein gültiges Codewort ergibt, z.B.&nbsp; $(0, 1, 1) + (1, 0, 1) = (1, 1, 0)$.<br>
  
*Die obige Definition gilt auch für die Modulo&ndash;2&ndash;Addition eines Codewortes mit sich selbst, zum Beispiel $(0, 1, 1) + (0, 1, 1) = (0, 0, 0)$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Jeder lineare Code beinhaltet das Nullwort $\underline{0}$.<br>
+
*Die obige Definition gilt auch für die Modulo&ndash;2&ndash;Addition eines Codewortes mit sich selbst, zum Beispiel&nbsp; $(0, 1, 1) + (0, 1, 1) = (0, 0, 0)$ <br>&nbsp;&nbsp;&#8658;&nbsp;&nbsp; Jeder lineare Code beinhaltet das Nullwort&nbsp; $\underline{0}$.<br>
  
*Obwohl die letzte Voraussetzung erfüllt wird, ist $\mathcal{C}_2$ kein linearer Code. Für diesen Code gilt nämlich beispielsweise:  $(0, 1, 1) + (1, 1, 0) = (1, 0, 1)$. Dies ist kein gültiges Codewort von $\mathcal{C}_2$.}}<br>
+
*Obwohl die letzte Voraussetzung erfüllt wird, ist&nbsp; $\mathcal{C}_2$&nbsp; kein linearer Code. Für diesen Code gilt nämlich beispielsweise: &nbsp; $(0, 1, 1) + (1, 1, 0) = (1, 0, 1)$. Dies ist kein gültiges Codewort von&nbsp; $\mathcal{C}_2$.}}<br>
  
 
Im Folgenden beschränken wir uns ausschließlich auf lineare Codes, da nichtlineare Codes für die Praxis von untergeordneter Bedeutung sind.<br>
 
Im Folgenden beschränken wir uns ausschließlich auf lineare Codes, da nichtlineare Codes für die Praxis von untergeordneter Bedeutung sind.<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Ein linearer Blockcode $\mathcal{C}$ heißt '''zyklisch''', wenn eine jede zyklische Verschiebung eines Codewortes $\underline{x}$ (nach links oder rechts) wieder ein gültiges Codewort ergibt:
+
$\text{Definition:}$&nbsp; Ein linearer Blockcode&nbsp; $\mathcal{C}$&nbsp; heißt&nbsp; '''zyklisch''', wenn jede zyklische Verschiebung eines Codewortes&nbsp; $\underline{x}$&nbsp; (nach links oder rechts) ein gültiges Codewort ergibt:
  
::<math>\underline{x}= (x_1, x_2, ... \hspace{0.05cm}, x_n) \in  \mathcal{C}  
+
::<math>\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...} \hspace{0.05cm}, x_n) \in  \mathcal{C}  
  \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{x}\hspace{0.05cm}'= (x_n, x_1,  ... \hspace{0.05cm}, x_{n-1}) \in  \mathcal{C}
+
  \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{x}\hspace{0.05cm}'= (x_n, x_1,  \hspace{0.05cm}\text{...} \hspace{0.05cm} \hspace{0.05cm}, x_{n-1}) \in  \mathcal{C}
 
  \hspace{0.05cm}.</math>}}<br>
 
  \hspace{0.05cm}.</math>}}<br>
  
[[Datei:P ID2354 KC T 1 3 S3c.png|right|frame|Codetabelle des systematischen (7, 4, 3)–Hamming–Codes<br>
+
[[Datei:P ID2354 KC T 1 3 S3c.png|right|frame|Codetabelle des systematischen&nbsp; $\text{(7, 4, 3)}$&ndash;Hamming–Codes;<br>
schwarz: $k= 4$ Informationsbits, rot: $n-k = 3$ Prüfbits ]]
+
schwarz: &nbsp; $k= 4$&nbsp; Informationsbits, rot: &nbsp; $n-k = 3$&nbsp; Prüfbits ]]
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
 
$\text{Beispiel 2:}$&nbsp;  
 
$\text{Beispiel 2:}$&nbsp;  
*Man erkennt aus der Tabelle für den [[Kanalcodierung/Beispiele_binärer_Blockcodes#Hamming.E2.80.93Codes|(7, 4, 3)&ndash;Hamming&ndash;Code]] , dass dieser linear und zyklisch ist.
+
*Man erkennt aus der Tabelle für den&nbsp; [[Kanalcodierung/Beispiele_binärer_Blockcodes#Hamming.E2.80.93Codes|$\text{HC (7, 4, 3)}$]], dass dieser linear und zyklisch ist.
*Es ergibt sich auch dann ein gültiges Codewort, wenn man alle Bit invertiert: $0 &#8596; 1$.  
+
*Es ergibt sich auch dann ein gültiges Codewort, wenn man alle Bit invertiert: &nbsp; $0 &#8596; 1$.  
*Auch das $\underline{0}$&ndash;Wort ($n$ mal eine &bdquo;Null&rdquo;) und das $\underline{1}$&ndash;Wort ($n$ mal eine &bdquo;Eins&rdquo;) sind bei diesem Code zulässig.}}<br>
+
*Auch das&nbsp; $\underline{0}$&ndash;Wort&nbsp; ($n$&nbsp; mal eine &bdquo;Null&rdquo;) und das&nbsp; $\underline{1}$&ndash;Wort ($n$&nbsp; mal eine &bdquo;Eins&rdquo;) sind bei diesem Code zulässig.}}<br>
  
 
== Codefestlegung durch die Prüfmatrix ==
 
== Codefestlegung durch die Prüfmatrix ==
 
<br>
 
<br>
[[Datei:P ID2355 KC T 1 3 S3.png|right|frame|(7, 4, 3)–Hamming–Code]]
+
[[Datei:P ID2355 KC T 1 3 S3.png|right|frame|$\text{(7, 4, 3)}$–Hamming–Code]]
Wir betrachten den [[Kanalcodierung/Beispiele_binärer_Blockcodes#Hamming.E2.80.93Codes|(7, 4, 3)&ndash;Hamming&ndash;Code]] mit Codeworten $\underline{x}$ der Länge $n=7$, nämlich
+
Wir betrachten den&nbsp; [[Kanalcodierung/Beispiele_binärer_Blockcodes#Hamming.E2.80.93Codes|$\text{(7, 4, 3)}$&ndash;Hamming&ndash;Code]]&nbsp; mit Codeworten&nbsp; $\underline{x}$&nbsp; der Länge&nbsp; $n=7$, bestehend aus
*den $k = 4$ Informationsbits $x_1$>, $x_2$, $x_3$, $x_4$ , und<br>
+
*$k = 4$&nbsp; Informationsbits&nbsp; $x_1$,&nbsp; $x_2$,&nbsp; $x_3$,&nbsp; $x_4$, und<br>
*den  $m = 3$ Prüfbits $x_5$, $x_6$, $x_7$.<br><br>
+
*$m = n-k = 3$&nbsp; Prüfbits $x_5$,&nbsp; $x_6$,&nbsp; $x_7$.<br><br>
  
 
Die Paritätsgleichungen lauten somit:
 
Die Paritätsgleichungen lauten somit:
  
::<math>x_1 + x_2 + x_3 + x_5    \hspace{-0.1cm} = \hspace{-0.1cm} 0 \hspace{0.05cm},\hspace{0.5cm}
+
::<math>x_1 + x_2 + x_3 + x_5    = 0 \hspace{0.05cm},</math>
x_2 + x_3 + x_4 + x_6    \hspace{-0.1cm} = \hspace{-0.1cm} 0 \hspace{0.05cm},\hspace{0.05cm}
+
::<math>x_2 + x_3 + x_4 + x_6    = 0 \hspace{0.05cm},</math>
x_1 + x_2 + x_4 + x_7    \hspace{-0.1cm} = \hspace{-0.1cm} 0 \hspace{0.05cm}. </math>
+
::<math>x_1 + x_2 + x_4 + x_7    =  0 \hspace{0.05cm}. </math>
  
 
In Matrixschreibweise lautet dieser Gleichungssatz:
 
In Matrixschreibweise lautet dieser Gleichungssatz:
Zeile 76: Zeile 77:
  
 
In dieser Gleichung werden verwendet:
 
In dieser Gleichung werden verwendet:
*die '''Prüfmatrix''' ${ \boldsymbol{\rm H}}$  mit $m = n-k = 3$ Zeilen und $n = 7$ Spalten:
+
*die&nbsp; '''Prüfmatrix'''&nbsp; ${ \boldsymbol{\rm H}}$&nbsp; mit&nbsp; $m = n-k = 3$&nbsp; Zeilen und&nbsp; $n = 7$&nbsp; Spalten:
  
 
::<math>{ \boldsymbol{\rm H}} = \begin{pmatrix}
 
::<math>{ \boldsymbol{\rm H}} = \begin{pmatrix}
Zeile 84: Zeile 85:
 
       \end{pmatrix}\hspace{0.05cm},</math>
 
       \end{pmatrix}\hspace{0.05cm},</math>
  
*das ''Codewort'' $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_7)$ der Länge $n = 7$,<br>
+
*das&nbsp; ''Codewort''&nbsp; $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_7)$&nbsp; der Länge&nbsp; $n = 7$,<br>
  
*das ''Nullvektor'' $\underline{0} = (0, 0, 0)$ der Länge $m = 3$.<br><br>
+
*der&nbsp; ''Nullvektor''&nbsp; $\underline{0} = (0, 0, 0)$&nbsp; der Länge&nbsp; $m = 3$.<br><br>
  
Durch Transponieren werden aus den ''Zeilenvektoren'' $\underline{x}$ und $\underline{0}$ die entsprechenden ''Spaltenvektoren'' $\underline{x}^{\rm T}$ und $\underline{0}^{\rm T}$.<br>
+
Durch Transponieren werden aus den&nbsp; ''Zeilenvektoren''&nbsp; $\underline{x}$ &nbsp;und&nbsp; $\underline{0}$&nbsp; die entsprechenden&nbsp; ''Spaltenvektoren''&nbsp; $\underline{x}^{\rm T}$ &nbsp;und&nbsp; $\underline{0}^{\rm T}$.<br>
  
[[Datei:P ID2356 KC T 1 4 S2.png|right|frame|(6, 3, 3)–Blockcode]]
+
[[Datei:P ID2356 KC T 1 4 S2.png|right|frame|$\text{(6, 3, 3)}$–Blockcode]]
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 3:}$&nbsp; Die Grafik illustriert die $m = 3$ Paritätsgleichungen eines Codes $\mathcal{C}$ mit den Codeparametern $n = 6$ und $k = 3$  in der Reihenfolge rot, grün und blau. Es handelt sich also nicht um einen Hamming–Code.
+
$\text{Beispiel 3:}$&nbsp; Die Grafik illustriert die&nbsp; $m = 3$&nbsp; Paritätsgleichungen eines Codes&nbsp; $\mathcal{C}$&nbsp; mit den Codeparametern&nbsp; $n = 6$&nbsp; und&nbsp; $k = 3$&nbsp; in der Reihenfolge rot, grün und blau. Es handelt sich also nicht um einen Hamming–Code&nbsp; $(n \ne 2^m-1)$.
  
Entsprechend $\boldsymbol{\rm H} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T}$ lautet die Prüfmatrix:
+
Entsprechend der Gleichung&nbsp; $\boldsymbol{\rm H} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T}$&nbsp; lautet die Prüfmatrix:
 
::<math> \boldsymbol{\rm H} = \begin{pmatrix}
 
::<math> \boldsymbol{\rm H} = \begin{pmatrix}
 
1 &1 &0 &1 &0 & 0\\
 
1 &1 &0 &1 &0 & 0\\
Zeile 101: Zeile 102:
 
       \end{pmatrix}\hspace{0.05cm}.</math>
 
       \end{pmatrix}\hspace{0.05cm}.</math>
  
Die $2^k = 8$ Codeworte bei systematischer Realisierung lauten (mit den Prüfbits rechts vom kleinen Pfeil):
+
Die&nbsp; $2^k = 8$&nbsp; Codeworte bei systematischer Realisierung lauten (mit den Prüfbits rechts vom kleinen Pfeil):
  
 
:<math>\underline{x}_0 = (0, 0, 0_{\hspace{0.01cm} \rightarrow} 0, 0, 0)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_1 = (0, 0, 1_{\hspace{0.01cm} \rightarrow}0, 1, 1)\hspace{0.05cm},\hspace{0.5cm}  
 
:<math>\underline{x}_0 = (0, 0, 0_{\hspace{0.01cm} \rightarrow} 0, 0, 0)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_1 = (0, 0, 1_{\hspace{0.01cm} \rightarrow}0, 1, 1)\hspace{0.05cm},\hspace{0.5cm}  
 
\underline{x}_2 = (0, 1, 0_{\hspace{0.01cm} \rightarrow}1, 0, 1)\hspace{0.05cm},\hspace{0.5cm}\underline{x}_3 = (0, 1, 1_{\hspace{0.01cm} \rightarrow}1, 1, 0)\hspace{0.05cm}, </math>
 
\underline{x}_2 = (0, 1, 0_{\hspace{0.01cm} \rightarrow}1, 0, 1)\hspace{0.05cm},\hspace{0.5cm}\underline{x}_3 = (0, 1, 1_{\hspace{0.01cm} \rightarrow}1, 1, 0)\hspace{0.05cm}, </math>
 
:<math>\underline{x}_4 = (1, 0, 0_{\hspace{0.01cm} \rightarrow} 1, 1, 0)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_5 = (1, 0, 1_{\hspace{0.01cm} \rightarrow}1, 0, 1)\hspace{0.05cm},\hspace{0.5cm}  
 
:<math>\underline{x}_4 = (1, 0, 0_{\hspace{0.01cm} \rightarrow} 1, 1, 0)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_5 = (1, 0, 1_{\hspace{0.01cm} \rightarrow}1, 0, 1)\hspace{0.05cm},\hspace{0.5cm}  
\underline{x}_6 = (1, 1, 0_{\hspace{0.01cm} \rightarrow}0, 1, 1)\hspace{0.05cm}, \hspace{0.2cm} \underline{x}_7 = (1, 1, 1_{\hspace{0.01cm} \rightarrow}0, 0, 0)\hspace{0.05cm}.</math>
+
\underline{x}_6 = (1, 1, 0_{\hspace{0.01cm} \rightarrow}0, 1, 1)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_7 = (1, 1, 1_{\hspace{0.01cm} \rightarrow}0, 0, 0)\hspace{0.05cm}.</math>
  
 
Man erkennt aus diesen Angaben:
 
Man erkennt aus diesen Angaben:
*Die Spaltenanzahl  $\boldsymbol{\rm H}$ ist gleich der Codelänge $n$.<br>
+
*Die Spaltenanzahl&nbsp; $\boldsymbol{\rm H}$&nbsp; ist gleich der Codelänge $n$.<br>
  
*Die Zeilenanzahl von $\boldsymbol{\rm H}$ ist gleich der Anzahl $m = n-k$ der Prüfgleichungen.<br>
+
*Die Zeilenanzahl von&nbsp; $\boldsymbol{\rm H}$&nbsp; ist gleich der Anzahl&nbsp; $m = n-k$&nbsp; der Prüfgleichungen.<br>
  
*Aus $\boldsymbol{\rm H} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} $ folgt nicht, dass alle Codeworte eine gerade Anzahl von Einsen beinhalten.}}<br>
+
*Aus&nbsp; $\boldsymbol{\rm H} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} $&nbsp; folgt also nicht, dass alle Codeworte eine gerade Anzahl von Einsen beinhalten.}}<br>
  
 
== Codefestlegung durch die Generatormatrix ==
 
== Codefestlegung durch die Generatormatrix ==
 
<br>
 
<br>
Die Prüfmatrix $\boldsymbol{\rm H}$  eines $(n, k)$)&ndash;Blockcodes hat $m = n-k$ Zeilen und $n$ Spalten. Den gleichen Code kann man aber auch durch die $\boldsymbol{\rm G}$ mit ebenfalls $n$ Spalten, aber $k$ Zeilen beschreiben:<br>
+
Die Prüfmatrix&nbsp; $\boldsymbol{\rm H}$&nbsp; eines&nbsp; $(n, k)$&ndash;Blockcodes hat&nbsp; $m = n-k$&nbsp; Zeilen und&nbsp; $n$&nbsp; Spalten. Den gleichen Code kann man aber auch durch die Matrix&nbsp; $\boldsymbol{\rm G}$&nbsp; mit ebenfalls&nbsp; $n$&nbsp; Spalten, aber&nbsp; $k$&nbsp; Zeilen beschreiben:<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Ein linearer binärer Blockcode $\mathcal{C}$ kann durch die '''Prüfmatrix''' $\boldsymbol{\rm H}$ bzw. mit der '''Generatormatrix''' $\boldsymbol{\rm G}$ wie folgt charakterisiert werden:
+
$\text{Definition:}$&nbsp; Ein linearer binärer Blockcode&nbsp; $\mathcal{C}$&nbsp; kann durch die&nbsp; '''Prüfmatrix'''&nbsp; $\boldsymbol{\rm H}$&nbsp; bzw. mit der&nbsp; '''Generatormatrix'''&nbsp; $\boldsymbol{\rm G}$&nbsp; wie folgt charakterisiert werden:
  
 
::<math>\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\text{:} \hspace{0.2cm}{ \boldsymbol{\rm H} } \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} \}\hspace{0.05cm},</math>  
 
::<math>\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\text{:} \hspace{0.2cm}{ \boldsymbol{\rm H} } \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} \}\hspace{0.05cm},</math>  
Zeile 129: Zeile 130:
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 4:}$&nbsp; Wir betrachten einen linearen $(5, 3)$&ndash;Blockcode mit der Generatormatrix
+
$\text{Beispiel 4:}$&nbsp; Wir betrachten einen linearen&nbsp; $(5, 3)$&ndash;Blockcode mit der Generatormatrix (auch dies ist kein Hamming&ndash;Code)
  
:<math> \boldsymbol{\rm G} = \begin{pmatrix}
+
::<math> \boldsymbol{\rm G} = \begin{pmatrix}
 
1 &1 &0 &1 &1\\
 
1 &1 &0 &1 &1\\
 
0 &1 &0 &1 &0\\
 
0 &1 &0 &1 &0\\
Zeile 144: Zeile 145:
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Damit werden die Informationsworte $\underline{u}= (u_1, u_2, u_3)$  den Codeworten $\underline{x}= (x_1, x_2, x_3, x_4, x_5)$ gemäß der folgenden Tabelle mit acht Einträgen zugeordnet. Es gilt $\underline{x} = \underline{u} \cdot  \boldsymbol{\rm G}$.
+
Damit werden die Informationsworte&nbsp; $\underline{u}= (u_1, u_2, u_3)$&nbsp; den Codeworten&nbsp; $\underline{x}= (x_1, x_2, x_3, x_4, x_5)$&nbsp; gemäß folgenden Gleichungen zugeordnet. <br>Es gilt stets&nbsp; $\underline{x} = \underline{u} \cdot  \boldsymbol{\rm G}$:
  
 
::<math>\underline{u}_0 = (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_0 = (0, 0, 0, 0, 0) \hspace{0.05cm},</math>
 
::<math>\underline{u}_0 = (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_0 = (0, 0, 0, 0, 0) \hspace{0.05cm},</math>
Zeile 156: Zeile 157:
  
 
''Anmerkungen'':
 
''Anmerkungen'':
*Die hier zur Berechnung herangezogenen Basisvektoren $\underline{g}_1$, $\underline{g}_2$ und  $\underline{g}_3$ &ndash; jeweils mit der Länge $n = 5$ &ndash; entsprechen den $k = 3$ Zeilen der Generatormatrix $\boldsymbol{\rm G}$.  
+
*Die hier zur Berechnung herangezogenen Basisvektoren&nbsp; $\underline{g}_1$,&nbsp; $\underline{g}_2$&nbsp; und&nbsp; $\underline{g}_3$&nbsp; &ndash; jeweils mit der Länge&nbsp; $n = 5$&nbsp; &ndash; entsprechen den&nbsp; $k = 3$&nbsp; Zeilen der Generatormatrix&nbsp; $\boldsymbol{\rm G}$.  
*Dieser Code ist wegen $d_{\rm min} = 1$ weder zur Fehlerkorrektur noch zur Fehlererkennung geeignet ist. Trotzdem wird er auch auf den nächsten Seiten beispielhaft weiter betrachtet.<br>
+
*Dieser Code ist wegen&nbsp; $d_{\rm min} = 1$&nbsp; weder zur Fehlerkorrektur noch zur Fehlererkennung geeignet ist. Trotzdem wird dieser Code auch auf den nächsten Seiten beispielhaft betrachtet, weil die Codierergebnisse gut interpretierbar sind.<br>
* Wir möchten Sie an dieser Stelle auf das Applet [[Gram&ndash;Schmidt&ndash;Verfahren]] zum Buch &bdquo;Digitalsignalübertragung&rdquo; aufmerksam machen, das die Berechnung von Basisfunktionen vermittelt, wenn auch in völlig anderem Zusammenhang als im hier gebrauchten Zusammenhang.<br>
+
* Wir möchten Sie an dieser Stelle auf das Applet&nbsp; [[Applets:Gram-Schmidt-Verfahren|Gram&ndash;Schmidt&ndash;Verfahren]]&nbsp; zum Buch &bdquo;Digitalsignalübertragung&rdquo; aufmerksam machen, das die Berechnung von Basisfunktionen vermittelt, wenn auch in einem anderen als dem hier gebrauchten Zusammenhang.<br>
  
  
 
== Identische Codes ==
 
== Identische Codes ==
 
<br>
 
<br>
Die im Beispiel 4 auf der letzten Seite verwendeten Vektoren $\underline{g}_1$, $\underline{g}_2$, ... , $\underline{g}_k$ sind die [[Digitalsignal%C3%BCbertragung/Signale,_Basisfunktionen_und_Vektorr%C3%A4ume#Orthonormale_Basisfunktionen| Basisvektoren]] des linearen Blockcodes $\mathcal{C}$. Der Code selbst kann als $k$&ndash;dimensionaler <i>Untervektorraum</i> von $\text{GF}(2^n)$ angesehen werden. Die Basisvektoren $\underline{g}_1$, $\underline{g}_2$, ... , $\underline{g}_k$ sind linear unabhängig.<br>
+
Die im&nbsp; $\text{Beispiel 4}$&nbsp; auf der letzten Seite verwendeten Vektoren&nbsp; $\underline{g}_1$,&nbsp; $\underline{g}_2$,&nbsp; ... &nbsp;,&nbsp; $\underline{g}_k$&nbsp; sind die&nbsp; [[Digitalsignal%C3%BCbertragung/Signale,_Basisfunktionen_und_Vektorr%C3%A4ume#Orthonormale_Basisfunktionen| Basisvektoren]]&nbsp; des linearen Blockcodes&nbsp; $\mathcal{C}$.  
 +
*Der Code selbst kann als&nbsp; $k$&ndash;dimensionaler <i>Untervektorraum</i> von&nbsp; $\text{GF}(2^n)$&nbsp; angesehen werden.  
 +
*Die Basisvektoren&nbsp; $\underline{g}_1$,&nbsp; $\underline{g}_2$,&nbsp; ... &nbsp;, $\underline{g}_k$&nbsp; sind linear unabhängig.<br>
 +
 
  
Der Untervektorraum $\mathcal{C}$ wird aber nicht nur durch die Basisvektoren
+
Der Untervektorraum&nbsp; $\mathcal{C}$&nbsp; wird aber nicht nur durch die Basisvektoren
  
 
::<math>\underline{g}_1 = (1, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.3cm}
 
::<math>\underline{g}_1 = (1, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.3cm}
Zeile 171: Zeile 175:
 
\underline{g}_3 = (0, 1, 1, 1, 0) \hspace{0.05cm}</math>
 
\underline{g}_3 = (0, 1, 1, 1, 0) \hspace{0.05cm}</math>
  
aufgespannt, sondern andere Basisvektoren $\underline{g}_1'$, $\underline{g}_2'$ und $\underline{g}_3'$ sind ebenso geeignet, so lange zwischen diesen die lineare Unabhängigkeit gewährleistet ist.<br>
+
aufgespannt, sondern andere Basisvektoren&nbsp; $\underline{g}\hspace{0.05cm}'_1$,&nbsp; $\underline{g}\hspace{0.05cm}'_2$&nbsp; und&nbsp; $\underline{g}\hspace{0.05cm}'_3$&nbsp; sind ebenso geeignet, so lange zwischen diesen die lineare Unabhängigkeit gewährleistet ist.<br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 5:}$&nbsp; Wir vergleichen den Code $\mathcal{C}$ von Beispiel 4 mit einem zweiten Code $\mathcal{C}'$.  Die Generatormatrizen lauten:
+
$\text{Beispiel 5:}$&nbsp; Wir vergleichen den Code&nbsp; $\mathcal{C}$&nbsp; von&nbsp; $\text{Beispiel 4}$&nbsp; mit einem zweiten Code&nbsp; $\mathcal{C}\hspace{0.05cm}'$.  Die Generatormatrizen lauten:
  
 
::<math> \boldsymbol{\rm G} = \begin{pmatrix}
 
::<math> \boldsymbol{\rm G} = \begin{pmatrix}
Zeile 197: Zeile 201:
 
\end{pmatrix}\hspace{0.05cm}.</math>
 
\end{pmatrix}\hspace{0.05cm}.</math>
  
Die beiden Codes sind identisch: Sie beinhalten die genau gleichen Codeworte; es gilt nur eine andere Zuordnung. Bei dem Übergang von $\boldsymbol{\rm G}$ auf $\boldsymbol{\rm G}'$ wurden folgende erlaubte Operationen ausgeführt:
+
*Die beiden Codes sind identisch: &nbsp; Sie beinhalten die genau gleichen Codeworte; es gilt nur eine andere Zuordnung.  
 +
*Bei dem Übergang von&nbsp; $\boldsymbol{\rm G}$&nbsp; auf&nbsp; $\boldsymbol{\rm G}\hspace{0.05cm}'$&nbsp; wurden folgende erlaubte Operationen ausgeführt:
  
 
::<math>\underline{g}\hspace{0.05cm}'_1 = \underline{g}_1 + \underline{g}_2  \hspace{0.05cm},\hspace{0.3cm}
 
::<math>\underline{g}\hspace{0.05cm}'_1 = \underline{g}_1 + \underline{g}_2  \hspace{0.05cm},\hspace{0.3cm}
Zeile 203: Zeile 208:
 
\underline{g}\hspace{0.05cm}'_3 = \underline{g}_2 + \underline{g}_3 \hspace{0.05cm}.</math>
 
\underline{g}\hspace{0.05cm}'_3 = \underline{g}_2 + \underline{g}_3 \hspace{0.05cm}.</math>
  
Zum entsprechenden Code $\mathcal{C}'$ kommt man mit der Gleichung $\underline{x}' = \underline{u} \cdot  \boldsymbol{\rm G}'$.
+
*Zum entsprechenden Code&nbsp; $\mathcal{C}'$&nbsp; kommt man mit der Gleichung&nbsp; $\underline{x}' = \underline{u} \cdot  \boldsymbol{\rm G}'$:
  
 
::<math>\underline{u}_0 = (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_0 =  
 
::<math>\underline{u}_0 = (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_0 =  
Zeile 209: Zeile 214:
 
::<math>\underline{u}_1 = (0, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_1 =  
 
::<math>\underline{u}_1 = (0, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_1 =  
 
(0, 0, 1, 0, 0) \hspace{0.1cm}= \hspace{0.1cm}\underline{x}_3\hspace{0.05cm},</math>
 
(0, 0, 1, 0, 0) \hspace{0.1cm}= \hspace{0.1cm}\underline{x}_3\hspace{0.05cm},</math>
::<math>\underline{u}_2 \hspace{-0.15cm} = \hspace{-0.15cm} (0, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_2 =  
+
::<math>\underline{u}_2 = (0, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_2 =  
 
(0, 1, 0, 1, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_2\hspace{0.05cm},</math>
 
(0, 1, 0, 1, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_2\hspace{0.05cm},</math>
 
::<math>\underline{u}_3 = (0, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_3 =  
 
::<math>\underline{u}_3 = (0, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_3 =  
Zeile 222: Zeile 227:
 
(1, 1, 1, 1, 1) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_7\hspace{0.05cm}.</math>
 
(1, 1, 1, 1, 1) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_7\hspace{0.05cm}.</math>
  
Die entsprechenden Codeworte $\underline{x}_i = \underline{u}_i \cdot  \boldsymbol{\rm G}$ des odes $\mathcal{C}$ &nbsp; &rArr; &nbsp; Generatormatrix  $\boldsymbol{\rm G}$ sind im  [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix|Beispiel 4]] (vorherige Seite) angegeben.}}<br>
+
*Die entsprechenden Codeworte&nbsp; $\underline{x}_i = \underline{u}_i \cdot  \boldsymbol{\rm G}$&nbsp; des Codes&nbsp; $\mathcal{C}$ &nbsp; &rArr; &nbsp; Generatormatrix&nbsp; $\boldsymbol{\rm G}$&nbsp; sind im&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix|$\text{Beispiel 4}$]]&nbsp; (vorherige Seite) angegeben.}}<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Fazit:}$&nbsp; Die Codetabellen von Beispiel 4 und Beispiel 5 machen deutlich:
+
$\text{Fazit:}$&nbsp; Die Codetabellen von&nbsp; $\text{Beispiel 4}$&nbsp; und&nbsp; $\text{Beispiel 5}$&nbsp; machen deutlich:
*$\mathcal{C}$ und $\mathcal{C}'$ beinhalten die genau gleichen Codeworte. Sie sind damit <i>identische Codes</i> und besitzen beide die gleiche Korrekturfähigkeit (siehe nächste Seite).<br>
+
*$\mathcal{C}$&nbsp; und&nbsp; $\mathcal{C}\hspace{0.05cm}'$&nbsp; beinhalten die genau gleichen Codeworte. Sie sind damit&nbsp; <i>identische Codes</i>&nbsp; und besitzen beide die gleiche Korrekturfähigkeit (siehe nächste Seite).<br>
  
*$\mathcal{C}'$ ist aber nun ein ''systematischer Code'', da die ersten $k$ Binärstellen eines jeden Codewortes $\underline{x}'_i$ mit den Binärstellen des Informationswortes $\underline{u}$  übereinstimmen.}}<br>
+
*$\mathcal{C}\hspace{0.05cm}'$&nbsp; ist nun ein&nbsp; ''systematischer Code'', da die ersten&nbsp; $k$&nbsp; Binärstellen eines jeden Codewortes&nbsp; $\underline{x}\hspace{0.05cm}'_i$&nbsp; mit den Binärstellen des Informationswortes&nbsp; $\underline{u}_i$&nbsp; übereinstimmen.}}<br>
  
 
== Systematische Codes==
 
== Systematische Codes==
Zeile 235: Zeile 240:
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Bei einem '''systematischen (n, k)&ndash;Blockcode''' $\mathcal{C}$ beinhaltet jedes Codewort $\underline{x}$ explizit das Informationswort $\underline{u}$.  
+
$\text{Definition:}$&nbsp; Bei einem&nbsp; $\text{systematischen }(n, k)&ndash;\text{Blockcode} \ \ \mathcal{C}$&nbsp; beinhaltet jedes Codewort&nbsp; $\underline{x}$&nbsp; explizit das Informationswort&nbsp; $\underline{u}$.  
*Das heißt, es gilt:
+
*Das heißt, es gilt: &nbsp; $\underline{u} =  (u_1, u_2, \hspace{0.05cm}\text{...} \hspace{0.05cm}, u_k) \hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm} =  
::<math>\underline{u} =  (u_1, u_2, ... \hspace{0.05cm}, u_k) \hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm} =  
+
(u_1, u_2, ... \hspace{0.05cm}, u_k, x_{k+1}, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_n)\hspace{0.05cm}.$
(u_1, u_2, ... \hspace{0.05cm}, u_k, x_{k+1}, ... \hspace{0.05cm}, x_n)\hspace{0.05cm}.</math>
 
  
*Die Generatormatrix hat in diesem Fall die Form $\boldsymbol{\rm G_{\rm sys} } =\left({ \boldsymbol{\rm I}_{\rm k} \ ; \{ \boldsymbol{\rm P} }\right)$ mit der $k&times;k$&ndash;Einheitsmatrix $\boldsymbol{\rm I}_{\rm k}$ und einer geeignet zu wählenden $(n-1)&times;k$&ndash;Matrix $\boldsymbol{\rm P}$.}}<br>
+
*Die Generatormatrix hat in diesem Fall die Form&nbsp; $\boldsymbol{\rm G_{\rm sys} } =\left({ \boldsymbol{\rm I}_{\rm k} \ ; \ \boldsymbol{\rm P} }\right)$&nbsp; mit der&nbsp; $k&times;k$&ndash;Einheitsmatrix&nbsp; $\boldsymbol{\rm I}_{\rm k}$&nbsp; und einer geeignet zu wählenden&nbsp; $(n-1)&times;k$&ndash;Matrix&nbsp; $\boldsymbol{\rm P}$.}}<br>
  
Für das Beispiel 5 auf der letzten Seite kann also auch geschrieben werden:
+
Für das&nbsp; $\text{Beispiel 5}$&nbsp; auf der letzten Seite kann also auch geschrieben werden:
  
 
::<math> \boldsymbol{\rm G_{sys}} =\left({ \boldsymbol{\rm I}}_3 \: ; \: { \boldsymbol{\rm P}}\right)\hspace{0.3cm}{\rm mit}\hspace{0.3cm}
 
::<math> \boldsymbol{\rm G_{sys}} =\left({ \boldsymbol{\rm I}}_3 \: ; \: { \boldsymbol{\rm P}}\right)\hspace{0.3cm}{\rm mit}\hspace{0.3cm}
Zeile 256: Zeile 260:
 
\end{pmatrix}\hspace{0.05cm}.</math>
 
\end{pmatrix}\hspace{0.05cm}.</math>
  
Erfreulich aus Sicht der Kanalcodierung ist, dass für jeden Code $\mathcal{C}$ ein systematischer (identischer oder zumindest äquivalenter) Code $\mathcal{C}_{\rm sys}$ gefunden werden kann.<br>
+
Erfreulich aus Sicht der Kanalcodierung ist, dass für jeden Code&nbsp; $\mathcal{C}$&nbsp; ein systematischer (identischer oder zumindest äquivalenter) Code&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; gefunden werden kann.<br>
  
  
Beim '''identischen systematischen Code''' beinhalten $\underline{x}$ und $\underline{x}_{\rm sys}$ die gleichen Codeworte, nur die Zuordnung $  &nbsp; &#8594; &nbsp; \underline{x}$ ist unterschiedlich. Man kommt durch folgende Manipulationen bezüglich $\boldsymbol{\rm G}$ von $\mathcal{C}$ zu $\mathcal{C}_{\rm sys}$:
+
Beim&nbsp; '''identischen systematischen Code'''&nbsp; beinhalten&nbsp; $\underline{x}$&nbsp; und&nbsp; $\underline{x}_{\rm sys}$&nbsp; die gleichen Codeworte, nur die Zuordnung&nbsp; $\underline{u} &nbsp; &#8594; &nbsp; \underline{x}$&nbsp; ist unterschiedlich. Man kommt durch folgende Manipulationen bezüglich der Generatormatrix&nbsp; $\boldsymbol{\rm G}$&nbsp; von einem Blockcode&nbsp; $\mathcal{C}$&nbsp; zum identischen systematischen Code&nbsp; $\mathcal{C}_{\rm sys}$:
 
*Vertauschen oder Permutieren der Zeilen,<br>
 
*Vertauschen oder Permutieren der Zeilen,<br>
  
*Multiplizieren aller Zeilen mit einem konstanten Vektor ungleich $\underline{0}$,<br>
+
*Multiplizieren aller Zeilen mit einem konstanten Vektor ungleich&nbsp; $\underline{0}$,<br>
  
 
*Ersetzen einer Zeile durch eine Linearkombination zwischen dieser Zeile und einer anderen.<br>
 
*Ersetzen einer Zeile durch eine Linearkombination zwischen dieser Zeile und einer anderen.<br>
Zeile 268: Zeile 272:
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Ohne Beweis:}$&nbsp; Ein identischer systematischer Code $\mathcal{C}_{\rm sys}$ kann immer dann gefunden werden, wenn zu einer Generatormatrix $\boldsymbol{\rm G}$ eine Matrix $\boldsymbol{\rm A}$ existiert, so dass $\boldsymbol{\rm G}_{\rm sys} = \boldsymbol{\rm A} \cdot \boldsymbol{\rm G}$ gilt.}}  
+
$\text{Ohne Beweis:}$&nbsp; Ein $\text{identischer systematischer Code }\mathcal{C}_{\rm sys}$ kann immer dann gefunden werden, wenn zu einer Generatormatrix&nbsp; $\boldsymbol{\rm G}$&nbsp; eine Matrix&nbsp; $\boldsymbol{\rm A}$&nbsp; existiert, so dass&nbsp; $\boldsymbol{\rm G}_{\rm sys} = \boldsymbol{\rm A} \cdot \boldsymbol{\rm G}$&nbsp; gilt.}}  
  
  
Ist dies nicht möglich, so findet man zumindest durch Vertauschen oder Permutieren der Spalten von $\boldsymbol{\rm G}$ einen '''äquivalenten systematischen Code''':
+
Ist dies nicht möglich, so findet man zumindest durch Vertauschen oder Permutieren der Spalten von&nbsp; $\boldsymbol{\rm G}$&nbsp; einen&nbsp; '''äquivalenten systematischen Code''':
  
 
::<math>\mathcal{C}_{\rm sys} = {\rm \pi} (\mathcal{C})\hspace{0.3cm}{\rm mit}\hspace{0.3cm}{\rm \pi}():\hspace{0.15cm}{\rm Permutationsoperator}\hspace{0.05cm}.</math>
 
::<math>\mathcal{C}_{\rm sys} = {\rm \pi} (\mathcal{C})\hspace{0.3cm}{\rm mit}\hspace{0.3cm}{\rm \pi}():\hspace{0.15cm}{\rm Permutationsoperator}\hspace{0.05cm}.</math>
  
Die Codes $\mathcal{C}$ und $\mathcal{C}_{\rm sys}$ beinhalten dann zwar andere Codeworte, aber sie zeigen gleiche Eigenschaften. Beispielsweise weist $\mathcal{C}_{\rm sys}$ die gleiche minimale Hamming&ndash;Distanz $d_{\rm min}$ auf wie der Code $\mathcal{C}$.<br>
+
Die Codes&nbsp; $\mathcal{C}$&nbsp; und&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; beinhalten dann zwar andere Codeworte, aber sie zeigen gleiche Eigenschaften. Beispielsweise weist&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; in diesem Fall die gleiche minimale Hamming&ndash;Distanz&nbsp; $d_{\rm min}$&nbsp; auf wie der Code&nbsp; $\mathcal{C}$.<br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
Zeile 290: Zeile 294:
  
 
Die Analyse zeigt:
 
Die Analyse zeigt:
*Die zugehörigen Codes $\mathcal{C}$ und $\mathcal{C}_{\rm sys}$ beinhalten unterschiedliche Codeworte und sind somit auch <i>nicht identisch</i>:  
+
*Die zugehörigen Codes&nbsp; $\mathcal{C}$&nbsp; und&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; beinhalten unterschiedliche Codeworte und sind somit auch <i>nicht identisch</i>:  
::<math>\mathcal{C} = \{ (0, 0, 0, 0) \hspace{0.05cm}, (0, 0, 1, 1) \hspace{0.05cm},(1, 1, 0, 0) \hspace{0.05cm},(1, 1, 1, 1) \}\hspace{0.05cm},</math>
+
::<math>\mathcal{C} = \big \{ (0, 0, 0, 0) \hspace{0.05cm}, (0, 0, 1, 1) \hspace{0.05cm},(1, 1, 0, 0) \hspace{0.05cm},(1, 1, 1, 1) \big \}\hspace{0.05cm},</math>
::<math>\mathcal{C}_{\rm sys}= \{ (0, 0, 0, 0) \hspace{0.05cm}, (0, 1, 0, 1) \hspace{0.05cm},(1, 0, 1, 0) \hspace{0.05cm},(1, 1, 1, 1) \}\hspace{0.05cm}.</math>
+
::<math>\mathcal{C}_{\rm sys}= \big \{ (0, 0, 0, 0) \hspace{0.05cm}, (0, 1, 0, 1) \hspace{0.05cm},(1, 0, 1, 0) \hspace{0.05cm},(1, 1, 1, 1) \big \}\hspace{0.05cm}.</math>
*Aber sie sind <i>äquivalent</i>: &nbsp; $\boldsymbol{\rm G}_{\rm sys}$  ergibt sich aus $\boldsymbol{\rm G}$} durch Vertauschen der zweiten und dritten Spalte.  
+
*Aber sie sind <i>äquivalent</i>: &nbsp; $\boldsymbol{\rm G}_{\rm sys}$&nbsp; ergibt sich aus&nbsp; $\boldsymbol{\rm G}$&nbsp; durch Vertauschen der zweiten und dritten Spalte.  
*Es handelt sich in beiden Fällen um einen (4, 2, 2)&ndash;Blockcode &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $d_{\rm min} = 2$.}}
+
*Es handelt sich in beiden Fällen um einen&nbsp; $\text{(4, 2, 2)}$&ndash;Blockcode &nbsp;&nbsp;&#8658;&nbsp;&nbsp; $d_{\rm min} = 2$.}}
  
  
Zeile 308: Zeile 312:
 
Verknüpft man diese zwei Gleichungen, so erhält man:
 
Verknüpft man diese zwei Gleichungen, so erhält man:
  
:<math>{ \boldsymbol{\rm H}}  \cdot  { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T}  = \underline{0}\hspace{0.5cm}
+
::<math>{ \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}  
 
  \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}.</math>
 
\Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H}}  \cdot  { \boldsymbol{\rm G}}^{\rm T} = { \boldsymbol{\rm 0}} \hspace{0.05cm}.</math>
  
 
Anzumerken ist, dass in diesen Gleichungen  
 
Anzumerken ist, dass in diesen Gleichungen  
*$\underline{0}$ einen Zeilenvektor mit $k$ Elementen bezeichnet
+
*$\underline{0}$&nbsp; einen Zeilenvektor mit&nbsp; $k$&nbsp; Elementen bezeichnet und
*$\boldsymbol{\rm 0}$ eine Matrix mit $m$ Zeilen und $k$ Spalten.
+
*$\boldsymbol{\rm 0}$&nbsp; eine Matrix mit&nbsp; $m$&nbsp; Zeilen und&nbsp; $k$&nbsp; Spalten angibt,
  
  
Alle Elemente von $\underline{0}$ und $\boldsymbol{\rm 0}$ sind identisch Null.<br>
+
wobei alle Elemente von&nbsp; $\underline{0}$&nbsp; und&nbsp; $\boldsymbol{\rm 0}$&nbsp; identisch Null sind.<br>
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 7:}$&nbsp; Wir betrachten wie im [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix| Beispiel 3]] den (5, 3)&ndash;Blockcode
+
$\text{Beispiel 7:}$&nbsp; Wir betrachten wie im&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix|$\text{Beispiel 4}$]]&nbsp; den&nbsp; $\text{(5, 3)}$&ndash;Blockcode
  
:<math>\mathcal{C}  = \{  \hspace{0.15cm} (  \hspace{0.05cm}  0, 0, 0, 0, 0) \hspace{0.05cm},</math>
+
:<math>\mathcal{C}  = \big \{  \hspace{0.15cm} (  \hspace{0.05cm}  0, 0, 0, 0, 0) \hspace{0.05cm},</math>
 
::<math>  \hspace{0.6cm}(  \hspace{0.05cm}  0, 1, 1, 1, 0) \hspace{0.05cm},</math>
 
::<math>  \hspace{0.6cm}(  \hspace{0.05cm}  0, 1, 1, 1, 0) \hspace{0.05cm},</math>
 
::<math>  \hspace{0.6cm}( \hspace{0.05cm}0, 1, 0, 1, 0) \hspace{0.05cm},</math>
 
::<math>  \hspace{0.6cm}( \hspace{0.05cm}0, 1, 0, 1, 0) \hspace{0.05cm},</math>
Zeile 329: Zeile 333:
 
::<math> \hspace{0.6cm}( \hspace{0.05cm}1, 0, 1, 0, 1) \hspace{0.05cm},</math>
 
::<math> \hspace{0.6cm}( \hspace{0.05cm}1, 0, 1, 0, 1) \hspace{0.05cm},</math>
 
::<math> \hspace{0.6cm}( \hspace{0.05cm}1, 0, 0, 0, 1) \hspace{0.05cm},</math>
 
::<math> \hspace{0.6cm}( \hspace{0.05cm}1, 0, 0, 0, 1) \hspace{0.05cm},</math>
::<math> \hspace{0.6cm}(\hspace{0.05cm}1, 1, 1, 1, 1) \}\hspace{0.05cm}.</math>
+
::<math> \hspace{0.6cm}(\hspace{0.05cm}1, 1, 1, 1, 1) \big \}\hspace{0.05cm}.</math>
  
Aus $n= 5$ und $k = 3$ folgt für die Anzahl der Prüfgleichungen $m = 2$. Durch Analyse der möglichen Codeworte erhält man folgende Ergebnisse:
+
Aus&nbsp; $n= 5$&nbsp; und&nbsp; $k = 3$&nbsp; folgt für die Anzahl der Prüfgleichungen&nbsp; $m = 2$. Durch Analyse der möglichen Codeworte erhält man folgende Ergebnisse:
  
 
::<math>x_1 \oplus x_5 = 0 \hspace{0.05cm},\hspace{0.5cm}
 
::<math>x_1 \oplus x_5 = 0 \hspace{0.05cm},\hspace{0.5cm}
Zeile 357: Zeile 361:
 
\end{pmatrix}\hspace{0.05cm}.</math>
 
\end{pmatrix}\hspace{0.05cm}.</math>
  
Die Nullmatrix besteht hier aus $m = 2$ Zeilen und $k = 3$ Spalten. Beispielsweise gilt für das Element in der ersten Zeile und der ersten Spalte:
+
Die Nullmatrix besteht hier aus&nbsp; $m = 2$&nbsp; Zeilen und&nbsp; $k = 3$&nbsp; Spalten. Beispielsweise gilt für das Element in der ersten Zeile und der ersten Spalte:
  
 
::<math>1 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm}
 
::<math>1 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm}
Zeile 370: Zeile 374:
 
== Generatormatrix vs. Prüfmatrix bei systematischen Codes ==
 
== Generatormatrix vs. Prüfmatrix bei systematischen Codes ==
 
<br>
 
<br>
Im allgemeinen Fall können $\boldsymbol{\rm G}$ und $\boldsymbol{\rm H}$  nicht direkt ineinander umgerechnet werden, schon allein aufgrund der unterschiedlichen Dimensionen von Generatormatrix  $(k \times n)$ und  Prüfmatrix $(m \times n)$.<br>
+
Im allgemeinen Fall können&nbsp; $\boldsymbol{\rm G}$&nbsp; und&nbsp; $\boldsymbol{\rm H}$&nbsp; nicht direkt ineinander umgerechnet werden, schon allein aufgrund der unterschiedlichen Dimensionen von Generatormatrix&nbsp; $(k \times n)$&nbsp; und  Prüfmatrix&nbsp; $(m \times n)$.<br>
  
Der Rechengang vereinfacht sich, wenn die $(k \times n)$ &ndash;Generatormatrix in systematischer Form vorliegt: &nbsp; $ \boldsymbol{\rm G_{sys}} =\left({ \boldsymbol{\rm I}}_k \: ; \: { \boldsymbol{\rm P}}\right).$ Dann folgt aus $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$ für die  $(m \times n)$&ndash;Prüfmatrix mit $m = n-k$:
+
{{BlaueBox|TEXT= 
 +
$\text{Ohne Beweis:}$&nbsp;
 +
Der Rechengang vereinfacht sich, wenn die&nbsp; $(k \times n)$ &ndash;Generatormatrix in systematischer Form vorliegt: &nbsp; $ \boldsymbol{\rm G_{sys} } =\left({ \boldsymbol{\rm I} }_k \: ; \: { \boldsymbol{\rm P} }\right)$. Dann folgt aus&nbsp; $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$&nbsp; für die&nbsp; $(m \times n)$&ndash;Prüfmatrix mit&nbsp; $m = n-k$:
  
::<math>{ \boldsymbol{\rm H}} =\left(-{ \boldsymbol{\rm P}}^{\rm T}  \: ; \: { \boldsymbol{\rm I}}_m \right)
+
::<math>{ \boldsymbol{\rm H} } =\left( - { \boldsymbol{\rm P} }^{\rm T}  \: ; \: { \boldsymbol{\rm I} }_m \right)
 
  \hspace{0.05cm}.</math>
 
  \hspace{0.05cm}.</math>
  
Diese Gleichung gilt allgemein, also auch im nichtbinären Fall. Da wir uns im gesamten ersten Hauptkapitel auf binäre Codes beschränken &#8658; &nbsp; $\mathcal{C} \in \text{GF}(2^n)$, gilt $-\boldsymbol{\rm P} = +\boldsymbol{\rm P}$, und man erhält die Form, die wir im Weiteren verwenden.<br>
+
Diese Gleichung gilt allgemein, also auch im nichtbinären Fall. Da wir uns im gesamten ersten Hauptkapitel auf binäre Codes beschränken &#8658; &nbsp; $\mathcal{C} \in \text{GF}(2^n)$, gilt&nbsp; $ - \boldsymbol{\rm P} = +\boldsymbol{\rm P}$, und man erhält die Form, die wir im Weiteren verwenden.<br>
 +
 
 +
::<math>{ \boldsymbol{\rm H} } =\left( - { \boldsymbol{\rm P} }^{\rm T}  \: ; \: { \boldsymbol{\rm I} }_m \right)=\left(  { \boldsymbol{\rm P} }^{\rm T}  \: ; \: { \boldsymbol{\rm I} }_m \right)\hspace{0.05cm}.
 +
</math>}}
  
::<math>{ \boldsymbol{\rm H}} =\left(-{ \boldsymbol{\rm P}}^{\rm T}  \: ; \: { \boldsymbol{\rm I}}_m \right)
 
= \left [ \left({ \boldsymbol{\rm P}}^{\rm T}  \: ; \: { \boldsymbol{\rm I}}_m \right)\right ]_{{\rm bin\ddot{a}r}} \hspace{0.05cm}.</math>
 
  
 
{{GraueBox|TEXT=   
 
{{GraueBox|TEXT=   
$\text{Beispiel 8:}$&nbsp; Wir betrachten weiterhin den beispielhaften  (5,&nbsp;3)&ndash;Blockcode,  gehen aber nun von der systematischen Generatormatrix $\boldsymbol{\rm G}_{\rm sys}$ aus, die wir im  [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Identische_Codes|Beispiel 5]] ermittelt haben:
+
$\text{Beispiel 8:}$&nbsp; Wir betrachten weiterhin den beispielhaften&nbsp; $\text{(5,&nbsp;3)}$&ndash;Blockcode,  gehen aber nun von der systematischen Generatormatrix&nbsp; $\boldsymbol{\rm G}_{\rm sys}$&nbsp; aus, die wir im&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Identische_Codes|$\text{Beispiel 5}$]]&nbsp; ermittelt haben:
  
 
::<math> \boldsymbol{\rm G_{sys} } = \begin{pmatrix}
 
::<math> \boldsymbol{\rm G_{sys} } = \begin{pmatrix}
Zeile 431: Zeile 438:
 
(1, 1, 1, 1, 1) \hspace{0.05cm}.</math>
 
(1, 1, 1, 1, 1) \hspace{0.05cm}.</math>
  
Zusammen mit dem Vektor $\underline{x} = (u_1, u_2, u_3, p_1, p_2) =  (x_1, x_2, x_3, x_4, x_5)$ lauten dann die Prüfbits:
+
Zusammen mit dem Vektor&nbsp; $\underline{x} = (u_1, u_2, u_3, p_1, p_2) =  (x_1, x_2, x_3, x_4, x_5)$&nbsp; lauten dann die Prüfbits:
  
 
::<math>p_1 = u_2 \hspace{0.05cm},\hspace{0.2cm}p_2 = u_1 \hspace{0.05cm},</math>
 
::<math>p_1 = u_2 \hspace{0.05cm},\hspace{0.2cm}p_2 = u_1 \hspace{0.05cm},</math>
Zeile 437: Zeile 444:
 
und die entsprechenden Prüfgleichungen des Decoders:
 
und die entsprechenden Prüfgleichungen des Decoders:
  
:<math>x_2 + x_4 = 0 \hspace{0.05cm},\hspace{0.2cm}x_1 + x_5 = 0 \hspace{0.05cm}.</math>
+
::<math>x_2 + x_4 = 0 \hspace{0.05cm},\hspace{0.2cm}x_1 + x_5 = 0 \hspace{0.05cm}.</math>
  
 
Man erkennt aus diesen Gleichungen und auch aus obiger Codetabelle:  
 
Man erkennt aus diesen Gleichungen und auch aus obiger Codetabelle:  
*Dieser Code bietet gegenüber einem Übertragungsfehler hinsichtlich des dritten Bits $(x_3 = u_3)$ keinen Schutz.  
+
*Dieser Code bietet gegenüber einem Übertragungsfehler hinsichtlich des dritten Bits&nbsp; $(x_3 = u_3)$&nbsp; keinen Schutz.  
 
*Damit ist natürlich weder eine Fehlererkennung und noch weniger Fehlerkorrektur möglich.  
 
*Damit ist natürlich weder eine Fehlererkennung und noch weniger Fehlerkorrektur möglich.  
*Gleiches gilt aber auch für den nichtsystematischen Code auf der letzten Seite.}}<br>
+
*Gleiches gilt aber auch für den nichtsystematischen Code entsprechend&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Zusammenhang_zwischen_Generator.E2.80.93_und_Pr.C3.BCfmatrix|$\text{Beispiel 7}$]]&nbsp; auf der letzten Seite.}}<br>
  
 
== Darstellung von SPC und RC als duale Codes ==
 
== Darstellung von SPC und RC als duale Codes ==
 
<br>
 
<br>
Nun sollen für die bereits im Kapitel  [[Kanalcodierung/Beispiele_bin%C3%A4rer_BlockcodesBeispiele binärer Blockcodes]] behandelten Codes noch jeweils die Generatormatrix $\boldsymbol{\rm G}$ und die Prüfmatrix $\boldsymbol{\rm H}$ angegeben werden. Die Codelänge sei für die folgenden Beispiele stets $n = 5$, doch lassen sich die Ergebnisse auch für andere Codelängen in gleicher Weise interpretieren. Es gilt für
+
Nun sollen für die bereits im Kapitel&nbsp; [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes|Beispiele binärer Blockcodes]]&nbsp; behandelten Codes noch jeweils die Generatormatrix&nbsp; $\boldsymbol{\rm G}$&nbsp; und die Prüfmatrix&nbsp; $\boldsymbol{\rm H}$&nbsp; angegeben werden. Die Codelänge sei für die folgenden Beispiele stets&nbsp; $n = 5$, doch lassen sich die Ergebnisse auch für andere Codelängen in gleicher Weise interpretieren. Es gilt für
*den [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes|Single&ndash;Parity&ndash;check Code]] &nbsp; &#8658; &nbsp; SPC (5, 4):
+
*den&nbsp; [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Single_Parity.E2.80.93check_Codes|Single&ndash;Parity&ndash;check Code]] &nbsp; &#8658; &nbsp; $\text{SPC (5, 4)}$:
  
 
::<math>{ \boldsymbol{\rm H}}  
 
::<math>{ \boldsymbol{\rm H}}  
Zeile 460: Zeile 467:
 
0 &0 &0 &1 &1
 
0 &0 &0 &1 &1
 
\end{pmatrix}
 
\end{pmatrix}
\hspace{0.05cm}.</math>
+
\hspace{0.05cm};</math>
  
*den [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Wiederholungscodes|Wiederholungscode]] (<i>Repetition Code</i>) &nbsp; &#8658; &nbsp; RC (5,1):
+
*den&nbsp; [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Wiederholungscodes|Wiederholungscode]] (<i>Repetition Code</i>) &nbsp; &#8658; &nbsp; $\text{RC (5, 1)}$:
  
 
::<math>{ \boldsymbol{\rm G}}  
 
::<math>{ \boldsymbol{\rm G}}  
Zeile 477: Zeile 484:
 
\hspace{0.05cm}.</math>
 
\hspace{0.05cm}.</math>
  
Die jeweils erste Gleichung lässt sich einfach aus der jeweiligen Definition herleiten und die abgeleitete Gleichung folgt aus der Beziehung $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$. Aus den obigen Matrizen kann verallgemeinert werden:
+
Die jeweils erste Gleichung lässt sich einfach aus der jeweiligen Definition herleiten und die abgeleitete Gleichung folgt aus der Beziehung&nbsp; $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$.  
*Die Generatormatrix des RC (5, 1) ist identisch mit der Prüfmatrix des SPC (5, 4). Es handelt sich jeweils um $(5 \times 1)$&ndash;Matrizen.<br>
+
 
 +
Aus den obigen Matrizen kann verallgemeinert werden:
 +
*Die Generatormatrix des&nbsp; $\text{RC (5, 1)}$&nbsp; ist identisch mit der Prüfmatrix des&nbsp; $\text{SPC (5, 4)}$. Es handelt sich jeweils um&nbsp; $(5 \times 1)$&ndash;Matrizen.<br>
  
*Die Prüfmatrix des RC (5, 1) ist identisch mit der Generatormatrix des SPC (5, 4). Diese beiden Matrizen haben jeweils 5 Spalten und 4 Zeilen.<br>
+
*Die Prüfmatrix des&nbsp; $\text{RC (5, 1)}$&nbsp; ist identisch mit der Generatormatrix des&nbsp; $\text{SPC (5, 4)}$. Diese beiden Matrizen haben jeweils&nbsp; $5$&nbsp; Spalten und&nbsp; $4$&nbsp; Zeilen.<br>
  
*Dieser Sachverhalt ergibt sich, weil es sich hier um '''duale Codes''' handelt. Zur Erklärung benötigen wir noch zwei Definitionen:<br>
+
*Dieser Sachverhalt ergibt sich, weil es sich hier um so genannte &bdquo;duale Codes&rdquo; handelt. Zur Erklärung benötigen wir noch zwei Definitionen:<br>
  
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Zwei lineare Codes $\mathcal{C}$ und $\mathcal{C}'$, beide aus ${\rm GF}(2^n)$, sind ''orthogonal'', wenn alle Codeworte $\underline{x} \in \mathcal{C}$ zu allen Codeworten $\underline{x}' \in \mathcal{C}'$ orthogonal sind. Man bezeichnet dann $\mathcal{C}$ und $\mathcal{C}'$ als '''duale Codes'''.}}<br><br>
+
$\text{Definition:}$&nbsp; Zwei lineare Codes&nbsp; $\mathcal{C}$&nbsp; und&nbsp; $\mathcal{C}\hspace{0.05cm}'$, beide aus&nbsp; ${\rm GF}(2^n)$, sind&nbsp; ''orthogonal'', wenn alle Codeworte&nbsp; $\underline{x} \in \mathcal{C}$&nbsp; zu allen Codeworten&nbsp; $\underline{x}\hspace{0.05cm}' \in \mathcal{C}\hspace{0.05cm}'$&nbsp; orthogonal sind. Man bezeichnet dann&nbsp; $\mathcal{C}$&nbsp; und&nbsp; $\mathcal{C}\hspace{0.05cm}'$&nbsp; als '''duale Codes'''.}}<br>
  
 
{{BlaueBox|TEXT=   
 
{{BlaueBox|TEXT=   
$\text{Definition:}$&nbsp; Zwei Codeworte $\underline{x} \in{\rm GF}(2^n)$ und $\underline{x} \in {\rm GF}(2^n)$ sind immer dann zueinander '''orthogonal''', wenn das [[Digitalsignalübertragung/Signale,_Basisfunktionen_und_Vektorräume#Zur_Nomenklatur_im_vierten_Kapitel|innere Produkt]] verschwindet:
+
$\text{Definition:}$&nbsp; Zwei Codeworte&nbsp; $\underline{x} \in{\rm GF}(2^n)$&nbsp; und&nbsp; $\underline{x\hspace{0.05cm}'} \in {\rm GF}(2^n)$&nbsp; sind immer dann zueinander&nbsp; '''orthogonal''', wenn das&nbsp; [[Digitalsignalübertragung/Signale,_Basisfunktionen_und_Vektorräume#Zur_Nomenklatur_im_vierten_Kapitel|innere Produkt]]&nbsp; verschwindet:
  
::<math>\left \langle \underline{x} \cdot \underline{x}' \right \rangle =  \sum_{i=1  }^{n} x_i \cdot x_i' = 0 \hspace{0.05cm}, \hspace{0.5cm}
+
::<math>\big \langle \underline{x} \cdot \underline{x}\hspace{0.05cm}' \big \rangle =  \sum_{i=1  }^{n} x_i \cdot x\hspace{0.05cm}'_i = 0 \hspace{0.05cm}, \hspace{0.5cm}
\left \langle \underline{x} \cdot \underline{x}' \right \rangle \in {\rm GF}(2^n)
+
\left \langle \underline{x} \cdot \underline{x}\hspace{0.05cm}' \right \rangle \in {\rm GF}(2^n)
 
\hspace{0.05cm}.</math>}}<br>
 
\hspace{0.05cm}.</math>}}<br>
  
Wegen der Produktbildung in ${\rm GF}(2^n)$ sind auch folgende Codewort&ndash;Paare zueinander orthogonal:
+
Wegen der Produktbildung in&nbsp; ${\rm GF}(2^n)$&nbsp; sind auch folgende Codewort&ndash;Paare zueinander orthogonal:
  
::<math>\left \langle \hspace{0.05cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.2cm} (1, 1, 1, 0) \hspace{0.05cm} \right \rangle = 0\hspace{0.05cm},\hspace{0.2cm}
+
::<math>\left \langle \hspace{0.05cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.5cm} (1, 1, 1, 0) \hspace{0.05cm} \right \rangle = 0\hspace{0.05cm},\hspace{0.2cm}
 
\left \langle \hspace{0.1cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.2cm} (0, 1, 1, 0) \hspace{0.1cm}\right \rangle = 0\hspace{0.05cm}.</math>
 
\left \langle \hspace{0.1cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.2cm} (0, 1, 1, 0) \hspace{0.1cm}\right \rangle = 0\hspace{0.05cm}.</math>
  
Der Code $\mathcal{C}$ spannt einen $k$&ndash;dimensionalen Untervektorraum in ${\rm GF}(2^n)$ auf. Der Untervektorraum des dualen Codes $\mathcal{C}'$ ist zu diesem orthogonal und weist die Dimension $n-k$ auf. Damit gilt: &nbsp; ${\rm dim} \{ \mathcal{C} \} + {\rm dim} \{ \mathcal{C}' \} = n\hspace{0.05cm}.$<br>
+
*Der Code&nbsp; $\mathcal{C}$&nbsp; spannt einen&nbsp; $k$&ndash;dimensionalen Untervektorraum in&nbsp; ${\rm GF}(2^n)$&nbsp; auf.  
 +
*Der Untervektorraum des dualen Codes&nbsp; $\mathcal{C}\hspace{0.05cm}'$&nbsp; ist zu diesem orthogonal und weist die Dimension&nbsp; $n-k$&nbsp; auf.
 +
* Damit gilt: &nbsp; ${\rm dim} \{ \mathcal{C} \} + {\rm dim} \{ \mathcal{C}\hspace{0.05cm}' \} = n\hspace{0.05cm}.$<br>
  
 
== Einige Eigenschaften des (7, 4, 3)–Hamming–Codes ==
 
== Einige Eigenschaften des (7, 4, 3)–Hamming–Codes ==
 
<br>
 
<br>
Fassen wir die bisherigen Ergebnisse dieses Kapitels am Beispiel des systematischen Hamming&ndash;Codes nochmals zusammen, der bereits im Kapitel [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes|Beispiele binärer Blockcodes]] ausführlich beschrieben wurde. Dieser (7,&nbsp;4,&nbsp;3)&ndash;Code ist gekennzeichnet durch
+
Fassen wir die bisherigen Ergebnisse dieses Kapitels am Beispiel des systematischen Hamming&ndash;Codes nochmals zusammen,&nbsp; der bereits im Kapitel&nbsp; [[Kanalcodierung/Beispiele_bin%C3%A4rer_Blockcodes#Hamming.E2.80.93Codes|"Beispiele binärer Blockcodes"]]&nbsp; ausführlich beschrieben wurde.&nbsp; Dieser&nbsp; $\text{(7, 4, 3)}$&ndash;Code ist gekennzeichnet durch
[[Datei:P ID2359 KC T 1 4 S7.png|right|frame|Codeworte des (7, 4, 3)–Hamming–Codes|class=fit]]
+
[[Datei:P ID2359 KC T 1 4 S7.png|right|frame|Codeworte des&nbsp; $\text{HC (7, 4, 3)}$|class=fit]]
*die Anzahl der Prüfgleichungen $m = 3$,<br>
+
*die Anzahl der Prüfgleichungen:&nbsp; $m = 3$,<br>
*die Codelänge $n = 2^m-1 = 7$,<br>
+
 
*die Informationswortlänge $k = n-m = 4$,<br>
+
*die Codelänge&nbsp; $n = 2^m-1 = 7$,<br>
*die Anzahl $2^k =16$ der Codeworte (Dimension),<br>
+
 
*die Rate $R= k/n = 4/7$,<br>
+
*die Informationswortlänge&nbsp; $k = n-m = 4$,<br>
*die minimale Distanz $d_{\rm min} = 3$ (unabhängig von $m$, $n$ und$k$).<br>
+
 
 +
*die Anzahl&nbsp; $2^k =16$&nbsp; der Codeworte&nbsp; (Dimension),<br>
 +
 
 +
*die Rate&nbsp; $R= k/n = 4/7$,<br>
 +
 
 +
*die minimale Distanz&nbsp; $d_{\rm min} = 3$&nbsp; $($unabhängig von&nbsp; $m$,&nbsp; $n$&nbsp; und&nbsp; $k)$.<br>
  
  
In obiger Tabelle sind die $2^4 = 16$ Codeworte angegeben ( schwarz: vier Informationsbits, rot: dreiPrüfbits).  
+
In obiger Tabelle sind die&nbsp; $2^4 = 16$&nbsp; Codeworte angegeben <br>(schwarz:&nbsp; vier Informationsbits, rot:&nbsp; drei Prüfbits).  
  
 
Man erkennt daraus:
 
Man erkennt daraus:
*Der Code  beinhaltet sowohl das Null&ndash;Wort $(0000000)$ als auch das Eins>&ndash;Wort  $(1111111)$.
+
*Der Code  beinhaltet sowohl das Null&ndash;Wort&nbsp; "$0000000$"&nbsp; als auch das Eins&ndash;Wort&nbsp; "$1111111$".
*Es gibt sieben Codeworte, die sich aus $(0001011)$ jeweils durch zyklische Verschiebung ergeben (alle gelb hinterlegt).
+
 
*Es gibt sieben Codeworte, die sich aus $(0011101)$ jeweils durch zyklische Verschiebung ergeben (alle grün hinterlegt).
+
*Es gibt sieben Codeworte,&nbsp; die sich aus&nbsp; "$0001011$"&nbsp; jeweils durch zyklische Verschiebung ergeben&nbsp; (alle gelb hinterlegt).
*Zu jedem Codewort  existiert auch das &bdquo;negierte&rdquo; Codewort, zum Beispiel gibt es neben $(0001011)$ auch das Codewort $(1110100)$.
+
 
 +
*Es gibt sieben Codeworte,&nbsp; die sich aus&nbsp; "$0011101$"&nbsp; jeweils durch zyklische Verschiebung ergeben&nbsp; (alle grün hinterlegt).
 +
 
 +
*Zu jedem Codewort  existiert auch das&nbsp; "negierte Codewort",&nbsp; zum Beispiel gibt es neben&nbsp; "$0001011$"&nbsp; auch das Codewort&nbsp; "$1110100$".
 +
 
 
*Die Prüfmatrix kann wie folgt geschrieben werden:
 
*Die Prüfmatrix kann wie folgt geschrieben werden:
  
Zeile 539: Zeile 559:
 
\end{pmatrix}\hspace{0.05cm}.</math>
 
\end{pmatrix}\hspace{0.05cm}.</math>
  
Dementsprechend gilt für die Generatormatrix:
+
*Dementsprechend gilt für die Generatormatrix:
  
 
::<math>{ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_4 \: ; \: { \boldsymbol{\rm P}}\right)
 
::<math>{ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_4 \: ; \: { \boldsymbol{\rm P}}\right)
Zeile 551: Zeile 571:
 
== Aufgaben zum Kapitel ==
 
== Aufgaben zum Kapitel ==
 
<br>
 
<br>
[[Aufgaben:1.07_Prüfmatrix_und_Generatormatrix_des_HC_(7,_4,_3)|Aufgabe 1.7: 1.07 Prüfmatrix und Generatormatrix des HC (7, 4, 3)]]
+
[[Aufgaben:Aufgabe_1.07:_Prüf-_und_Generatormatrix_des_HC_(7,_4,_3)|Aufgabe 1.7: Prüfmatrix und Generatormatrix des HC (7, 4, 3)]]
  
[[Aufgaben:1.07Z_Klassifizierung_von_Blockcodes|Zusatzaufgaben 1.7: Klassifizierung von Blockcodes]]
+
[[Aufgaben:Aufgabe_1.07Z:_Klassifizierung_von_Blockcodes|Aufgabe 1.7Z: Klassifizierung von Blockcodes]]
  
[[Aufgaben:1.08_Identische_Codes|Aufgabe 1.8: Identische Codes]]
+
[[Aufgaben:Aufgabe_1.08:_Identische_Codes|Aufgabe 1.8: Identische Codes]]
  
[[Aufgaben:1.08Z_Äquivalente_Codes|Zusatzaufgaben 1.8: Äquivalente Codes]]
+
[[Aufgaben:Aufgabe_1.08Z:_Äquivalente_Codes|Aufgabe 1.8Z: Äquivalente Codes]]
  
[[Aufgaben:1.09_Erweiterter_Hamming–Code|Aufgabe 1.9: Erweiterter Hamming–Code]]
+
[[Aufgaben:Aufgabe_1.09:_Erweiterter_Hamming–Code|Aufgabe 1.9: Erweiterter Hamming–Code]]
  
[[Aufgaben:1.09Z_Erweiterung_–_Punktierung|Zusatzaufgaben 1.9: Erweiterung Punktierung]]
+
[[Aufgaben:Aufgabe_1.09Z:_Erweiterung_und/oder_Punktierung|Aufgabe 1.9Z: Erweiterung und/oder Punktierung]]
  
[[Aufgaben:1.10_Einige_Generatormatrizen|Aufgabe 1.10: Einige Generatormatrizen]]
+
[[Aufgaben:Aufgabe_1.10:_Einige_Generatormatrizen|Aufgabe 1.10: Einige Generatormatrizen]]
  
 
{{Display}}
 
{{Display}}

Aktuelle Version vom 10. Juli 2022, 14:37 Uhr

Lineare Codes und zyklische Codes


Alle bisher behandelten Codes,

  • der  "Single Parity–check Code",
  • der  "Repetition Code"  und
  • der  Hamming–Code


sind linear. Nun wird die für binäre Blockcodes gültige Definition von Linearität nachgereicht.

$\text{Definition:}$  Ein  linearer binärer Blockcode  $\mathcal{C}$ ist ein Satz von  $2^k$  Codeworten  $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_n)$, wobei die (Modulo–2)–Summe zweier beliebiger Codeworte  $\underline{x}$  und  $\underline{x}\hspace{0.05cm}'$  wiederum ein gültiges Codewort ergibt:

\[\underline{x}, \underline{x}\hspace{0.05cm}' \in {\rm GF}(2^n),\hspace{0.3cm} \underline{x}, \underline{x}\hspace{0.05cm}' \in \mathcal{C} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{x} + \underline{x}\hspace{0.05cm}' \in \mathcal{C} \hspace{0.05cm}.\]

Diese Bedingung muss auch für  $\underline{x} = \underline{x}\hspace{0.05cm}'$  erfüllt sein.

Hinweis:   Die Modulo–Addition wird für den Rest dieses Buches zur Vereinfachung der Schreibweise nicht mehr durch das Modulo–Additionszeichen ausgedrückt, sondern mit dem herkömmlichen Pluszeichen.


$\text{Beispiel 1:}$  Wir betrachten zwei  $\text{(3, 2)}$–Blockcodes:

\[\mathcal{C}_1 = \{ (0, 0, 0) \hspace{0.05cm}, (0, 1, 1) \hspace{0.05cm},(1, 0, 1) \hspace{0.05cm},(1, 1, 0) \}\hspace{0.05cm},\]
\[\mathcal{C}_2 = \{ (0, 0, 0) \hspace{0.05cm}, (0, 1, 1) \hspace{0.05cm},(1, 1, 0) \hspace{0.05cm},(1, 1, 1) \hspace{0.05cm}.\]

Man erkennt:

  • Der Code  $\mathcal{C}_1$  ist linear, da die Modulo–2–Addition zweier beliebiger Codeworte stets auch ein gültiges Codewort ergibt, z.B.  $(0, 1, 1) + (1, 0, 1) = (1, 1, 0)$.
  • Die obige Definition gilt auch für die Modulo–2–Addition eines Codewortes mit sich selbst, zum Beispiel  $(0, 1, 1) + (0, 1, 1) = (0, 0, 0)$
      ⇒   Jeder lineare Code beinhaltet das Nullwort  $\underline{0}$.
  • Obwohl die letzte Voraussetzung erfüllt wird, ist  $\mathcal{C}_2$  kein linearer Code. Für diesen Code gilt nämlich beispielsweise:   $(0, 1, 1) + (1, 1, 0) = (1, 0, 1)$. Dies ist kein gültiges Codewort von  $\mathcal{C}_2$.


Im Folgenden beschränken wir uns ausschließlich auf lineare Codes, da nichtlineare Codes für die Praxis von untergeordneter Bedeutung sind.

$\text{Definition:}$  Ein linearer Blockcode  $\mathcal{C}$  heißt  zyklisch, wenn jede zyklische Verschiebung eines Codewortes  $\underline{x}$  (nach links oder rechts) ein gültiges Codewort ergibt:

\[\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...} \hspace{0.05cm}, x_n) \in \mathcal{C} \hspace{0.3cm} \Rightarrow \hspace{0.3cm}\underline{x}\hspace{0.05cm}'= (x_n, x_1, \hspace{0.05cm}\text{...} \hspace{0.05cm} \hspace{0.05cm}, x_{n-1}) \in \mathcal{C} \hspace{0.05cm}.\]


Codetabelle des systematischen  $\text{(7, 4, 3)}$–Hamming–Codes;
schwarz:   $k= 4$  Informationsbits, rot:   $n-k = 3$  Prüfbits

$\text{Beispiel 2:}$ 

  • Man erkennt aus der Tabelle für den  $\text{HC (7, 4, 3)}$, dass dieser linear und zyklisch ist.
  • Es ergibt sich auch dann ein gültiges Codewort, wenn man alle Bit invertiert:   $0 ↔ 1$.
  • Auch das  $\underline{0}$–Wort  ($n$  mal eine „Null”) und das  $\underline{1}$–Wort ($n$  mal eine „Eins”) sind bei diesem Code zulässig.


Codefestlegung durch die Prüfmatrix


$\text{(7, 4, 3)}$–Hamming–Code

Wir betrachten den  $\text{(7, 4, 3)}$–Hamming–Code  mit Codeworten  $\underline{x}$  der Länge  $n=7$, bestehend aus

  • $k = 4$  Informationsbits  $x_1$,  $x_2$,  $x_3$,  $x_4$, und
  • $m = n-k = 3$  Prüfbits $x_5$,  $x_6$,  $x_7$.

Die Paritätsgleichungen lauten somit:

\[x_1 + x_2 + x_3 + x_5 = 0 \hspace{0.05cm},\]
\[x_2 + x_3 + x_4 + x_6 = 0 \hspace{0.05cm},\]
\[x_1 + x_2 + x_4 + x_7 = 0 \hspace{0.05cm}. \]

In Matrixschreibweise lautet dieser Gleichungssatz:

\[{ \boldsymbol{\rm H}} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} \hspace{0.05cm}. \]

In dieser Gleichung werden verwendet:

  • die  Prüfmatrix  ${ \boldsymbol{\rm H}}$  mit  $m = n-k = 3$  Zeilen und  $n = 7$  Spalten:
\[{ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &0 &1 & 0 & 0\\ 0 &1 &1 &1 &0 & 1 & 0\\ 1 &1 &0 &1 &0 & 0 & 1 \end{pmatrix}\hspace{0.05cm},\]
  • das  Codewort  $\underline{x}= (x_1, x_2, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_7)$  der Länge  $n = 7$,
  • der  Nullvektor  $\underline{0} = (0, 0, 0)$  der Länge  $m = 3$.

Durch Transponieren werden aus den  Zeilenvektoren  $\underline{x}$  und  $\underline{0}$  die entsprechenden  Spaltenvektoren  $\underline{x}^{\rm T}$  und  $\underline{0}^{\rm T}$.

$\text{(6, 3, 3)}$–Blockcode

$\text{Beispiel 3:}$  Die Grafik illustriert die  $m = 3$  Paritätsgleichungen eines Codes  $\mathcal{C}$  mit den Codeparametern  $n = 6$  und  $k = 3$  in der Reihenfolge rot, grün und blau. Es handelt sich also nicht um einen Hamming–Code  $(n \ne 2^m-1)$.

Entsprechend der Gleichung  $\boldsymbol{\rm H} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T}$  lautet die Prüfmatrix:

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

Die  $2^k = 8$  Codeworte bei systematischer Realisierung lauten (mit den Prüfbits rechts vom kleinen Pfeil):

\[\underline{x}_0 = (0, 0, 0_{\hspace{0.01cm} \rightarrow} 0, 0, 0)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_1 = (0, 0, 1_{\hspace{0.01cm} \rightarrow}0, 1, 1)\hspace{0.05cm},\hspace{0.5cm} \underline{x}_2 = (0, 1, 0_{\hspace{0.01cm} \rightarrow}1, 0, 1)\hspace{0.05cm},\hspace{0.5cm}\underline{x}_3 = (0, 1, 1_{\hspace{0.01cm} \rightarrow}1, 1, 0)\hspace{0.05cm}, \] \[\underline{x}_4 = (1, 0, 0_{\hspace{0.01cm} \rightarrow} 1, 1, 0)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_5 = (1, 0, 1_{\hspace{0.01cm} \rightarrow}1, 0, 1)\hspace{0.05cm},\hspace{0.5cm} \underline{x}_6 = (1, 1, 0_{\hspace{0.01cm} \rightarrow}0, 1, 1)\hspace{0.05cm}, \hspace{0.5cm} \underline{x}_7 = (1, 1, 1_{\hspace{0.01cm} \rightarrow}0, 0, 0)\hspace{0.05cm}.\]

Man erkennt aus diesen Angaben:

  • Die Spaltenanzahl  $\boldsymbol{\rm H}$  ist gleich der Codelänge $n$.
  • Die Zeilenanzahl von  $\boldsymbol{\rm H}$  ist gleich der Anzahl  $m = n-k$  der Prüfgleichungen.
  • Aus  $\boldsymbol{\rm H} \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} $  folgt also nicht, dass alle Codeworte eine gerade Anzahl von Einsen beinhalten.


Codefestlegung durch die Generatormatrix


Die Prüfmatrix  $\boldsymbol{\rm H}$  eines  $(n, k)$–Blockcodes hat  $m = n-k$  Zeilen und  $n$  Spalten. Den gleichen Code kann man aber auch durch die Matrix  $\boldsymbol{\rm G}$  mit ebenfalls  $n$  Spalten, aber  $k$  Zeilen beschreiben:

$\text{Definition:}$  Ein linearer binärer Blockcode  $\mathcal{C}$  kann durch die  Prüfmatrix  $\boldsymbol{\rm H}$  bzw. mit der  Generatormatrix  $\boldsymbol{\rm G}$  wie folgt charakterisiert werden:

\[\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\text{:} \hspace{0.2cm}{ \boldsymbol{\rm H} } \cdot \underline{x}^{\rm T}= \underline{0}^{\rm T} \}\hspace{0.05cm},\]
\[\mathcal{C} = \{ \underline{x} \in {\rm GF}(2^n)\hspace{0.05cm}, \hspace{0.1cm}\underline{u} \in {\rm GF}(2^k)\text{:} \hspace{0.2cm}\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G} } \}\hspace{0.05cm}.\]


Bevor wir uns den Eigenschaften der Generatormatrix zuwenden, beschreiben wir an einem Beispiel die Erzeugung der Codeworte.

$\text{Beispiel 4:}$  Wir betrachten einen linearen  $(5, 3)$–Blockcode mit der Generatormatrix (auch dies ist kein Hamming–Code)

\[ \boldsymbol{\rm G} = \begin{pmatrix} 1 &1 &0 &1 &1\\ 0 &1 &0 &1 &0\\ 0 &1 &1 &1 &0 \end{pmatrix} = \begin{pmatrix} \underline{g}_1\\ \underline{g}_2\\ \underline{g}_3\\ \end{pmatrix} \hspace{0.05cm}.\]

Damit werden die Informationsworte  $\underline{u}= (u_1, u_2, u_3)$  den Codeworten  $\underline{x}= (x_1, x_2, x_3, x_4, x_5)$  gemäß folgenden Gleichungen zugeordnet.
Es gilt stets  $\underline{x} = \underline{u} \cdot \boldsymbol{\rm G}$:

\[\underline{u}_0 = (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_0 = (0, 0, 0, 0, 0) \hspace{0.05cm},\]
\[\underline{u}_1 = (0, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_1 = (0, 1, 1, 1, 0) \hspace{0.1cm}= \hspace{0.1cm}\underline{g}_3\hspace{0.05cm},\]
\[\underline{u}_2 = (0, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_2 = (0, 1, 0, 1, 0)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_2\hspace{0.05cm},\]
\[\underline{u}_3 = (0, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_3 = (0, 0, 1, 0, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{g}_2+\underline{g}_3\hspace{0.05cm},\]
\[\underline{u}_4 = (1, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_4 = (1, 1, 0, 1, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1 \hspace{0.05cm},\]
\[\underline{u}_5 =(1, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_5 = (1, 0, 1, 0, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1+\underline{g}_3\hspace{0.05cm},\]
\[\underline{u}_6 = (1, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_6 = (1, 0, 0, 0, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1+\underline{g}_2\hspace{0.05cm},\]
\[\underline{u}_7 =(1, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}_7 = (1, 1, 1, 1, 1) \hspace{0.1cm}= \hspace{0.1cm} \underline{g}_1+ \underline{g}_2+\underline{g}_3\hspace{0.05cm}.\]


Anmerkungen:

  • Die hier zur Berechnung herangezogenen Basisvektoren  $\underline{g}_1$,  $\underline{g}_2$  und  $\underline{g}_3$  – jeweils mit der Länge  $n = 5$  – entsprechen den  $k = 3$  Zeilen der Generatormatrix  $\boldsymbol{\rm G}$.
  • Dieser Code ist wegen  $d_{\rm min} = 1$  weder zur Fehlerkorrektur noch zur Fehlererkennung geeignet ist. Trotzdem wird dieser Code auch auf den nächsten Seiten beispielhaft betrachtet, weil die Codierergebnisse gut interpretierbar sind.
  • Wir möchten Sie an dieser Stelle auf das Applet  Gram–Schmidt–Verfahren  zum Buch „Digitalsignalübertragung” aufmerksam machen, das die Berechnung von Basisfunktionen vermittelt, wenn auch in einem anderen als dem hier gebrauchten Zusammenhang.


Identische Codes


Die im  $\text{Beispiel 4}$  auf der letzten Seite verwendeten Vektoren  $\underline{g}_1$,  $\underline{g}_2$,  ...  ,  $\underline{g}_k$  sind die  Basisvektoren  des linearen Blockcodes  $\mathcal{C}$.

  • Der Code selbst kann als  $k$–dimensionaler Untervektorraum von  $\text{GF}(2^n)$  angesehen werden.
  • Die Basisvektoren  $\underline{g}_1$,  $\underline{g}_2$,  ...  , $\underline{g}_k$  sind linear unabhängig.


Der Untervektorraum  $\mathcal{C}$  wird aber nicht nur durch die Basisvektoren

\[\underline{g}_1 = (1, 1, 0, 1, 1) \hspace{0.05cm},\hspace{0.3cm} \underline{g}_2 = (0, 1, 0, 1, 0) \hspace{0.05cm},\hspace{0.3cm} \underline{g}_3 = (0, 1, 1, 1, 0) \hspace{0.05cm}\]

aufgespannt, sondern andere Basisvektoren  $\underline{g}\hspace{0.05cm}'_1$,  $\underline{g}\hspace{0.05cm}'_2$  und  $\underline{g}\hspace{0.05cm}'_3$  sind ebenso geeignet, so lange zwischen diesen die lineare Unabhängigkeit gewährleistet ist.

$\text{Beispiel 5:}$  Wir vergleichen den Code  $\mathcal{C}$  von  $\text{Beispiel 4}$  mit einem zweiten Code  $\mathcal{C}\hspace{0.05cm}'$. Die Generatormatrizen lauten:

\[ \boldsymbol{\rm G} = \begin{pmatrix} \underline{g}_1\\ \underline{g}_2\\ \underline{g}_3\\ \end{pmatrix}= \begin{pmatrix} 1 &1 &0 &1 &1\\ 0 &1 &0 &1 &0\\ 0 &1 &1 &1 &0 \end{pmatrix}\hspace{0.05cm},\hspace{0.3cm} \boldsymbol{\rm G}\hspace{0.05cm}' = \begin{pmatrix} \underline{g}\hspace{0.05cm}'_1\\ \underline{g}\hspace{0.05cm}'_2\\ \underline{g}\hspace{0.05cm}'_3\\ \end{pmatrix}= \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0\\ 0 &0 &1 &0 &0 \end{pmatrix}\hspace{0.05cm}.\]
  • Die beiden Codes sind identisch:   Sie beinhalten die genau gleichen Codeworte; es gilt nur eine andere Zuordnung.
  • Bei dem Übergang von  $\boldsymbol{\rm G}$  auf  $\boldsymbol{\rm G}\hspace{0.05cm}'$  wurden folgende erlaubte Operationen ausgeführt:
\[\underline{g}\hspace{0.05cm}'_1 = \underline{g}_1 + \underline{g}_2 \hspace{0.05cm},\hspace{0.3cm} \underline{g}\hspace{0.05cm}'_2 = \underline{g}_2 \hspace{0.05cm},\hspace{0.3cm} \underline{g}\hspace{0.05cm}'_3 = \underline{g}_2 + \underline{g}_3 \hspace{0.05cm}.\]
  • Zum entsprechenden Code  $\mathcal{C}'$  kommt man mit der Gleichung  $\underline{x}' = \underline{u} \cdot \boldsymbol{\rm G}'$:
\[\underline{u}_0 = (0, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_0 = (0, 0, 0, 0, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_0 \hspace{0.05cm},\]
\[\underline{u}_1 = (0, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_1 = (0, 0, 1, 0, 0) \hspace{0.1cm}= \hspace{0.1cm}\underline{x}_3\hspace{0.05cm},\]
\[\underline{u}_2 = (0, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_2 = (0, 1, 0, 1, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_2\hspace{0.05cm},\]
\[\underline{u}_3 = (0, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_3 = (0, 1, 1, 1, 0) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_1\hspace{0.05cm},\]
\[\underline{u}_4 = (1, 0, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_4 = (1, 0, 0, 0, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{x}_6 \hspace{0.05cm},\]
\[\underline{u}_5 =(1, 0, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_5 = (1, 0, 1, 0, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{x}_5\hspace{0.05cm},\]
\[\underline{u}_6 = (1, 1, 0)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_6 = (1, 1, 0, 1, 1)\hspace{0.1cm}= \hspace{0.1cm} \underline{x}_4\hspace{0.05cm},\]
\[\underline{u}_7 = (1, 1, 1)\hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm}'_7 = (1, 1, 1, 1, 1) \hspace{0.1cm}= \hspace{0.1cm} \underline{x}_7\hspace{0.05cm}.\]
  • Die entsprechenden Codeworte  $\underline{x}_i = \underline{u}_i \cdot \boldsymbol{\rm G}$  des Codes  $\mathcal{C}$   ⇒   Generatormatrix  $\boldsymbol{\rm G}$  sind im  $\text{Beispiel 4}$  (vorherige Seite) angegeben.


$\text{Fazit:}$  Die Codetabellen von  $\text{Beispiel 4}$  und  $\text{Beispiel 5}$  machen deutlich:

  • $\mathcal{C}$  und  $\mathcal{C}\hspace{0.05cm}'$  beinhalten die genau gleichen Codeworte. Sie sind damit  identische Codes  und besitzen beide die gleiche Korrekturfähigkeit (siehe nächste Seite).
  • $\mathcal{C}\hspace{0.05cm}'$  ist nun ein  systematischer Code, da die ersten  $k$  Binärstellen eines jeden Codewortes  $\underline{x}\hspace{0.05cm}'_i$  mit den Binärstellen des Informationswortes  $\underline{u}_i$  übereinstimmen.


Systematische Codes


Die Eigenschaft „systematisch” soll nun noch in mathematischer Form angegeben werden.

$\text{Definition:}$  Bei einem  $\text{systematischen }(n, k)–\text{Blockcode} \ \ \mathcal{C}$  beinhaltet jedes Codewort  $\underline{x}$  explizit das Informationswort  $\underline{u}$.

  • Das heißt, es gilt:   $\underline{u} = (u_1, u_2, \hspace{0.05cm}\text{...} \hspace{0.05cm}, u_k) \hspace{0.3cm} \rightarrow\hspace{0.3cm} \underline{x}\hspace{0.05cm} = (u_1, u_2, ... \hspace{0.05cm}, u_k, x_{k+1}, \hspace{0.05cm}\text{...}\hspace{0.05cm}, x_n)\hspace{0.05cm}.$
  • Die Generatormatrix hat in diesem Fall die Form  $\boldsymbol{\rm G_{\rm sys} } =\left({ \boldsymbol{\rm I}_{\rm k} \ ; \ \boldsymbol{\rm P} }\right)$  mit der  $k×k$–Einheitsmatrix  $\boldsymbol{\rm I}_{\rm k}$  und einer geeignet zu wählenden  $(n-1)×k$–Matrix  $\boldsymbol{\rm P}$.


Für das  $\text{Beispiel 5}$  auf der letzten Seite kann also auch geschrieben werden:

\[ \boldsymbol{\rm G_{sys}} =\left({ \boldsymbol{\rm I}}_3 \: ; \: { \boldsymbol{\rm P}}\right)\hspace{0.3cm}{\rm mit}\hspace{0.3cm} { \boldsymbol{\rm I_{3}}} = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix}\hspace{0.3cm}{\rm und}\hspace{0.3cm} { \boldsymbol{\rm P}} = \begin{pmatrix} 0 &1 \\ 1 &0 \\ 0 &0 \end{pmatrix}\hspace{0.05cm}.\]

Erfreulich aus Sicht der Kanalcodierung ist, dass für jeden Code  $\mathcal{C}$  ein systematischer (identischer oder zumindest äquivalenter) Code  $\mathcal{C}_{\rm sys}$  gefunden werden kann.


Beim  identischen systematischen Code  beinhalten  $\underline{x}$  und  $\underline{x}_{\rm sys}$  die gleichen Codeworte, nur die Zuordnung  $\underline{u}   →   \underline{x}$  ist unterschiedlich. Man kommt durch folgende Manipulationen bezüglich der Generatormatrix  $\boldsymbol{\rm G}$  von einem Blockcode  $\mathcal{C}$  zum identischen systematischen Code  $\mathcal{C}_{\rm sys}$:

  • Vertauschen oder Permutieren der Zeilen,
  • Multiplizieren aller Zeilen mit einem konstanten Vektor ungleich  $\underline{0}$,
  • Ersetzen einer Zeile durch eine Linearkombination zwischen dieser Zeile und einer anderen.


$\text{Ohne Beweis:}$  Ein $\text{identischer systematischer Code }\mathcal{C}_{\rm sys}$ kann immer dann gefunden werden, wenn zu einer Generatormatrix  $\boldsymbol{\rm G}$  eine Matrix  $\boldsymbol{\rm A}$  existiert, so dass  $\boldsymbol{\rm G}_{\rm sys} = \boldsymbol{\rm A} \cdot \boldsymbol{\rm G}$  gilt.


Ist dies nicht möglich, so findet man zumindest durch Vertauschen oder Permutieren der Spalten von  $\boldsymbol{\rm G}$  einen  äquivalenten systematischen Code:

\[\mathcal{C}_{\rm sys} = {\rm \pi} (\mathcal{C})\hspace{0.3cm}{\rm mit}\hspace{0.3cm}{\rm \pi}():\hspace{0.15cm}{\rm Permutationsoperator}\hspace{0.05cm}.\]

Die Codes  $\mathcal{C}$  und  $\mathcal{C}_{\rm sys}$  beinhalten dann zwar andere Codeworte, aber sie zeigen gleiche Eigenschaften. Beispielsweise weist  $\mathcal{C}_{\rm sys}$  in diesem Fall die gleiche minimale Hamming–Distanz  $d_{\rm min}$  auf wie der Code  $\mathcal{C}$.

$\text{Beispiel 6:}$  Wir betrachten die Generatormatrizen

\[ \boldsymbol{\rm G} = \begin{pmatrix} 1 &1 &0 &0 \\ 0 &0 &1 &1 \end{pmatrix}\hspace{0.3cm}{\rm und}\hspace{0.3cm} \boldsymbol{\rm G_{sys} } = \begin{pmatrix} 1 &0 &1 &0 \\ 0 &1 &0 &1 \end{pmatrix}\hspace{0.05cm}.\]

Die Analyse zeigt:

  • Die zugehörigen Codes  $\mathcal{C}$  und  $\mathcal{C}_{\rm sys}$  beinhalten unterschiedliche Codeworte und sind somit auch nicht identisch:
\[\mathcal{C} = \big \{ (0, 0, 0, 0) \hspace{0.05cm}, (0, 0, 1, 1) \hspace{0.05cm},(1, 1, 0, 0) \hspace{0.05cm},(1, 1, 1, 1) \big \}\hspace{0.05cm},\]
\[\mathcal{C}_{\rm sys}= \big \{ (0, 0, 0, 0) \hspace{0.05cm}, (0, 1, 0, 1) \hspace{0.05cm},(1, 0, 1, 0) \hspace{0.05cm},(1, 1, 1, 1) \big \}\hspace{0.05cm}.\]
  • Aber sie sind äquivalent:   $\boldsymbol{\rm G}_{\rm sys}$  ergibt sich aus  $\boldsymbol{\rm G}$  durch Vertauschen der zweiten und dritten Spalte.
  • Es handelt sich in beiden Fällen um einen  $\text{(4, 2, 2)}$–Blockcode   ⇒   $d_{\rm min} = 2$.


Zusammenhang zwischen Generator– und Prüfmatrix


Zur Definition dieser beiden Beschreibungsmatrizen gehen wir von folgenden Gleichungen aus:

\[\underline{x} = \underline{u} \cdot { \boldsymbol{\rm G}} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} \underline{x}^{\rm T} = { \boldsymbol{\rm G}}^{\rm T} \cdot \underline{u}^{\rm T} \hspace{0.05cm}, \hspace{0.8cm} { \boldsymbol{\rm H}} \cdot \underline{x}^{\rm T} = { \boldsymbol{\rm 0}}\hspace{0.05cm}.\]

Verknüpft man diese zwei Gleichungen, so erhält man:

\[{ \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 angibt,


wobei alle Elemente von  $\underline{0}$  und  $\boldsymbol{\rm 0}$  identisch Null sind.

$\text{Beispiel 7:}$  Wir betrachten wie im  $\text{Beispiel 4}$  den  $\text{(5, 3)}$–Blockcode

\[\mathcal{C} = \big \{ \hspace{0.15cm} ( \hspace{0.05cm} 0, 0, 0, 0, 0) \hspace{0.05cm},\]

\[ \hspace{0.6cm}( \hspace{0.05cm} 0, 1, 1, 1, 0) \hspace{0.05cm},\]
\[ \hspace{0.6cm}( \hspace{0.05cm}0, 1, 0, 1, 0) \hspace{0.05cm},\]
\[ \hspace{0.6cm}( \hspace{0.05cm}0, 0, 1, 0, 0) \hspace{0.05cm},\]
\[ \hspace{0.6cm}( \hspace{0.05cm} 1, 1, 0, 1, 1) \hspace{0.05cm},\]
\[ \hspace{0.6cm}( \hspace{0.05cm}1, 0, 1, 0, 1) \hspace{0.05cm},\]
\[ \hspace{0.6cm}( \hspace{0.05cm}1, 0, 0, 0, 1) \hspace{0.05cm},\]
\[ \hspace{0.6cm}(\hspace{0.05cm}1, 1, 1, 1, 1) \big \}\hspace{0.05cm}.\]

Aus  $n= 5$  und  $k = 3$  folgt für die Anzahl der Prüfgleichungen  $m = 2$. Durch Analyse der möglichen Codeworte erhält man folgende Ergebnisse:

\[x_1 \oplus x_5 = 0 \hspace{0.05cm},\hspace{0.5cm} x_2 \oplus x_4 = 0\hspace{1cm} \Rightarrow \hspace{0.3cm}{ \boldsymbol{\rm H} } = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0 \end{pmatrix}\]
\[\Rightarrow \hspace{0.3cm} { \boldsymbol{\rm H} } \cdot { \boldsymbol{\rm G} }^{\rm T} = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0 \end{pmatrix} \begin{pmatrix} 1 &0 &0 \\ 1 &1 &1 \\ 0 &0 &1 \\ 1 &1 &1 \\ 1 &0 &0 \end{pmatrix} = \begin{pmatrix} 0 &0 &0 \\ 0 &0 &0 \end{pmatrix}\hspace{0.05cm}.\]

Die Nullmatrix besteht hier aus  $m = 2$  Zeilen und  $k = 3$  Spalten. Beispielsweise gilt für das Element in der ersten Zeile und der ersten Spalte:

\[1 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm} 0 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm} 0 \cdot 0 \hspace{0.05cm}\oplus \hspace{0.05cm} 0 \cdot 1 \hspace{0.05cm}\oplus \hspace{0.05cm} 1 \cdot 1 = 0 \hspace{0.05cm}.\]



Generatormatrix vs. Prüfmatrix bei systematischen Codes


Im allgemeinen Fall können  $\boldsymbol{\rm G}$  und  $\boldsymbol{\rm H}$  nicht direkt ineinander umgerechnet werden, schon allein aufgrund der unterschiedlichen Dimensionen von Generatormatrix  $(k \times n)$  und Prüfmatrix  $(m \times n)$.

$\text{Ohne Beweis:}$  Der Rechengang vereinfacht sich, wenn die  $(k \times n)$ –Generatormatrix in systematischer Form vorliegt:   $ \boldsymbol{\rm G_{sys} } =\left({ \boldsymbol{\rm I} }_k \: ; \: { \boldsymbol{\rm P} }\right)$. Dann folgt aus  $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$  für die  $(m \times n)$–Prüfmatrix mit  $m = n-k$:

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

Diese Gleichung gilt allgemein, also auch im nichtbinären Fall. Da wir uns im gesamten ersten Hauptkapitel auf binäre Codes beschränken ⇒   $\mathcal{C} \in \text{GF}(2^n)$, gilt  $ - \boldsymbol{\rm P} = +\boldsymbol{\rm P}$, und man erhält die Form, die wir im Weiteren verwenden.

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


$\text{Beispiel 8:}$  Wir betrachten weiterhin den beispielhaften  $\text{(5, 3)}$–Blockcode, gehen aber nun von der systematischen Generatormatrix  $\boldsymbol{\rm G}_{\rm sys}$  aus, die wir im  $\text{Beispiel 5}$  ermittelt haben:

\[ \boldsymbol{\rm G_{sys} } = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &1 &0\\ 0 &0 &1 &0 &0 \end{pmatrix} =\left({ \boldsymbol{\rm I} }_3 \: ; \: { \boldsymbol{\rm P} }\right) \hspace{0.3cm} \Rightarrow \hspace{0.3cm} { \boldsymbol{\rm I_3} }= \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix}, \hspace{0.3cm} { \boldsymbol{\rm P} }= \begin{pmatrix} 0 &1 \\ 1 &0\\ 0 &0 \end{pmatrix} \hspace{0.3cm}\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm P}^{\rm T} } = \begin{pmatrix} 0 &1 &0\\ 1 &0 &0 \end{pmatrix}\hspace{0.05cm}.\]

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

\[{ \boldsymbol{\rm H} } =\left({ \boldsymbol{\rm P} }^{\rm T} \: ; \: { \boldsymbol{\rm I} }_2 \right) = \begin{pmatrix} 0 &1 &0 &1 &0\\ 1 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm},\]

und es ergibt sich folgende Codetabelle:

\[\underline{u}_0 = (0, 0, 0)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_0 = (0, 0, 0, 0, 0) \hspace{0.05cm},\hspace{0.8cm}\underline{u}_4 = (1, 0, 0)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_4 = (1, 0, 0, 0, 1) \hspace{0.05cm},\]
\[\underline{u}_1 = (0, 0, 1)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_1 = (0, 0, 1, 0, 0) \hspace{0.05cm},\hspace{0.8cm}\underline{u}_5 =(1, 0, 1)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_5 = (1, 0, 1, 0, 1)\hspace{0.05cm},\]
\[\underline{u}_2 =(0, 1, 0)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_2 = (0, 1, 0, 1, 0) \hspace{0.05cm},\hspace{0.8cm}\underline{u}_6 =(1, 1, 0)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_6 = (1, 1, 0, 1, 1)\hspace{0.05cm},\]
\[\underline{u}_3 = (0, 1, 1)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_3 = (0, 1, 1, 1, 0) \hspace{0.05cm},\hspace{0.8cm}\underline{u}_7 = (1, 1, 1)\hspace{0.2cm} \rightarrow\hspace{0.2cm} \underline{x}\hspace{0.05cm}_7 = (1, 1, 1, 1, 1) \hspace{0.05cm}.\]

Zusammen mit dem Vektor  $\underline{x} = (u_1, u_2, u_3, p_1, p_2) = (x_1, x_2, x_3, x_4, x_5)$  lauten dann die Prüfbits:

\[p_1 = u_2 \hspace{0.05cm},\hspace{0.2cm}p_2 = u_1 \hspace{0.05cm},\]

und die entsprechenden Prüfgleichungen des Decoders:

\[x_2 + x_4 = 0 \hspace{0.05cm},\hspace{0.2cm}x_1 + x_5 = 0 \hspace{0.05cm}.\]

Man erkennt aus diesen Gleichungen und auch aus obiger Codetabelle:

  • Dieser Code bietet gegenüber einem Übertragungsfehler hinsichtlich des dritten Bits  $(x_3 = u_3)$  keinen Schutz.
  • Damit ist natürlich weder eine Fehlererkennung und noch weniger Fehlerkorrektur möglich.
  • Gleiches gilt aber auch für den nichtsystematischen Code entsprechend  $\text{Beispiel 7}$  auf der letzten Seite.


Darstellung von SPC und RC als duale Codes


Nun sollen für die bereits im Kapitel  Beispiele binärer Blockcodes  behandelten Codes noch jeweils die Generatormatrix  $\boldsymbol{\rm G}$  und die Prüfmatrix  $\boldsymbol{\rm H}$  angegeben werden. Die Codelänge sei für die folgenden Beispiele stets  $n = 5$, doch lassen sich die Ergebnisse auch für andere Codelängen in gleicher Weise interpretieren. Es gilt für

\[{ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &0 &1\\ 0 &0 &1 &0 &1\\ 0 &0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm};\]
\[{ \boldsymbol{\rm G}} = \begin{pmatrix} 1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &0 &0 &0 &1\\ 0 &1 &0 &0 &1\\ 0 &0 &1 &0 &1\\ 0 &0 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.\]

Die jeweils erste Gleichung lässt sich einfach aus der jeweiligen Definition herleiten und die abgeleitete Gleichung folgt aus der Beziehung  $\boldsymbol{\rm H} \cdot \boldsymbol{\rm G}^{\rm T} = \boldsymbol{\rm 0}$.

Aus den obigen Matrizen kann verallgemeinert werden:

  • Die Generatormatrix des  $\text{RC (5, 1)}$  ist identisch mit der Prüfmatrix des  $\text{SPC (5, 4)}$. Es handelt sich jeweils um  $(5 \times 1)$–Matrizen.
  • Die Prüfmatrix des  $\text{RC (5, 1)}$  ist identisch mit der Generatormatrix des  $\text{SPC (5, 4)}$. Diese beiden Matrizen haben jeweils  $5$  Spalten und  $4$  Zeilen.
  • Dieser Sachverhalt ergibt sich, weil es sich hier um so genannte „duale Codes” handelt. Zur Erklärung benötigen wir noch zwei Definitionen:


$\text{Definition:}$  Zwei lineare Codes  $\mathcal{C}$  und  $\mathcal{C}\hspace{0.05cm}'$, beide aus  ${\rm GF}(2^n)$, sind  orthogonal, wenn alle Codeworte  $\underline{x} \in \mathcal{C}$  zu allen Codeworten  $\underline{x}\hspace{0.05cm}' \in \mathcal{C}\hspace{0.05cm}'$  orthogonal sind. Man bezeichnet dann  $\mathcal{C}$  und  $\mathcal{C}\hspace{0.05cm}'$  als duale Codes.


$\text{Definition:}$  Zwei Codeworte  $\underline{x} \in{\rm GF}(2^n)$  und  $\underline{x\hspace{0.05cm}'} \in {\rm GF}(2^n)$  sind immer dann zueinander  orthogonal, wenn das  innere Produkt  verschwindet:

\[\big \langle \underline{x} \cdot \underline{x}\hspace{0.05cm}' \big \rangle = \sum_{i=1 }^{n} x_i \cdot x\hspace{0.05cm}'_i = 0 \hspace{0.05cm}, \hspace{0.5cm} \left \langle \underline{x} \cdot \underline{x}\hspace{0.05cm}' \right \rangle \in {\rm GF}(2^n) \hspace{0.05cm}.\]


Wegen der Produktbildung in  ${\rm GF}(2^n)$  sind auch folgende Codewort–Paare zueinander orthogonal:

\[\left \langle \hspace{0.05cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.5cm} (1, 1, 1, 0) \hspace{0.05cm} \right \rangle = 0\hspace{0.05cm},\hspace{0.2cm} \left \langle \hspace{0.1cm}(0, 1, 1, 0) \hspace{0.05cm}, \hspace{0.2cm} (0, 1, 1, 0) \hspace{0.1cm}\right \rangle = 0\hspace{0.05cm}.\]
  • Der Code  $\mathcal{C}$  spannt einen  $k$–dimensionalen Untervektorraum in  ${\rm GF}(2^n)$  auf.
  • Der Untervektorraum des dualen Codes  $\mathcal{C}\hspace{0.05cm}'$  ist zu diesem orthogonal und weist die Dimension  $n-k$  auf.
  • Damit gilt:   ${\rm dim} \{ \mathcal{C} \} + {\rm dim} \{ \mathcal{C}\hspace{0.05cm}' \} = n\hspace{0.05cm}.$

Einige Eigenschaften des (7, 4, 3)–Hamming–Codes


Fassen wir die bisherigen Ergebnisse dieses Kapitels am Beispiel des systematischen Hamming–Codes nochmals zusammen,  der bereits im Kapitel  "Beispiele binärer Blockcodes"  ausführlich beschrieben wurde.  Dieser  $\text{(7, 4, 3)}$–Code ist gekennzeichnet durch

Codeworte des  $\text{HC (7, 4, 3)}$
  • die Anzahl der Prüfgleichungen:  $m = 3$,
  • die Codelänge  $n = 2^m-1 = 7$,
  • die Informationswortlänge  $k = n-m = 4$,
  • die Anzahl  $2^k =16$  der Codeworte  (Dimension),
  • die Rate  $R= k/n = 4/7$,
  • die minimale Distanz  $d_{\rm min} = 3$  $($unabhängig von  $m$,  $n$  und  $k)$.


In obiger Tabelle sind die  $2^4 = 16$  Codeworte angegeben
(schwarz:  vier Informationsbits, rot:  drei Prüfbits).

Man erkennt daraus:

  • Der Code beinhaltet sowohl das Null–Wort  "$0000000$"  als auch das Eins–Wort  "$1111111$".
  • Es gibt sieben Codeworte,  die sich aus  "$0001011$"  jeweils durch zyklische Verschiebung ergeben  (alle gelb hinterlegt).
  • Es gibt sieben Codeworte,  die sich aus  "$0011101$"  jeweils durch zyklische Verschiebung ergeben  (alle grün hinterlegt).
  • Zu jedem Codewort existiert auch das  "negierte Codewort",  zum Beispiel gibt es neben  "$0001011$"  auch das Codewort  "$1110100$".
  • Die Prüfmatrix kann wie folgt geschrieben werden:
\[{ \boldsymbol{\rm H}} = \begin{pmatrix} 1 &1 &1 &0 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &1 &0 &1 &0 &0 &1 \end{pmatrix}=\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_3 \right)\hspace{0.8cm} \Rightarrow\hspace{0.8cm}{ \boldsymbol{\rm P}}^{\rm T} = \begin{pmatrix} 1 &1 &1 &0 \\ 0 &1 &1 &1 \\ 1 &1 &0 &1 \end{pmatrix}\hspace{0.05cm},\hspace{0.2cm}{ \boldsymbol{\rm I}}_3 = \begin{pmatrix} 1 &0 &0 \\ 0 &1 &0 \\ 0 &0 &1 \end{pmatrix}\hspace{0.05cm}.\]
  • Dementsprechend gilt für die Generatormatrix:
\[{ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_4 \: ; \: { \boldsymbol{\rm P}}\right) = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &1\\ 0 &0 &1 &0 &1 &1 &0\\ 0 &0 &0 &1 &0 &1 &1 \end{pmatrix}\hspace{0.05cm}.\]

Aufgaben zum Kapitel


Aufgabe 1.7: Prüfmatrix und Generatormatrix des HC (7, 4, 3)

Aufgabe 1.7Z: Klassifizierung von Blockcodes

Aufgabe 1.8: Identische Codes

Aufgabe 1.8Z: Äquivalente Codes

Aufgabe 1.9: Erweiterter Hamming–Code

Aufgabe 1.9Z: Erweiterung und/oder Punktierung

Aufgabe 1.10: Einige Generatormatrizen