Aufgaben:Exercise 4.13: Decoding LDPC Codes - Revision history

Guenter at 17:30, 17 December 2022

2022-12-17T17:30:07Z

Guenter at 16:40, 17 December 2022

2022-12-17T16:40:00Z

Noah at 21:22, 10 December 2022

2022-12-10T21:22:33Z

Noah at 21:22, 10 December 2022

2022-12-10T21:22:09Z

Noah at 21:21, 10 December 2022

2022-12-10T21:21:59Z

Noah at 21:12, 10 December 2022

2022-12-10T21:12:04Z

Noah at 21:09, 10 December 2022

2022-12-10T21:09:47Z

Noah at 21:09, 10 December 2022

2022-12-10T21:09:32Z

Show changes

Guenter: Guenter moved page Aufgaben:Aufgabe 4.13: Decodierung von LDPC–Codes to Aufgaben:Exercise 4.13: Decoding LDPC Codes

2022-11-22T13:01:53Z

Guenter moved page Aufgabe 4.13: Decodierung von LDPC–Codes to Exercise 4.13: Decoding LDPC Codes

Javier: Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

2021-03-23T12:49:37Z

Text replacement - "Category:Aufgaben zu Kanalcodierung" to "Category:Channel Coding: Exercises"

@@ Line 69: / Line 69: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; The <i>variable node</i>$\rm (VN)$ $V_i$ stands for the $i$th code word bit, so that $I_{\rm VN}$ is equal to the code word length $n$.
+'''(1)'''&nbsp; The variable node&nbsp; $V_i$&nbsp; stands for the&nbsp; $i$<sup>th</sup>&nbsp; code word bit,&nbsp; so that&nbsp; $I_{\rm VN}$&nbsp; is&nbsp; equal to the code word length&nbsp; $n$.
-*From the column number of the $\mathbf{H}$&ndash;matrix, we can see $I_{\rm VN} = n \ \underline{= 12}$.
+*From the column number of the&nbsp; $\mathbf{H}$&nbsp; matrix,&nbsp; we can see&nbsp; $I_{\rm VN} = n \ \underline{= 12}$.
-*For the set of all <i>variable nodes</i>,one can thus write in general: ${\rm VN} = \{V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , V_i, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ V_n\}$.
-*The <i>check node</i> ${\rm (CN)} \ C_j$ represents the $j$ parity-check equation, and for the set of all <i>check nodes</i>, ${\rm CN} = \{C_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ C_j, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ C_m\}$.
+*For the set of all variable nodes,&nbsp; one can thus write in general:&nbsp; ${\rm VN} = \{V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , V_i, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ V_n\}$.
 *From the number of rows of the $\mathbf{H}$ matrix we get $I_{\rm CN} \ \underline {= m = 9}$.
-'''(2)'''&nbsp; The results can be read from the Tanner graph sketched below.
+'''(2)'''&nbsp; The results can be read from the Tanner graph sketched on the right.
-[[File:P_ID3084__KC_A_4_13c_v1.png|right|frame|Tanner graph for the present example. ]]
+Correct are <u>the proposed solutions 1, 2 and 5</u>:
-Correct are <u>the proposed solutions 1, 2 and 5</u>:
+* $h_{6,\hspace{0.05cm} 10} = h_{6,\hspace{0.05cm} 11} = 1$,&nbsp; $h_{6,\hspace{0.05cm}12} = 0$ &nbsp; &#8658; &nbsp; not all three edges exist.
-* The matrix element $h_{5,\hspace{0.05cm}5}$ (column 5, row 5) ist $1$ &nbsp; <br>&#8658; &nbsp; red edge.
-* The matrix element $h_{4,\hspace{0.05cm} 6}$ (column 4, row 6) ist $1$ &nbsp; <br>&#8658; &nbsp; blue edge.
+* It holds&nbsp; $h_{7,\hspace{0.05cm}6} = h_{8,\hspace{0.05cm}7} = h_{9,\hspace{0.05cm}8} = 1$ &nbsp; &#8658; &nbsp; green edges.
 '''(3)'''&nbsp; It is a regular LDPC code with
-* $w_{\rm Z}(j) = 4 = w_{\rm Z}$ für $1 &#8804; j &#8804; 9$,
+* $w_{\rm R}(j) = 4 = w_{\rm R}$ for $1 &#8804; j &#8804; 9$,
-The <u>answers 2 and 3</u> are correct, as can be seen from the first row and ninth column, respectively, of the parity-check matrix $\mathbf{H}$. <br>The Tanner graph confirms these results:
-* From $C_1$ there are edges to $V_1, \ V_2, \ V_3$, and $V_4$.
+The&nbsp; <u>answers 2 and 3</u>&nbsp; are correct,&nbsp; as can be seen from the first row and ninth column,&nbsp; respectively, of the parity-check matrix&nbsp; $\mathbf{H}$.
 * From $V_9$ there are edges to $C_3, \ C_5$, and $C_7$.
 The answers 1 and 4 cannot be correct already because
