Difference between revisions of "Aufgaben:Exercise 1.09: Extended Hamming Code"

From LNTwww
 
(21 intermediate revisions by 6 users not shown)
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_ID2396__KC_A_1_9.png|right|frame|(7, 4) Hamming–Code <br>und (8, 4) Erweiterung]]
+
[[File:EN_KC_A_1_9_neu.png|right|frame|$\text{HC (7, 4)}$&nbsp; (yellow background)  and&nbsp; $\text{(8, 4)}$&nbsp; extension&nbsp; (green background).]]
  
Es sollen zwei Codes miteinander verglichen werden, deren Codetabellen rechts angegeben sind.  
+
Two codes are to be compared,&nbsp; whose code tables are given on the right.  
*Die ersten vier Bit eines jeden Codewortes $\underline{x}$ sind gleich dem jeweiligen Informationswort $\underline{u}$ (schwarze Schrift).  
+
*The first four bits of each code word&nbsp; $\underline{x}$&nbsp; are equal to the respective information word&nbsp; $\underline{u}$&nbsp; (black font).
*Danach folgen $m = n- k$ Prüfbit (rote Schrift).
+
 +
*Then follow&nbsp; $m = n- k$&nbsp; parity bit&nbsp; (red font).
  
  
Der systematische (7, 4)–Hamming–Code wurde bereits in [[Aufgaben:1.6_Zum_(7,_4)–Hamming–Code|Aufgabe 1.6]] sowie [[Aufgaben:1.07_H_und_G_des_(7,_4)–Hamming–Codes|Aufgabe 1.7]] behandelt. Prüfmatrix und Generatormatrix dieses Codes sind wie folgt gegeben:
+
The systematic&nbsp; $\text{(7, 4)}$&nbsp; Hamming code has already been discussed in&nbsp; [[Aufgaben:Exercise_1.6:_(7,_4)_Hamming_Code|"Exercise 1.6"]]&nbsp; and&nbsp; [[Aufgaben:Exercise_1.6:_(7,_4)_Hamming_Code|"Exercise 1.7"]].&nbsp; The parity-check matrix and generator matrix of this code are given as follows:
 
:$${ \boldsymbol{\rm H}}_1 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &0 &1 &1 &0 &0 &1 \end{pmatrix}\hspace{0.05cm},$$
 
:$${ \boldsymbol{\rm H}}_1 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &0 &1 &1 &0 &0 &1 \end{pmatrix}\hspace{0.05cm},$$
  
 
:$${ \boldsymbol{\rm G}}_1 = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &0\\ 0 &0 &1 &0 &0 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm G}}_1 = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1\\ 0 &1 &0 &0 &1 &1 &0\\ 0 &0 &1 &0 &0 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 \end{pmatrix}\hspace{0.05cm}.$$
  
Im weiteren Verlauf der Aufgabe wird dieser (gelb hinterlegte) Code $\mathcal{C}_{1}$ genannt.
+
In the further course of the exercise this&nbsp; (yellow highlighted)&nbsp; code is called&nbsp; $\mathcal{C}_{1}$.
  
 +
The right column in the above table specifies a block code with parameters&nbsp; $n = 8$&nbsp; and&nbsp; $k = 4$,&nbsp; usually referred to in the literature as the&nbsp; "Extended Hamming Code".&nbsp; We refer to this code&nbsp; (highlighted in green)&nbsp; in the following&nbsp; $\mathcal{C}_{2}$&nbsp; and denote its parity-check matrix by&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp; and the corresponding generator matrix by&nbsp; ${ \boldsymbol{\rm G}}_{2}$.
  
Die rechte Spalte in obiger Tabelle gibt einen Blockcode mit den Parametern $n = 8$ und $k = 4$ an, der in der Literatur meist als „erweiteter Hamming–Code” bezeichnet wird. Wir nennen diesen (grün hinterlegten) Code im Folgenden $\mathcal{C}_{2}$ und bezeichnen dessen Prüfmatrix mit ${ \boldsymbol{\rm H}}_{2}$ und die dazugehörige Generatormatrix mit ${ \boldsymbol{\rm G}}_{2}$ .
+
The questions for this exercise are related to
 +
*the&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|"code rate"]],
 +
