Aufgaben:Exercise 4.7: Product Code Decoding - Revision history

Guenter at 15:29, 13 March 2023

2023-03-13T15:29:08Z

Guenter at 11:52, 21 December 2022

2022-12-21T11:52:08Z

Guenter at 16:26, 19 December 2022

2022-12-19T16:26:20Z

Noah at 20:35, 17 December 2022

2022-12-17T20:35:11Z

Noah at 20:25, 17 December 2022

2022-12-17T20:25:22Z

Guenter at 15:26, 8 December 2022

2022-12-08T15:26:27Z

Guenter at 12:26, 8 December 2022

2022-12-08T12:26:37Z

Guenter at 12:25, 8 December 2022

2022-12-08T12:25:41Z

Guenter at 12:24, 8 December 2022

2022-12-08T12:24:51Z

Guenter at 08:45, 8 December 2022

2022-12-08T08:45:54Z

@@ Line 44: / Line 44: @@
 #The corrected code word is then&nbsp; $\underline{y} + \underline{e}_{\mu}$.
-[[File:EN_KC_A_4_7_Zusatz_v2.png|right|frame|Predefined encoder and receiver matrices '''Korrektur''' encoded]]
+[[File:EN_KC_A_4_7_Zusatz_v2.png|right|frame|Predefined encoder and receiver matrices]]
@@ Line 98: / Line 98: @@
 '''(1)'''&nbsp; The decoding process of the received matrix&nbsp; $\mathbf{A}$&nbsp; is illustrated by the following diagram.
-[[File:EN_KC_A_4_7a_v2.png|right|frame|Syndrome decoding of the two-dimensional received matrix $\mathbf{A}$ '''Korrektur''' bereits zweite Grafik falsch. Auch Deutscg]]
+[[File:EN_KC_A_4_7a_v2.png|right|frame|Syndrome decoding of the two-dimensional received matrix $\mathbf{A}$ ]]
 * The single errors in rows&nbsp; 1, 3, 5 and 6&nbsp; are detected by&nbsp; $(7, \ 4, \ 3)$&nbsp; Hamming code and can be corrected <br>&nbsp;&#8658;&nbsp; green markings in the graphic&nbsp; "1st iteration horizontal".

← Older revision		Revision as of 11:52, 21 December 2022
Line 44:		Line 44:
	#The corrected code word is then  $\underline{y} + \underline{e}_{\mu}$.		#The corrected code word is then  $\underline{y} + \underline{e}_{\mu}$.

−	[[File:~~EN_KC_A_4_7_Zusatz~~.png\|right\|frame\|Predefined encoder and receiver matrices '''Korrektur''' encoded]]	+	[[File:EN_KC_A_4_7_Zusatz_v2.png\|right\|frame\|Predefined encoder and receiver matrices '''Korrektur''' encoded]]

@@ Line 1: / Line 1: @@
 {{quiz-Header|Buchseite=Channel_Coding/The_Basics_of_Product_Codes}}
-[[File:EN_KC_A_4_7_v2.png|right|frame|Syndrome tables of the considered component codes &nbsp;$\mathcal{C}_1$&nbsp; and &nbsp;$\mathcal{C}_2$]]
+[[File:EN_KC_T_4_2_S2b_v2.png|right|frame|Syndrome tables of the considered component codes &nbsp;$\mathcal{C}_1$&nbsp; and &nbsp;$\mathcal{C}_2$]]
 We consider as in the&nbsp; [[Aufgaben:Exercise_4.6:_Product_Code_Generation|$\text{Exercise 4.6}$]]&nbsp; a product code based on
 * the Hamming code&nbsp; $\rm HC \ (7, \ 4, \ 3)$ &nbsp; &rArr; &nbsp; $\mathcal{C}_1$,

@@ Line 149: / Line 149: @@
 '''(2)'''&nbsp; The following graphic shows the decoding process according to the specifications given by&nbsp; $\mathbf{B}$.&nbsp;
