Aufgaben:Aufgabe 1.09Z: Erweiterung und/oder Punktierung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(5 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
[[Datei:P_ID2403__KC_Z_1_9.png|right|frame|Zur Erweiterung und Punktierung]]
 
[[Datei:P_ID2403__KC_Z_1_9.png|right|frame|Zur Erweiterung und Punktierung]]
  
Häufig kennt man einen Code, der für eine Anwendung als geeignet erscheint, dessen Coderate aber nicht exakt mit den Vorgaben übereinstimmt.
+
Häufig kennt man einen Code,  der für eine Anwendung als geeignet erscheint,  dessen Coderate aber nicht exakt mit den Vorgaben übereinstimmt.
  
 
Zur Ratenanpassung gibt es verschiedene Möglichkeiten
 
Zur Ratenanpassung gibt es verschiedene Möglichkeiten
  
'''Erweiterung''' (englisch ''Extension''):  
+
'''Erweiterung'''  (englisch:   "Extension"):  
<br>Ausgehend vom $(n, \, k)$–Code, dessen Prüfmatrix $\mathbf{H}$ gegeben ist, erhält man einen $(n+1, \, k)$–Code, indem man die Prüfmatrix um eine Zeile und eine Spalte erweitert und die neuen Matrixelemente entsprechend der oberen Grafik mit Nullen und Einsen ergänzt. Man fügt ein neues Prüfbit
+
<br>Ausgehend vom&nbsp; $(n, \, k)$–Code,&nbsp; dessen Prüfmatrix&nbsp; $\mathbf{H}$&nbsp; gegeben ist,&nbsp; erhält man einen&nbsp; $(n+1, \, k)$–Code,&nbsp; indem man die Prüfmatrix um eine Zeile und eine Spalte erweitert und die neuen Matrixelemente entsprechend der oberen Grafik mit Nullen und Einsen ergänzt.&nbsp; Man fügt ein neues Prüfbit
 
:$$x_{n+1} = x_1 \oplus x_2 \oplus ... \hspace{0.05cm} \oplus x_n$$
 
:$$x_{n+1} = x_1 \oplus x_2 \oplus ... \hspace{0.05cm} \oplus x_n$$
hinzu und damit auch eine neue Prüfgleichung, die in $\mathbf{H}'$ berücksichtigt ist.
+
hinzu und damit auch eine neue Prüfgleichung,&nbsp; die in&nbsp; $\mathbf{H}\hspace{0.05cm}'$&nbsp; berücksichtigt ist.
  
'''Punktierung''' (englisch ''Puncturing''):  
+
'''Punktierung'''&nbsp; (englisch: &nbsp; "Puncturing"):  
<br>Entsprechend der unteren Abbildung kommt man zu einem $(n–1, \, k)$–Code größerer Rate, wenn man auf ein Prüfbit und eine Prüfgleichung verzichtet, was gleichbedeutend damit ist, aus der Prüfmatrix $\mathbf{H}$ eine Zeile und eine Spalte zu streichen.
+
<br>Entsprechend der unteren Abbildung kommt man zu einem&nbsp; $(n-1, \, k)$–Code größerer Rate,&nbsp; wenn man auf ein Prüfbit und eine Prüfgleichung verzichtet,&nbsp; was gleichbedeutend damit ist,&nbsp; aus der Prüfmatrix&nbsp; $\mathbf{H}$&nbsp; eine Zeile und eine Spalte zu streichen.
  
'''Verkürzung''' (englisch Shortening): Verzichtet man anstelle eines Prüfbits auf ein Informationsbit, so ergibt sich ein $(n–1, \, k–1)$–Code kleinerer Rate.
+
'''Verkürzung'''&nbsp; (englisch: &nbsp; "Shortening"):  
 +
<br>Verzichtet man anstelle eines Prüfbits auf ein Informationsbit,&nbsp; so ergibt sich ein&nbsp; $(n-1, \, k-1)$–Code kleinerer Rate.
  
  
In dieser Aufgabe sollen ausgehend von einem $(5, \, 2)$–Blockcode
+
In dieser Aufgabe sollen ausgehend von einem&nbsp; $(5, \, 2)$–Blockcode
  
:$$\mathcal{C} = \{ (0, 0, 0, 0, 0) \hspace{0.1cm}, (0, 1, 0, 1, 1) \hspace{0.1cm},(1, 0, 1, 1, 0) \hspace{0.1cm},(1, 1, 1, 0, 1) \}$$
+
:$$\mathcal{C} = \{ (0, 0, 0, 0, 0), \hspace{0.3cm} (0, 1, 0, 1, 1), \hspace{0.3cm}(1, 0, 1, 1, 0), \hspace{0.3cm}(1, 1, 1, 0, 1) \}$$
  
 
folgende Codes konstruiert und analysiert werden:
 
folgende Codes konstruiert und analysiert werden:
*ein $(6, \, 2)$–Code durch einmalige Erweiterung,
+
*ein&nbsp; $(6, \, 2)$–Code durch einmalige Erweiterung,
  
*ein $(7, \, 2)$–Code durch nochmalige Erweiterung,
+
*ein&nbsp; $(7, \, 2)$–Code durch nochmalige Erweiterung,
  
*ein $(4, \, 2)$–Code durch Punktierung.
+
*ein&nbsp; $(4, \, 2)$–Code durch Punktierung.
  
  
Die Prüfmatrix und die Generatormatrix des systematischen $(5, \, 2)$–Codes lauten:
+
Die Prüfmatrix und die Generatormatrix des systematischen&nbsp; $(5, \, 2)$–Codes lauten:
  
 
:$${ \boldsymbol{\rm H}}_{(5, 2)} = \begin{pmatrix} 1 &0 &1 &0 &0\\ 1 &1 &0 &1 &0\\ 0 &1 &0 &0 &1 \end{pmatrix} \hspace{0.3cm} \Leftrightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{(5, 2)} = \begin{pmatrix} 1 &0 &1 &1 &0\\ 0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm H}}_{(5, 2)} = \begin{pmatrix} 1 &0 &1 &0 &0\\ 1 &1 &0 &1 &0\\ 0 &1 &0 &0 &1 \end{pmatrix} \hspace{0.3cm} \Leftrightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{(5, 2)} = \begin{pmatrix} 1 &0 &1 &1 &0\\ 0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
Zeile 36: Zeile 37:
  
  
''Hinweise'' :
 
  
*Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer Blockcodes]].
+
Hinweise:
* In der [[Aufgaben:1.09_Erweiterter_Hamming–Code|Aufgabe 1.09]] wird beispielhaft gezeigt, wie aus dem $(7, \, 4, \, 3)$–Hamming–Code durch Erweiterung ein $(8, \, 4, \, 4)$–Code entsteht.
+
 