*the&nbsp; [[Channel_Coding/Objective_of_Channel_Coding#Important_definitions_for_block_coding|"minimum distance"]]&nbsp; between two code words,
 +
*the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_parity-check_matrix|"parity-check matrix"]]&nbsp; and the&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Code_definition_by_the_generator_matrix|"generator matrix"]]&nbsp; of the extended&nbsp; $\text{(8, 4)}$&nbsp; Hamming code.
  
Die Fragen zu dieser Aufgabe beziehen sich auf
 
*die [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|Coderate]],
 
*die [[Kanalcodierung/Zielsetzung_der_Kanalcodierung#Einige_wichtige_Definitionen_zur_Blockcodierung|minimale Distanz]] zwischen zwei Codeworten,
 
*die [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Pr.C3.BCfmatrix|Prüfmatrix]] und die [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Codefestlegung_durch_die_Generatormatrix|Generatormatrix]] des erweiterten (8, 4)–Hamming–Codes.
 
  
  
  
 +
Hints:
  
''Hinweise'' :
+
*This exercise belongs to the chapter&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General Description of Linear Block Codes"]].
  
*Die Aufgabe gehört zum Kapitel [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes|Allgemeine Beschreibung linearer Blockcodes]].
+
*Note in the solution that&nbsp; $\mathcal{C}_{1}$&nbsp; and&nbsp; $\mathcal{C}_{2}$&nbsp; are each&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes#Systematic_Codes|"systematic codes"]].
*Beachten Sie bei der Lösung, dass $\mathcal{C}_{1}$ und $\mathcal{C}_{2}$ jeweils [[Kanalcodierung/Allgemeine_Beschreibung_linearer_Blockcodes#Systematische_Codes|systematische Codes]] sind.  
+
*Die folgende [[Aufgaben:1.09Z_Erweiterung_–_Punktierung|Aufgabe 1.9Z]] behandelt die Erweiterung von Codes in etwas allgemeinerer Form.
+
*The following&nbsp; [[Aufgaben:Exercise_1.09Z:_Extension_and/or_Puncturing|"Exercise 1.9Z"]]&nbsp; deals with the extension of codes in somewhat more general terms.
*Sollte die Eingabe des Zahlenwertes „0” erforderlich sein, so geben Sie bitte „0.” ein.
+
  
  
  
===Fragebogen===
+
===Questions===
  
 
<quiz display=simple>
 
<quiz display=simple>
  
{Geben Sie die Coderaten von $C_{1}$ und $C_{2}$ an.
+
{Specify the code rates of&nbsp; $\mathcal{C}_{1}$&nbsp; and&nbsp; $\mathcal{C}_{2}$.
 
|type="{}"}
 
|type="{}"}
$\C_{1}:   \ \ \ R$ = { 0.571 3% }
+
$\mathcal{C}_{1}\text{:}\hspace{0.4cm}R \ = \ $ { 0.571 3% }
$\C_{2}:   \ \ \ R$ = { 0.5 3% }
+
$\mathcal{C}_{2}\text{:}\hspace{0.4cm}R \ = \ $ { 0.5 3% }
  
  
{Geben Sie die minimalen Distanzen von $C_{1}$ und $C_{2}$ an.
+
{Give the minimum distances of&nbsp; $\mathcal{C}_{1}$&nbsp; and&nbsp; $\mathcal{C}_{2}$.
 
|type="{}"}
 
|type="{}"}
$\C_{1}: \ \  \ d_{\rm min}$ = { 3 3% }
+
$\mathcal{C}_{1}\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $ { 3 }
$\C_{2}: \ \  \ d_{\rm min}$ = { 4 3% }
+
$\mathcal{C}_{2}\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $ { 4 }
  
  
{Welches Format besitzt die Prüfmatrix von $C_{2}$?
+
{What is the format of the parity-check matrix&nbsp; $\boldsymbol{\rm H}_{2}$&nbsp; of&nbsp; $\mathcal{C}_{2}$?
 
|type="{}"}
 
|type="{}"}
$\ { \boldsymbol{\rm H}}_{2}{\rm :}  \ \ \ {\rm Spaltenzahl}$ = { 8 3% }
+
$\text{Number of columns} \ = \ $ { 8 }
$\ { \boldsymbol{\rm H}}_{2}{\rm :}  \ \ \ {\rm  Zeilenzahl}$ = { 4 3% }
+
$\text{Number of rows} \ = \ $   { 4 }
  
{Leiten Sie aus der Codetabelle die Gleichung für das Codebit $x_ {8} (= p_{4})$ ab.
+
{Derive the equation for the code bit &nbsp; $x_ {8} (= p_{4})$ &nbsp; from the code table. Which specification is correct?
|type="[]"}
+
|type="()"}
  
 
- $x_{8} = 0.$
 
- $x_{8} = 0.$
Line 65: Line 67:
 
+ $x_{8} = x_{1}⊕x_{2}⊕x_{3}⊕x_{4}⊕x_{5}⊕x_{6}⊕x_{7}.$
 
+ $x_{8} = x_{1}⊕x_{2}⊕x_{3}⊕x_{4}⊕x_{5}⊕x_{6}⊕x_{7}.$
  
{Welche Aussagen gelten für ${ \boldsymbol{\rm H}}_{2}$? ''Hinweis:'' Richtig sind 3 von 4 Antworten.
+
{Which statements are true for&nbsp; ${ \boldsymbol{\rm H}}_{2}$?&nbsp; Hint: &nbsp;Correct are three out of four answers.
 
|type="[]"}
 
|type="[]"}
  
+ Die erste Zeile lautet:   $1 1 0 1 1 0 0 0$.
+
+ Row 1 reads: &nbsp; $1 1 0 1 1 0 0 0$.
+ Die zweite Zeile lautet: $0 1 1 1 0 1 0 0$.
+
+ Row 2 reads: &nbsp; $0 1 1 1 0 1 0 0$.
- Die dritte Zeile lautet:   $0 0 0 0 1 1 1 1$.
+
- Row 3 reads: &nbsp;  $0 0 0 0 1 1 1 1$.
+ Die letzte Zeile lautet:   $1 1 1 1 1 1 1 1$.
+
+ Row 4 reads: &nbsp;  $1 1 1 1 1 1 1 1$.
  
{Welche Umformung ist für die letzte Zeile von ${ \boldsymbol{\rm H}}_{2}$ zulässig?
+
{Which transformation is allowed for the last row of&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp;?
|type="[]"}
+
|type="()"}
 
- $1 1 1 1 1 1 1 1  →  0 0 0 0 0 0 0 0,$
 
- $1 1 1 1 1 1 1 1  →  0 0 0 0 0 0 0 0,$
 
+ $1 1 1 1 1 1 1 1  →  1 1 1 0 0 0 0 1,$
 
+ $1 1 1 1 1 1 1 1  →  1 1 1 0 0 0 0 1,$
 
- $1 1 1 1 1 1 1 1  →  0 0 1 0 1 0 0 0.$
 
- $1 1 1 1 1 1 1 1  →  0 0 1 0 1 0 0 0.$
  
{Geben Sie die zugehörige Generatormatrix ${ \boldsymbol{\rm G}}_{2}$ an. Welche Aussagen treffen zu?
+
{Give the corresponding generator matrix&nbsp; ${ \boldsymbol{\rm G}}_{2}$.&nbsp; Which statements are true?
 
|type="[]"}
 
|type="[]"}
- ${ \boldsymbol{\rm G}}_{2}$ hat gleiches Format wie die Matrix ${ \boldsymbol{\rm G}}_{1}$ des (7, 4)–Codes.
+
- ${ \boldsymbol{\rm G}}_{2}$&nbsp; has same format as matrix&nbsp; ${ \boldsymbol{\rm G}}_{1}$&nbsp; of the&nbsp; $\text{(7, 4)}$ code.
+ ${ \boldsymbol{\rm G}}_{2}$ beginnt wie ${ \boldsymbol{\rm G}}_{1}$ mit einer Diagonalmatrix ${ \boldsymbol{\rm I}}_{4}$ .
+
+ ${ \boldsymbol{\rm G}}_{2}$&nbsp; starts like ${ \boldsymbol{\rm G}}_{1}$&nbsp; with a diagonal matrix&nbsp; ${ \boldsymbol{\rm I}}_{4}$.
+ ${ \boldsymbol{\rm G}}_{2}$ hat im betrachteten Beispiel das gleiche Format wie ${ \boldsymbol{\rm H}}_{2}$ .
+
+ ${ \boldsymbol{\rm G}}_{2}$&nbsp; in the considered example has the same format as&nbsp; ${ \boldsymbol{\rm H}}_{2}$ .
  
  
Line 92: Line 94:
 
</quiz>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Die entsprechende Gleichung für die Coderate lautet in beiden Fällen $R = k/n:$
+
'''(1)'''&nbsp; The corresponding equation for the code rate in both cases is&nbsp; $R = k/n\text{:}$
*$C_{1} : n = 7, k = 4 ⇒ R = 4/7  \underline {= 0.571},$
+
*$\mathcal{C}_{1} \text{:} \  n = 7, k = 4\ R = 4/7  \underline {= 0.571},$
*$C_{2} : n = 8, k = 4 ⇒ R = 4/8  \underline { =0.5}.$
+
 
 +
*$\mathcal{C}_{2} \text{:} \ n = 8, k = 4 \ \ R = 4/8  \underline { =0.5}.$
 +
 
 +
 
 +
 
 +
'''(2)'''&nbsp; The minimum distance of the&nbsp; $(7, 4, 3)$&nbsp; Hamming code&nbsp; $\mathcal{C}_{1}$&nbsp; is&nbsp; $d_{\rm min} \underline{= 3}$,&nbsp; which can be read from the naming alone.
 +
 
 +
*From the table in the information section,&nbsp; it can be seen that for the extended Hamming code&nbsp; $d_{\rm min} \underline{= 4}$&nbsp; holds.
  
'''(2)'''&nbsp; Die minimale Distanz des (7, 4, 3)–Hamming–Codes $C_{1}$ beträgt $d_{\rm min} \underline{= 3}$, was allein schon aus der Namensgebung ablesbar ist. Aus der Tabelle auf der Angabenseite ist ersichtlich, dass für den erweiterten Hamming–Code $d_{\rm min} \underline{= 4}$ gilt. $C_{2}$ bezeichnet man deshalb in der Literatur auch als einen (8, 4, 4)–Blockcode.
+
* $\mathcal{C}_{2}$&nbsp; is therefore also called  in the literature a&nbsp; $\rm (8, 4, 4)$&nbsp; block code.
  
  
'''(3)'''&nbsp; Die Prüfmatrix ${ \boldsymbol{\rm H}}$ besteht im Allgemeinen aus ''n'' Spalten und $m = n – k$ Zeilen, wobei m die Anzahl der Prüfgleichungen angibt. Beim (7, 4, 3)–Hamming–Code ist ${ \boldsymbol{\rm H}}$ eine 3 × 7–Matrix. Für den erweiterten Hamming–Code ⇒ Code $C_{2}$ gilt demgegenüber $\underline{n = 8}$ (Spaltenzahl) und $\underline{m = 4}$ (Zeilenzahl).
 
  
'''(4)'''&nbsp; Aus der Codetabelle auf der Angabenseite erkennt man, dass allein <u>Antwort 3</u> richtig ist. Das Prüfbit $p_{4}$ ist so zu bestimmen, dass die Modulo–2–Summe über alle Bits des Codewortes den Wert 0 ergibt.
+
'''(3)'''&nbsp; The parity-check matrix&nbsp; ${ \boldsymbol{\rm H}}$&nbsp; generally consists of&nbsp; $n$&nbsp; columns and&nbsp; $m = n - k$ rows,&nbsp; where&nbsp; $m$&nbsp; indicates the number of parity-check equations.  
  
'''(5)'''&nbsp; Anzumerken ist zunächst, dass die Angabe der Prüfmatrix nie eindeutig ist, schon allein deshalb, weil die Reihenfolge der Prüfgleichungen vertauschbar ist. Unter Berücksichtigung des Hinweises, dass nur eine der vorgegebenen Zeilen falsch ist, ist ${ \boldsymbol{\rm H}}_{2}$ allerdings eindeutig bestimmt:
+
*For the&nbsp; $(7, 4, 3)$&nbsp; Hamming code,&nbsp; ${ \boldsymbol{\rm H}}$&nbsp; is a&nbsp; $3 × 7$&nbsp; matrix.
 +
 +
*For the extended Hamming code &nbsp; ⇒ &nbsp;  $\mathcal{C}_{2}$,&nbsp; on the other hand:&nbsp; $\underline{n = 8}$&nbsp; (column number)&nbsp; and&nbsp; $\underline{m = 4}$&nbsp; (row number).
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; From the code table in the information section you can see that only&nbsp; <u>answer 3</u>&nbsp; is correct.
 +
*The parity bit&nbsp; $p_{4}$&nbsp; is to be determined in such a way that the modulo 2 sum over all bits of the code word results in the value&nbsp; $0$.
 +
 
 +
 
 +
 
 +
'''(5)'''&nbsp; It should first be noted that the specification of the parity-check matrix is never unambiguous,&nbsp; if only because the order of the parity-check equations is interchangeable.  
 +
*However,&nbsp; considering that only one of the given rows is wrong,&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp; is uniquely determined:
  
 
:$${ \boldsymbol{\rm H}}_2 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0 &0\\ 0 &1 &1 &1 &0 &1 &0 &0\\ 1 &0 &1 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm H}}_2 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0 &0\\ 0 &1 &1 &1 &0 &1 &0 &0\\ 1 &0 &1 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
  
