Density Evolution

1 Introduction

For a given Tanner graph, it is still an open question to tell for which channel noise level the message passing algorithm will be able to reach a reliable transmission. Fortunately, it is possible to tell how an ensemble of Tanner graphs is likely to behave given that the channel is memoryless and the Tanner graphs are all cycle free. We could do this by tracking the evolution of probability density functions during the message passing procedure. We call this method Density Evolution which is first invented by Richardson and Urbanke in their papers in 2001.

Now there are some effective ways to decide whether a LDPC ensemble is good or not, but most of them are based on density evolution. We define threshold as the maximum level of channel noise under which the MPA(message passing algorithm) can reach a reliable transmission. By watching the threshold, we can design some excellent LDPC ensemble, from which a good LDPC matrix can be selected.

2 Density evolution on the BEC

On the BEC, an erased bit can be corrected if that bit was the only bit in the parity check equation. We assume that the MPA is passing messages down through the layers of a Tanner graph which is a tree. Under such assumption the bit-to-check message to check node in a lower level of the graph is determined by the check-to-bit message from all the incoming edges in the level above.

2.1 Regular LDPC codes

Problem: given an ensemble \(\mathcal{T}(w_{c},w_{r})\), which sonsists of all regular LDPC Tanner graphs with bit nodes of degree \(w_{c}\) and check nodes of degree \(w_{r}\), show the maximum erasure probability at which the MPA can recover all the erasure bit.

For BEC, the message hold either the current value of the bit ( can be “1” or “0”) or “x” (the bit value is unknown). Define \(q_{l}\) as the probability that at iteration \(l\) a check to bit message is an \(x\) and \(p_{l}\) as the probability that at iteration \(l\) a bit to check message is an \(x\).

For a regular LDPC ensemble, the C2B (check to bit) message on an edge is \(x\) if one or more of the incoming messages on the other \(w_{r} - 1\) edges into that check node is an \(x\). Suppose that all the incoming messages are identical and independent of each other, i.e. they have i.i.d. So,

\begin{equation} \label{eq:2} q_{l} = 1 - (1-p_{l})^{(w_{r} - 1)} \end{equation}

At iteration \(l\), the B2C message will be \(x\) if the origin message from the channel was an erasure and all the incoming message from check at iteration \(l-1\) are erasures. So,

\begin{equation} \label{eq3} p_{l} = \epsilon(q_{l-1})^{w_{c} - 1} \end{equation}

Here, \(\epsilon\) is the probability of \(x\) for the origin message from the channel. We use \(w_{c} - 1\) instead of \(w_{c}\), because we have to remove the message coming from the check node to which the bit node will send the new message. We do this to make the messages uncorrelated.

Combining the \(q_{l}\) and \(p_{l}\), we get:

\begin{equation} \label{eq:6} p_{l} = \epsilon \big( 1 - (1-p_{l-1})^{(w_{r} - 1)}\big)^{(w_{c} -1)} \end{equation}

Before the iteration, we have \(p_{0} = \epsilon\) which is the probability that a bit is erased by the channel.

Thus, for a \((w_{c},w_{r})\) regular ensemble, we have a recursion:

\begin{eqnarray} \label{eq:3} p_{0}&=&\epsilon \\
p_{l}&=& \epsilon \big( 1 - (1-p_{l-1})^{(w_{r} - 1)}\big)^{(w_{c} -1)} \end{eqnarray}

The above recursion describes how the erasure probability of MPA evolves as a function of the iteration number \(l\). For example, we can find that with \(\epsilon = 0.3\) the decoder can correct the erasure after \(l = 7\). With \(l \to \infty\), we find that \(\epsilon \in (0.4293,0.4294)\) is OK. So we can say that the threshold for a \((3,6)\) regular LDPC code is between \(0.4293\) and \(0.4294\).

2.2 Irregular LDPC codes

For an irregular LDPC codes, the columns and rows have varying weights. So we describe an irregular LDPC ensemble in a different way. We designated the fraction of columns of weight \(i\) by \(v_{i}\) and the fraction of rows of weight \(i\) by \(h_{i}\). An irregular LDPC ensemble can be described using \(v_{i}\) and \(h_{i}\)

To develop the irregular version of density evolution, we define fraction of edges connecting to degree-\(i\) bit nodes as \(\lambda_{i}\) and \(\rho_{i}\) the fraction of edges connecting to degree-\(i\) check nodes.

It’s easy to get:

\begin{eqnarray} \label{eq:7} \sum_{i}\lambda_{i}&=& 1 \\
\sum_{i}\rho_{i} &=& 1 \end{eqnarray}

We also define the degree distrubution functions as:

\begin{eqnarray} \label{eq:8} \lambda(x)&=&\lambda_{2} x + \lambda_{3}x^{2} + \ldots + \lambda_{i}x^{i-1} + \ldots \\
\rho(x) &=& \rho_{2}(x) + \rho_{3}x^{2} + \ldots + \rho_{i}x^{i-1} + \ldots \end{eqnarray}

We can transform between node degrees and edge degrees by:

\begin{eqnarray} \label{eq9} v_{i}&=& \frac{\lambda_{i}/i}{\sum_{j}\lambda_{j}/j} \\
h_{i}&=& \frac{\rho_{i}/i}{\sum_{j}\rho_{j}/j} \end{eqnarray}

About the above equation, take \[v_{i}=\frac{\lambda_{i}/i}{\sum_{j}\lambda_{j}/j} \] for example, suppose the number of degree \(i\) bit nodes is \(n_{i}\), so \(\lambda_{i} = \frac{ n_{i} i }{\sum_{j}n_{j}j} \). Then

\begin{equation} \label{eq:1} \lambda_{i}/i = \frac{n_{i}}{\sum_{j}n_{j}j} \end{equation}

Thus,

\begin{equation} \label{eq:9} \sum_{k}\lambda_{k}/k = \sum_{k} \frac{n_{k}}{\sum_{j}n_{j}j} \end{equation}

Then,

\begin{eqnarray} \label{eq:10} \frac{\lambda_{i}/i}{\sum_{k} \lambda_{k}/k } &=& \frac{ \frac{n_{i}}{\sum_{j}n_{j}j} }{ \sum_{k} \frac{n_{k}}{\sum_{j}n_{j}j}} \\
&=& \frac{n_{i}}{\sum_{k}n_{k}} \\
&=& v_{i} \end{eqnarray}

At the regular LDPC codes section, we get that, at the \(l\) iteration of MPA decoding, the probability that C2B is \(x\), is:

\begin{equation} \label{eq:11} q_{l} = 1- (1-p_{l})^{(w_{r} -1)} \end{equation}

for an edge connected to a degree \(w_{r}\) check node. When it comes to an irregular Tanner graph, the probability that an edge is connected to a degree \(w_{r}\) check node is \( \rho_{w_{r}} \).

So,

\begin{equation} \label{eq:12} q_{l} =\sum_{i} \rho_{i} ( 1 - (1-p_{l})^{(i-1)} ) = 1 - \sum_{i}\rho_{i} (1-p_{l})^{(i-1)} \end{equation}

Before, we define

\begin{equation} \label{eq:13} \rho(x) = \rho_{2}(x) + \rho_{3}x^{2} + \ldots + \rho_{i}x^{i-1} + \ldots \end{equation}

So,

\begin{equation} \label{eq:14} q_{l} = 1-\rho(1-p_{l}) \end{equation}

Now, let’s check the \(p_{l}\). In the regular LDPC codes on BEC with erasure probability \(\epsilon\), at the \(l\)-th iteration of MPA decoding if all incoming messages are independent, is :

\begin{equation} \label{eq:15} p_{l} = \epsilon (q_{l-1})^{(w_{c} -1)} \end{equation}

When it comes to irregular LDPC codes with the probability that an edge is connected to a bit node of degree \(w_{c}\) is \(\lambda_{w_{c}}\), the \(p_{l}\) can be derived in a straightforward way:

\begin{equation} \label{eq:16} p_{l} = \epsilon\sum_{i}\lambda_{i} (q_{l-1})^{i-1} \end{equation}

We also have the definition of \(\lambda(x)\), So,

\begin{equation} \label{eq:17} p_{l} = \epsilon \lambda(q_{l-1}) \end{equation}

At last, we get

\begin{equation} \label{eq:18} p_{l} = \epsilon \lambda \big( 1- \rho(1-p_{l-1}) \big) \end{equation}

with \(p_{0}=\epsilon\)

3 threshold and stability of density evolution on BEC

According to \ref{eq:18}, we can evaluate the ensemble code with given degree distribution \(\lambda,\rho\) assuming that the graphs are cycle free.

To examine the influence of \(\epsilon\), we define the function:

\begin{equation} \label{eq:24} f(p,\epsilon) = \epsilon\lambda(1- \rho(1-p)) \end{equation}

The erasure probability at iteration \(l\) is then

\begin{equation} \label{eq:25} p_{l}(\epsilon) = f(p_{l-1},\epsilon) \end{equation}

\(f(p,\epsilon)\) is a strictly increasing function in \(p\) for \(\epsilon > 0\) so \(p_{l+1} > p_{l}\).

In particular,

\begin{eqnarray} \label{eq:26} f(0,\epsilon)&=&\epsilon \lambda(1-\rho(1)) = 0 \\
f(1,\epsilon)&=&\epsilon \lambda(1-\rho(1-1)) = \epsilon \end{eqnarray}

Since \(f(p,\epsilon)\) is a strictly increasing function in \(p\)

\begin{equation} \label{eq:27} 0 \leq f(p,\epsilon) \leq \epsilon, \quad \forall p\in [0,1], \forall \epsilon\in [0,1] \end{equation}

Thus, \(p_{\infty}\) will definitely converges to an element \(p_{\infty} \in [0,\epsilon]\).Further, for a degree distribution pair \(\lambda,\rho\) and an \(\epsilon\in [0,1]\), it can be proven that if \(p_{l}(\epsilon) \to 0\) then \(p_{l}(\epsilon^{‘}) \to 0\) for all \(\epsilon < \epsilon^{‘}\). Indeed, there is a value \(\epsilon^{*}\) called the threshold such that for values of \(\epsilon\) below \(\epsilon^{*}\), \(p_{l}\) approaches zero as the number of iterations goes to infinity while for values of \(\epsilon > \epsilon^{*}\) it does not. The threshold, \(\epsilon^{*}\), for \((\lambda,\rho)\) is defined as the supremum of \(\epsilon\) for which \(p_{l}(\epsilon) \to 0\):

\begin{equation} \label{eq:28} \epsilon^{*} (\lambda,\rho) = \sup { \epsilon\in [0.1] :p_{l}(\epsilon)_{l\to \infty} \to 0 } \end{equation}

We wish to find the threshold of an irregular LDPC ensemble with degree distributions:

\begin{equation} \label{eq:29} \lambda(x) = 0.1x + 0.4x^{2} + 0.5x^{19} \end{equation}

and

\begin{equation} \label{eq:30} \rho(x) = 0.5 x^{7} + 0.5 x^{8} \end{equation}

This code has rate:

\begin{equation} \label{eq:31} 1- \frac{\sum_{i}\lambda_{i}/i}{\sum_{i}\rho_{i}/i} \approx 0.5 \end{equation}

By using the recursion of Density evolution, we find that the threshold for this ensemble is an erasure probability between 0.465 and 0.475.

It is easy to find that the density evolution quickly results in very high order as the iteration number is increased. However, to understand its behavior when \(p_{l}\) is small we can approximate it by a Taylor series expansion of the right hand side around 0. i.e.

\begin{equation} \label{eq:32} p_{l} = f(p_{l-1},\epsilon)\approx f^{‘}(p,\epsilon) p_{l-1} \end{equation}

A function \(f(x) = g(h(x))\) has a derivative with respect to \(x\) given by:

\begin{equation} \label{eq:34} \frac{df}{dx} = \frac{dg}{dh} \frac{dh}{dx} \end{equation}

Thus for:

\begin{equation} \label{eq:35} f(p,\epsilon) = \epsilon \lambda(h(p)) \quad h(p) = 1-\rho(1-p) \end{equation}

the derivative with respect to \(p\) is :

\begin{equation} \label{eq:36} \frac{df(p,\epsilon)}{dp} = \frac{d\lambda}{dh} \frac{dh}{dp} \end{equation}

Evaluating this derivative at \(p = 0\) we have that

\begin{equation} \label{eq:37} h(p=0) = 1-\rho(1) =0 \end{equation}

and so

\begin{equation} \label{eq:38} \frac{d\lambda}{dh}\bigg|_{p=0} = \lambda_{2} + 2\lambda_{3}h + \ldots + (i-1)\lambda_{i}h^{(i-2)} + \ldots \bigg|_{h=0} = \lambda_{2} \end{equation}

and

