Aufgaben:Aufgabe 1.08: Identische Codes: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(11 dazwischenliegende Versionen von 4 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2393__KC_A_1_8_neu.png|right|frame|Zuordnung des betrachteten (6, 3)–Blockcodes]]
+
[[Datei:P_ID2393__KC_A_1_8_neu.png|right|frame|Zuordnung des  $(6, 3)$–Blockcodes]]
  
Wir betrachten einen Blockcode ''C'', der durch folgende Generatormatrix beschrieben wird:
+
Wir betrachten einen Blockcode  $\mathcal{C}$,  der durch folgende Generatormatrix beschrieben wird:
  
 
:$${ \boldsymbol{\rm G}} = \begin{pmatrix} 0 &0 &1 &0 &1 &1\\ 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm G}} = \begin{pmatrix} 0 &0 &1 &0 &1 &1\\ 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$
  
Die Zuordnung zwischen den Informationsworten <u>''u''</u> und den Codeworten <u>''x''</u> kann der beiliegenden Tabelle entnommen werden. Man erkennt, dass es sich dabei nicht um einen systematischen Code handelt.
+
Die Zuordnung zwischen den Informationsworten&nbsp; $\underline{u}$&nbsp; und den Codeworten&nbsp; $\underline{x}$&nbsp; kann der Tabelle entnommen werden.&nbsp; Man erkennt,&nbsp; dass es sich dabei nicht um einen systematischen Code handelt.
  
Durch Manipulation der Generatormatrix '''G''' lassen sich daraus identische Codes konstruieren. Darunter versteht man Codes mit gleichen Codeworten, jedoch unterschiedlicher Zuordnung <u>''u''</u> → <u>''x''</u>. Folgende Operationen sind erlaubt, um einen identischen Code zu erhalten:
+
Durch Manipulation der Generatormatrix&nbsp; $\boldsymbol {\rm G}$&nbsp; lassen sich daraus identische Codes konstruieren.&nbsp; Darunter versteht man Codes mit gleichen Codeworten,&nbsp; jedoch unterschiedlicher Zuordnung&nbsp; $\underline{u} \rightarrow \underline{x}$.  
 +
 
 +
Folgende Operationen sind erlaubt,&nbsp; um einen identischen Code zu erhalten:
  
 
*Vertauschen oder Permutieren der Zeilen,
 
*Vertauschen oder Permutieren der Zeilen,
*Multiplizieren aller Zeilen mit einem konstanten Vektor ungleich 0,
+
 
 +
*Multiplizieren aller Zeilen mit einem konstanten Vektor ungleich&nbsp; "$\underline{0}$",
 +
 
 
*Ersetzen einer Zeile durch eine Linearkombination zwischen dieser Zeile und einer anderen.
 
*Ersetzen einer Zeile durch eine Linearkombination zwischen dieser Zeile und einer anderen.
  
Für den in der Teilaufgabe 3) gesuchten Code $C_{\rm sys}$ ⇒ Generatormatrix $\boldsymbol{\rm G}_{\rm sys}$ wird weiter gefordert, dass er systematisch ist.
 
  
''Hinweis'' :  
+
Für den in der Teilaufgabe&nbsp; '''(3)'''&nbsp; gesuchten Code&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; mit Generatormatrix&nbsp; $\boldsymbol{\rm G}_{\rm sys}$&nbsp; wird weiter gefordert,&nbsp; dass er systematisch ist.
 +
 
 +
 
 +
 
 +
 
 +
 
 +
Hinweise:
 +
 
 +
*Die Aufgabe gehört zum Kapitel&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|"Allgemeine Beschreibung linearer Blockcodes"]].
 +
 
 +
*Bezug genommen wird insbesondere auf die Seite&nbsp; [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|"Systematische Codes"]].
 +
 
 +
*Bezug genommen wird zudem auf die so genannte&nbsp; "Singleton–Schranke":&
 +
 
 +
*Diese besagt,&nbsp; dass die minimale Hamming–Distanz eines&nbsp; $(n, k)$–Blockcodes nach oben beschränkt ist: &nbsp; $d_{\rm min} \le n - k +1.$
 +
 +
 
  
Die Aufgabe bezieht sich vorwiegend auf die Seite [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|Systematische Codes]] im Kapitel [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer
 
Blockcodes]]1.4. Bezug genommen wird zudem auf die so genannte Singleton–Schranke. Diese besagt, dass die minimale Hamming–Distanz eines $(n, k)$–Blockcodes nach oben beschränkt ist:
 