Richtig sind also die <u>Aussagen 1, 2 und 4</u>. Die Zeilen dieser Prüfmatrix stehen in dieser Reihenfolge für die vier Prüfgleichungen:
+
*Correct are therefore the&nbsp; <u>statements 1, 2 and 4</u>.&nbsp; The rows of this parity-check matrix represent the four parity-check equations in this order:
 +
 
 +
:$$ x_1\oplus  x_2 \oplus x_4 \oplus x_5 = 0 \hspace{0.05cm},$$
 +
:$$x_2 \oplus x_3 \oplus x_4 \oplus x_6 = 0 \hspace{0.05cm},$$
 +
:$$ x_1  \oplus  x_3 \oplus x_4 \oplus x_7 = 0 \hspace{0.05cm},$$
 +
:$$ x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0 \hspace{0.05cm}.$$
 +
 
  
:$$ x_1 \hspace{-0.3cm} \ \oplus \ \hspace{-0.25cm} x_2 \oplus x_4 \oplus x_5 = 0 \hspace{0.05cm},\hspace{0.3cm} x_2 \oplus x_3 \oplus x_4 \oplus x_6 = 0 \hspace{0.05cm},$$
+
'''(6)'''&nbsp;  Correct is&nbsp; <u>answer 2</u>:  
:$$ x_1 \hspace{-0.3cm} \ \oplus \ \hspace{-0.25cm} x_3 \oplus x_4 \oplus x_7 = 0 \hspace{0.05cm},\hspace{0.3cm} x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0 \hspace{0.05cm}.$$
+
*This result is obtained by replacing the last row with the modulo 2 sum over all four rows,&nbsp; which is allowed.
 +
 +
