Aufgabe 1.08Z: Äquivalente Codes

From LNTwww

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 :


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

(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 A, Code C und Code D, nicht aber Code B.


(2)  Richtig ist nur Antwort 1:

  • Nur Code A und Code 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 A und Code B sind mehr als äquivalent, nämlich identisch.
  • Code C und D unterscheiden sich zum Beispiel auch durch die minimale Hamming–Distanz $d_{\rm min} = 3$ bzw. $d_{\rm min} = 2$ und sind somit auch nicht äquivalent.
  • Code B und Code 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.