:$$d_{\rm min} \le n - k +1.$$
 
  
  
Zeile 29: Zeile 45:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Geben Sie die Kenngrößen des gegebenen Codes ''C'' an.
+
{Geben Sie die Kenngrößen des gegebenen Codes&nbsp; $\mathcal{C}$&nbsp; an.
 
|type="{}"}
 
|type="{}"}
$\ n$ = { 6 3% }
+
$n \hspace{0.3cm} = \ $ { 6 }
$\ k$ = { 3 3% }
+
$k \hspace{0.3cm} = \ $ { 3 }
$\ |C|$ = { 8 3% }
+
$m \hspace{0.15cm} = \ $ { 3 }
$\ R$ = { 0.5 3% }
+
$R \hspace{0.2cm} = \ ${ 0.5 3% }
$\ m$ = { 0.5 3% }
+
$|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \hspace{-0.05cm} = \ ${ 8 }
$\ {\rm d}_{min}$ = { 0.5 3% }
+
$d_{\rm min} \hspace{0.01cm} = \ $ { 3 }
  
{Gibt es einen (6, 3)–Blockcode mit größerer Minimaldistanz?
+
{Gibt es einen&nbsp; $(6, 3)$–Blockcode mit größerer Minimaldistanz?
|type="[]"}
+
|type="()"}
 
+ Ja.
 
+ Ja.
 
- Nein.
 
- Nein.
  
