LDPC Codes

LDPC Introduction

Density Evolution with LODE and LOPT

1. Low-density parity-check codes
2. Density evolution
3. Using LODE
4. Using LOPT


Low-density parity-check codes

As their name suggests, LDPC codes are block codes with parity-check matrices that contain only a very small number of non-zero entries. It is the sparseness of $ H$ which guarantees that the decoding complexity increases only linearly with the code length when iterative message passing algorithms, such as the sum-product algorithm, are used for decoding.

LDPC codes are often represented in graphical form by a Tanner graph. The Tanner graph consists of two sets of vertices: $ n$ vertices for the codeword bits (called bit nodes), and $ m$ vertices for the parity-check equations (called check nodes). An edge joins a bit node to a check node if that bit is included in the corresponding parity-check equation and so the number of edges in the Tanner graph is equal to the number of ones in the parity-check matrix.

The degree distribution of the Tanner graph describes the number of edges into the bit and check nodes. The fraction of edges which are connected to degree-$ i$ bit nodes is denoted $ \lambda_i$ , and the fraction of edges which are connected to degree-$ i$ check nodes, is denoted $ \rho_i$ . The functions

$\displaystyle \lambda(x) = \lambda_2x + \lambda_3x^2 + \cdots + \lambda_ix^{i-1} + \cdots$ (1)

$\displaystyle \rho(x) = \rho_2x + \rho_3x^2 + \cdots + \rho_ix^{i-1} + \cdots$ (2)

are defined to describe the degree distributions. Translating between node degrees and edge degrees, the fraction of bit nodes with degree $ i$ (equivalently columns of weight $ i$ ) is

$\displaystyle v_i = \frac{\lambda_i/i}{\sum_j \lambda_j/j}, $

and the fraction of check nodes with degree $ i$ (equivalently rows of weight $ i$ ) is

$\displaystyle h_i = \frac{\rho_i/i}{\sum_j \rho_j/j}. $



example
The Tanner graph of the parity-check matrix

$\displaystyle H = \left[ \begin{array}{ccccccc} 0&1&1&0&0&1 \\ 1&1&1&0&1&0 \\ 1&0&0&1&1&1 \\ 0&0&1&1&0&1 \end{array} \right]. \vspace{0.5em}$ (3)

is shown in Fig. 1. The bit vertices are represented by circular nodes and the check vertices by square nodes. The degree distribution of this codes is

$\displaystyle \lambda(x) = 0.5714x + 0.42857x^2 $

$\displaystyle \rho(x) = 0.42857x^2 + 0.5714x^3 $




Figure 1: The Tanner graph representation of the parity-check matrix in (3).
Image irregtanner

An LDPC ensemble is the set of all possible Tanner graphs with a particular degree distribution.

Density evolution


While it is not possible to predict (without actually simulating it) how a particular LDPC Tanner graph will perform with sum-product decoding, it is possible to determine is how an ensemble of Tanner graphs is likely to behave, on average, if the channel is memoryless and under the assumption that the Tanner graphs are all cycle free. To do this the evolution of probability density functions are tracked through the message-passing algorithm, a process called density evolution.

Density evolution can be used to find the maximum level of channel noise which is likely to be corrected by a particular ensemble using the message-passing algorithm, called the threshold for that ensemble. For an additive white gaussian noise channel the threshold is the noise variance, $ \sigma$ , or the signal-to-noise ratio (usually given in dB).

For message-passing decoding on general memoryless channels, the bit-to-check and check-to-bit messages are the log likelihood ratios (LLRs) of the probabilities that a given bit is `1' or `0'. As these LLR values are continuous, the probability that a message is a particular LLR value is described by a probability density function (pdf). Density evolution tracks the evolution of these pdfs in the message passing decoder.

Density evolution enables the code designer to search for the ensemble with the best threshold. Once the best ensemble is found the code designer has a degree distribution from which to choose a specific LDPC code.

Using LODE

LODE website

LODE is an online density evolution calculator, which you can use to find the threshold of your favorite LDPC ensemble.

To use LODE you enter the degrees, and corresponding $ \rho$ 's and $ \lambda$ 's (defined above) for your ensemble. By definition:

$\displaystyle \sum_i \lambda_i = 1$ (4)

and

$\displaystyle \sum_i \rho_i = 1,$ (5)

so to enter a valid degree distribution both these equations must be satisfied.

Next you can adjust the tuning parameters of the simulation (leaving them as the defaults should be fine though). Although in theory the DE pdfs are continuous and defined for all possible LLRs this is not possible in practice. LODE limits the LLRs considered to those between Min LLR and Max LLR and chooses Number of LLR points equally spaced samples between Min LLR and Max LLR. Although in theory the sum-product decoder is allowed to run for an infinite number of iterations, and we expect the bit error rate to be zero for a successful decoding run, LODE limits the simulation to the Number of iterations specified and considers BERs below Minimum BER to be equivalent to a BER of zero.

Lastly you can select the output you would prefer. The threshold option will search between Minimum (dB) and Maximum (dB) to find the threshold of your ensemble. The result will be accurate to within Minimum difference dB. Output is the threshold found given as both the signal-to-noise ratio in dB and the corresponding noise variance ($ \sigma$ ). The specify Eb/No option will plot bit error rate plots and/or EXIT charts for your ensemble for each of the Number equally spaced $ Eb/No$ values between Eb/No Min (dB) and Eb/No Max (dB).



example
Figs. 2 and 3 show the input and output screen shots used to find the threshold of the ensemble with the same degree distribution as the code in Example 1



Figure 2: LODE input screen
\includegraphics[width=16cm]{lode_inputscreen}





Figure 3: LODE output screen
\includegraphics[width=9cm]{LODE_outputscreen}

Using LOPT

LOPT website

LOPT is an online optimisation tool which uses density evolution to find the ensemble which returns the best possible threshold, subject to your chosen rate and allowed degrees.

To use LODE you enter the degrees, and rate, $ R$ you would like for your ensemble. The ensemble degrees must satisfy (4), (5) and the code rate is given by

$\displaystyle \sum_i \frac{\rho_i}{i} = (1-R) \sum_i \frac{\lambda_i}{i} .$ (6)

Consequently, three of the allowed degrees are dependent variables, and so you must select at least four allowed degrees for the optimisation to progress.

The tuning parameters for the density evolution are the same as described above. As well, you can select the required degree of accuracy in the noise variance. Obviously, the more precise you would like the threshold (the smaller the choice of desired $ \mathbf{\sigma}$ accuracy), the longer the optimisation will take.



example
In this example we use LOPT to find an ensemble with a better threshold than the ensemble we used in Example 2. Figs. 4 and 5 show the input and output screen shots used.



Figure 4: LOPT input screen
\includegraphics[width=16cm]{LOPT_inputscreen}






Figure 5: LOPT output screen
\includegraphics[width=11cm]{LOPT_outputscreen}

Maintained by David Hayes
University of Newcastle
31 Oct 2008, © Copyright