Difference between revisions of "Aufgaben:Exercise 1.11Z: Syndrome Decoding again"

From LNTwww
 
(14 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{quiz-Header|Buchseite=Kanalcodierung/Decodierung linearer Blockcodes}}
+
{{quiz-Header|Buchseite=Channel_Coding/Decoding_of_Linear_Block_Codes}}
  
[[File:P_ID2399__KC_Z_1_10.png|right|frame|Schaubild der Prüfgleichungen]]
+
[[File:P_ID2399__KC_Z_1_10.png|right|frame|Parity-check chart]]
  
Betrachtet wird die gleiche Konstellation wie in der [[Aufgaben:1.11_Syndromdecodierung|Aufgabe 1.11]], nämlich die Decodierung eines $(7, 4, 3)$–Hamming–Codes mit der Prüfmatrix
+
The same constellation is considered as in  [[Aufgaben:Exercise_1.11:_Syndrome_Decoding|"Exercise 1.11"]]:  The decoding of a  $(7, 4, 3)$  Hamming code with the parity-check matrix
  
 
:$${ \boldsymbol{\rm H}}_{\rm } = \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}}_{\rm } = \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}.$$
  
Dementsprechend lautet das Generatorpolynom:
+
Accordingly,  the generator matrix is:
  
 
:$${ \boldsymbol{\rm G}} = \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}} = \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}.$$
  
