Aufgaben:Aufgabe 1.08Z: Äquivalente Codes: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
Zeile 5: Zeile 5:
 
[[Datei:P_ID2394__KC_Z_1_8.png|right|frame|Vier verschiedene (6, 3)–Blockcodes]]
 
[[Datei:P_ID2394__KC_Z_1_8.png|right|frame|Vier verschiedene (6, 3)–Blockcodes]]
  
In der Grafik sind die Zuordnungen $\underline{u} \underline{x}$ für verschiedene Codes angegeben, die im Folgenden jeweils durch die Generatormatrix '''G''' und die Prüfmatrix '''H''' charakterisiert werden:
+
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:
  
*$\color{red}{\boldsymbol{\rm Code \ A}}$:
+
*$\color{red}{\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},$$
 
:$${ \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},$$
 
:$${ \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 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}.$$
Zeile 30: Zeile 30:
 
''Hinweis'' :  
 
''Hinweis'' :  
  
Die Aufgabe gehört zum Themengebiet von Kapitel [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer
+
Die Aufgabe gehört zum Themengebiet [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer
  Blockcodes]] Anzumerken ist, dass die Angabe einer Prüfmatrix '''H''' nicht eindeutig ist. Verändert man die Reihenfolge der Prüfgleichungen, so entspricht dies einer Vertauschung von Zeilen.
+
  Blockcodes]] Anzumerken ist, dass die Angabe einer Prüfmatrix $\boldsymbol{\rm H}$ nicht eindeutig ist. Verändert man die Reihenfolge der Prüfgleichungen, so entspricht dies einer Vertauschung von Zeilen.
  
 
===Fragebogen===
 
===Fragebogen===

Version vom 14. Dezember 2017, 19:07 Uhr

Vier verschiedene (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:

  • $\color{red}{\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},$$
$${ \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}.$$
  • $\color{red}{\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},$$
$$ { \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}.$$
  • $\color{red}{\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},{ \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},$$
  • $\color{red}{\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},{ \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).


Hinweis :

Die Aufgabe gehört zum Themengebiet Allgemeine Beschreibung linearer Blockcodes Anzumerken ist, dass die Angabe einer Prüfmatrix $\boldsymbol{\rm H}$ nicht eindeutig ist. Verändert man die Reihenfolge der Prüfgleichungen, so entspricht dies einer Vertauschung von Zeilen.

Fragebogen

1

Welche der nachfolgend aufgeführten Codes sind systematisch?

Code A,
Code B,
Code C,
Code D.

2

Welche der vorgegebenen Codepaare sind identisch?

Code A und Code B,
Code B und Code C,
Code C und Code D.

3

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

Code A und Code B,
Code B und Code C,
Code C und Code 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}} · { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$?

Code A,
Code B,
Code C,
Code D.


Musterlösung

(1)  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 die Codes A, C und D ⇒ Antwort 1, 2, 4.

(2)  Nur Code A und Code B sind identische Codes ⇒ Antwort 1. Sie beinhalten genau die gleichen Codeworte und unterscheiden sich nur durch andere Zuordnungen $\underline{u} → \underline{x}$. Wie in der Musterlösung zur Aufgabe A1.08 (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)  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.

Richtig ist somit allein Antwort 2. Code B und Code C haben 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)  Die Bedingung ${ \boldsymbol{\rm H}} · { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$ gilt für alle linearen Codes ⇒ Alle Aussagen treffen zu.