{Wie lautet die Generatormatrix ${\boldsymbol{\rm G}}_{\rm sys}$ des identischen systematischen Codes?
+
{Wie lautet die Generatormatrix&nbsp; ${\boldsymbol{\rm G}}_{\rm sys}$&nbsp; des identischen systematischen Codes?
 
|type="[]"}
 
|type="[]"}
- Die 1. Zeile lautet „1 0 1 1 0 1”.
+
- Die 1. Zeile lautet &nbsp; &bdquo;$1 \ 0 \ 1 \ 1 \ 0 \ 1$&rdquo;.
+ Die 2. Zeile lautet „0 1 0 1 0 1”.
+
+ Die 2. Zeile lautet &nbsp;  &bdquo;$0 \ 1 \ 0 \ 1 \ 0 \ 1$&rdquo;.
+ Die 3. Zeile lautet „0 0 1 0 1 1”.
+
+ Die 3. Zeile lautet &nbsp;  &bdquo;$0 \ 0 \ 1 \ 0 \ 1 \ 1$&rdquo;.
  
 
{Welche Zuordnungen ergeben sich bei dieser Codierung?
 
{Welche Zuordnungen ergeben sich bei dieser Codierung?
 
|type="[]"}
 
|type="[]"}
+ $\underline{u} = (0, 0, 0)$   ⇒  $\underline{x}_{\rm sys} = (0, 0, 0, 0, 0, 0)$.
+
+ $\underline{u} = (0, 0, 0)  \ \Rightarrow \  \underline{x}_{\rm sys} = (0, 0, 0, 0, 0, 0)$.
+ $\underline{u} = (0, 0, 1)$  ⇒  $\underline{x}_{\rm sys}= (0, 0, 1, 0, 0, 1)$.
+
+ $\underline{u} = (0, 0, 1) \ \Rightarrow \  \underline{x}_{\rm sys}= (0, 0, 1, 0, 0, 1)$.
- $\underline{u} = (0, 1, 0)$  ⇒  $\underline{x}_{\rm sys} = (0, 1, 0, 1, 1, 0)$.
+
- $\underline{u} = (0, 1, 0) \  \Rightarrow  \ \underline{x}_{\rm sys} = (0, 1, 0, 1, 1, 0)$.
  
  
{Welche Prüfbits hat der systematische Code $\underline{x}_{\rm sys} = (u_{1}, u_{2}, u_{3}, p_{1}, p_{2}, p_{3})$?
+
{Welche Prüfbits hat der systematische Code&nbsp; $\underline{x}_{\rm sys} = (u_{1},\ u_{2},\ u_{3},\ p_{1},\ p_{2},\ p_{3})$?
 
|type="[]"}
 
|type="[]"}
+$p_{1} = u_{1} u_{2},$
+
+$p_{1} = u_{1} \oplus u_{2},$
-$p_{2} = u_{2} u_{3},$
+
-$p_{2} = u_{2} \oplus u_{3},$
-$p_{3} = u_{1} u_{3}.$
+
-$p_{3} = u_{1} \oplus u_{3}.$
  
  
Zeile 68: Zeile 84:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''1.'''
+
'''(1)'''&nbsp; Der vorgegebene Code&nbsp; $\mathcal{C}$&nbsp; wird durch folgende Kenngrößen charakterisiert:
'''2.'''
+
*Bitanzahl der Codeworte:&nbsp; $\underline{n = 6}$,
'''3.'''
+
 
'''4.'''
+
*Bitanzahl der Informationsworte:&nbsp; $\underline{k = 3}$,
'''5.'''
+
 
'''6.'''
+
*Anzahl der Prüfbitgleichungen:&nbsp; $\underline{m = n - k = 3}$,
'''7.'''
+
 
 +
*Coderate:&nbsp; $R = k/n = 3/6  \Rightarrow  \underline{R = 0.5}$,
 +
 
 +
*Anzahl der Codeworte (Codeumfang):&nbsp; $|\mathcal{C}| = 2^k  \Rightarrow  \underline{|C| = 8}$,
 +
 
 +
*minimale Hamming–Distanz (siehe Tabelle):&nbsp; $\underline{d}_{\rm min} \underline{= 3}$.
 +
 
 +
 
 +
 
 +
'''(2)'''&nbsp; Richtig ist&nbsp; $\underline{\rm JA}$:
 +
*Nach der Singleton–Schranke gilt&nbsp; $d_{\rm min} ≤ n - k + 1$.&nbsp; Mit&nbsp; $n = 6$&nbsp; und&nbsp; $k = 3$&nbsp; erhält man hierfür&nbsp; $d_{\rm min} ≤ 4$.
 +
 +
*Es kann also durchaus ein&nbsp; $(6, 3)$–Blockcode mit größerer Minimaldistanz konstruiert werden.&nbsp; Wie ein solcher Code aussieht,&nbsp; wurde freundlicherweise nicht gefragt.
 +
 
 +
 
 +
Die Minimaldistanz aller Hamming–Codes ist&nbsp; $d_{\rm min} = 3$,&nbsp; und nur der Sonderfall mit&nbsp; $n = 3$&nbsp; und&nbsp; $k = 1$&nbsp; erreicht den Grenzwert. Dagegen erreichen das Maximum entsprechend der Singleton–Schranke:
 +
 
 +
*alle&nbsp; [[Kanalcodierung/Beispiele_binärer_Blockcodes#Wiederholungscodes|Wiederholungscodes]]&nbsp; $($Repetition Codes,&nbsp; $\rm RC)$&nbsp; wegen&nbsp; $k = 1$&nbsp; und&nbsp; $d_{\rm min} = n$;&nbsp; hierzu gehört auch der&nbsp; $\rm (3, 1)$–Hamming–Code,&nbsp; der ja bekannterweise identisch ist mit dem&nbsp; $\text{RC (3, 1)}$,
 +
 
 +
*alle&nbsp; [[Kanalcodierung/Beispiele_binärer_Blockcodes#Single_Parity.E2.80.93check_Codes|Single Parity–check Codes]]&nbsp; $\rm (SPC)$:&nbsp; $k = n - 1, d_{\rm min} = 2$.
 +
 
 +
 
 +
 
 +
'''(3)'''&nbsp; Richtig sind die&nbsp; <u>Lösungsvorschläge 2 und 3</u>:
 +
*Vertauscht man Zeilen der Generatormatrix $\boldsymbol {\rm G}$,&nbsp; so kommt man zu einem identischen Code&nbsp; $\mathcal{C}'$.&nbsp; Das heißt:&nbsp; $\mathcal{C}$&nbsp; und&nbsp; $\mathcal{C}'$&nbsp; beinhalten die genau gleichen Codeworte.
 +
 +
*Beispielsweise erhält man nach zyklischem Zeilentausch&nbsp; $2 \rightarrow 1,\ 3 \rightarrow 2$&nbsp; und&nbsp; $1 \rightarrow 3$&nbsp; die neue Matrix
 +
 
 +
:$${ \boldsymbol{\rm G}}' = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
 +
 
 +
*Die erste und die letzte Zeile der neuen Matrix entsprechen schon den Vorgaben eines systematischen Codes,&nbsp; nämlich,&nbsp; dass deren Generatormatrix&nbsp; ${ \boldsymbol{\rm G}_{\rm sys}}$&nbsp; mit einer Diagonalmatrix beginnen muss.
 +
 +
*Ersetzt man die Zeile 2 durch die Modulo–2–Summe von Zeile 2 und 3,&nbsp; so erhält man:
 +
 
 +
:$${ \boldsymbol{\rm G}}_{\rm sys} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
 +
 
 +
*Dieser systematische Code beinhaltet genau die gleichen Codeworte wie die Codes&nbsp; $\mathcal{C}$&nbsp; und&nbsp; $\mathcal{C}'$.
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; Richtig sind die&nbsp; <u>Lösungsvorschläge 1 und 2</u>:
 +
*Wendet man die Gleichung&nbsp; $\underline{x}_{\rm sys} = \underline{u} \cdot \boldsymbol{\rm G}_{\rm sys}$&nbsp; auf obige Beispiele an,&nbsp; so erkennt man,&nbsp; dass die beiden ersten Aussagen richtig sind,&nbsp; nicht aber die letzte.
 +
 
 +
*Ohne Rechnung kommt man zum gleichen Ergebnis,&nbsp; wenn man berücksichtigt,&nbsp; dass
 +
 
 +
:*das systematische Codewort&nbsp; $\underline{x}_{\rm sys}$&nbsp; mit&nbsp; $\underline{u}$&nbsp; beginnen muss,
 +
:*der Code&nbsp; $\mathcal{C}_{\rm sys}$&nbsp; die gleichen Codeworte beinhaltet wie der vorgegebene Code&nbsp; $\mathcal{C}$.
 +
 
 +
*Für&nbsp; $\underline{u} = (0, 1, 0)$&nbsp; lautet somit das Codewort&nbsp; $(0, 1, 0, ?, ?, ?)$.&nbsp;
 +
 
 +
*Ein Vergleich mit der Codetabelle von&nbsp; $\mathcal{C}$&nbsp; auf der Angabenseite führt zu&nbsp; $\underline{x}_{\rm sys} = (0, 1, 0, 1, 0, 1)$.
 +
 
 +
 
 +
 
 +
'''(5)'''&nbsp; Richtig ist nur die&nbsp; <u>Aussage 1</u>.&nbsp; Die Angaben für&nbsp; $p_{2}$&nbsp; und&nbsp; $p_{3}$&nbsp; sind dagegen genau vertauscht.
 +
*Bei systematischer Codierung besteht folgender Zusammenhang zwischen Generator– und Prüfmatrix:
 +
 
 +
:$${ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_k \: ; \:{ \boldsymbol{\rm P}} \right) \hspace{0.3cm}\Leftrightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} =\left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.05cm}.$$
 +
 
 +
[[Datei:P_ID2395__KC_A_1_8_ML.png|right|frame|Schaubild der Prüfgleichungen]]
 +
*Angewendet auf das aktuelle Beispiel erhält man so:
 +
 
 +
:$${ \boldsymbol{\rm G}}_{\rm sys} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{\rm sys} = \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}.$$
 +
 
 +
*Daraus ergeben sich Prüfgleichungen (siehe Grafik):
 +
:$$u_1 \oplus u_2 \oplus p_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_1 = u_1 \oplus u_2 \hspace{0.05cm},$$
 +
:$$ u_1 \oplus u_3 \oplus p_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_2 = u_1 \oplus u_3 \hspace{0.05cm},$$
 +
:$$ u_2 \oplus u_3 \oplus p_3 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_3 = u_2 \oplus u_3 \hspace{0.05cm}.$$
 +
 
 +
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu  Kanalcodierung|^1.4 Allgemeine Beschreibung linearer Blockcodes
+
[[Category:Aufgaben zu  Kanalcodierung|^1.4 Beschreibung linearer Blockcodes
  
 
^]]
 
^]]

Aktuelle Version vom 10. Juli 2022, 16:41 Uhr

Zuordnung des  $(6, 3)$–Blockcodes

Wir betrachten einen Blockcode  $\mathcal{C}$,  der durch folgende Generatormatrix beschrieben wird:

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

Die Zuordnung zwischen den Informationsworten  $\underline{u}$  und den Codeworten  $\underline{x}$  kann der Tabelle entnommen werden.  Man erkennt,  dass es sich dabei nicht um einen systematischen Code handelt.

Durch Manipulation der Generatormatrix  $\boldsymbol {\rm G}$  lassen sich daraus identische Codes konstruieren.  Darunter versteht man Codes mit gleichen Codeworten,  jedoch unterschiedlicher Zuordnung  $\underline{u} \rightarrow \underline{x}$.

Folgende Operationen sind erlaubt,  um einen identischen Code zu erhalten:

  • 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.


Für den in der Teilaufgabe  (3)  gesuchten Code  $\mathcal{C}_{\rm sys}$  mit Generatormatrix  $\boldsymbol{\rm G}_{\rm sys}$  wird weiter gefordert,  dass er systematisch ist.



Hinweise:

  • Bezug genommen wird zudem auf die so genannte  "Singleton–Schranke":&
  • Diese besagt,  dass die minimale Hamming–Distanz eines  $(n, k)$–Blockcodes nach oben beschränkt ist:   $d_{\rm min} \le n - k +1.$



Fragebogen

1

Geben Sie die Kenngrößen des gegebenen Codes  $\mathcal{C}$  an.

$n \hspace{0.3cm} = \ $

$k \hspace{0.3cm} = \ $

$m \hspace{0.15cm} = \ $

$R \hspace{0.2cm} = \ $

$|\hspace{0.05cm}\mathcal{C}\hspace{0.05cm}| \hspace{-0.05cm} = \ $

$d_{\rm min} \hspace{0.01cm} = \ $

2

Gibt es einen  $(6, 3)$–Blockcode mit größerer Minimaldistanz?

Ja.
Nein.

3

Wie lautet die Generatormatrix  ${\boldsymbol{\rm G}}_{\rm sys}$  des identischen systematischen Codes?

Die 1. Zeile lautet   „$1 \ 0 \ 1 \ 1 \ 0 \ 1$”.
Die 2. Zeile lautet   „$0 \ 1 \ 0 \ 1 \ 0 \ 1$”.
Die 3. Zeile lautet   „$0 \ 0 \ 1 \ 0 \ 1 \ 1$”.

4

Welche Zuordnungen ergeben sich bei dieser Codierung?

$\underline{u} = (0, 0, 0) \ \Rightarrow \ \underline{x}_{\rm sys} = (0, 0, 0, 0, 0, 0)$.
$\underline{u} = (0, 0, 1) \ \Rightarrow \ \underline{x}_{\rm sys}= (0, 0, 1, 0, 0, 1)$.
$\underline{u} = (0, 1, 0) \ \Rightarrow \ \underline{x}_{\rm sys} = (0, 1, 0, 1, 1, 0)$.

5

Welche Prüfbits hat der systematische Code  $\underline{x}_{\rm sys} = (u_{1},\ u_{2},\ u_{3},\ p_{1},\ p_{2},\ p_{3})$?

$p_{1} = u_{1} \oplus u_{2},$
$p_{2} = u_{2} \oplus u_{3},$
$p_{3} = u_{1} \oplus u_{3}.$


Musterlösung

(1)  Der vorgegebene Code  $\mathcal{C}$  wird durch folgende Kenngrößen charakterisiert:

  • Bitanzahl der Codeworte:  $\underline{n = 6}$,
  • Bitanzahl der Informationsworte:  $\underline{k = 3}$,
  • Anzahl der Prüfbitgleichungen:  $\underline{m = n - k = 3}$,
  • Coderate:  $R = k/n = 3/6 \Rightarrow \underline{R = 0.5}$,
  • Anzahl der Codeworte (Codeumfang):  $|\mathcal{C}| = 2^k \Rightarrow \underline{|C| = 8}$,
  • minimale Hamming–Distanz (siehe Tabelle):  $\underline{d}_{\rm min} \underline{= 3}$.


(2)  Richtig ist  $\underline{\rm JA}$:

  • Nach der Singleton–Schranke gilt  $d_{\rm min} ≤ n - k + 1$.  Mit  $n = 6$  und  $k = 3$  erhält man hierfür  $d_{\rm min} ≤ 4$.
  • Es kann also durchaus ein  $(6, 3)$–Blockcode mit größerer Minimaldistanz konstruiert werden.  Wie ein solcher Code aussieht,  wurde freundlicherweise nicht gefragt.


Die Minimaldistanz aller Hamming–Codes ist  $d_{\rm min} = 3$,  und nur der Sonderfall mit  $n = 3$  und  $k = 1$  erreicht den Grenzwert. Dagegen erreichen das Maximum entsprechend der Singleton–Schranke:

  • alle  Wiederholungscodes  $($Repetition Codes,  $\rm RC)$  wegen  $k = 1$  und  $d_{\rm min} = n$;  hierzu gehört auch der  $\rm (3, 1)$–Hamming–Code,  der ja bekannterweise identisch ist mit dem  $\text{RC (3, 1)}$,


(3)  Richtig sind die  Lösungsvorschläge 2 und 3:

  • Vertauscht man Zeilen der Generatormatrix $\boldsymbol {\rm G}$,  so kommt man zu einem identischen Code  $\mathcal{C}'$.  Das heißt:  $\mathcal{C}$  und  $\mathcal{C}'$  beinhalten die genau gleichen Codeworte.
  • Beispielsweise erhält man nach zyklischem Zeilentausch  $2 \rightarrow 1,\ 3 \rightarrow 2$  und  $1 \rightarrow 3$  die neue Matrix
$${ \boldsymbol{\rm G}}' = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &1 &1 &1 &0\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
  • Die erste und die letzte Zeile der neuen Matrix entsprechen schon den Vorgaben eines systematischen Codes,  nämlich,  dass deren Generatormatrix  ${ \boldsymbol{\rm G}_{\rm sys}}$  mit einer Diagonalmatrix beginnen muss.
  • Ersetzt man die Zeile 2 durch die Modulo–2–Summe von Zeile 2 und 3,  so erhält man:
$${ \boldsymbol{\rm G}}_{\rm sys} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
  • Dieser systematische Code beinhaltet genau die gleichen Codeworte wie die Codes  $\mathcal{C}$  und  $\mathcal{C}'$.


(4)  Richtig sind die  Lösungsvorschläge 1 und 2:

  • Wendet man die Gleichung  $\underline{x}_{\rm sys} = \underline{u} \cdot \boldsymbol{\rm G}_{\rm sys}$  auf obige Beispiele an,  so erkennt man,  dass die beiden ersten Aussagen richtig sind,  nicht aber die letzte.
  • Ohne Rechnung kommt man zum gleichen Ergebnis,  wenn man berücksichtigt,  dass
  • das systematische Codewort  $\underline{x}_{\rm sys}$  mit  $\underline{u}$  beginnen muss,
  • der Code  $\mathcal{C}_{\rm sys}$  die gleichen Codeworte beinhaltet wie der vorgegebene Code  $\mathcal{C}$.
  • Für  $\underline{u} = (0, 1, 0)$  lautet somit das Codewort  $(0, 1, 0, ?, ?, ?)$. 
  • Ein Vergleich mit der Codetabelle von  $\mathcal{C}$  auf der Angabenseite führt zu  $\underline{x}_{\rm sys} = (0, 1, 0, 1, 0, 1)$.


(5)  Richtig ist nur die  Aussage 1.  Die Angaben für  $p_{2}$  und  $p_{3}$  sind dagegen genau vertauscht.

  • Bei systematischer Codierung besteht folgender Zusammenhang zwischen Generator– und Prüfmatrix:
$${ \boldsymbol{\rm G}} =\left({ \boldsymbol{\rm I}}_k \: ; \:{ \boldsymbol{\rm P}} \right) \hspace{0.3cm}\Leftrightarrow \hspace{0.3cm} { \boldsymbol{\rm H}} =\left({ \boldsymbol{\rm P}}^{\rm T}\: ; \:{ \boldsymbol{\rm I}}_m \right) \hspace{0.05cm}.$$
Schaubild der Prüfgleichungen
  • Angewendet auf das aktuelle Beispiel erhält man so:
$${ \boldsymbol{\rm G}}_{\rm sys} = \begin{pmatrix} 1 &0 &0 &1 &1 &0\\ 0 &1 &0 &1 &0 &1\\ 0 &0 &1 &0 &1 &1 \end{pmatrix} \hspace{0.3cm} \Rightarrow\hspace{0.3cm} { \boldsymbol{\rm H}}_{\rm sys} = \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}.$$
  • Daraus ergeben sich Prüfgleichungen (siehe Grafik):
$$u_1 \oplus u_2 \oplus p_1 \hspace{-0.15cm} \ = \ \hspace{-0.15cm}0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_1 = u_1 \oplus u_2 \hspace{0.05cm},$$
$$ u_1 \oplus u_3 \oplus p_2 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_2 = u_1 \oplus u_3 \hspace{0.05cm},$$
$$ u_2 \oplus u_3 \oplus p_3 \hspace{-0.15cm} \ = \ \hspace{-0.15cm} 0 \hspace{0.3cm} \Rightarrow\hspace{0.3cm} p_3 = u_2 \oplus u_3 \hspace{0.05cm}.$$