Bei der [[Kanalcodierung/Decodierung_linearer_Blockcodes#Prinzip_der_Syndromdecodierung|Syndromdecodierung]] bildet man aus dem Empfangsvektor $\underline{y}$ das Syndrom $\underline{s}$:
+
In  [[Channel_Coding/Decoding_of_Linear_Block_Codes#Principle_of_syndrome_decoding|"syndrome decoding"]]  one forms from the received vector  $\underline{y}$  the syndrome  $\underline{s}$  according to the equation
  
 
:$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}.$$
 
:$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}.$$
  
Mit diesem Ergebnis lässt sich beim betrachteten Hamming–Code ein jeder Einzelfehler im Codewort korrigieren. Im fehlerfreien Fall gilt $\underline{s} = \underline{s}_{0} = (0, 0, 0)$. Aber auch bei 3 Übertragungsfehlern kann sich unter Umständen $\underline{s}_{0} = (0, 0, 0)$ ergeben, so dass diese Fehler unerkannt bleiben.
+
With this result,  any single error in the code word can be corrected in the Hamming code under consideration.  
 +
*In the error-free case  $\underline{s} = \underline{s}_{0} = (0, 0, 0)$.
 +
 +
*But even three transmission errors may result in  $\underline{s}_{0} = (0, 0, 0)$,  so these errors remain undetected.
  
''Hinweise:''
 
* Die Aufgabe bezieht sich auf die im Kapitel [[Kanalcodierung/Decodierung_linearer_Blockcodes|Decodierung linearer Blockcodes]] behandelte Thematik.
 
* Weitere Informationen zur Syndromdecodierung finden Sie im Angabenblatt zur [[Aufgaben:1.11_Syndromdecodierung|Aufgabe 1.11]].
 
* Die Grafik verdeutlicht die drei Prüfgleichungen entsprechend der Prüfmatrix:
 
**erste Zeile: rote Gruppierung,
 
**zweite Zeile: grüne Gruppierung,
 
**dritte Zeile: blaue Gruppierung.
 
  
  
  
  
===Fragebogen===
+
 
 +
 
 +
Hints:
 +
* The exercise belongs to the chapter  [[Channel_Coding/Decoding_of_Linear_Block_Codes|"Decoding of Linear Block Codes"]].
 +
 
 +
* For more information on syndrome decoding,  see the specification sheet for  [[Aufgaben:Exercise_1.11:_Syndrome_Decoding|"Exercise 1.11"]].
 +
 +
* The graph illustrates the three parity-check equations corresponding to the parity-check matrix:
 +
**first row:   red circle,
 +
**second row:   green circle,
 +
**third row:   blue circle.
 +
 
 +
 
 +
 
 +
 
 +
===Questions===
 
<quiz display=simple>
 
<quiz display=simple>
{Handelt es sich um einen systematischen Code?
+
{Is it a systematic code?
|type="[]"}
+
|type="()"}
+ Ja,
+
+ Yes,
- Nein.
+
- No.
  
{Empfangen wurde $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$. Ist dies ein gültiges Codewort?
+
{With received vector&nbsp; $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$.&nbsp; Is this a valid code word?
|type="[]"}
+
|type="()"}
+ Ja,
+
+ Yes,
- Nein.
+
- No.
  
{Welches Syndrom ergibt sich mit diesem Empfangswort?
+
{What syndrome results with this received word?
|type="[]"}
+
|type="()"}
 
+ $\underline{s} = \underline{s}_{0} = (0, 0, 0),$
 
+ $\underline{s} = \underline{s}_{0} = (0, 0, 0),$
 
- $\underline{s} = \underline{s}_{3} = (0, 1, 1),$
 
- $\underline{s} = \underline{s}_{3} = (0, 1, 1),$
 
- $\underline{s} = \underline{s}_{7} = (1, 1, 1).$
 
- $\underline{s} = \underline{s}_{7} = (1, 1, 1).$
  
{Welche Empfangsworte führen zum gleichen Syndrom wie in Teilaufgabe (3)?
+
{Which received words lead to the same syndrome as in subtask&nbsp; '''(3)'''?
 
|type="[]"}
 
|type="[]"}
 
-  $\underline{y} = (1, 1, 0, 1, 0, 1, 0),$
 
-  $\underline{y} = (1, 1, 0, 1, 0, 1, 0),$
Line 53: Line 64:
 
</quiz>
 
</quiz>
  
===Musterlösung===
+
===Solution===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
'''(1)'''&nbsp; Die Antwort ist <u>JA</u>, wie man aus der vorgegebenen Prüfmatrix $\mathbf{H}$ erkennt. Diese beinhaltet am Ende eine $3×3$–Diagonalmatrix. Die Codeworte lauten demzufolge:
+
'''(1)'''&nbsp; The answer is&nbsp; <u>YES</u>,&nbsp; as can be seen from the given parity-check matrix&nbsp; $\mathbf{H}$:
 +
*This contains a&nbsp; $3×3$&nbsp; diagonal matrix at the end.  
 +
*The code words are therefore:
  
 
:$$ \underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6, x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_{3}) \hspace{0.05cm}.$$
 
:$$ \underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6, x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_{3}) \hspace{0.05cm}.$$
  
  
'''(2)'''&nbsp; Mit diesem Empfangsvektor $y$ werden alle Prüfgleichungen erfüllt:
+
 
 +
'''(2)'''&nbsp; With this received vector&nbsp; $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$,&nbsp; all parity-check equations are satisfied:
  
 
:$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
 
:$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
Line 66: Line 80:
 
:$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm}.$$
 
:$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm}.$$
  
Richtig ist dementsprechend die Antwort <u>JA</u>.
+
Accordingly,&nbsp; the correct answer is&nbsp; <u>YES</u>.
  
  
'''(3)'''&nbsp;  Es gilt $\underline{s} = \underline{y} · \boldsymbol{\rm H}^{\rm T}$:
 
  
:$$ \underline{s} = \begin{pmatrix} 1 &0 &0 &1 &0 &1 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &1\\ 1 &1 &0\\ 0 &1 &1\\ 1 &1 &1\\ 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} = \begin{pmatrix} 0 &0 &0 \end{pmatrix} = \underline{s}_0 \hspace{0.2cm} \Rightarrow\hspace{0.2cm} \hspace{0.15cm} \underline{ \rm Antwort \hspace{0.15cm}1} \hspace{0.05cm}.$$
+
'''(3)'''&nbsp;  It holds $\underline{s} = \underline{y} · \boldsymbol{\rm H}^{\rm T}$:
  
 +