-[[File:EN_KC_A_4_7b_v2.png|right|frame|For syndrome decoding of the two-dimensional receive matrix&nbsp; $\mathbf{B}$.]]
+[[File:EN_KC_A_4_7b_v2.png|right|frame|For syndrome decoding of the two-dimensional received matrix&nbsp; $\mathbf{B}$.]]
 Despite only minor modifications compared to&nbsp; $\mathbf{A}$,&nbsp; there are now serious differences:
@@ Line 166: / Line 166: @@
-The error matrix is equal to the receive matrix of $\mathbf{A}$ &nbsp;&#8658;&nbsp; again, <u>proposed solution 3</u> is correct.
+The error matrix is equal to the received matrix of $\mathbf{A}$ &nbsp;&#8658;&nbsp; again, <u>proposed solution 3</u> is correct.
 {{ML-Fuß}}
 [[Category:Channel Coding: Exercises|^4.2 About the Product Codes^]]

@@ Line 41: / Line 41: @@
 Syndrome decoding of&nbsp; (one-dimensional)&nbsp; block codes has already been covered in the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes| "Decoding of Linear Block Codes"]].&nbsp; Here is a brief summary and an adaptation to the two-dimensional case:
 # From the received word&nbsp; $\underline{y}$&nbsp; $($a row or a column of the given received matrix$)$,&nbsp; <br>the syndrome corresponding to &nbsp; $\underline{s} = \underline{y} \cdot \mathbf{H}_1^{\rm T}$ &nbsp; resp. &nbsp; $\underline{s} = \underline{y} \cdot \mathbf{H}_2^{\rm T}$ &nbsp; is formed.
-#With the result &nbsp; $\underline{s} = \underline{s}_{\mu}$ &nbsp; one can read in above tables the so called&nbsp; "sub-class leader"&nbsp; $\underline{e}_{\mu}$&nbsp;.
+#With the result &nbsp; $\underline{s} = \underline{s}_{\mu}$ &nbsp; one can read in above tables the so called&nbsp; "coset leader"&nbsp; $\underline{e}_{\mu}$&nbsp;.
 #The corrected code word is then&nbsp; $\underline{y} + \underline{e}_{\mu}$.
@@ Line 47: / Line 47: @@
-The accompanying diagram shows three different encoded and receivec matrices to be analyzed in the subtasks&nbsp; '''(1)''',&nbsp; '''(2)''',&nbsp; and&nbsp; '''(3)''':
+The accompanying diagram shows three different encoded and received matrices to be analyzed in the subtasks&nbsp; '''(1)''',&nbsp; '''(2)''',&nbsp; and&nbsp; '''(3)''':
 *We name them constellation&nbsp; $\mathbf{A}$,&nbsp; $\mathbf{B}$&nbsp; and&nbsp; $\mathbf{C}$.

@@ Line 81: / Line 81: @@
 - Yes,&nbsp; after the first decoding in horizontal direction.
 - Yes,&nbsp; after the first decoding in vertical direction.
-+ Yes,&nbsp; after the second decoding in horizontal direction.
+- Yes,&nbsp; after the second decoding in horizontal direction.
 - Yes,&nbsp; after the second decoding in vertical direction.
-- No.
++ No.
 {Is the two-dimensional received matrix &nbsp;$\mathbf{C}$&nbsp; decodable?&nbsp; <br>Try to find the solution via an equivalence to subtask&nbsp; '''(1)'''&nbsp; resp.&nbsp; '''(2)'''.
@@ Line 96: / Line 96: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; The decoding process of the receive matrix $\mathbf{A}$ is illustrated by the following diagram.
+'''(1)'''&nbsp; The decoding process of the received matrix&nbsp; $\mathbf{A}$&nbsp; is illustrated by the following diagram.
-[[File:EN_KC_A_4_7a_v2.png|center|frame|Syndrome decoding of the two-dimensional received matrix $\mathbf{A}$.]]
+* The single errors in rows&nbsp; 1, 3, 5 and 6&nbsp; are detected by&nbsp; $(7, \ 4, \ 3)$&nbsp; Hamming code and can be corrected <br>&nbsp;&#8658;&nbsp; green markings in the graphic&nbsp; "1st iteration horizontal".
 * For the second row results the syndrome
 :$$\underline{s} = \underline{y}_2 \hspace{-0.03cm}\cdot \hspace{-0.03cm}{ \boldsymbol{\rm H}}_1^{\rm T} = \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0, \hspace{0.03cm}1, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0 \right ) \cdot \hspace{-0.05cm}
