Aufgaben:Aufgabe 1.08Z: Äquivalente Codes

• Zurück zum Buch

Vier  $(6, 3)$–Blockcodes

In der Grafik sind die Zuordnungen  $\underline{u} \rightarrow \underline{x}$  für verschiedene Codes angegeben,  die im Folgenden jeweils durch die Generatormatrix  $\boldsymbol{\rm G}$  und die Prüfmatrix  $\boldsymbol{\rm H}$  charakterisiert werden:

• ${\boldsymbol{\rm Code \ A}}$:

$${ \boldsymbol{\rm G}}_{\rm A} = \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},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm A} = \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}.$$

• ${\boldsymbol{\rm Code \ B}}$:

$${ \boldsymbol{\rm G}}_{\rm B} = \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},\hspace{0.5cm} { \boldsymbol{\rm H}}_{\rm B} = \begin{pmatrix} 1 &0 &1 &0 &1 &0\\ 1 &1 &0 &1 &0 &0\\ 0 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$

• ${\boldsymbol{\rm Code \ C}}$:

$${ \boldsymbol{\rm G}}_{\rm C} = \begin{pmatrix} 1 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1\\ 0 &0 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm C} = \begin{pmatrix} 1 &0 &1 &1 &0 &0\\ 0 &1 &1 &0 &1 &0\\ 1 &1 &1 &0 &0 &1 \end{pmatrix} \hspace{0.05cm},$$

• ${\boldsymbol{\rm Code \ D}}$:

$${ \boldsymbol{\rm G}}_{\rm D} = \begin{pmatrix} 1 &0 &0 &1 &0 &1\\ 0 &1 &0 &1 &0 &0\\ 0 &0 &1 &0 &1 &0 \end{pmatrix} \hspace{0.05cm},\hspace{0.5cm}{ \boldsymbol{\rm H}}_{\rm D} = \begin{pmatrix} 1 &1 &0 &1 &0 &0\\ 0 &0 &1 &0 &1 &0\\ 1 &0 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$

In dieser Aufgabe soll untersucht werden,  welche dieser Codes bzw. Codepaare

• systematisch sind,
• identisch sind  (das heißt:   Verschiedene Codes haben gleiche Codeworte),
• äquivalent sind  (das heißt:   Verschiedene Codes haben gleiche Codeparameter).

Hinweise:

• Die Aufgabe gehört zum Kapitel  "Allgemeine Beschreibung linearer Blockcodes".

• Bezug genommen wird insbesondere auf die Seiten  "Systematische Codes"  sowie  "Identische Codes".

• Anzumerken ist,  dass die Angabe einer Prüfmatrix  $\boldsymbol{\rm H}$  nicht eindeutig ist.  Verändert man die Reihenfolge der Gleichungen,  entspricht dies der Vertauschung von Zeilen.

Fragebogen

1

Welche der nachfolgend aufgeführten Codes sind systematisch?

	Code  $\rm A$,
	Code  $\rm B$,
	Code  $\rm C$,
	Code  $\rm D$.

2

Welche der vorgegebenen Codepaare sind identisch?

	Code  $\rm A$  und  Code  $\rm B$,
	Code  $\rm B$  und  Code  $\rm C$,
	Code  $\rm C$  und  Code  $\rm D$.

3

Welche der gegebenen Codepaare sind äquivalent,  aber nicht identisch?

	Code  $\rm A$  und  Code  $\rm B$,
	Code  $\rm B$  und  Code  $\rm C$,
	Code  $\rm C$  und  Code  $\rm D$.

4

Wie unterscheiden sich die Generatormatrizen  $G_{\rm B}$  und  $G_{\rm C}$?

	Durch verschiedene Linearkombinationen verschiedener Zeilen.
	Durch zyklische Vertauschung der Zeilen um  $1$  nach unten.
	Durch zyklische Vertauschung der Spalten um  $1$  nach rechts.

5

Bei welchen Codes gilt  ${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$?

	Code  $\rm A$,
	Code  $\rm B$,
	Code  $\rm C$,
	Code  $\rm D$.

Musterlösung

Musterlösung

(1)  Richtig sind die  Antworten 1, 3 und 4:

• Für einen systematischen  $(6, 3)$–Blockcode muss gelten:

$$\underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6) = ( u_1, u_2, u_3, p_1, p_2, p_{3}) \hspace{0.05cm}.$$

• Diese Bedingung erfüllen Code  $\rm A$,  Code  $\rm C$  und  Code  $\rm D$,  nicht aber Code  $\rm B$.

(2)  Richtig ist nur  Antwort 1:

• Nur  Code  $\rm A$  und  Code  $\rm B$  sind identische Codes.  Sie beinhalten genau die gleichen Codeworte und unterscheiden sich nur durch andere Zuordnungen  $\underline{u} \rightarrow \underline{x}$.

• Wie in der Musterlösung zur  "Aufgabe A1.8 (3)" angegeben,  gelangt man von der Generatormatrix  ${ \boldsymbol{\rm G}}_{\rm B}$  zur  Generatormatrix ${ \boldsymbol{\rm G}}_{\rm A}$

• allein durch Vertauschen/Permutieren von Zeilen,  oder
• durch Ersetzen einer Zeile durch die Linearkombination zwischen dieser Zeile und einer anderen.

(3)  Richtig ist somit allein  Antwort 2:

• Code  $\rm A$  und  Code  $\rm B$  sind mehr als äquivalent,  nämlich identisch.

• Code  $\rm C$  und  Code  $\rm D$  unterscheiden sich durch die minimale Hamming–Distanz  $d_{\rm min} = 3$  bzw.  $d_{\rm min} = 2$  und sind somit auch nicht äquivalent.

• Code  $\rm B$  und  Code  $\rm C$  zeigen dagegen gleiche Eigenschaften,  beispielsweise gilt für beide  $d_{\rm min} = 3$.  Sie beinhalten aber andere Codeworte.

(4)  Richtig ist  Antwort 3:

• Die letzte Spalte von  ${ \boldsymbol{\rm G}}_{\rm B}$  ergibt die erste Spalte von  ${ \boldsymbol{\rm G}}_{\rm C}$.
• Die erste Spalte von  ${ \boldsymbol{\rm G}}_{\rm B}$  ergibt die zweite Spalte von  ${ \boldsymbol{\rm G}}_{\rm C}$.
• Die zweite Spalte von  ${ \boldsymbol{\rm G}}_{\rm B}$  ergibt die dritte Spalte von  ${ \boldsymbol{\rm G}}_{\rm C}$,  usw.

(5)  Alle Aussagen treffen zu:

• Die Bedingung  ${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$  gilt für alle linearen Codes.