:$$ \underline{s} = \begin{pmatrix} 1 &0 &0 &1 &0 &1 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &1\\ 1 &1 &0\\ 0 &1 &1\\ 1 &1 &1\\ 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} = \begin{pmatrix} 0 &0 &0 \end{pmatrix} = \underline{s}_0 \hspace{0.2cm} \Rightarrow\hspace{0.2cm} \hspace{0.15cm} \underline{ \rm Answer \hspace{0.15cm}1} \hspace{0.05cm}.$$
  
'''(4)'''&nbsp; Man könnte nun für jedes $\underline{y}$ die Gleichung $\underline{y} · \boldsymbol{\rm H}^{\rm T} = (0, 0, 0)$ überprüfen. Hier soll nun das Ergebnis auf anderem Wege gewonnen werden:
 
  
*$\underline{y}= (1, 1, 0, 1, 0, 1, 0)$ unterscheidet sich von $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$ im Bit $u_{2}$, das nur in den beiden ersten Prüfgleichungen verwendet wird, nicht jedoch in der letzten  ⇒  $\underline{s} = \underline{s}_{6} = (1, 1, 0)$.
 
  
*Wendet man die Prüfgleichungen auf $\underline{y} = (0, 1, 0, 1, 0, 0, 1)$ an, so erhält man $\underline{s} = \underline{s}_{0} = (0, 0, 0)$, wie die folgende Rechnung belegt:
+
'''(4)'''&nbsp; One could now for each&nbsp; $\underline{y}$&nbsp; check the equation&nbsp; $\underline{y} · \boldsymbol{\rm H}^{\rm T} = (0, 0, 0)$.&nbsp; Now here the result shall be obtained in a different way:
 +
 
 +
*$\underline{y}= (1, 1, 0, 1, 0, 1, 0)$&nbsp; differs from&nbsp; $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$&nbsp; in bit&nbsp; $u_{2}$,&nbsp; which is used only in the first two parity-check equations,&nbsp; but not in the last  ⇒  $\underline{s} = \underline{s}_{6} = (1, 1, 0)$.
 +
 
 +
*Applying the parity-check equations to&nbsp;  $\underline{y} = (0, 1, 0, 1, 0, 0, 1)$,&nbsp; we obtain $\underline{s} = \underline{s}_{0} = (0, 0, 0)$, as evidenced by the following calculation:
  
 
:$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
 
:$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
Line 84: Line 100:
 
:$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \hspace{0.05cm}.$$
 
:$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \hspace{0.05cm}.$$
  
*Zum gleichen Ergebnis kommt man mit dem Empfangsvektor $\underline{y} = (0, 1, 1, 0, 1, 0, 1),$ der sich vom Vektor $(1, 0, 0, 1, 0, 1, 0)$ in allen 7 Bitpositionen unterscheidet:
+
*The same result is obtained with the received vector&nbsp; $\underline{y} = (0, 1, 1, 0, 1, 0, 1),$&nbsp; which differs from the vector&nbsp; $(1, 0, 0, 1, 0, 1, 0)$&nbsp; in all seven bit positions:
  
 
:$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm},$$
 
:$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm},$$
Line 90: Line 106:
 
:$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm}.$$
 
:$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm}.$$
  
Richtig sind also die <u>Antworten 2 und 3</u>.
+
So the correct answers are&nbsp; <u>answers 2 and 3</u>.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}
Line 96: Line 112:
  
  
[[Category:Aufgaben zu  Kanalcodierung|^1.5 Decodierung linearer Blockcodes
+
[[Category:Channel Coding: Exercises|^1.5 Linear Block Code Decoding^]]
 
 
 
 
^]]
 

Latest revision as of 12:24, 20 July 2022

Parity-check chart

The same constellation is considered as in  "Exercise 1.11":  The decoding of a  $(7, 4, 3)$  Hamming code with the parity-check matrix

$${ \boldsymbol{\rm H}}_{\rm } = \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}.$$

Accordingly,  the generator matrix is:

$${ \boldsymbol{\rm G}} = \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  "syndrome decoding"  one forms from the received vector  $\underline{y}$  the syndrome  $\underline{s}$  according to the equation

$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m) \hspace{0.05cm}.$$

