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.
The mapping between the information words $\underline{u}$ and the code words $\underline{x}$ can be seen in the table. It can be seen that this is not a "systematic code".
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:
By manipulating the generator matrix $\boldsymbol {\rm G}$, identical codes can be constructed from it. This refers to codes with the same code words but different assignments $\underline{u} \rightarrow \underline{x}$.
*Vertauschen oder Permutieren der Zeilen,
The following operations are allowed to obtain identical code:
*Multiplizieren aller Zeilen mit einem konstanten Vektor ungleich 0,
*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.
*swapping or permuting the rows,
''Hinweis'' :
*Multiplying all rows by a constant vector not equal to "$\underline{0}$".
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
*Replacing a row with a linear combination between this row and another one.
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.$$
===Fragebogen===
For the code $\mathcal{C}_{\rm sys}$ sought in subtask '''(3)''' it is further required to be systematic ⇒ generator matrix $\boldsymbol{\rm G}_{\rm sys}$.
Hints:
*This exercise belongs to the chapter [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General Description of Linear Block Codes"]].
*Reference is made in particular to the section [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|"Systematic Codes"]].
*Reference is also made to the so-called "Singleton bound".
*This states that the minimum Hamming distance of a $(n, k)$ block code is upper bounded: $d_{\rm min} \le n - k +1.$
===Questions===
<quiz display=simple>
<quiz display=simple>
{Geben Sie die Kenngrößen des gegebenen Codes ''C'' an.
{Give the characteristics of the given code $\mathcal{C}$ .
*minimum Hamming distance (see table): $\underline{d}_{\rm min} \underline{= 3}$.
'''(2)''' Correct is $\underline{\rm Yes}$:
*According to the singleton bound ⇒ $d_{\rm min} ≤ n - k + 1$. With $n = 6$ and $k = 3$ one obtains $d_{\rm min} ≤ 4$.
*It is thus quite possible to construct a $(6, 3)$ block code with larger minimal distance. How such a code looks, was kindly not asked.
The minimum distance of all Hamming codes is $d_{\rm min} = 3$, and only the special case with $n = 3$ and $k = 1$ reaches the limit. In contrast, the maximum reach according to the Singleton bound:
*all [[Channel_Coding/Examples_of_Binary_Block_Codes#Repetition_Codes|repetition codes]] $\rm (RC)$ because $k = 1$ and $d_{\rm min} = n$; this includes the $\rm (3, 1)$ Hamming code, which is known to be identical to $\rm RC\ (3, 1)$,
'''(3)''' Correct are th e <u>solutions 2 and 3</u>:
*If we swap rows in the generator matrix $\boldsymbol {\rm G}$, we arrive at an identical code $\mathcal{C}'$. That is, the codes $\mathcal{C}$ and $\mathcal{C}'$ contain the exact same code words.
*For example, after cyclic row swapping $2 \rightarrow 1,\ 3 \rightarrow 2$, and $1 \rightarrow 3$, one obtains the new matrix
*The first and the last row of the new matrix already comply with the requirements of a systematic code ⇒ matrix ${ \boldsymbol{\rm G}_{\rm sys}}$ must start with a diagonal matrix.
*Replacing row 2 by the modulo 2 sum of rows 2 and 3, we get:
*This systematic code contains exactly the same code words as the codes $\mathcal{C}$ and $\mathcal{C}'$.
'''(4)''' Correct are the <u>solutions 1 and 2</u>:
*Applying the equation $\underline{x}_{\rm sys} = \underline{u} \cdot \boldsymbol{\rm G}_{\rm sys}$ to the above examples, we see that the first two statements are correct, but not the last one.
*Without calculation one comes to the same result, if one considers that
:*the systematic code word $\underline{x}_{\rm sys}$ must start with $\underline{u}$,
:*the code $\mathcal{C}_{\rm sys}$ contains the same code words as the given code $\mathcal{C}$.
*For $\underline{u} = (0, 1, 0)$, the code word is thus $(0, 1, 0, ?, ?, ?)$.
*A comparison with the code table of $\mathcal{C}$ in the information section leads to $\underline{x}_{\rm sys} = (0, 1, 0, 1, 0, 1)$.
'''(5)''' Only <u>statement 1</u> is correct. The statements for $p_{2}$ and $p_{3}$, on the other hand, are exactly reversed.
*With systematic coding, the following relationship exists between the generator matrix and the parity-check matrix:
The mapping between the information words $\underline{u}$ and the code words $\underline{x}$ can be seen in the table. It can be seen that this is not a "systematic code".
By manipulating the generator matrix $\boldsymbol {\rm G}$, identical codes can be constructed from it. This refers to codes with the same code words but different assignments $\underline{u} \rightarrow \underline{x}$.
The following operations are allowed to obtain identical code:
swapping or permuting the rows,
Multiplying all rows by a constant vector not equal to "$\underline{0}$".
Replacing a row with a linear combination between this row and another one.
For the code $\mathcal{C}_{\rm sys}$ sought in subtask (3) it is further required to be systematic ⇒ generator matrix $\boldsymbol{\rm G}_{\rm sys}$.
Number of code words (code size): $|\mathcal{C}| = 2^k \Rightarrow \underline{|C| = 8}$,
minimum Hamming distance (see table): $\underline{d}_{\rm min} \underline{= 3}$.
(2) Correct is $\underline{\rm Yes}$:
According to the singleton bound ⇒ $d_{\rm min} ≤ n - k + 1$. With $n = 6$ and $k = 3$ one obtains $d_{\rm min} ≤ 4$.
It is thus quite possible to construct a $(6, 3)$ block code with larger minimal distance. How such a code looks, was kindly not asked.
The minimum distance of all Hamming codes is $d_{\rm min} = 3$, and only the special case with $n = 3$ and $k = 1$ reaches the limit. In contrast, the maximum reach according to the Singleton bound:
all repetition codes $\rm (RC)$ because $k = 1$ and $d_{\rm min} = n$; this includes the $\rm (3, 1)$ Hamming code, which is known to be identical to $\rm RC\ (3, 1)$,
If we swap rows in the generator matrix $\boldsymbol {\rm G}$, we arrive at an identical code $\mathcal{C}'$. That is, the codes $\mathcal{C}$ and $\mathcal{C}'$ contain the exact same code words.
For example, after cyclic row swapping $2 \rightarrow 1,\ 3 \rightarrow 2$, and $1 \rightarrow 3$, one obtains the new matrix
The first and the last row of the new matrix already comply with the requirements of a systematic code ⇒ matrix ${ \boldsymbol{\rm G}_{\rm sys}}$ must start with a diagonal matrix.
Replacing row 2 by the modulo 2 sum of rows 2 and 3, we get:
This systematic code contains exactly the same code words as the codes $\mathcal{C}$ and $\mathcal{C}'$.
(4) Correct are the solutions 1 and 2:
Applying the equation $\underline{x}_{\rm sys} = \underline{u} \cdot \boldsymbol{\rm G}_{\rm sys}$ to the above examples, we see that the first two statements are correct, but not the last one.
Without calculation one comes to the same result, if one considers that
the systematic code word $\underline{x}_{\rm sys}$ must start with $\underline{u}$,
the code $\mathcal{C}_{\rm sys}$ contains the same code words as the given code $\mathcal{C}$.
For $\underline{u} = (0, 1, 0)$, the code word is thus $(0, 1, 0, ?, ?, ?)$.
A comparison with the code table of $\mathcal{C}$ in the information section leads to $\underline{x}_{\rm sys} = (0, 1, 0, 1, 0, 1)$.
(5) Only statement 1 is correct. The statements for $p_{2}$ and $p_{3}$, on the other hand, are exactly reversed.
With systematic coding, the following relationship exists between the generator matrix and the parity-check matrix:
