Exercise 4.13: Decoding LDPC Codes

From LNTwww
Revision as of 17:40, 17 December 2022 by Guenter (talk | contribs)

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$\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}$–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 ${\rm (CN)} \ C_j$ represents the $j$ 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}$.


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

Tanner graph for the present example.

Correct are the proposed solutions 1, 2 and 5:

  • The matrix element $h_{5,\hspace{0.05cm}5}$ (column 5, row 5) ist $1$  
    ⇒   red edge.
  • The matrix element $h_{4,\hspace{0.05cm} 6}$ (column 4, row 6) ist $1$  
    ⇒   blue edge.
  • The matrix element $h_{6, \hspace{0.05cm}4}$ (column 6, row 4) ist $0$  
    ⇒   no edge.
  • $h_{6,\hspace{0.05cm} 10} = h_{6,\hspace{0.05cm} 11} = 1$. But $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 Z}(j) = 4 = w_{\rm Z}$ für $1 ≤ j ≤ 9$,
  • $w_{\rm S}(i) = 3 = w_{\rm S}$ für $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 S} = 3$ elements, and
  • the neighborhood $N(C_j)$ of each check ndes $C_j$ contains exactly $w_{\rm Z} = 4$ elements.


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

  • At the beginning 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.