Aufgaben:Exercise 4.7Z: Principle of Syndrome Decoding - Revision history

Guenter at 14:53, 22 December 2022

2022-12-22T14:53:56Z

Guenter at 11:44, 21 December 2022

2022-12-21T11:44:58Z

Guenter at 11:41, 21 December 2022

2022-12-21T11:41:27Z

Guenter at 16:31, 8 December 2022

2022-12-08T16:31:18Z

Guenter at 16:12, 8 December 2022

2022-12-08T16:12:49Z

Guenter at 15:53, 8 December 2022

2022-12-08T15:53:07Z

Guenter at 16:32, 7 December 2022

2022-12-07T16:32:33Z

Noah at 21:52, 8 November 2022

2022-11-08T21:52:35Z

Noah at 21:52, 8 November 2022

2022-11-08T21:52:06Z

Noah at 21:51, 8 November 2022

2022-11-08T21:51:34Z

Show changes

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/The_Basics_of_Product_Codes}}
-[[File:[[File:EN KC T 4 2 S2b v2 neu.png|right|frame|Syndrome table for code $\mathcal{C}_1$]] |right|frame|Coset leader for the code under consideration&nbsp; $\rm HC \ (7, \ 4, \ 3)$]]
+[[File:EN KC T 4 2 S2b v2 neu.png|right|frame|Syndrome table for code&nbsp; $\mathcal{C}_1$]]
 The syndrome decoding was already treated in detail in the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes| "Decoding of Linear Block Codes"]].&nbsp;

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/The_Basics_of_Product_Codes}}
-[[File:EN_KC_T_4_2_S2b_v2.png|right|frame|Coset leader for the code under consideration&nbsp; $\rm HC \ (7, \ 4, \ 3)$]]
+[[File:[[File:EN KC T 4 2 S2b v2 neu.png|right|frame|Syndrome table for code $\mathcal{C}_1$]] |right|frame|Coset leader for the code under consideration&nbsp; $\rm HC \ (7, \ 4, \ 3)$]]
 The syndrome decoding was already treated in detail in the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes| "Decoding of Linear Block Codes"]].&nbsp;

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/The_Basics_of_Product_Codes}}
-[[File:EN_KC_Z_4_7_neu.png|right|frame|Coset leader for the code under consideration&nbsp; $\rm HC \ (7, \ 4, \ 3)$]]
+[[File:EN_KC_T_4_2_S2b_v2.png|right|frame|Coset leader for the code under consideration&nbsp; $\rm HC \ (7, \ 4, \ 3)$]]
 The syndrome decoding was already treated in detail in the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes| "Decoding of Linear Block Codes"]].&nbsp;

@@ Line 86: / Line 86: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; Correct is <u>proposed solution 2</u>:
+'''(1)'''&nbsp; Correct is the&nbsp; <u>proposed solution 2</u>:
-*From the [[Aufgaben:Exercise_4.7Z: _Principle_of_Syndrome_Decoding| "Syndrome table"]] on the information page &ndash; valid for the $\rm (7, \ 4, \ 3)$&ndash;Hamming code &ndash; it can be read that the syndrome $\underline{s} = \underline{s}_3 = (0, \, 1, \, 1)$ corresponds to the error pattern $\underline{e} = (0, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0)$. Thus the code word
+*From the&nbsp; [[Aufgaben:Exercise_4.7Z: _Principle_of_Syndrome_Decoding| "syndrome table"]]&nbsp; on the information page &ndash; valid for the&nbsp; $\rm (7,  4,  3)$&nbsp; Hamming code &ndash; it can be read that the syndrome &nbsp; $\underline{s} = \underline{s}_3 = (0, \, 1, \, 1)$&nbsp; corresponds to the error pattern &nbsp; $\underline{e} = (0, \, 0, \, 1, \, 0, \, 0, \, 0, \, 0)$. Thus the code word
 :$$\underline{x} = \underline{y} \hspace{0.15cm}+ \hspace{0.15cm}  \underline{y} = (0, 1, 1, 0, 1, 1, 0)  \hspace{0.15cm}+ \hspace{0.15cm}(0, 0, 1, 0, 0, 0, 0)
 \hspace{0.15cm}= \hspace{0.15cm}(0, 1, 0, 0, 1, 1, 0)$$
-most likely and the syndrome decoder will output this as the result.
+is most likely and the syndrome decoder will output this as the result.
-'''(2)'''&nbsp; Correct are <u>solutions 2, 3, and 4</u>:
+'''(2)'''&nbsp; Correct are the&nbsp; <u>solutions 2, 3, and 4</u>:
-*The parity-check matrix $\mathbf{H}$ of the truncated $\rm (6, \ 3)$&ndash;Hamming code $C_2$ has $m = n - k = 3$ rows and $n$ columns. Consequently, it is a $3 &times 6$&ndash;matrix &nbsp; &#8658; &nbsp; statement 1 is false.
+*The parity-check matrix&nbsp; $\mathbf{H}$&nbsp; of the truncated&nbsp; $\rm (6,  3)$&nbsp; Hamming code&nbsp; $C_2$&nbsp; has&nbsp; $m = n - k = 3$&nbsp; rows and&nbsp; $n$&nbsp; columns.&nbsp;
-*Since $\mathcal{C}_2$ is also a systematic code, the generator matrix $\mathbf{G}$ can be represented in the following form:
+*Since&nbsp; $\mathcal{C}_2$&nbsp; is also a systematic code,&nbsp; the generator matrix&nbsp; $\mathbf{G}$&nbsp; can be represented&nbsp; in the following form:
 :$${ \boldsymbol{\rm G}}
 =  \begin{pmatrix}
@@ Line 126: / Line 127: @@
 \hspace{0.05cm}.$$
-*Here $\mathbf{I}_3$ denotes a $3 &times 3$ diagonal matrix typical of the systematic code.
+*Here&nbsp; $\mathbf{I}_3$&nbsp; denotes a&nbsp; $3 &times 3$&nbsp; diagonal matrix typical of the systematic code.
-*Proposed solutions 2, 3, and 4 are therefore correct:
+*<u>Proposed solutions 2, 3, and 4</u>&nbsp; are therefore correct:
-:* Row 1: &nbsp; $\ 110100$,
+:* Row 1: &nbsp; $110100$,
-:* Row 2: &nbsp; $\ 101010$,
+:* Row 2: &nbsp; $101010$,
-:* row 3: &nbsp; $\ 011001$.
+:* Row 3: &nbsp; $011001$.
-'''(3)'''&nbsp; Correct is <u>proposed solution 1</u>:
+'''(3)'''&nbsp; Correct is the&nbsp; <u>proposed solution 1</u>:
-*According to the statements in the chapter [[Channel_Coding/Decoding_of_Linear_Block_Codes| "Decoding of Linear Block Codes"]], $\underline{s} = \underline{e} \cdot \mathbf{H}^{\rm T}$ can be written.
+*According to the statements in the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes| "Decoding of Linear Block Codes"]] &nbsp; &rArr; &nbsp;  $\underline{s} = \underline{e} \cdot \mathbf{H}^{\rm T}$&nbsp; can be written.
 *Thus, for the error-free case &nbsp; &#8658; &nbsp; $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$:
 :$$\underline{s}= \left ( 0, \hspace{0.03cm} 0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0 \right ) \cdot
    \begin{pmatrix}
@@ Line 150: / Line 152: @@
-'''(4)'''&nbsp; <u>All statements</u> are true, as can be seen from the sample solution to the last subtask:
+'''(4)'''&nbsp; <u>All statements</u>&nbsp; are true,&nbsp; as can be seen from the sample solution to the last subtask:
-*The rows of the transposed parity-check matrix, read from top to bottom, give the respective syndromes for the error patterns $\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 0), \hspace{0.05cm} \text{ ... } \hspace{0.05cm} , \ \underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 1)$.
+*The rows of the transposed parity-check matrix,&nbsp; read from top to bottom,&nbsp; give the respective syndromes for the error patterns $\underline{e} = (1, \, 0, \, 0, \, 0, \, 0, \, 0), \hspace{0.05cm} \text{ ... } \hspace{0.05cm} , \ \underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 1)$.
-'''(5)'''&nbsp; Correct are <u>solutions 2, 3, and 4</u>:
+'''(5)'''&nbsp; Correct are the&nbsp; <u>solutions 2, 3, and 4</u>:
-*The first statement is false because the first two rows of the transposed parity-check matrix  $\mathbf{H}^{\rm T}$ summed $(1, \, 1, \, 0) + (1, \, 0, \, 1) = (0, \, 1, \, 1) = \underline{s_3} &ne; \underline{s}_7$ results in.
+*The first statement is false because the sum of the first two rows of the transposed parity-check matrix  results in &nbsp;  $\mathbf{H}^{\rm T}$ summed $(1, \, 1, \, 0) + (1, \, 0, \, 1) = (0, \, 1, \, 1) = \underline{s_3} &ne; \underline{s}_7$.
-*Statements 2, 3 and 4, on the other hand, are correct:
+*The statements 2, 3 and 4&nbsp;are correct:
 :* First and last row: $\ (1, \, 1, \, 0) + (0, \, 0, \, 1) = (1, \, 1, \, 1) = \underline{s}_7$,
 :* second and fifth row: $\ (1, \, 0, \, 1) + (0, \, 1, \, 0) = (1, \, 1, \, 1) = \underline{s}_7$,