* Sollte die Eingabe des Zahlenwertes &bdquo;0&rdquo; erforderlich sein, so geben Sie bitte &bdquo;0.&rdquo; ein.
+
*Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|"Allgemeine Beschreibung linearer Blockcodes"]].
 +
 
 +
* In der&nbsp; [[Aufgaben:Aufgabe_1.09:_Erweiterter_Hamming–Code|"Aufgabe 1.9"]]&nbsp; wird beispielhaft gezeigt,&nbsp; wie aus dem&nbsp; $(7, \, 4, \, 3)$–Hamming–Code durch Erweiterung ein&nbsp; $(8, \, 4, \, 4)$–Code entsteht.
  
  
Zeile 46: Zeile 48:
 
===Fragebogen===
 
===Fragebogen===
 
<quiz display=simple>
 
<quiz display=simple>
{Geben Sie die Kenngrößen des vorgegebenen $(5, \, 2)$–Codes an.
+
{Geben Sie die Kenngrößen des vorgegebenen&nbsp; $(5, \, 2)$–Codes an.
 
|type="{}"}
 
|type="{}"}
 
$R \ = \ $ { 0.4 3% }
 
$R \ = \ $ { 0.4 3% }
 
$d_{\rm min} \ = \ $ {  3 3% }  
 
$d_{\rm min} \ = \ $ {  3 3% }  
  
{Welche Codeworte besitzt der $(6, \, 2)$–Code nach Erweiterung?
+
{Welche Codeworte besitzt der&nbsp; $(6, \, 2)$–Code nach Erweiterung?
 
|type="[]"}
 
|type="[]"}
 
- $(0 0 0 0 0 1), \ (0 1 0 1 1 0), \ (1 0 1 1 0 0), \ (1 1 1 0 1 1).$
 
- $(0 0 0 0 0 1), \ (0 1 0 1 1 0), \ (1 0 1 1 0 0), \ (1 1 1 0 1 1).$
 