*Proposition 1 does not represent a parity-check equation.
 +
 +
*Proposal 3 represents the parity-check equation&nbsp; $x_{3}⊕x_{5} = 0$,&nbsp; which also does not correspond to the facts.
  
'''(6)'''&nbsp;  Richtig ist <u>Antwort 2</u>: Zu diesem Ergebnis kommt man, wenn man die letzte Zeile durch die Modulo–2–Summe über alle vier Zeilen ersetzt, was erlaubt ist. Der Vorschlag 1 stellt keine Prüfgleichung dar. Der Vorschlag 3 steht für die Prüfgleichung $x_{3}⊕x_{5} = 0$, was auch nicht den Gegebenheiten entspricht.
 
  
Entsprechend dem richtigen Lösungsvorschlag 2 wird dagegen die Prüfgleichung
+
According to the correct solution suggestion 2,&nbsp; on the other hand,&nbsp; the parity-check equation becomes
 
:$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0$$
 
:$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0$$
durch folgende neue Prüfgleichung ersetzt:
+
:is replaced by the following new parity-check equation:
 
:$$x_1 \oplus x_2 \oplus x_3 \oplus x_8 = 0 \hspace{0.05cm}.$$
 
:$$x_1 \oplus x_2 \oplus x_3 \oplus x_8 = 0 \hspace{0.05cm}.$$
Die modifizierte Prüfmatrix lautet nun:
+
*The modified parity-check matrix is now:
 