@@ Line 111: / Line 112: @@
 &1 &0 \\
 &0 &1
-	\end{pmatrix} \hspace{-0.05cm}=
+	\end{pmatrix} \hspace{-0.05cm}=$$
 	\left ( 1, \hspace{0.03cm} 1, \hspace{0.03cm}0 \right )
 + \left ( 1, \hspace{0.03cm} 1, \hspace{0.03cm}1 \right )=
@@ Line 117: / Line 119: @@
 = \underline{s}_1 \hspace{0.03cm}.$$
-* According to the upper syndrome table on the information page, the last bit is thus incorrectly "corrected". Incorrect corrections are entered in red in the upper graphic.
+* According to the upper syndrome table on the information page,&nbsp; the last bit is incorrectly&nbsp; "corrected".&nbsp; Incorrect corrections are entered in red in the upper graphic.
 * Correspondingly applies to the fourth row:
 :$$\underline{s} = \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}0, \hspace{0.03cm}1, \hspace{0.03cm}0 \right ) \cdot { \boldsymbol{\rm H}}_1^{\rm T} =
@@ Line 123: / Line 126: @@
 + \left ( 0, \hspace{0.03cm} 1, \hspace{0.03cm}0 \right )=
 \left ( 1, \hspace{0.03cm} 0, \hspace{0.03cm}0 \right )= \underline{s}_4 \hspace{0.05cm}.$$
-* This causes a miscorrection of bit 5.
+* This causes a miscorrection of bit&nbsp; '''5'''.
 :* Vertical decoding of columns 1, 3, 4, 5, 6, and 7 is straightforward because there is at most one error per column, which can be corrected by the truncated Hamming code $\rm (6, \ 3, \ 3)$.
@@ Line 145: / Line 148: @@
-'''(2)'''&nbsp; The following graphic shows the decoding process according to the specifications given by $\mathbf{B}$.
+'''(2)'''&nbsp; The following graphic shows the decoding process according to the specifications given by&nbsp; $\mathbf{B}$.&nbsp;
-[[File:EN_KC_A_4_7b_v2.png|center|frame|For syndrome decoding of the two-dimensional receive matrix $\mathbf{B}$.]]
+Despite only minor modifications compared to&nbsp; $\mathbf{A}$,&nbsp; there are now serious differences:
-Despite only minor modifications compared to $\mathbf{A}$, there are now serious differences:
+* Due to the first horizontal decoding,&nbsp; the&nbsp; "corrected"&nbsp; rows 2 and 4 now read equally:&nbsp; $(0, \, 1, \, 0, \, 1, \, 0, \, 0, \, 1)$, i.e.,&nbsp; the last bit of these rows is miscorrected in each case.
-The correct solution is <u>proposal 5</u>.
+* This constellation remains for arbitrary further (horizontal or vertical) decodings, because for $d_{\rm min} = 3$ always the syndrome $\underline{s}_0 = (0, \, 0, \, 0)$ results.
-'''(3)'''&nbsp; Comparing the encoder&ndash; and receiver matrices (differences are marked in blue), one can create the error matrix by modulo 2 additions according to the following graph.
+The correct solution is&nbsp; <u>proposal 5</u>.
 The error matrix is equal to the receive matrix of $\mathbf{A}$ &nbsp;&#8658;&nbsp; again, <u>proposed solution 3</u> is correct.

@@ Line 52: / Line 52: @@
 *Marked in yellow are the differences in the received matrices of constellation&nbsp; $\mathbf{B}$&nbsp; versus&nbsp; $\mathbf{A}$.&nbsp; In both cases,&nbsp; the encoded matrix consists only of&nbsp; "zeros".
