Difference between revisions of "Aufgaben:Exercise 1.08Z: Equivalent Codes"

From LNTwww
Line 1: Line 1:
{{quiz-Header|Buchseite=Kanalcodierung/Allgemeine Beschreibung linearer Blockcodes
+
{{quiz-Header|Buchseite=Channel_Coding/General_Description_of_Linear_Block_Codes
  
 
}}
 
}}
  
[[File:P_ID2394__KC_Z_1_8.png|right|frame|Vier  $(6, 3)$–Blockcodes]]
+
[[File:P_ID2394__KC_Z_1_8.png|right|frame|Four  $(6, 3)$ block codes]]
  
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:
+
In the graph, the mappings  $\underline{u} \rightarrow \underline{x}$  for different codes are given, each characterized below by the generator matrix  $\boldsymbol{\rm G}$  and the parity-check matrix  $\boldsymbol{\rm H}$  respectively:
  
 
*${\boldsymbol{\rm Code \ A}}$:
 
*${\boldsymbol{\rm Code \ A}}$:
Line 19: Line 19:
 
:$${ \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}.$$
 
:$${ \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
+
This task is to investigate which of these codes or code pairs are
  
*systematisch sind,
+
*are systematic,
*identisch sind  (das heißt:   Verschiedene Codes haben gleiche Codeworte),
+
*are identical  (that is:   Different codes have same code words),
*äquivalent sind  (das heißt:   Verschiedene Codes haben gleiche Codeparameter).
+
*are equivalent  (that is:   Different codes have same code parameters).
  
  
Line 30: Line 30:
  
  
''Hinweise'' :  
+
Hints :  
  
*Die Aufgabe gehört zum Kapitel  [[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer Blockcodes]].
+
*This exercise belongs to the chapter  [[Channel_Coding/General_Description_of_Linear_Block_Codes|General Description of Linear Block Codes]].
*Bezug genommen wird insbesondere auf die Seiten  [[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|Systematische Codes]]  sowie  [[Channel_Coding/Allgemeine_Beschreibung_linearer_Blockcodes#Identische_Codes|Identische Codes]].
+
*Reference is made in particular to the pages  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|Systematic Codes]]  and  [[Channel_Coding/General_Description_of_Linear_Block_Codes#Identical_Codes|Identical Codes]].
*Anzumerken ist, dass die Angabe einer Prüfmatrix  $\boldsymbol{\rm H}$  nicht eindeutig ist.  
+
*Note that the specification of a parity-check matrix  $\boldsymbol{\rm H}$  is not unique.  
*Verändert man die Reihenfolge der Prüfgleichungen, so entspricht dies einer Vertauschung von Zeilen.
+
*If one changes the order of the parity-check equations, this corresponds to a swapping of rows.
  
  
  
===Fragebogen===
+
===Questions===
  
 
<quiz display=simple>
 
<quiz display=simple>
{Welche der nachfolgend aufgeführten Codes sind systematisch?
+
{Which of the codes listed below are systematic?
 
|type="[]"}
 
|type="[]"}
 
+ Code &nbsp;$\rm A$,
 
+ Code &nbsp;$\rm A$,
Line 49: Line 49:
 
+ Code &nbsp;$\rm D$.
 
+ Code &nbsp;$\rm D$.
  
{Welche der vorgegebenen Codepaare sind identisch?
+
{Which of the given code pairs are identical?
 
|type="[]"}
 
|type="[]"}
 
 
+ Code &nbsp;$\rm A$&nbsp; und Code &nbsp;$\rm B$,
+
+ Code &nbsp;$\rm A$&nbsp; and code &nbsp;$\rm B$,
- Code &nbsp;$\rm B$&nbsp; und Code &nbsp;$\rm C$,
+
- Code &nbsp;$\rm B$&nbsp; and code &nbsp;$\rm C$,
- Code &nbsp;$\rm C$&nbsp; und Code &nbsp;$\rm D$.
+
- Code &nbsp;$\rm C$&nbsp; and code &nbsp;$\rm D$.
  
  
{Welche der gegebenen Codepaare sind äquivalent, aber nicht identisch?
+
{Which of the given code pairs are equivalent but not identical?
 
|type="[]"}
 
|type="[]"}
- Code &nbsp;$\rm A$&nbsp; und Code &nbsp;$\rm B$,
+
- Code &nbsp;$\rm A$&nbsp; and code &nbsp;$\rm B$,
+ Code &nbsp;$\rm B$&nbsp; und Code &nbsp;$\rm C$,
+
+ Code &nbsp;$\rm B$&nbsp; and code &nbsp;$\rm C$,
- Code &nbsp;$\rm C$&nbsp; und Code &nbsp;$\rm D$.
+
- Code &nbsp;$\rm C$&nbsp; and code &nbsp;$\rm D$.
  
{Wie unterscheiden sich die Generatormatrizen&nbsp; $G_{\rm B}$&nbsp; und&nbsp; $G_{\rm C}$?
+
{How do the generator matrices&nbsp; $G_{\rm B}$&nbsp; and&nbsp; $G_{\rm C}$ differ?
 
|type="[]"}
 
|type="[]"}
- Durch verschiedene Linearkombinationen verschiedener Zeilen.
+
- By different linear combinations of different rows.
- Durch zyklische Vertauschung der Zeilen um &nbsp;$1$&nbsp; nach unten.
+
- By cyclic shifting of rows by &nbsp;$1$&nbsp; down.
+ Durch zyklische Vertauschung der Spalten um &nbsp;$1$&nbsp; nach rechts.
+
+ By cyclic shifting of columns by &nbsp;$1$&nbsp; to the right.?
  
  
{Bei welchen Codes gilt&nbsp; ${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$?
+
{For which codes applies&nbsp; ${ \boldsymbol{\rm H}} \cdot { \boldsymbol{\rm G}}^{\rm T} = \boldsymbol{0}$?
 
|type="[]"}
 
|type="[]"}
 
+ Code &nbsp;$\rm A$,
 
+ Code &nbsp;$\rm A$,

Revision as of 14:57, 6 July 2022

Four  $(6, 3)$ block codes

In the graph, the mappings  $\underline{u} \rightarrow \underline{x}$  for different codes are given, each characterized below by the generator matrix  $\boldsymbol{\rm G}$  and the parity-check matrix  $\boldsymbol{\rm H}$  respectively:

  • ${\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}.$$

This task is to investigate which of these codes or code pairs are

  • are systematic,
  • are identical  (that is:   Different codes have same code words),
  • are equivalent  (that is:   Different codes have same code parameters).




Hints :


Questions

1

Which of the codes listed below are systematic?

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

2

Which of the given code pairs are identical?

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

3

Which of the given code pairs are equivalent but not identical?

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

4

How do the generator matrices  $G_{\rm B}$  and  $G_{\rm C}$ differ?

By different linear combinations of different rows.
By cyclic shifting of rows by  $1$  down.
By cyclic shifting of columns by  $1$  to the right.?

5

For which codes applies  ${ \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.