:$${ \boldsymbol{\rm H}}_2 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0 &0\\ 0 &1 &1 &1 &0 &1 &0 &0\\ 1 &0 &1 &1 &0 &0 &1 &0\\ 1 &1 &1 &0 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm H}}_2 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0 &0\\ 0 &1 &1 &1 &0 &1 &0 &0\\ 1 &0 &1 &1 &0 &0 &1 &0\\ 1 &1 &1 &0 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$
  
  
'''(7)'''&nbsp;  Nach dieser Matrixmanipulation liegt ${ \boldsymbol{\rm H}}_{2}$ in der für systematische Codes typischen Form vor:
+
'''(7)'''&nbsp;  After this matrix manipulation,&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp; is in the form typical for systematic codes:
  
 
:$${ \boldsymbol{\rm H}}_2 =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_m \right)\hspace{0.3cm} \Rightarrow\hspace{0.3cm} m = 4 {\rm :}\hspace{0.3cm}{ \boldsymbol{\rm H}}_2 =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_4 \right) \hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm H}}_2 =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_m \right)\hspace{0.3cm} \Rightarrow\hspace{0.3cm} m = 4 {\rm :}\hspace{0.3cm}{ \boldsymbol{\rm H}}_2 =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_4 \right) \hspace{0.05cm}.$$
  
