Research‎ > ‎

Multi-Edge Type LDPC Codes

This part of our research, we focus on analysis tools and optimization algorithms for multi-edge type low-density parity-check (MET-LPDC) codes, a generalization of the concept of standard LDPC codes.
Fig. 1. Graphical representation of an example MET-LDPC code with four edge-types, where '.o' (resp., '●') un-punctured (resp., punctured) variable nodes and '□' represent check nodes. Number of nodes for different edge-types are
shown as fractions of the code length N, where N is the number of un-punctured variable nodes.

  • Optimization of Graph Based Codes for Belief Propagation Decoding
The code optimization of MET-LDPC codes is a non-linear cost function maximization problem, where the decoding threshold is the cost function and the Tanner graph structure and degree-distributions give the variables to be optimized. This part of our work introduces a novel code optimization technique called  "Adaptive range method'' which can be successfully applied to optimize degree distributions for both standard LDPC codes and MET-LDPC codes. We then propose a joint optimization technique for MET-LDPC codes which allows the optimization of the MET structure and degree distribution given just the number of edge classes and maximum node degrees.  An example of cost functions for the four edge-type MET-LDPC code  on a BI-AWGN channel is shown in Fig. 2. Through the joint optimization we gain a threshold improvement of 0.007 compared to the reference MET-LDPC code1 which has a threshold of 0.9682 over the BI-AWGN channel. Here we see the benefit of MET-LDPC codes as standard LPDC codes require a maximum node degree of 85 to obtain a threshold this high.

                                                                               (a)                                                                                                       (b)
Fig 2. (a) MET-DE cost function for optimization of degree distribution for fixed L(r,x) = a1r1x12 + a2r1x13 + a3r0x23x33 + a4r1x4 .
 (b) MET-DE cost function for optimization of MET code structure where Λ1 = [i11, i12, 0, 0] , Λ2 = [0, 0, 3, 0], Λ3 = [0, 0, 3, 0], 
Λ4 = [0, 0, 0, 1]  .

1Table VI of T. Richardson, R. Urbanke, MET-LDPC codes, 2002.

  • Gaussian Approximations for Density Evolution for Multi-Edge Type LDPC Codes
This part of our work investigates the performance of belief propagation decoding of MET-LDPC  codes over BI-AWGN channel. Because calculating threshold using full multi-edge type density evolution is computationally intensive task, we applied and analyzed three single-parameter Gaussian approximation models for MET-LDPC codes which are based on mean value of message PDF (Approximation 1), BER (Approximation 2), reciprocal channel approximation (Approximation 3). Then we showed that the accuracy of Gaussian approximations is poor under several conditions, namely codes at low-rate, with punctured variable node and with degree-one variable nodes. Unfortunately, these represent the case where MET-LDPC codes are most beneficial. See Fig. 3 and 4.
                    (a) Channel noise variance = 0.75                                                               (b) Channel noise variance = 1.2
Fig.3. Output PDFs of check-to-variable  messages of an ensemble of  rate-1/10 MET-LDPC code at the first iteration.

Fig. 4. Output PDF of variable-to-check  messages of an ensemble of  rate-1/2  MET-LDPC code at the second iteration, fed with channel noise variance = 0.85.