With this result,  any single error in the code word can be corrected in the Hamming code under consideration.

  • In the error-free case  $\underline{s} = \underline{s}_{0} = (0, 0, 0)$.
  • But even three transmission errors may result in  $\underline{s}_{0} = (0, 0, 0)$,  so these errors remain undetected.




Hints:

  • For more information on syndrome decoding,  see the specification sheet for  "Exercise 1.11".
  • The graph illustrates the three parity-check equations corresponding to the parity-check matrix:
    • first row:   red circle,
    • second row:   green circle,
    • third row:   blue circle.



Questions

1

Is it a systematic code?

Yes,
No.

2

With received vector  $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$.  Is this a valid code word?

Yes,
No.

3

What syndrome results with this received word?

$\underline{s} = \underline{s}_{0} = (0, 0, 0),$
$\underline{s} = \underline{s}_{3} = (0, 1, 1),$
$\underline{s} = \underline{s}_{7} = (1, 1, 1).$

4

Which received words lead to the same syndrome as in subtask  (3)?

$\underline{y} = (1, 1, 0, 1, 0, 1, 0),$
$\underline{y} = (0, 1, 0, 1, 0, 0, 1),$
$\underline{y} = (0, 1, 1, 0, 1, 0, 1).$


Solution

(1)  The answer is  YES,  as can be seen from the given parity-check matrix  $\mathbf{H}$:

  • This contains a  $3×3$  diagonal matrix at the end.
  • The code words are therefore:
$$ \underline{x} = ( x_1, x_2, x_3, x_4, x_5, x_6, x_7) = ( u_1, u_2, u_3, u_4, p_1, p_2, p_{3}) \hspace{0.05cm}.$$


(2)  With this received vector  $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$,  all parity-check equations are satisfied:

$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
$$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \hspace{0.05cm},$$
$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm}.$$

Accordingly,  the correct answer is  YES.


(3)  It holds $\underline{s} = \underline{y} · \boldsymbol{\rm H}^{\rm T}$:

$$ \underline{s} = \begin{pmatrix} 1 &0 &0 &1 &0 &1 &0 \end{pmatrix} \cdot \begin{pmatrix} 1 &0 &1\\ 1 &1 &0\\ 0 &1 &1\\ 1 &1 &1\\ 1 &0 &0\\ 0 &1 &0\\ 0 &0 &1 \end{pmatrix} = \begin{pmatrix} 0 &0 &0 \end{pmatrix} = \underline{s}_0 \hspace{0.2cm} \Rightarrow\hspace{0.2cm} \hspace{0.15cm} \underline{ \rm Answer \hspace{0.15cm}1} \hspace{0.05cm}.$$


(4)  One could now for each  $\underline{y}$  check the equation  $\underline{y} · \boldsymbol{\rm H}^{\rm T} = (0, 0, 0)$.  Now here the result shall be obtained in a different way:

  • $\underline{y}= (1, 1, 0, 1, 0, 1, 0)$  differs from  $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$  in bit  $u_{2}$,  which is used only in the first two parity-check equations,  but not in the last ⇒ $\underline{s} = \underline{s}_{6} = (1, 1, 0)$.
  • Applying the parity-check equations to  $\underline{y} = (0, 1, 0, 1, 0, 0, 1)$,  we obtain $\underline{s} = \underline{s}_{0} = (0, 0, 0)$, as evidenced by the following calculation:
$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
$$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 0 \oplus 1 \oplus 1 = 0 \hspace{0.05cm}.$$
  • The same result is obtained with the received vector  $\underline{y} = (0, 1, 1, 0, 1, 0, 1),$  which differs from the vector  $(1, 0, 0, 1, 0, 1, 0)$  in all seven bit positions:
$$u_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm},$$
$$u_2 \oplus u_3 \oplus u_4 \oplus p_2 = 1 \oplus 1 \oplus 0 \oplus 0 = 0 \hspace{0.05cm},$$
$$u_1 \oplus u_3 \oplus u_4 \oplus p_3 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm}.$$

So the correct answers are  answers 2 and 3.