Damit lautet die Generatormatrix:
+
*Thus,&nbsp; the generator matrix is:
 
:$${ \boldsymbol{\rm G_{2}}} =\left({ \boldsymbol{\rm I}}_4 \: ; \: { \boldsymbol{\rm P}}\right) = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 &1\\ 0 &1 &0 &0 &1 &1 &0 &1\\ 0 &0 &1 &0 &0 &1 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$
 
:$${ \boldsymbol{\rm G_{2}}} =\left({ \boldsymbol{\rm I}}_4 \: ; \: { \boldsymbol{\rm P}}\right) = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 &1\\ 0 &1 &0 &0 &1 &1 &0 &1\\ 0 &0 &1 &0 &0 &1 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$
  
Richtig sind also die <u>Aussagen 2 und 3</u>. ${ \boldsymbol{\rm G}}_{2}$ beginnt wie ${ \boldsymbol{\rm G}}_{1}$ (siehe Angabenblatt) mit einer Diagonalmatrix ${ \boldsymbol{\rm I}}_{4}$ , hat aber im Gegensatz zu ${ \boldsymbol{\rm G}}_{1}$ nun 8 Spalten. Im vorliegenden Fall $n = 8, k = 4 ⇒ m = 4$ sind sowohl ${ \boldsymbol{\rm G}}_{2}$ als auch ${ \boldsymbol{\rm H}}_{2}$ jeweils 4×8–Matrizen.
+
So the&nbsp; <u>statements 2 and 3</u>&nbsp; are correct:
 +
* ${ \boldsymbol{\rm G}}_{2}$&nbsp; starts like&nbsp; ${ \boldsymbol{\rm G}}_{1}$&nbsp; $($see specification sheet$)$&nbsp; with a diagonal matrix&nbsp; ${ \boldsymbol{\rm I}}_{4}$,&nbsp; but unlike&nbsp; ${ \boldsymbol{\rm G}}_{1}$&nbsp; now has 8 columns.
 +
 +
*In the present case&nbsp; $n = 8, k = 4 \ \ m = 4$&nbsp; both&nbsp; ${ \boldsymbol{\rm G}}_{2}$&nbsp; and&nbsp; ${ \boldsymbol{\rm H}}_{2}$&nbsp; are&nbsp; $4×8$&nbsp; matrices respectively.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  
  
  
[[Category:Aufgaben zu  Kanalcodierung|^1.4 Beschreibung linearer Blockcodes
+
[[Category:Channel Coding: Exercises|^1.4 Linear Block Code Description
  
 
^]]
 
^]]

Latest revision as of 17:01, 23 January 2023

$\text{HC (7, 4)}$  (yellow background) and  $\text{(8, 4)}$  extension  (green background).

Two codes are to be compared,  whose code tables are given on the right.

  • The first four bits of each code word  $\underline{x}$  are equal to the respective information word  $\underline{u}$  (black font).
  • Then follow  $m = n- k$  parity bit  (red font).


The systematic  $\text{(7, 4)}$  Hamming code has already been discussed in  "Exercise 1.6"  and  "Exercise 1.7".  The parity-check matrix and generator matrix of this code are given as follows:

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

In the further course of the exercise this  (yellow highlighted)  code is called  $\mathcal{C}_{1}$.

The right column in the above table specifies a block code with parameters  $n = 8$  and  $k = 4$,  usually referred to in the literature as the  "Extended Hamming Code".  We refer to this code  (highlighted in green)  in the following  $\mathcal{C}_{2}$  and denote its parity-check matrix by  ${ \boldsymbol{\rm H}}_{2}$  and the corresponding generator matrix by  ${ \boldsymbol{\rm G}}_{2}$.

The questions for this exercise are related to



Hints:

  • Note in the solution that  $\mathcal{C}_{1}$  and  $\mathcal{C}_{2}$  are each  "systematic codes".
  • The following  "Exercise 1.9Z"  deals with the extension of codes in somewhat more general terms.



Questions

1

Specify the code rates of  $\mathcal{C}_{1}$  and  $\mathcal{C}_{2}$.

$\mathcal{C}_{1}\text{:}\hspace{0.4cm}R \ = \ $

$\mathcal{C}_{2}\text{:}\hspace{0.4cm}R \ = \ $

2

Give the minimum distances of  $\mathcal{C}_{1}$  and  $\mathcal{C}_{2}$.

$\mathcal{C}_{1}\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $

$\mathcal{C}_{2}\text{:}\hspace{0.4cm}d_{\rm min} \ = \ $

3

What is the format of the parity-check matrix  $\boldsymbol{\rm H}_{2}$  of  $\mathcal{C}_{2}$?

$\text{Number of columns} \ = \ $

$\text{Number of rows} \ = \ $

4

Derive the equation for the code bit   $x_ {8} (= p_{4})$   from the code table. Which specification is correct?

$x_{8} = 0.$
$x_{8} = x_{1}⊕x_{2}⊕x_{4}⊕x_{5}.$
$x_{8} = x_{1}⊕x_{2}⊕x_{3}⊕x_{4}⊕x_{5}⊕x_{6}⊕x_{7}.$

5

Which statements are true for  ${ \boldsymbol{\rm H}}_{2}$?  Hint:  Correct are three out of four answers.

Row 1 reads:   $1 1 0 1 1 0 0 0$.
Row 2 reads:   $0 1 1 1 0 1 0 0$.
Row 3 reads:   $0 0 0 0 1 1 1 1$.
Row 4 reads:   $1 1 1 1 1 1 1 1$.

6

Which transformation is allowed for the last row of  ${ \boldsymbol{\rm H}}_{2}$ ?

$1 1 1 1 1 1 1 1 → 0 0 0 0 0 0 0 0,$
$1 1 1 1 1 1 1 1 → 1 1 1 0 0 0 0 1,$
$1 1 1 1 1 1 1 1 → 0 0 1 0 1 0 0 0.$

7

Give the corresponding generator matrix  ${ \boldsymbol{\rm G}}_{2}$.  Which statements are true?

${ \boldsymbol{\rm G}}_{2}$  has same format as matrix  ${ \boldsymbol{\rm G}}_{1}$  of the  $\text{(7, 4)}$ code.
${ \boldsymbol{\rm G}}_{2}$  starts like ${ \boldsymbol{\rm G}}_{1}$  with a diagonal matrix  ${ \boldsymbol{\rm I}}_{4}$.
${ \boldsymbol{\rm G}}_{2}$  in the considered example has the same format as  ${ \boldsymbol{\rm H}}_{2}$ .


Solution

(1)  The corresponding equation for the code rate in both cases is  $R = k/n\text{:}$

  • $\mathcal{C}_{1} \text{:} \ n = 7, k = 4\ ⇒ \ R = 4/7 \underline {= 0.571},$
  • $\mathcal{C}_{2} \text{:} \ n = 8, k = 4 \ ⇒ \ R = 4/8 \underline { =0.5}.$


(2)  The minimum distance of the  $(7, 4, 3)$  Hamming code  $\mathcal{C}_{1}$  is  $d_{\rm min} \underline{= 3}$,  which can be read from the naming alone.

  • From the table in the information section,  it can be seen that for the extended Hamming code  $d_{\rm min} \underline{= 4}$  holds.
  • $\mathcal{C}_{2}$  is therefore also called in the literature a  $\rm (8, 4, 4)$  block code.


(3)  The parity-check matrix  ${ \boldsymbol{\rm H}}$  generally consists of  $n$  columns and  $m = n - k$ rows,  where  $m$  indicates the number of parity-check equations.

  • For the  $(7, 4, 3)$  Hamming code,  ${ \boldsymbol{\rm H}}$  is a  $3 × 7$  matrix.
  • For the extended Hamming code   ⇒   $\mathcal{C}_{2}$,  on the other hand:  $\underline{n = 8}$  (column number)  and  $\underline{m = 4}$  (row number).


