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

From LNTwww
Line 11: Line 11:
 
:$${ \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  [[Channel_Coding/Decodierung_linearer_Blockcodes#Prinzip_der_Syndromdecodierung|Syndromdecodierung]]  bildet man aus dem Empfangsvektor  $\underline{y}$  das Syndrom  $\underline{s}$  entsprechend der Gleichung
+
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.  
+
With this result, any single error in the codeword can be corrected in the Hamming code under consideration.  
−
*Im fehlerfreien Fall gilt  $\underline{s} = \underline{s}_{0} = (0, 0, 0)$.  
+
*In the error-free case  $\underline{s} = \underline{s}_{0} = (0, 0, 0)$.  
−
*Aber auch bei drei Übertragungsfehlern kann sich unter Umständen  $\underline{s}_{0} = (0, 0, 0)$  ergeben, so dass diese Fehler unerkannt bleiben.
+
*But even three transmission errors may result in  $\underline{s}_{0} = (0, 0, 0)$ , so these errors remain undetected.
  
  
Line 25: Line 25:
  
  
−
''Hinweise:''
+
Hints:
−
* Die Aufgabe gehört zum Kapitel  [[Channel_Coding/Decodierung_linearer_Blockcodes|Decodierung linearer Blockcodes]].  
+
* The exercise belongs to the chapter  [[Channel_Coding/Decoding_of_Linear_Block_Codes|Decoding of Linear Block Codes]].  
−
* Weitere Informationen zur Syndromdecodierung finden Sie im Angabenblatt zur  [[Aufgaben:1.11_Syndromdecodierung|Aufgabe 1.11]].  
+
* For more information on syndrome decoding, see the specification sheet for  [[Aufgaben:Exercise_1.11:_Syndrome_Decoding|Exercise 1.11]].  
−
* Die Grafik verdeutlicht die drei Prüfgleichungen entsprechend der Prüfmatrix:
+
* The graph illustrates the three parity-check equations corresponding to the parity-check matrix:
−
**erste Zeile: rote Gruppierung,
+
**first row: red circle,
−
**zweite Zeile: grüne Gruppierung,
+
**second row: green circle,
−
**dritte Zeile: blaue Gruppierung.
+
**third row: blue circle.
  
  
  
  
−
===Fragebogen===
+
===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&nbsp; $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$. Ist dies ein gültiges Codewort?
+
{Received&nbsp; $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$. Is this a valid codeword?
 
|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),$
Line 54: Line 54:
 
- $\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 '''(3)'''?
 
|type="[]"}
 
|type="[]"}
 
-  $\underline{y} = (1, 1, 0, 1, 0, 1, 0),$
 
-  $\underline{y} = (1, 1, 0, 1, 0, 1, 0),$
Line 61: Line 61:
 
</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:
+
'''(1)'''&nbsp; The answer is <u>YES</u>, as can be seen from the given parity-check matrix $\mathbf{H}$:
−
*Diese beinhaltet am Ende eine $3×3$–Diagonalmatrix.  
+
*This contains a $3×3$ diagonal matrix at the end.  
−
*Die Codeworte lauten demzufolge:
+
*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}.$$
Line 71: Line 71:
  
  
−
'''(2)'''&nbsp; Mit diesem Empfangsvektor $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$ werden alle Prüfgleichungen erfüllt:
+
'''(2)'''&nbsp; 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_1 \oplus u_2 \oplus u_4 \oplus p_1 = 1 \oplus 0 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
Line 77: Line 77:
 
:$$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, the correct answer is <u>YES</u>.
  
  
  
−
'''(3)'''&nbsp;  Es gilt $\underline{s} = \underline{y} · \boldsymbol{\rm H}^{\rm T}$:
+
'''(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 Antwort \hspace{0.15cm}1} \hspace{0.05cm}.$$
 
:$$ \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}.$$
Line 87: Line 87:
  
  
−
'''(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:
+
'''(4)'''&nbsp; 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)$ 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)$.
+
*$\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)$.
  
−
*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:
+
*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_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 1 \oplus 0 = 0 \hspace{0.05cm},$$
Line 97: Line 97:
 
:$$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 sieben Bitpositionen unterscheidet:
+
*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_1 \oplus u_2 \oplus u_4 \oplus p_1 = 0 \oplus 1 \oplus 0 \oplus 1 = 0 \hspace{0.05cm},$$
Line 103: Line 103:
 
:$$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 <u>answers 2 and 3</u>.
  
 
{{ML-Fuß}}
 
{{ML-Fuß}}

Revision as of 17:26, 14 July 2022

Diagram: Parity-check equations

The same constellation is considered as in  Exercise 1.11, namely 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 polynomial 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 codeword 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:

  • The exercise belongs to the chapter  Decoding of Linear Block Codes.
  • 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

Received  $\underline{y} = (1, 0, 0, 1, 0, 1, 0)$. Is this a valid codeword?

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

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 Antwort \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.

Retrieved from "http://en.lntwww.de/index.php?title=Aufgaben:Exercise_1.11Z:_Syndrome_Decoding_again&oldid=48167"
  • Powered by MediaWiki