-* the neighborhood $N(V_i)$ of each <i>variable node</i> $V_i$ contains exactly $w_{\rm S} = 3$ elements, and
+* the neighborhood&nbsp; $N(V_i)$&nbsp; of each variable node&nbsp; $V_i$&nbsp; contains exactly&nbsp; $w_{\rm C} = 3$&nbsp; elements,&nbsp; and
-* the neighborhood $N(C_j)$ of each <i>check ndes</i> $C_j$ contains exactly $w_{\rm Z} = 4$ elements.
-'''(5)'''&nbsp; Correct is <u>only proposed solution 3</u> because.
+* there are indeed analogies between the CND algorithm and SPC decoding.
 {{ML-Fuß}}

@@ Line 4: / Line 4: @@
 The exercise deals with&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes#Iterative_decoding_of_LDPC_codes|"Iterative decoding of LDPC&ndash;codes"]]&nbsp; according to the&nbsp; ''Message passing algorithm''.
-The starting point is the presented&nbsp; $9 &times 12$&ndash;parity-check matrix&nbsp; $\mathbf{H}$, which is to be represented as a Tanner graph at the beginning of the exercise. It should be noted that:
+The starting point is the presented&nbsp; $9 &times 12$&nbsp; parity-check matrix&nbsp; $\mathbf{H}$,&nbsp; which is to be represented as Tanner graph at the beginning of the exercise.&nbsp; It should be noted:
-* The&nbsp; <i>variable nodes</i>&nbsp; (abbreviated&nbsp; $\rm VNs$)&nbsp; $V_i$&nbsp; denote the&nbsp; $n$&nbsp; code word bits.
+# The&nbsp; "variable nodes"&nbsp; $V_i$&nbsp; denote the&nbsp; $n$&nbsp; bits of the code word.
-* The&nbsp; <i>check nodes</i>&nbsp; (abbreviated&nbsp; $\rm CNs$)&nbsp; $C_j$&nbsp; represent the&nbsp; $m$&nbsp; parity-check equations.
+# The&nbsp; "check nodes"&nbsp;  $C_j$&nbsp; represent the&nbsp; $m$&nbsp; parity-check equations.
-* A connection between&nbsp; $V_i$&nbsp; and&nbsp; $C_j$&nbsp; indicates that the matrix element&nbsp; $h_{j,\hspace{0.05cm} i}$&nbsp; of the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; $($in row&nbsp; $j$, column&nbsp; $i)$&nbsp; is equal&nbsp; $1$&nbsp;. For&nbsp; $h_{j,\hspace{0.05cm}i} = 0$&nbsp; there is no connection between&nbsp; $V_i$&nbsp; and&nbsp; $C_j$.
+# A connection between&nbsp; $V_i$&nbsp; and&nbsp; $C_j$&nbsp; indicates that the element of matrix&nbsp; $\mathbf{H}$&nbsp; $($in row&nbsp; $j$, column&nbsp; $i)$&nbsp; is &nbsp; $h_{j,\hspace{0.05cm} i} =1$.
-* The&nbsp; <i>neighbors</i>&nbsp; $N(V_i)$&nbsp; of&nbsp; $V_i$&nbsp; is called the set of all&nbsp; check nodes&nbsp; $C_j$ connected to&nbsp; $V_i$&nbsp; in the Tanner graph. Correspondingly, to&nbsp; $N(C_j)$&nbsp; belong all variable nodes&nbsp; $V_i$&nbsp; with a connection to&nbsp; $C_j$.
+#For&nbsp; $h_{j,\hspace{0.05cm}i} = 0$&nbsp; there is no connection between&nbsp; $V_i$&nbsp; and&nbsp; $C_j$.
 The decoding is performed alternately with respect to
-* den&nbsp; <i>variable nodes</i> &nbsp; &#8658; &nbsp; variable nodes decoder (VND), and
+* the&nbsp; variable nodes &nbsp; &#8658; &nbsp; "variable nodes decoder"&nbsp; $\rm (VND)$,&nbsp; and
 Hints:
 *The exercise belongs to the chapter&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes| "Basic information about Low&ndash;density Parity&ndash;check Codes"]].
-*Reference is made in particular to the page&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes#Iterative_decoding_of_LDPC_codes|"Iterative decoding of LDPC codes"]].
@@ Line 30: / Line 34: @@
 ===Questions===
 <quiz display=simple>