(4)  From the code table in the information section you can see that only  answer 3  is correct.

  • The parity bit  $p_{4}$  is to be determined in such a way that the modulo 2 sum over all bits of the code word results in the value  $0$.


(5)  It should first be noted that the specification of the parity-check matrix is never unambiguous,  if only because the order of the parity-check equations is interchangeable.

  • However,  considering that only one of the given rows is wrong,  ${ \boldsymbol{\rm H}}_{2}$  is uniquely determined:
$${ \boldsymbol{\rm H}}_2 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0 &0\\ 0 &1 &1 &1 &0 &1 &0 &0\\ 1 &0 &1 &1 &0 &0 &1 &0\\ 1 &1 &1 &1 &1 &1 &1 &1 \end{pmatrix} \hspace{0.05cm}.$$
  • Correct are therefore the  statements 1, 2 and 4.  The rows of this parity-check matrix represent the four parity-check equations in this order:
$$ x_1\oplus x_2 \oplus x_4 \oplus x_5 = 0 \hspace{0.05cm},$$
$$x_2 \oplus x_3 \oplus x_4 \oplus x_6 = 0 \hspace{0.05cm},$$
$$ x_1 \oplus x_3 \oplus x_4 \oplus x_7 = 0 \hspace{0.05cm},$$
$$ x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0 \hspace{0.05cm}.$$


(6)  Correct is  answer 2:

  • This result is obtained by replacing the last row with the modulo 2 sum over all four rows,  which is allowed.
  • Proposition 1 does not represent a parity-check equation.
  • Proposal 3 represents the parity-check equation  $x_{3}⊕x_{5} = 0$,  which also does not correspond to the facts.


According to the correct solution suggestion 2,  on the other hand,  the parity-check equation becomes

$$x_1 \oplus x_2 \oplus x_3 \oplus x_4 \oplus x_5 \oplus x_6 \oplus x_7 \oplus x_8 = 0$$
is replaced by the following new parity-check equation:
$$x_1 \oplus x_2 \oplus x_3 \oplus x_8 = 0 \hspace{0.05cm}.$$
  • The modified parity-check matrix is now:
$${ \boldsymbol{\rm H}}_2 = \begin{pmatrix} 1 &1 &0 &1 &1 &0 &0 &0\\ 0 &1 &1 &1 &0 &1 &0 &0\\ 1 &0 &1 &1 &0 &0 &1 &0\\ 1 &1 &1 &0 &0 &0 &0 &1 \end{pmatrix} \hspace{0.05cm}.$$


(7)  After this matrix manipulation,  ${ \boldsymbol{\rm H}}_{2}$  is in the form typical for systematic codes:

$${ \boldsymbol{\rm H}}_2 =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_m \right)\hspace{0.3cm} \Rightarrow\hspace{0.3cm} m = 4 {\rm :}\hspace{0.3cm}{ \boldsymbol{\rm H}}_2 =\left({ \boldsymbol{\rm P}}^{\rm T} \: ; \: { \boldsymbol{\rm I}}_4 \right) \hspace{0.05cm}.$$
  • Thus,  the generator matrix is:
$${ \boldsymbol{\rm G_{2}}} =\left({ \boldsymbol{\rm I}}_4 \: ; \: { \boldsymbol{\rm P}}\right) = \begin{pmatrix} 1 &0 &0 &0 &1 &0 &1 &1\\ 0 &1 &0 &0 &1 &1 &0 &1\\ 0 &0 &1 &0 &0 &1 &1 &1\\ 0 &0 &0 &1 &1 &1 &1 &0 \end{pmatrix} \hspace{0.05cm}.$$

So the  statements 2 and 3  are correct:

  • ${ \boldsymbol{\rm G}}_{2}$  starts like  ${ \boldsymbol{\rm G}}_{1}$  $($see specification sheet$)$  with a diagonal matrix  ${ \boldsymbol{\rm I}}_{4}$,  but unlike  ${ \boldsymbol{\rm G}}_{1}$  now has 8 columns.
  • In the present case  $n = 8, k = 4 \ ⇒ \ m = 4$  both  ${ \boldsymbol{\rm G}}_{2}$  and  ${ \boldsymbol{\rm H}}_{2}$  are  $4×8$  matrices respectively.