\begin{equation} \label{eq:39} \frac{dh}{dp}\bigg|_{p=0} = \frac{d(1-\rho(1-p)}{dp} \bigg|_{(1-p)=1} = \rho^{‘}(1) \end{equation}

So, we get:

\begin{equation} \label{eq:40} p_{l} \approx \epsilon \lambda_{2}\rho^{‘}(1)p_{l-1}, \quad p_{l} \to 0 \end{equation}

For \(p_{l} \to 0\) as \(l\to \infty\), must have \(p_{l} < p_{l-1} \), and so requires:

\begin{equation} \label{eq:41} \epsilon \lambda_{2}\rho^{‘}(1) < 1 \end{equation}

So \(\lambda_{2}\) is upper bounded by:

\begin{equation} \label{eq:42} \lambda_{2} < \frac{1}{\epsilon \rho^{‘}(1)} \end{equation}

We call (\ref{eq:42}) the stability constraint of density evolution.

4 Density evolution on general memoryless channels

On general memoryless channels, the B2C messages are the LLRs during the MPA. We define LLR as

\begin{equation} \label{eq:19} L(x) = \log \big( \frac{p(x=0)}{p(x=1)} \big) \end{equation}

So the sign of \(L(x)\) determine it is \(0\) or \(1\) and the magnatue of \(|L(x)|\) tell us how sure we are about the decision.

Figure 1 shows a gaussian PDF for \(\mathcal{p}( r)\) and the probability that the bit is “1” is the area of the shade.

Figure 1: a Gaussian PDF

Figure 1: a Gaussian PDF

The LLR are real numbers, so it can be illustrated using a probability density function. We define the PDF for a B2C message at iteration as \(p(M_{l})\) and C2B \(p(E_{l})\). Also, \(p( r)\) as the PDF for the LLR of the received signal corrupted by the channel. Also, we suppose that the message along the edges are I.I.D (This constraint can can be removed when it comes to MET-LDPC).

The output of a bit node is the sum of incoming LLRs on the other edges into that node:

\begin{equation} \label{eq:20} M_{j,i} = \sum_{j^{‘}\in A_{i},j^{‘}\neq j} E_{j^{‘},i} + r_{i} \end{equation}

The probability textbook told us that the PDF of summation of I.I.D random variables is the convolution of the PDF of these random variables. So the PDF of the B2C message can be expressed as:

\begin{equation} p_{M} = p( r) \otimes p(E_{l})^{\otimes(w_{c}-1)} \end{equation}

Considering the irregular LDPC codes and the bit degree distribution \(\lambda(x)\):

\begin{equation} \label{eq:21} p(M_{l}) = p( r) \otimes\sum_{i}\lambda_{i} p(E_{l})^{\otimes(i-1)} = p( r)\otimes \lambda^{\otimes}(p(E_{l})) \end{equation}

Now, there are many efficient ways to evaluate the convolution.

For belief propagation, the function to be evaluated at each check node is show as below:

\begin{equation} \label{eq:22} E_{j,i} = \log \big( \frac{ 1+ \prod_{i^{‘}\in B_{j,i^{‘} \neq i} } tanh (M_{j,i^{‘}}/2)}{ 1- \prod_{i^{‘}\in B_{j,i^{‘} \neq i} } tanh (M_{j,i^{‘}}/2)} \big) \end{equation}

So, to get the PDF of two messages \(x\) and \(y\), we have to caculate the function:

\begin{equation} \label{eq:23} f(x,y) = \log \frac{ 1 + tanh(x/2) tanh(y/2) }{ 1- tanh(x/2)tanh(y/2)} = -\log \frac{ e^{x} + e^{y} }{ 1 + e^{x+y}} \end{equation}

One simple way to use the density evolution on general channels is to assume tht the original codeword was all zeros. So that the probability that the bit is in error is the probability that the LLR is negative.

One more thing, although the PDFs at the beginning of iteration is Gaussian, the result of the convolution of Gaussian PDFs is not Gaussian except in the limit. However, for the sake of simplicity, we assume that after convolution the PDFs remain Gaussian. The truth make Gaussian easy to use that we can use mean and variance to describe Gaussian. So that we can only track the mean and variance of the PDFs during the iteration.

4.1 get an excellent degree distribution

Using density evolution, we can analyze the threshold of an LDPC ensemble. However, for a code designers, the question more urging is which degree distribution will produce the best threshold.

In general, the more irregular, the better. Accroding to work of Sae-Young Chung, Forney, Richardson and Urbanke, there is only an 0.0045dB gap between Shannon limit and the irregular LDPC they designed. For that LDPC code, it has a codewordlength of \(10^{7}\) and degree varying from 2 to 8000.

Because \(H\) is sparse, a large proportion of degree-2 bit nodes are required to guarentee the low density. It can be shown that a degree distribution with a good threshold will contain a few very high degree bit nodes, many degree two nodes, but no more than allowed for by stability, and some nodes with degree between these.

5 Summary

In this post, we analyze density evolution for regular and irregular LDPC codes based on BEC and memoryless channel. As a tool for designing and analyzing LDPC matrix, density evolution plays a foundamental role and helps researchers find many LDPC matrices of good performance.

However, the drawback of density evolution includes: 1. assumption of cycle-free tanner graph, which is hard to be satisfied in reality; 2. assumption of infinite length of codeword, which is also hard to be satisfied; 3. extremely high computational complexity, which makes it hard to use and results in many simplied and effective alternatives which are out of this post’s scope.

We will meet density evolution again!!!

comments powered by Disqus