Difference between revisions of "Aufgaben:Exercise 4.13: Decoding LDPC Codes"

From LNTwww
 
Line 69: Line 69:
 
===Solution===
 
===Solution===
 
{{ML-Kopf}}
 
{{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}$.
+
 +
*The check node&nbsp; $ C_j$&nbsp; represents the&nbsp; $j$<sup>th</sup>&nbsp; parity-check equation,&nbsp; and for the set of all check nodes:
 +
:$${\rm CN} = \{C_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ C_j, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ C_m\}.$$  
 +
*From the number of rows of the&nbsp; $\mathbf{H}$&nbsp; matrix we get&nbsp; $I_{\rm CN} \ \underline {= m = 9}$.
  
  
 +
[[File:P_ID3084__KC_A_4_13c_v1.png|right|frame|Tanner graph for the present example ]]
  
'''(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>:
 +
* The  element&nbsp; $h_{5,\hspace{0.05cm}5}=1$ &nbsp; $($column 5, row 5$)$ &nbsp; &#8658; &nbsp; red edge.
 +
 
 +
* The element&nbsp; $h_{4,\hspace{0.05cm} 6}=1$&nbsp; $($column 4, row 6$)$ &nbsp; &#8658; &nbsp; blue edge.
 +
 
 +
* The element&nbsp; $h_{6, \hspace{0.05cm}4}=0$&nbsp; $($column 6, row 4$)$  &nbsp; &#8658; &nbsp; no edge.
  
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.
* The matrix element $h_{6, \hspace{0.05cm}4}$ (column 6, row 4) ist $0$ &nbsp; <br>&#8658; &nbsp; no edge.
 
* $h_{6,\hspace{0.05cm} 10} = h_{6,\hspace{0.05cm} 11} = 1$. But $h_{6,\hspace{0.05cm}12} = 0$ &nbsp; <br>&#8658; &nbsp; not all three edges exist.
 
* It holds $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  
 
'''(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$,
* $w_{\rm S}(i) = 3 = w_{\rm S}$ für $1 &#8804; i &#8804; 12$.
 
  
 +
* $w_{\rm C}(i) = 3 = w_{\rm C}$ for $1 &#8804; i &#8804; 12$.
  
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 Tanner graph confirms these results:
 +
* From&nbsp; $C_1$&nbsp; there are edges to&nbsp; $V_1, \ V_2, \ V_3$, and $V_4$.
 +
 
 +
* From&nbsp; $V_9$&nbsp; there are edges to $C_3, \ C_5$, and $C_7$.
  
  
 
The answers 1 and 4 cannot be correct already because
 
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.
+
 
 +
* the neighborhood&nbsp; $N(C_j)$&nbsp; of each check node&nbsp; $C_j$&nbsp; contains exactly&nbsp; $w_{\rm R} = 4$&nbsp; elements.
 +
 
 +
 
 +
 
 +
'''(4)'''&nbsp; Correct are the&nbsp; <u>proposed solutions 1 and 2</u>,&nbsp; as can be seen from the&nbsp; [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes#Iterative_decoding_of_LDPC_codes|"corresponding theory page"]]:
 +
* At the start of decoding&nbsp; $($so to speak at iteration&nbsp; $I=0)$&nbsp; the&nbsp; $L$&ndash;values of the variable nodes &nbsp; &#8658; &nbsp; $L(V_i)$ are preallocated with the channel input values.
 +
 
 +
* Later&nbsp; $($from iteration $I = 1)$&nbsp; the log likelihood ratio&nbsp; $L(C_j &#8594; V_i)$&nbsp; transmitted by the CND is considered in the VND as a-priori information.
  
 +
* Answer 3 is wrong.&nbsp; Rather,&nbsp; the correct answer would be:&nbsp; There are analogies between the VND algorithm and the decoding of a&nbsp; "repetition code".
  
  
'''(4)'''&nbsp; Correct are <u>proposed solutions 1 and 2</u>, as can be seen from the [[Channel_Coding/The_Basics_of_Low-Density_Parity_Check_Codes#Iterative_decoding_of_LDPC_codes|"corresponding theory page"]]:
 
* At the beginning of decoding&nbsp; $($so to speak at iteration $I=0)$&nbsp; the $L$&ndash;values of the <i>variable nodes</i> &nbsp;&#8658;&nbsp; $L(V_i)$ are preallocated with the channel input values.
 
* Later&nbsp; $($from iteration $I = 1)$&nbsp; the log&ndash;likelihood&ndash;ratio $L(C_j &#8594; V_i)$ transmitted by the CND is considered in the VND as a priori information.
 
* Answer 3 is wrong. Rather, the correct answer would be: there are analogies between the VND algorithm and the decoding of a <i>repetition code</i>.
 
  
 +
'''(5)'''&nbsp; Correct is&nbsp; <u>only proposed solution 3</u>&nbsp; because
 +
* the final a-posteriori&nbsp; $L$&ndash;values are derived from the VND,&nbsp; not from the CND;
  
 +
* the&nbsp; $L$&ndash;value&nbsp; $L(C_j &#8594; V_i)$&nbsp; represents extrinsic information for the CND;&nbsp; and
  
'''(5)'''&nbsp; Correct is <u>only proposed solution 3</u> because.
+
* there are indeed analogies between the CND algorithm and SPC decoding.
* the final a posteriori $L$ values are derived from the VND, not from the CND,
 
* the $L$ value $L(C_j &#8594; V_i)$ represents extrinsic information for the CND, and
 
* there are indeed analogies between the CND&ndash;algorithm and SPC&ndash;decoding.
 
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Latest revision as of 18:30, 17 December 2022

Given LDPC parity-check matrix

The exercise deals with  "Iterative decoding of LDPC–codes"  according to the  Message passing algorithm.

The starting point is the presented  $9 × 12$  parity-check matrix  $\mathbf{H}$,  which is to be represented as Tanner graph at the beginning of the exercise.  It should be noted:

  1. The  "variable nodes"  $V_i$  denote the  $n$  bits of the code word.
  2. The  "check nodes"  $C_j$  represent the  $m$  parity-check equations.
  3. A connection between  $V_i$  and  $C_j$  indicates that the element of matrix  $\mathbf{H}$  $($in row  $j$, column  $i)$  is   $h_{j,\hspace{0.05cm} i} =1$.
  4. For  $h_{j,\hspace{0.05cm}i} = 0$  there is no connection between  $V_i$  and  $C_j$.
  5. The  "neighbors  $N(V_i)$  of  $V_i$"  is called the set of all  check nodes  $C_j$ connected to  $V_i$  in the Tanner graph.
  6. Correspondingly,  to  $N(C_j)$  belong all variable nodes  $V_i$  with a connection to  $C_j$.


The decoding is performed alternately with respect to

  • the  variable nodes   ⇒   "variable nodes decoder"  $\rm (VND)$,  and
  • the  check nodes   ⇒   "check nodes decoder"  $\rm (CND)$.


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



Hints:



Questions

1

How many  variable nodes  $(I_{\rm VN})$  and  check nodes  $(I_{\rm CN})$  are to be considered?

$I_{\rm VN} \ = \ $

$I_{\rm CN} \ = \ $

2

Which of the following  check nodes  and  variable nodes  are connected?

$C_4$  and  $V_6$.
$C_5$  and  $V_5$.
$C_6$  and  $V_4$.
$C_6$  and  $V_i$  for  $i > 9$.
$C_j$  and  $V_{j-1}$  for  $j > 6$.

3

Which statements are true regarding neighbors   $N(V_i)$   and   $N(C_j)$ ?

$N(V_1) = \{C_1, \ C_2, \ C_3, \ C_4\}$,
$N(C_1) = \{V_1, \ V_2, \ V_3, \ V_4\}$,
$N(V_9) = \{C_3, \ C_5, \, C_7\}$,
$N(C_9) = \{V_3, \ V_5, \ V_7\}$.

4

Which statements are true for the  variable node decoder  $\rm (VND)$?

At the beginning  $($iteration 0$)$  the  $L$–values of the nodes  $V_1, \hspace{0.05cm} \text{...} \hspace{0.05cm}, \ V_n$  are preassigned corresponding to the channel input values  $y_i$.
For the VND represents  $L(C_j → V_i)$  a-priori information.
There are analogies between the  "variable node decoder"  and the decoding of a single parity–check code.

5

Which statements are true for the  check node decoder  $\rm (CND)$?

The CND returns at the end the desired a-posteriori  $L$–values.
For the CND represents  $L(C_j → V_i)$  a-priori information.
There are analogies between the  "check node decoder"  and the decoding of a single parity–check code.


Solution

(1)  The variable node  $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}$  matrix,  we can see  $I_{\rm VN} = n \ \underline{= 12}$.
  • For the set of all variable nodes,  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 check node  $ C_j$  represents the  $j$th  parity-check equation,  and for the set of all check nodes:
$${\rm CN} = \{C_1, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ C_j, \hspace{0.05cm} \text{...} \hspace{0.05cm} , \ C_m\}.$$
  • From the number of rows of the  $\mathbf{H}$  matrix we get  $I_{\rm CN} \ \underline {= m = 9}$.


Tanner graph for the present example

(2)  The results can be read from the Tanner graph sketched on the right.

Correct are the proposed solutions 1, 2 and 5:

  • The element  $h_{5,\hspace{0.05cm}5}=1$   $($column 5, row 5$)$   ⇒   red edge.
  • The element  $h_{4,\hspace{0.05cm} 6}=1$  $($column 4, row 6$)$   ⇒   blue edge.
  • The element  $h_{6, \hspace{0.05cm}4}=0$  $($column 6, row 4$)$   ⇒   no edge.
  • $h_{6,\hspace{0.05cm} 10} = h_{6,\hspace{0.05cm} 11} = 1$,  $h_{6,\hspace{0.05cm}12} = 0$   ⇒   not all three edges exist.
  • It holds  $h_{7,\hspace{0.05cm}6} = h_{8,\hspace{0.05cm}7} = h_{9,\hspace{0.05cm}8} = 1$   ⇒   green edges.


(3)  It is a regular LDPC code with

  • $w_{\rm R}(j) = 4 = w_{\rm R}$ for $1 ≤ j ≤ 9$,
  • $w_{\rm C}(i) = 3 = w_{\rm C}$ for $1 ≤ i ≤ 12$.


The  answers 2 and 3  are correct,  as can be seen from the first row and ninth column,  respectively, of the parity-check matrix  $\mathbf{H}$.

The Tanner graph confirms these results:

  • From  $C_1$  there are edges to  $V_1, \ V_2, \ V_3$, and $V_4$.
  • 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 variable node  $V_i$  contains exactly  $w_{\rm C} = 3$  elements,  and
  • the neighborhood  $N(C_j)$  of each check node  $C_j$  contains exactly  $w_{\rm R} = 4$  elements.


(4)  Correct are the  proposed solutions 1 and 2,  as can be seen from the  "corresponding theory page":

  • At the start of decoding  $($so to speak at iteration  $I=0)$  the  $L$–values of the variable nodes   ⇒   $L(V_i)$ are preallocated with the channel input values.
  • Later  $($from iteration $I = 1)$  the log likelihood ratio  $L(C_j → V_i)$  transmitted by the CND is considered in the VND as a-priori information.
  • Answer 3 is wrong.  Rather,  the correct answer would be:  There are analogies between the VND algorithm and the decoding of a  "repetition code".


(5)  Correct is  only proposed solution 3  because

  • the final a-posteriori  $L$–values are derived from the VND,  not from the CND;
  • the  $L$–value  $L(C_j → V_i)$  represents extrinsic information for the CND;  and
  • there are indeed analogies between the CND algorithm and SPC decoding.