+ $(0 0 0 0 0 0), \ (0 1 0 1 1 1), \ (1 0 1 1 0 1), \ (1 1 1 0 1 0).$
 
+ $(0 0 0 0 0 0), \ (0 1 0 1 1 1), \ (1 0 1 1 0 1), \ (1 1 1 0 1 0).$
  
{Geben Sie die Kenngrößen des erweiterten $(6, \, 2)$–Codes an.
+
{Geben Sie die Kenngrößen des erweiterten&nbsp; $(6, \, 2)$–Codes an.
 
|type="{}"}
 
|type="{}"}
 
$R \ = \ $ { 0.333 3% }
 
$R \ = \ $ { 0.333 3% }
 
$d_{\rm min} \ = \ $ {  4 3% }  
 
$d_{\rm min} \ = \ $ {  4 3% }  
  
{Wie lautet die systematische Generatormatrix $\boldsymbol{\rm G}$ des $(7, \, 2)$–Codes?
+
{Wie lautet die systematische Generatormatrix&nbsp; $\boldsymbol{\rm G}$&nbsp; des&nbsp; $(7, \, 2)$–Codes?
 
|type="[]"}
 
|type="[]"}
+ Zeile 1 von $\boldsymbol{\rm G} \text{:} \hspace{0.2cm} 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 0.$
+
+ Zeile 1 von&nbsp; $\boldsymbol{\rm G} \text{:} \hspace{0.2cm} 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 0.$
+ Zeile 2 von  $\boldsymbol{\rm G} \text{:} \hspace{0.2cm} 0, \, 1, \, 0, \, 1, \, 1, \, 1, \, 0.$
+
+ Zeile 2 von&nbsp; $\boldsymbol{\rm G} \text{:} \hspace{0.2cm} 0, \, 1, \, 0, \, 1, \, 1, \, 1, \, 0.$
  
{Geben Sie die Kenngrößen des erweiterten $(7, \, 2)$–Codes an.
+
{Geben Sie die Kenngrößen des erweiterten&nbsp; $(7, \, 2)$–Codes an.
 
|type="{}"}
 
|type="{}"}
 
$R \ = \ $ { 0.266 3% }
 
$R \ = \ $ { 0.266 3% }
 
$d_{\rm min} \ = \ $ {  4 3% }  
 
$d_{\rm min} \ = \ $ {  4 3% }  
  
{Welche Aussagen gelten für den $(4, \, 2)$–Code (Punktierung des letzten Prüfbits)?
+
{Welche Aussagen gelten für den&nbsp; $(4, \, 2)$–Code&nbsp; (Punktierung des letzten Prüfbits)?
 
|type="[]"}
 
|type="[]"}
+ Die Coderate beträgt nun $R = 2/4 = 0.5$.
+
+ Die Coderate beträgt nun&nbsp; $R = 2/4 = 0.5$.
 
+ $C_{(4, 2)} = \{(0, 0, 0, 0),  \, (1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)\}$.
 
+ $C_{(4, 2)} = \{(0, 0, 0, 0),  \, (1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)\}$.
- Die Minimaldistanz bleibt gegenüber dem $(5, \, 2)$–Code unverändert.
+
- Die Minimaldistanz bleibt gegenüber dem&nbsp; $(5, \, 2)$–Code unverändert.
 
</quiz>
 
</quiz>
  
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Die Rate des $(5, \, 2)$–Codes ist $R = 2/5 \ \underline{ = 0.4}$. Aus dem angegebenen Code erkennt man weiterhin die minimale Distanz $d_{\rm min} \ \underline{ = 3}$.
+
'''(1)'''&nbsp; Die Rate des&nbsp; $(5, \, 2)$–Codes ist&nbsp; $R = 2/5 \ \underline{ = 0.4}$.  
 +
*Aus dem angegebenen Code erkennt man weiterhin die minimale Distanz&nbsp; $d_{\rm min} \ \underline{ = 3}$.
 +
 
  
  
'''(2)'''&nbsp; Bei Erweiterung vom $(5, \, 2)$–Code zum $(6, \, 2)$–Code wird ein weiteres Prüfbit hinzugefügt. Das Codewort hat somit die Form
+
'''(2)'''&nbsp; Bei Erweiterung vom&nbsp; $(5, \, 2)$–Code zum&nbsp; $(6, \, 2)$–Code wird ein weiteres Prüfbit hinzugefügt.  
 +