-:* The sum over all rows also gives $\underline{s}_7$, since there are exactly three ones in each matrix column.
+:* The sum over all rows also gives&nbsp;  $\underline{s}_7$,&nbsp;  since there are exactly three&nbsp; "ones"&nbsp;  in each matrix column.
 {{ML-Fuß}}

@@ Line 43: / Line 43: @@
 * The relationship between generator matrix&nbsp; $\mathbf{G}$&nbsp; and parity-check matrix&nbsp; $\mathbf{H}$&nbsp; of systematic codes is given in chapter&nbsp; [[Channel_Coding/General_Description_of_Linear_Block_Codes|"General Description of Linear Block Codes"]].
@@ Line 52: / Line 48: @@
 ===Questions===
 <quiz display=simple>
-{The received word be&nbsp; $\underline{y} = (0, \, 1, \, 1,\, 0, \, 1, \, 0)$, the syndrome&nbsp; $\underline{s} = (0, \, 1, \, 1)$. For which code word&nbsp; $\underline{x}$&nbsp; of&nbsp; $\mathcal{C}_1$&nbsp; does the syndrome decoder decide?
+{The received word be&nbsp; $\underline{y} = (0, \, 1, \, 1,\, 0, \, 1, \, 0)$,&nbsp; the syndrome&nbsp; $\underline{s} = (0, \, 1, \, 1)$.&nbsp; For which code word&nbsp; $\underline{x}$&nbsp; of&nbsp; $\mathcal{C}_1$&nbsp; does the syndrome decoder decide?
 |type="()"}
-- The most likely codeword is&nbsp; $\ \underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0)$.
+- The most likely code word is&nbsp; $\ \underline{x} = (1, \, 1, \, 1, \, 0, \, 1, \, 1, \, 0)$.
-+ The most likely codeword is&nbsp; $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 0)$.
++ The most likely code word is&nbsp; $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 0)$.
-- The most likely codeword is&nbsp; $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 1)$.
+- The most likely code word is&nbsp; $\ \underline{x} = (0, \, 1, \, 0, \, 0, \, 1, \, 1, \, 1)$.
 {What statements hold for the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; of the truncated code&nbsp; $\mathcal{C}_2$?
 |type="[]"}
-- This is a&nbsp; $4 &times 6$&ndash;matrix.
+- This is a&nbsp; $4 &times 6$&nbsp; matrix.
-+ The first row of this matrix is: &nbsp;$\ 110100$.
++ The first row of this matrix is&nbsp; "$110100$".
-+ The second row of this matrix is: &nbsp;$\ 101010$.
++ The second row of this matrix is&nbsp; "$101010$".
-+ The third row of this matrix is: &nbsp;$\ 011001$.
++ The third row of this matrix is&nbsp; "$011001$".
 {What syndrome&nbsp; $\underline{s}$&nbsp; results for the error pattern&nbsp; $\underline{e} = (0, \, 0, \, 0, \, 0, \, 0, \, 0)$?

@@ Line 2: / Line 2: @@
 [[File:EN_KC_Z_4_7_neu.png|right|frame|Coset leader for the code under consideration&nbsp; $\rm HC \ (7, \ 4, \ 3)$]]
-The syndrome decoding was already treated in detail in the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes| "Decoding of Linear Block Codes"]]&nbsp;. With all Hamming codes, which are as well known perfect, this gives a decoding result as good as with the (generally) clearly more complicated maximum likelihood decoding.
+The syndrome decoding was already treated in detail in the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes| "Decoding of Linear Block Codes"]].&nbsp;
 For syndrome decoding one proceeds as follows:
-* One forms the syndrome from the received vector&nbsp; $\underline{y}$&nbsp; of length&nbsp; $n$&nbsp; and the parity-check matrix&nbsp; $\mathbf{H}$&nbsp;:
+* One forms the syndrome from the received vector&nbsp; $\underline{y}$&nbsp; of length&nbsp; $n$&nbsp; and the parity-check matrix&nbsp; $\mathbf{H}$:
 :$$\underline{s} = \underline{y} \cdot { \boldsymbol{\rm H}}^{\rm T} \in {\rm GF}(2^m)
    \hspace{0.05cm},  \hspace{0.5cm}{\rm Note\hspace{-0.10cm}:} \hspace{0.15cm}m = n-k \hspace{0.05cm}. $$