-*The encoded matrix of&nbsp; $\rm C$&nbsp; was determined in&nbsp; [[Aufgaben:Aufgabe_4.6:_Produktcode–Generierung|$\text{Exercise 4.6}$]]&nbsp;.
+*The encoded matrix of&nbsp; $\rm C$&nbsp; was determined in&nbsp; [[Aufgaben:Exercise_4.6:_Product_Code_Generation|$\text{Exercise 4.6}$]]&nbsp;.
@@ Line 60: / Line 60: @@
 <u>Hints:</u>
 *This exercise belongs to the chapter&nbsp; [[Channel_Coding/The_Basics_of_Product_Codes| "Basics of Product Codes"]].
 *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"]].

@@ Line 44: / Line 44: @@
 #The corrected code word is then&nbsp; $\underline{y} + \underline{e}_{\mu}$.
-[[File:EN_KC_A_4_7_Zusatz.png|right|frame|Predefined encoder and receiver matrices]]
+[[File:EN_KC_A_4_7_Zusatz.png|right|frame|Predefined encoder and receiver matrices '''Korrektur''' encoded]]
 Hints:
 *This exercise belongs to the chapter&nbsp; [[Channel_Coding/The_Basics_of_Product_Codes| "Basics of Product Codes"]].
-*Reference is made in particular to the page&nbsp; [[Channel_Coding/The_Basics_of_Product_Codes#Iterative_syndrome_decoding_of_product_codes| "Iterative syndrome decoding of product codes"]].
+*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"]].
@@ Line 69: / Line 70: @@
 {Is the two-dimensional received matrix &nbsp;$\mathbf{A}$&nbsp; decodable?
 |type="()"}
-- Yes, after the first decoding in horizontal direction.
+- Yes,&nbsp; after the first decoding in horizontal direction.
-- Yes, after the first decoding in vertical direction.
+- Yes,&nbsp; after the first decoding in vertical direction.
-+ Yes, after the second decoding in horizontal direction.
++ Yes,&nbsp; after the second decoding in horizontal direction.
-- Yes, after the second decoding in vertical direction.
+- Yes,&nbsp; after the second decoding in vertical direction.
 - No.
 {Is the two-dimensional received matrix &nbsp;$\mathbf{B}$&nbsp; decodable?
 |type="()"}
-- Yes, after the first decoding in horizontal direction.
+- Yes,&nbsp; after the first decoding in horizontal direction.
-- Yes, after the first decoding in vertical direction.
+- Yes,&nbsp; after the first decoding in vertical direction.
-+ Yes, after the second decoding in horizontal direction.
++ Yes,&nbsp; after the second decoding in horizontal direction.
-- Yes, after the second decoding in vertical direction.
+- Yes,&nbsp; after the second decoding in vertical direction.
 - No.
-{Is the two-dimensional received matrix &nbsp;$\mathbf{C}$&nbsp; decodable? Try to find the solution via an equivalence to the exercise '''(1)''' or '''(2)'''.
+{Is the two-dimensional received matrix &nbsp;$\mathbf{C}$&nbsp; decodable?&nbsp; <br>Try to find the solution via an equivalence to subtask&nbsp; '''(1)'''&nbsp; resp.&nbsp; '''(2)'''.
 |type="()"}
-- Yes, after the first decoding in horizontal direction.
+- Yes,&nbsp; after the first decoding in horizontal direction.
-- Yes, after the first decoding in vertical direction.
+- Yes,&nbsp; after the first decoding in vertical direction.
-+ Yes, after the second decoding in horizontal direction.
++ Yes,&nbsp; after the second decoding in horizontal direction.
-- Yes, after the second decoding in vertical direction.
+- Yes,&nbsp; after the second decoding in vertical direction.
 - No.
 </quiz>

@@ Line 2: / Line 2: @@
 [[File:EN_KC_A_4_7_v2.png|right|frame|Syndrome tables of the considered component codes &nbsp;$\mathcal{C}_1$&nbsp; and &nbsp;$\mathcal{C}_2$]]
-We consider, as in the&nbsp; [[Aufgaben:Aufgabe_4.6:_Produktcode–Generierung|"Exercise 4.6"]]&nbsp; a product code based on.
+We consider as in the&nbsp; [[Aufgaben:Aufgabe_4.6:_Produktcode–Generierung|$\text{Exercise 4.6}$]]&nbsp; a product code based on
 * the Hamming code&nbsp; $\rm HC \ (7, \ 4, \ 3)$ &nbsp; &rArr; &nbsp; $\mathcal{C}_1$,
 * the truncated Hamming code&nbsp; $\rm HC \ (6, \ 3, \ 3)$ &nbsp; &rArr; &nbsp; $\mathcal{C}_2$.
@@ Line 21: / Line 22: @@
 	\end{pmatrix} \hspace{0.05cm}.$$
-For the sake of completeness, the generator matrices are also given, but they are not needed to solve the exercise:
+For the sake of completeness,&nbsp; the generator matrices are also given,&nbsp; but they are not needed to solve the exercise:
 :$${ \boldsymbol{\rm G}}_1
 =  \begin{pmatrix}
@@ Line 36: / Line 37: @@
 	\end{pmatrix} \hspace{0.05cm}.$$
-The&nbsp; <i>Hard Decision Decoding</i>&nbsp; of this code is preferably done iteratively, by alternately syndromdecoding all rows and then all columns. See:&nbsp; [[Channel_Coding/The_Basics_of_Product_Codes#Iterative_syndrome_decoding_of_product_codes| "Iterative Syndrome Decoding of Product Codes"]].
+The&nbsp; "Hard Decision Decoding"&nbsp; of this code is preferably done iteratively,&nbsp; by alternately&nbsp; "syndrome decoding"&nbsp; all rows and then all columns.&nbsp; See section&nbsp; [[Channel_Coding/The_Basics_of_Product_Codes#Iterative_syndrome_decoding_of_product_codes| "Iterative Syndrome Decoding of Product Codes"]].
-Syndrome decoding of (one-dimensional) block codes has already been covered in the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes| "Decoding of Linear Block Codes"]]&nbsp;. Here is a brief summary and an adaptation to the two-dimensional case:
+Syndrome decoding of&nbsp; (one-dimensional)&nbsp; block codes has already been covered in the chapter&nbsp; [[Channel_Coding/Decoding_of_Linear_Block_Codes| "Decoding of Linear Block Codes"]].&nbsp; Here is a brief summary and an adaptation to the two-dimensional case:
-* From the received word&nbsp; $\underline{y}$&nbsp; (a row or a column of the given received matrix), the syndrome corresponding to&nbsp; $\underline{s} = \underline{y} \cdot \mathbf{H}_1^{\rm T}$&nbsp; respectively&nbsp; $\underline{s} = \underline{y} \cdot \mathbf{H}_2^{\rm T}$&nbsp; formed.
+# From the received word&nbsp; $\underline{y}$&nbsp; $($a row or a column of the given received matrix$)$,&nbsp; <br>the syndrome corresponding to &nbsp; $\underline{s} = \underline{y} \cdot \mathbf{H}_1^{\rm T}$ &nbsp; resp. &nbsp; $\underline{s} = \underline{y} \cdot \mathbf{H}_2^{\rm T}$ &nbsp; is formed.
-*With the result&nbsp; $\underline{s} = \underline{s}_{\mu}$&nbsp; one can read in above tables the so called side class adder&nbsp; $\underline{e}_{\mu}$&nbsp;.
+#With the result &nbsp; $\underline{s} = \underline{s}_{\mu}$ &nbsp; one can read in above tables the so called&nbsp; "sub-class leader"&nbsp; $\underline{e}_{\mu}$&nbsp;.
-*The corrected code word is then&nbsp; $\underline{y} + \underline{e}_{\mu}$.
+#The corrected code word is then&nbsp; $\underline{y} + \underline{e}_{\mu}$.
 [[File:EN_KC_A_4_7_Zusatz.png|right|frame|Predefined encoder and receiver matrices]]