*Das Codewort hat somit die Form
  
 
:$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, p_1, p_2, p_{3}, p_4) \hspace{0.05cm}.$$
 
:$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, p_1, p_2, p_{3}, p_4) \hspace{0.05cm}.$$
  
Für das hinzugekommene Prüfbit muss dabei gelten:
+
*Für das hinzugekommene Prüfbit muss dabei gelten:
  
 
:$$p_4 = x_6 = x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \hspace{0.05cm}.$$
 
:$$p_4 = x_6 = x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \hspace{0.05cm}.$$
  
Das heißt: Das neue Prüfbit $p_{4}$ wird so gewählt, dass sich in jedem Codewort eine gerade Anzahl von Einsen ergibt &nbsp;⇒&nbsp; <u>Antwort 2</u>. Löst man diese Aufgabe mit der Prüfmatrix, so erhält man
+
*Das heißt:&nbsp; Das neue Prüfbit&nbsp; $p_{4}$&nbsp; wird so gewählt,&nbsp; dass sich in jedem Codewort eine gerade Anzahl von Einsen ergibt &nbsp; ⇒ &nbsp; <u>Antwort 2</u>.
 +
 +
*Löst man diese Aufgabe mit der Prüfmatrix,&nbsp; so erhält man
 
:$${ \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &0 &0 &0 &1 \end{pmatrix}\hspace{0.3cm}
 
:$${ \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &0 &0 &0 &1 \end{pmatrix}\hspace{0.3cm}
 
\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &1 &0 &1\\ 0 &1 &0 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$
 
\Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &1 &0 &1\\ 0 &1 &0 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$
  
Die beiden Zeilen der Generatormatrix $\boldsymbol{\rm G}$ ergeben zwei der vier Codeworte, die Modulo–$2$–Summe das dritte und schließlich ist auch noch das Nullwort zu berücksichtigen.
+
*Die beiden Zeilen der Generatormatrix&nbsp; $\boldsymbol{\rm G}$&nbsp; ergeben zwei der vier Codeworte,&nbsp; die Modulo–$2$–Summe das dritte und schließlich ist auch noch das Nullwort zu berücksichtigen.
 +
 
 +
 
 +
 
 +
'''(3)'''&nbsp; Nach Erweiterung vom&nbsp; $(5, \, 2)$–Code auf den&nbsp; $(6, \, 2)$–Code
 +
*vermindert sich die Rate von&nbsp; $R = 2/5$&nbsp; auf $R = 2/6 \ \underline{= 0.333}$,
  
 +
*erhöht sich die Minimaldistanz von&nbsp; $d_{\rm min} = 3$&nbsp; auf&nbsp; $d_{\rm min} \ \underline{= 4}$ .
  
'''(3)'''&nbsp; Nach Erweiterung vom $(5, \, 2)$–Code auf den $(6, \, 2)$–Code
 
*vermindert sich die Rate von $R = 2/5$ auf $R = 2/6 \ \underline{= 0.333}$,
 
*erhöht sich die Minimaldistanz von $d_{\rm min} = 3$ auf $d_{\rm min} \ \underline{= 4}$ .
 
  
 +
<u>Allgemein gilt:</u> &nbsp; Erweitert man einen Code,&nbsp; so nimmt die Rate ab und die Minimaldistanz erhöht sich um&nbsp; $1$,&nbsp; falls&nbsp; $d_{\rm min}$&nbsp; vorher ungerade war.
  
<u>Allgemein gilt:</u> Erweitert man einen Code, so nimmt die Rate ab und die Minimaldistanz erhöht sich um $1$, falls $d_{\rm min}$ vorher ungerade war.
 
  
  
'''(4)'''&nbsp; Bei gleicher Vorgehensweise wie unter (3) erhält man
+
'''(4)'''&nbsp; Bei gleicher Vorgehensweise wie unter&nbsp; '''(3)'''&nbsp; erhält man
 
:$${ \boldsymbol{\rm H}}_{(7,\hspace{0.05cm} 2)} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &0 &0 &0 &0\\ 1 &1 &0 &1 &0 &0 &0\\ 0 &1 &0 &0 &1 &0 &0\\ 1 &1 &0 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.15cm} \Rightarrow\hspace{0.15cm} { \boldsymbol{\rm H}}_{{\rm (7,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &0 &0 &0 &0\\ 1 &1 &0 &1 &0 &0 &0\\ 0 &1 &0 &0 &1 &0 &0\\ 1 &1 &0 &0 &0 &1 &0\\ 0 &0 &0 &0 &0 &0 &1 \end{pmatrix}\hspace{0.15cm} \Rightarrow\hspace{0.15cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &1 &0 &1 &0 \\ 0 &1 &0 &1 &1 &1 &0 \end{pmatrix}\hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm H}}_{(7,\hspace{0.05cm} 2)} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &0 &0 &0 &0\\ 1 &1 &0 &1 &0 &0 &0\\ 0 &1 &0 &0 &1 &0 &0\\ 1 &1 &0 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.15cm} \Rightarrow\hspace{0.15cm} { \boldsymbol{\rm H}}_{{\rm (7,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &0 &0 &0 &0\\ 1 &1 &0 &1 &0 &0 &0\\ 0 &1 &0 &0 &1 &0 &0\\ 1 &1 &0 &0 &0 &1 &0\\ 0 &0 &0 &0 &0 &0 &1 \end{pmatrix}\hspace{0.15cm} \Rightarrow\hspace{0.15cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &1 &0 &1 &0 \\ 0 &1 &0 &1 &1 &1 &0 \end{pmatrix}\hspace{0.05cm}.$$
  
Zeile 112: Zeile 122:
  
  
'''(5)'''&nbsp; Die Rate beträgt nun $R = 2/7 = \underline{0.266}$. Die Minimaldistanz ist weiterhin $d_{\rm min} \ \underline{= 4}$ , wie man aus den $(7, \, 2)$–Codeworten ablesen kann:
 
:$$\mathcal{C} = \{ (0, 0, 0, 0, 0, 0, 0), \hspace{0.1cm}(0, 1, 0, 1, 1, 1, 0), \hspace{0.1cm}(1, 0, 1, 1, 0, 1, 0), \hspace{0.1cm}(1, 1, 1, 0, 1, 0, 0) \}\hspace{0.05cm}.$$
 
  
<u>Allgemein gilt:</u> Ist die Minimaldistanz eines Codes geradzahlig, so kann diese durch Erweiterung nicht vergrößert werden.
+
'''(5)'''&nbsp; Die Rate beträgt nun&nbsp; $R = 2/7 = \underline{0.266}$.
 +
*Die Minimaldistanz ist weiterhin&nbsp; $d_{\rm min} \ \underline{= 4}$,&nbsp; wie man aus den&nbsp; $(7, \, 2)$–Codeworten ablesen kann:
 +
:$$\mathcal{C} = \{ (0, 0, 0, 0, 0, 0, 0), \hspace{0.3cm}(0, 1, 0, 1, 1, 1, 0), \hspace{0.3cm}(1, 0, 1, 1, 0, 1, 0), \hspace{0.3cm}(1, 1, 1, 0, 1, 0, 0) \}\hspace{0.05cm}.$$
 +
 
 +
<u>Allgemein gilt:</u> &nbsp; Ist die Minimaldistanz eines Codes geradzahlig,&nbsp; so kann diese durch Erweiterung nicht vergrößert werden.
 +
 
  
  
'''(6)'''&nbsp; Richtig sind die <u>Aussagen 1 und 2</u>:  
+
'''(6)'''&nbsp; Richtig sind die&nbsp; <u>Aussagen 1 und 2</u>:  
*Durch Streichen der letzten Zeile und der letzten Spalte erhält man für Prüfmatrix bzw.  Generatormatrix (jeweils in systematischer Form):
+
*Durch Streichen der letzten Zeile und der letzten Spalte erhält man für Prüfmatrix bzw.  Generatormatrix&nbsp; (jeweils in systematischer Form):
 
:$${ \boldsymbol{\rm H}}_{(4,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 \\ 1 &1 &0 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (4,\hspace{0.05cm} 2)}} = \begin{pmatrix} 1 &0 &1 &1 \\ 0 &1 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm H}}_{(4,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 \\ 1 &1 &0 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (4,\hspace{0.05cm} 2)}} = \begin{pmatrix} 1 &0 &1 &1 \\ 0 &1 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$
  
*Aus der Generatormatrix ergeben sich die genannten Codeworte $(1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)$ als Zeilensumme sowie das Nullwort $(0, 0, 0, 0)$. Die Minimaldistanz dieses Codes ist $d_{\rm min}= 2$ und damit kleiner als die minimale Distanz $d_{\rm min}= 3$  des $(5, \, 2)$–Codes.
+
*Aus der Generatormatrix ergeben sich die genannten Codeworte&nbsp; $(1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)$&nbsp; als Zeilensumme sowie das Nullwort $(0, 0, 0, 0)$.&nbsp; Die Minimaldistanz dieses Codes ist&nbsp; $d_{\rm min}= 2$&nbsp; und damit kleiner als die minimale Distanz $d_{\rm min}= 3$&nbsp; des&nbsp; $(5, \, 2)$–Codes.
  
  
<u>Allgemein gilt:</u> Durch Punktierung wird $d_{\rm min}$ um $1$ kleiner (wenn sie vorher gerade war) oder sie bleibt gleich. Dies kann man sich verdeutlichen, wenn man durch eine weitere Punktierung (des Prüfbits $p_{2}$) den $(3, \, 2)$–Blockcode generiert. Dieser Code
+
<u>Allgemein gilt:</u> &nbsp; Durch Punktierung wird&nbsp; $d_{\rm min}$&nbsp; um&nbsp; $1$&nbsp; kleiner&nbsp; (wenn sie vorher gerade war)&nbsp; oder sie bleibt gleich.&nbsp; Dies kann man sich verdeutlichen,&nbsp; wenn man durch eine weitere Punktierung&nbsp; $($des Prüfbits $p_{2})$&nbsp; den&nbsp; $(3, \, 2)$–Blockcode generiert.&nbsp; Dieser Code
:$$ \mathcal{C} = \{ (0, 0, 0), \hspace{0.1cm}(0, 1, 1), \hspace{0.1cm}(1, 0, 1), \hspace{0.1cm}(1, 1, 0) \}$$
+
:$$ \mathcal{C} = \{ (0, 0, 0), \hspace{0.1cm}(0, 1, 1), \hspace{0.3cm}(1, 0, 1), \hspace{0.3cm}(1, 1, 0) \}$$
besitzt die gleiche Minimaldistanz $d_{\rm min}= 2$ wie der $(4, \, 2)$–Code.
+
besitzt die gleiche Minimaldistanz&nbsp; $d_{\rm min}= 2$&nbsp; wie der&nbsp; $(4, \, 2)$–Code.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 12. Juli 2022, 11:52 Uhr

Zur Erweiterung und Punktierung

Häufig kennt man einen Code,  der für eine Anwendung als geeignet erscheint,  dessen Coderate aber nicht exakt mit den Vorgaben übereinstimmt.

Zur Ratenanpassung gibt es verschiedene Möglichkeiten

Erweiterung  (englisch:   "Extension"):
Ausgehend vom  $(n, \, k)$–Code,  dessen Prüfmatrix  $\mathbf{H}$  gegeben ist,  erhält man einen  $(n+1, \, k)$–Code,  indem man die Prüfmatrix um eine Zeile und eine Spalte erweitert und die neuen Matrixelemente entsprechend der oberen Grafik mit Nullen und Einsen ergänzt.  Man fügt ein neues Prüfbit

$$x_{n+1} = x_1 \oplus x_2 \oplus ... \hspace{0.05cm} \oplus x_n$$

hinzu und damit auch eine neue Prüfgleichung,  die in  $\mathbf{H}\hspace{0.05cm}'$  berücksichtigt ist.

Punktierung  (englisch:   "Puncturing"):
Entsprechend der unteren Abbildung kommt man zu einem  $(n-1, \, k)$–Code größerer Rate,  wenn man auf ein Prüfbit und eine Prüfgleichung verzichtet,  was gleichbedeutend damit ist,  aus der Prüfmatrix  $\mathbf{H}$  eine Zeile und eine Spalte zu streichen.

Verkürzung  (englisch:   "Shortening"):
Verzichtet man anstelle eines Prüfbits auf ein Informationsbit,  so ergibt sich ein  $(n-1, \, k-1)$–Code kleinerer Rate.


In dieser Aufgabe sollen ausgehend von einem  $(5, \, 2)$–Blockcode

$$\mathcal{C} = \{ (0, 0, 0, 0, 0), \hspace{0.3cm} (0, 1, 0, 1, 1), \hspace{0.3cm}(1, 0, 1, 1, 0), \hspace{0.3cm}(1, 1, 1, 0, 1) \}$$

folgende Codes konstruiert und analysiert werden:

  • ein  $(6, \, 2)$–Code durch einmalige Erweiterung,
  • ein  $(7, \, 2)$–Code durch nochmalige Erweiterung,
  • ein  $(4, \, 2)$–Code durch Punktierung.


Die Prüfmatrix und die Generatormatrix des systematischen  $(5, \, 2)$–Codes lauten:

$${ \boldsymbol{\rm H}}_{(5, 2)} = \begin{pmatrix} 1 &0 &1 &0 &0\\ 1 &1 &0 &1 &0\\ 0 &1 &0 &0 &1 \end{pmatrix} \hspace{0.3cm} \Leftrightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{(5, 2)} = \begin{pmatrix} 1 &0 &1 &1 &0\\ 0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$



Hinweise:

  • In der  "Aufgabe 1.9"  wird beispielhaft gezeigt,  wie aus dem  $(7, \, 4, \, 3)$–Hamming–Code durch Erweiterung ein  $(8, \, 4, \, 4)$–Code entsteht.


Fragebogen

1

Geben Sie die Kenngrößen des vorgegebenen  $(5, \, 2)$–Codes an.

$R \ = \ $

$d_{\rm min} \ = \ $

2

Welche Codeworte besitzt der  $(6, \, 2)$–Code nach Erweiterung?

$(0 0 0 0 0 1), \ (0 1 0 1 1 0), \ (1 0 1 1 0 0), \ (1 1 1 0 1 1).$
$(0 0 0 0 0 0), \ (0 1 0 1 1 1), \ (1 0 1 1 0 1), \ (1 1 1 0 1 0).$

3

Geben Sie die Kenngrößen des erweiterten  $(6, \, 2)$–Codes an.

$R \ = \ $

$d_{\rm min} \ = \ $

4

Wie lautet die systematische Generatormatrix  $\boldsymbol{\rm G}$  des  $(7, \, 2)$–Codes?

Zeile 1 von  $\boldsymbol{\rm G} \text{:} \hspace{0.2cm} 1, \, 0, \, 1, \, 1, \, 0, \, 1, \, 0.$
Zeile 2 von  $\boldsymbol{\rm G} \text{:} \hspace{0.2cm} 0, \, 1, \, 0, \, 1, \, 1, \, 1, \, 0.$

5

Geben Sie die Kenngrößen des erweiterten  $(7, \, 2)$–Codes an.

$R \ = \ $

$d_{\rm min} \ = \ $

6

Welche Aussagen gelten für den  $(4, \, 2)$–Code  (Punktierung des letzten Prüfbits)?

Die Coderate beträgt nun  $R = 2/4 = 0.5$.
$C_{(4, 2)} = \{(0, 0, 0, 0), \, (1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)\}$.
Die Minimaldistanz bleibt gegenüber dem  $(5, \, 2)$–Code unverändert.


Musterlösung

(1)  Die Rate des  $(5, \, 2)$–Codes ist  $R = 2/5 \ \underline{ = 0.4}$.

  • Aus dem angegebenen Code erkennt man weiterhin die minimale Distanz  $d_{\rm min} \ \underline{ = 3}$.


(2)  Bei Erweiterung vom  $(5, \, 2)$–Code zum  $(6, \, 2)$–Code wird ein weiteres Prüfbit hinzugefügt.

  • Das Codewort hat somit die Form
$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, p_1, p_2, p_{3}, p_4) \hspace{0.05cm}.$$
  • Für das hinzugekommene Prüfbit muss dabei gelten:
$$p_4 = x_6 = x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \hspace{0.05cm}.$$
  • Das heißt:  Das neue Prüfbit  $p_{4}$  wird so gewählt,  dass sich in jedem Codewort eine gerade Anzahl von Einsen ergibt   ⇒   Antwort 2.
  • Löst man diese Aufgabe mit der Prüfmatrix,  so erhält man
$${ \boldsymbol{\rm H}}_{(6,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &0 &0 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &0 &0 &1 &0\\ 1 &1 &0 &0 &0 &1 \end{pmatrix}\hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} = \begin{pmatrix} 1 &0 &1 &1 &0 &1\\ 0 &1 &0 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$
  • Die beiden Zeilen der Generatormatrix  $\boldsymbol{\rm G}$  ergeben zwei der vier Codeworte,  die Modulo–$2$–Summe das dritte und schließlich ist auch noch das Nullwort zu berücksichtigen.


(3)  Nach Erweiterung vom  $(5, \, 2)$–Code auf den  $(6, \, 2)$–Code

  • vermindert sich die Rate von  $R = 2/5$  auf $R = 2/6 \ \underline{= 0.333}$,
  • erhöht sich die Minimaldistanz von  $d_{\rm min} = 3$  auf  $d_{\rm min} \ \underline{= 4}$ .


Allgemein gilt:   Erweitert man einen Code,  so nimmt die Rate ab und die Minimaldistanz erhöht sich um  $1$,  falls  $d_{\rm min}$  vorher ungerade war.


(4)  Bei gleicher Vorgehensweise wie unter  (3)  erhält man

$${ \boldsymbol{\rm H}}_{(7,\hspace{0.05cm} 2)} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &0 &0 &0 &0\\ 1 &1 &0 &1 &0 &0 &0\\ 0 &1 &0 &0 &1 &0 &0\\ 1 &1 &0 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.15cm} \Rightarrow\hspace{0.15cm} { \boldsymbol{\rm H}}_{{\rm (7,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &0 &0 &0 &0\\ 1 &1 &0 &1 &0 &0 &0\\ 0 &1 &0 &0 &1 &0 &0\\ 1 &1 &0 &0 &0 &1 &0\\ 0 &0 &0 &0 &0 &0 &1 \end{pmatrix}\hspace{0.15cm} \Rightarrow\hspace{0.15cm} { \boldsymbol{\rm G}}_{{\rm (6,\hspace{0.05cm} 2)\hspace{0.05cm}sys}} \hspace{-0.05cm}=\hspace{-0.05cm} \begin{pmatrix} 1 &0 &1 &1 &0 &1 &0 \\ 0 &1 &0 &1 &1 &1 &0 \end{pmatrix}\hspace{0.05cm}.$$

⇒  Beide Antworten sind richtig.


(5)  Die Rate beträgt nun  $R = 2/7 = \underline{0.266}$.

  • Die Minimaldistanz ist weiterhin  $d_{\rm min} \ \underline{= 4}$,  wie man aus den  $(7, \, 2)$–Codeworten ablesen kann:
$$\mathcal{C} = \{ (0, 0, 0, 0, 0, 0, 0), \hspace{0.3cm}(0, 1, 0, 1, 1, 1, 0), \hspace{0.3cm}(1, 0, 1, 1, 0, 1, 0), \hspace{0.3cm}(1, 1, 1, 0, 1, 0, 0) \}\hspace{0.05cm}.$$

Allgemein gilt:   Ist die Minimaldistanz eines Codes geradzahlig,  so kann diese durch Erweiterung nicht vergrößert werden.


(6)  Richtig sind die  Aussagen 1 und 2:

  • Durch Streichen der letzten Zeile und der letzten Spalte erhält man für Prüfmatrix bzw. Generatormatrix  (jeweils in systematischer Form):
$${ \boldsymbol{\rm H}}_{(4,\hspace{0.05cm} 2)} = \begin{pmatrix} 1 &0 &1 &0 \\ 1 &1 &0 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm G}}_{{\rm (4,\hspace{0.05cm} 2)}} = \begin{pmatrix} 1 &0 &1 &1 \\ 0 &1 &0 &1 \end{pmatrix}\hspace{0.05cm}.$$
  • Aus der Generatormatrix ergeben sich die genannten Codeworte  $(1, 0, 1, 1), \, (0, 1, 0, 1), \, (1, 1, 1, 0)$  als Zeilensumme sowie das Nullwort $(0, 0, 0, 0)$.  Die Minimaldistanz dieses Codes ist  $d_{\rm min}= 2$  und damit kleiner als die minimale Distanz $d_{\rm min}= 3$  des  $(5, \, 2)$–Codes.


Allgemein gilt:   Durch Punktierung wird  $d_{\rm min}$  um  $1$  kleiner  (wenn sie vorher gerade war)  oder sie bleibt gleich.  Dies kann man sich verdeutlichen,  wenn man durch eine weitere Punktierung  $($des Prüfbits $p_{2})$  den  $(3, \, 2)$–Blockcode generiert.  Dieser Code

$$ \mathcal{C} = \{ (0, 0, 0), \hspace{0.1cm}(0, 1, 1), \hspace{0.3cm}(1, 0, 1), \hspace{0.3cm}(1, 1, 0) \}$$

besitzt die gleiche Minimaldistanz  $d_{\rm min}= 2$  wie der  $(4, \, 2)$–Code.