-* The received word&nbsp; $\underline{y} = \underline{x} \ {\rm (code\:word)} + \underline{e} \ {\rm (error\:vector)}$&nbsp; is not necessarily an element of&nbsp; ${\rm GF}(2^m)$, but certainly an element of&nbsp; ${\rm GF}(2^n)$&nbsp; and it holds because of&nbsp; $\underline{x} \cdot \mathbf{H}^{\rm T} = \underline{0}$&nbsp; equally:
+* The received word&nbsp; $\underline{y} = \underline{x} \ {\rm (code\:word)} + \underline{e} \ {\rm (error\:vector)}$&nbsp; is not necessarily an element of&nbsp; ${\rm GF}(2^m)$,&nbsp; but certainly an element of&nbsp; ${\rm GF}(2^n)$&nbsp; and it holds because of &nbsp; $\underline{x} \cdot \mathbf{H}^{\rm T} = \underline{0}$ &nbsp; equally:
 :$$\underline{s} = \underline{e} \cdot { \boldsymbol{\rm H}}^{\rm T}\hspace{0.05cm}. $$
-* Many error patterns&nbsp; $\underline{e}$&nbsp; lead to the same syndrome&nbsp; $\underline{s}$. One now groups those error patterns with the same syndrome&nbsp; $\underline{s}_{\mu}$&nbsp; to the coset&nbsp; ${\it \Psi}_{\mu}$&nbsp;.
+* Many error patterns&nbsp; $\underline{e}$&nbsp; lead to the same syndrome&nbsp; $\underline{s}$. One now groups those error patterns with the same syndrome&nbsp; $\underline{s}_{\mu}$&nbsp; to the&nbsp; "coset&nbsp; ${\it \Psi}_{\mu}$".
-* The coset leader&nbsp; $\underline{e}_{\mu}$&nbsp; is the error vector that has the lowest Hamming weight within the class&nbsp; ${\it \Psi}_{\mu}$&nbsp; and is accordingly the most probable.
+* The&nbsp; "coset leader"&nbsp; $\underline{e}_{\mu}$&nbsp; is the error vector that has the lowest Hamming weight within the class&nbsp; ${\it \Psi}_{\mu}$&nbsp; and is accordingly the most probable.
-The table above shows the list of minor class leaders&nbsp; $\underline{e}_{\mu}$&nbsp; for each&nbsp; $\underline{s}_{\mu}$&nbsp; in the Hamming code&nbsp; $\rm HC \ (7, \ 4, \ 3)$. This table is needed for the subtask '''(1)'''.
+The table above shows the list of the class leaders&nbsp; $\underline{e}_{\mu}$&nbsp; for each&nbsp; $\underline{s}_{\mu}$&nbsp; in the Hamming code&nbsp; $\rm HC \ (7,  4,  3)$. This table is needed for the subtask&nbsp; '''(1)'''.
-A similar table is to be created for the truncated Hamming code&nbsp; $\rm HC \ (6, \ 3, \ 3)$&nbsp;. This has already been used in the&nbsp; [[Aufgaben:Exercise_4.6:_Product_Code_Generation| "Exercise 4.6"]]&nbsp; and the&nbsp; [[Aufgaben:Exercise_4.6Z:_Basics_of_Product_Codes| "Exercise 4.6Z"]]&nbsp; and is given by its generator matrix:
+A similar table is to be created for the truncated Hamming code&nbsp; $\rm HC \ (6,  3,  3)$.&nbsp; This has already been used in the&nbsp; [[Aufgaben:Exercise_4.6:_Product_Code_Generation|$\text{Exercise 4.6}$]]&nbsp; and the&nbsp; [[Aufgaben:Exercise_4.6Z:_Basics_of_Product_Codes| $\text{Exercise 4.6Z}$]]&nbsp; and is given by its generator matrix:
 :$${ \boldsymbol{\rm G}}
 =  \begin{pmatrix}
@@ Line 27: / Line 29: @@
 	\end{pmatrix} \hspace{0.05cm}.$$
-Unlike the original&nbsp; $\rm (7, \ 4, \ 3)$ Hamming code, the shortened&nbsp; $\rm (6, \ 3, \ 3)$&ndash; Hamming code is not perfect, so a single-w
+Unlike the original&nbsp; $\rm (7,  4,  3)$&nbsp; Hamming code,&nbsp; the shortened&nbsp; $\rm (6,  3,  3)$&nbsp; Hamming code is not perfect, so a single-error coset leader&nbsp; $\underline{s}_{\mu}$&nbsp; cannot be found for all possible&nbsp; $\underline{e}_{\mu}$.
@@ Line 36: / Line 36: @@
-Hints:
+*Reference is made in particular to the section&nbsp; [[Channel_Coding/The_Basics_of_Product_Codes#Iterative_syndrome_decoding_of_product_codes| "Iterative syndrome decoding of product codes"]].