-{How many&nbsp; <i>variable nodes</i> $(I_{\rm VN})$&nbsp; and&nbsp; <i>check nodes</i> $(I_{\rm CN})$&nbsp; are to be considered?
+{How many&nbsp; variable nodes&nbsp; $(I_{\rm VN})$&nbsp; and&nbsp; check nodes&nbsp; $(I_{\rm CN})$&nbsp; are to be considered?
 |type="{}"}
 $I_{\rm VN} \ = \ ${ 12 }
 $I_{\rm CN} \ = \ ${ 9 }
-{Which of the following&nbsp; <i>check nodes</i>&nbsp; and&nbsp; <i>variable nodes</i>&nbsp; are connected?
+{Which of the following&nbsp; check nodes&nbsp; and&nbsp; variable nodes&nbsp; are connected?
 |type="[]"}
 + $C_4$&nbsp; and &nbsp;$V_6$.
@@ Line 43: / Line 47: @@
 + $C_j$&nbsp; and &nbsp;$V_{j-1}$&nbsp; for&nbsp; $j > 6$.
-{Which statements are true regarding neighbors&nbsp; $N(V_i)$&nbsp; and&nbsp; $N(C_j)$&nbsp;?
+{Which statements are true regarding neighbors &nbsp; $N(V_i)$ &nbsp; and &nbsp; $N(C_j)$&nbsp;?
 |type="[]"}
 - $N(V_1) = \{C_1, \ C_2, \ C_3, \ C_4\}$,
@@ Line 50: / Line 54: @@
 - $N(C_9) = \{V_3, \ V_5, \ V_7\}$.
-{Which statements are true for the&nbsp; <i>variable node decoder</i>&nbsp; (VND)?
+{Which statements are true for the&nbsp; variable node decoder&nbsp; $\rm (VND)$?
 |type="[]"}
-+ At the beginning (iteration 0) the&nbsp; $L$ values of the nodes&nbsp; $V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm}, \ V_n$&nbsp; corresponding to the channel input values&nbsp; $y_i$&nbsp; preassigned.
++ At the beginning&nbsp; $($iteration 0$)$&nbsp; the&nbsp; $L$&ndash;values of the nodes&nbsp; $V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm}, \ V_n$&nbsp; are preassigned corresponding to the channel input values&nbsp; $y_i$.
-+ For the VND represents&nbsp; $L(C_j &#8594; V_i)$&nbsp; apriori&ndash;information.
++ For the VND represents&nbsp; $L(C_j &#8594; V_i)$&nbsp; a-priori information.
-- There are analogies between the&nbsp; <i>variable node decoder</i>&nbsp; and the decoding of a <i>single parity&ndash;check code</i>.
+- There are analogies between the&nbsp; "variable node decoder"&nbsp; and the decoding of a single parity&ndash;check code.
-{Which statements are true for the&nbsp; <i>check node decoder</i>&nbsp; (CND)?
+{Which statements are true for the&nbsp; check node decoder&nbsp; $\rm (CND)$?
 |type="[]"}
-- The CND returns the desired a posteriori&ndash;$L$&ndash;values at the end.
+- The CND returns  at the end the desired a-posteriori&nbsp; $L$&ndash;values.
-- For the CND represents&nbsp; $L(C_j &#8594; V_i)$&nbsp; apriori&ndash;information.
+- For the CND represents&nbsp; $L(C_j &#8594; V_i)$&nbsp; a-priori information.
-+ There are analogies between the&nbsp; <i>check node decoder</i>&nbsp; and the decoding of a <i>single parity&ndash;check code</i>.
++ There are analogies between the&nbsp; "check node decoder"&nbsp; and the decoding of a single parity&ndash;check code.
 </quiz>

@@ Line 5: / Line 5: @@
 The starting point is the presented&nbsp; $9 &times 12$&ndash;parity-check matrix&nbsp; $\mathbf{H}$, which is to be represented as a Tanner graph at the beginning of the exercise. It should be noted that:
-* The&nbsp; <i>variable nodes</i>&nbsp; (abbreviated&nbsp; $\rm VNs$)&nbsp; $V_i$&nbsp; denote the&nbsp; $n$&nbsp; codeword bits.
+* The&nbsp; <i>variable nodes</i>&nbsp; (abbreviated&nbsp; $\rm VNs$)&nbsp; $V_i$&nbsp; denote the&nbsp; $n$&nbsp; code word bits.
 * The&nbsp; <i>check nodes</i>&nbsp; (abbreviated&nbsp; $\rm CNs$)&nbsp; $C_j$&nbsp; represent the&nbsp; $m$&nbsp; parity-check equations.
 * A connection between&nbsp; $V_i$&nbsp; and&nbsp; $C_j$&nbsp; indicates that the matrix element&nbsp; $h_{j,\hspace{0.05cm} i}$&nbsp; of the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; $($in row&nbsp; $j$, column&nbsp; $i)$&nbsp; is equal&nbsp; $1$&nbsp;. For&nbsp; $h_{j,\hspace{0.05cm}i} = 0$&nbsp; there is no connection between&nbsp; $V_i$&nbsp; and&nbsp; $C_j$.
@@ Line 65: / Line 65: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; The <i>variable node</i>$\rm (VN)$ $V_i$ stands for the $i$&ndash;th codeword bit, so that $I_{\rm VN}$ is equal to the codeword length $n$.
+'''(1)'''&nbsp; The <i>variable node</i>$\rm (VN)$ $V_i$ stands for the $i$th code word bit, so that $I_{\rm VN}$ is equal to the code word length $n$.
 *From the column number of the $\mathbf{H}$&ndash;matrix, we can see $I_{\rm VN} = n \ \underline{= 12}$.
 *For the set of all <i>variable nodes</i>,one can thus write in general: ${\rm VN} = \{V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , V_i, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ V_n\}$.

← Older revision		Revision as of 21:22, 10 December 2022
Line 16:		Line 16:


−	This is referred to in subtasks '''(5)''' and '''(6)''''.	+	This is referred to in subtasks '''(5)''' and '''(6)'''.

@@ Line 4: / Line 4: @@
 The exercise deals with&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes#Iterative_decoding_of_LDPC_codes|"Iterative decoding of LDPC&ndash;codes"]]&nbsp; according to the&nbsp; ''Message passing algorithm''.
-The starting point is the presented&nbsp; $9 &times 12$&ndash;parity-check matrix&nbsp; $\mathbf{H}$, which is to be represented as a Tanner&ndash;graph at the beginning of the exercise. It should be noted that:
+The starting point is the presented&nbsp; $9 &times 12$&ndash;parity-check matrix&nbsp; $\mathbf{H}$, which is to be represented as a Tanner graph at the beginning of the exercise. It should be noted that:
 * The&nbsp; <i>variable nodes</i>&nbsp; (abbreviated&nbsp; $\rm VNs$)&nbsp; $V_i$&nbsp; denote the&nbsp; $n$&nbsp; codeword bits.
 * The&nbsp; <i>check nodes</i>&nbsp; (abbreviated&nbsp; $\rm CNs$)&nbsp; $C_j$&nbsp; represent the&nbsp; $m$&nbsp; parity-check equations.
 * A connection between&nbsp; $V_i$&nbsp; and&nbsp; $C_j$&nbsp; indicates that the matrix element&nbsp; $h_{j,\hspace{0.05cm} i}$&nbsp; of the parity-check matrix&nbsp; $\mathbf{H}$&nbsp; $($in row&nbsp; $j$, column&nbsp; $i)$&nbsp; is equal&nbsp; $1$&nbsp;. For&nbsp; $h_{j,\hspace{0.05cm}i} = 0$&nbsp; there is no connection between&nbsp; $V_i$&nbsp; and&nbsp; $C_j$.
-* The&nbsp; <i>neighbors</i>&nbsp; $N(V_i)$&nbsp; of&nbsp; $V_i$&nbsp; is called the set of all&nbsp; check nodes&nbsp; $C_j$ connected to&nbsp; $V_i$&nbsp; in the Tanner ;graph. Correspondingly, to&nbsp; $N(C_j)$&nbsp; belong all variable nodes&nbsp; $V_i$&nbsp; with a connection to&nbsp; $C_j$.
+* The&nbsp; <i>neighbors</i>&nbsp; $N(V_i)$&nbsp; of&nbsp; $V_i$&nbsp; is called the set of all&nbsp; check nodes&nbsp; $C_j$ connected to&nbsp; $V_i$&nbsp; in the Tanner graph. Correspondingly, to&nbsp; $N(C_j)$&nbsp; belong all variable nodes&nbsp; $V_i$&nbsp; with a connection to&nbsp; $C_j$.

@@ Line 22: / Line 22: @@
 Hints:
-*The exercise belongs to the chapter&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes| Basic information about Low&ndash;density Parity&ndash;check Codes]].
+*The exercise belongs to the chapter&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes| "Basic information about Low&ndash;density Parity&ndash;check Codes"]].
-*Reference is made in particular to the page&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes#Iterative_decoding_of_LDPC_codes|Iterative decoding of LDPC codes]].
+*Reference is made in particular to the page&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes#Iterative_decoding_of_LDPC_codes|"Iterative decoding of LDPC codes"]].

← Older revision	Revision as of 13:01, 22 November 2022
(No difference)

← Older revision		Revision as of 12:49, 23 March 2021
Line 117:		Line 117:


−	[[Category:~~Aufgaben zu Kanalcodierung~~\|^4.4 Low–density Parity–check Codes^]]	+	[[Category:Channel Coding: Exercises\|^4.4 Low–density Parity–check Codes^]]