Degree-degree Correlated Low-density Parity-check Codes Over a Binary Erasure Channel

Low-density parity-check (LDPC) codes, first introduced by R. Gallager in 1962 [1], have been widely used in practice, including the 5G new radio wireless communication standard (see, e.g., [2, 3]) and the flash-memory systems (see, e.g., [4, 5]). LDPC codes are linear block codes that can be characterized by either a generator matrix or a parity-check matrix. It is well-known that there is a one-to-one mapping between the generator matrix and the parity-check matrix (see, e.g., Section II.B of the survey paper [6]). In particular, for an $(n,k)$-LDPC code, there are $k$ information bits in a codeword of $n$ bits. The $n\times k$ generator matrix then maps the $k$ information bits to the $n$ codeword bits by multiplying the vector of the information bits with the generator matrix. On the other hand, the $n\times(n-k)$ parity-check matrix can be used for checking whether an $n$-bit binary vector is a legitimate codeword and decoding the $k$ information bits from that codeword.

The $n\times(n-k)$ parity-check matrix associated with an $(n,k)$-LDPC code can be represented by a bipartite graph, commonly known as the Tanner graph [7]. For such a bipartite graph, there are $n$ variable nodes on one side and $n-k$ check nodes on the other side. A check node represents a constraint on the values of variable nodes connected to that check node. In particular, for binary-valued variables, the value of a check node is simply the checksum of the values of the variable nodes connected to that check node. For a legitimate codeword, the checksums of the $n-k$ check nodes are all 0’s. In other words, multiplying a codeword with the parity-check matrix yields a vector with all 0’s.

Performance analysis of LDPC codes over a binary erasure channel (BEC) has been studied extensively in the literature (see e.g., [8, 9, 10, 11]). For a BEC with the erasure probability $\delta$, each bit in a codeword is erased independently with probability $\delta$. To recover the erased code bits, one can apply an iterative decoding (peeling) algorithm described below. First, the values of the non-erased variable nodes are added to the check nodes connected to them. Subsequently, these non-erased nodes and their edges are removed. The remaining bipartite graph consists only of erased variable nodes. An erased variable node connected to a check node with degree 1 can be decoded by the value of that check node. Upon successful decoding, the erased variable node becomes a non-erased node and can be removed similarly to the original non-erased nodes. Repeat this process until no more erased variable nodes can be decoded.

A probabilistic framework for analyzing the iterative algorithm is known as the density evolution method [9, 10, 11]. Such a method tracks the probability that the variable end of a randomly selected edge is not decoded after each iteration. The evolution of such a probability is characterized by the degree distribution of a randomly selected variable node and that of a randomly selected check node. The density evolution method can also be extended to provide unequal error protection of code bits [12, 13, 14, 15, 16]. For the setting with unequal error protection, code bits are classified into several classes, and the density evolution method tracks the probability that the variable end of a randomly selected edge in each class is not decoded after each iteration.

One common assumption used in the density evolution method for LDPC codes is that the degree distributions of the two ends of a randomly selected edge are independent. It seems that the effect of the degree-degree correlation of a randomly selected edge on LDPC codes has not been studied. One possible reason is that LDPC codes are (nearly) capacity-achieving codes when the degree distributions are optimized [17, 18, 19]. However, the optimized degree distributions are in general highly irregular [20, 10, 19, 21], and the throughput performance of regular LDPC codes is worse than irregular LDPC codes. The relaxation from independent degree distributions to a general bivariate distribution allows us to improve the performance of LDPC codes in the literature.

The main objective of this paper is to study the effect of the degree-degree correlation of a randomly selected edge on LDPC codes over a BEC. We summarize our contributions as follows:

• •

  Construction: As a generalization of the configuration model (with independent degree distributions) [22], we propose two constructions of random LDPC codes (bipartite graphs) with degree-degree correlations. The first construction, called the block construction in this paper, is an extension of the construction for uni-partite graphs in [23]. For such a model, we derive a closed-form expression of the degree-degree bivariate distribution of the two ends of a randomly selected edge. The second construction, called the general construction, is more general than the first one, and it can construct random LDPC codes with a specified degree-degree bivariate distribution. By classifying edges with the same degrees in the variable end and the check end into one specific type of edges, the second construction can be viewed as a special class of the multi-edge type LDPC codes in [24] that automatically satisfy the stub count constraints.

• •

  Analysis: It is known that the density evolution method is generally difficult to be applied to the multi-edge type LDPC codes as the densities of various types are convolved. However, by using the degree-degree bivariate distribution, we can average over the (convolved) densities of various edge types into a single node type. As such, we derive a system of density evolution equations over a BEC. Such an extension covers the independent case as a special case. From these systems of density evolution equations, we derive lower bounds on the maximum tolerable erasure probability (such that every code bit is recovered with high probability).

• •

  Effect of correlation: By conducting extensive numerical experiments, we show the effect of the degree-degree correlation on the performance of LDPC codes. Our numerical results show that optimizing negative correlation can achieve a much higher maximum tolerable erasure probability than LDPC codes with independent degree distributions. This implies that partially regular LDPC codes [13] with degree-degree correlation might be good enough for practical use.

• •

  Performance improvement: By taking the degree-degree correlation into consideration, we can further improve the best-known result for the maximum tolerable erasure probability in the literature. In particular, we show that under the same marginal degree distributions of the variable ends and the check ends in [25], the maximum tolerable erasure probability can be extended from 0.49553 to 0.49568.

Instead of assuming that the degree of the variable end and the degree of the check end of a randomly selected edge are independent in [10]. In this section, we construct a random bipartite graph with a specific degree-degree correlation. Suppose that there are $n$ variable nodes and $n-k$ check nodes. Let $p_{X}(x)$ (resp. $p_{Y}(y)$) be the degree distribution of a randomly selected variable node $X$ (resp. check node $Y$). Also, let ${\bf\sf E}[X]=\sum_{x}xp_{X}(x)$ (resp. ${\bf\sf E}[Y]=\sum_{y}yp_{Y}(y)$) be the average degree of a randomly selected variable node (resp. check node). Following the argument for the configuration model in [22], we generate $np_{X}(x)$ variable nodes with degree (stub) $x$ and $(n-k)p_{Y}(y)$ check nodes with degree (stub) $y$. Then the total number of stubs for variable nodes is $\sum_{x}nxp_{X}(x)$, and the total number of stubs for check nodes is $\sum_{y}(n-k)yp_{Y}(y)$. Suppose that

In this paper, we let

when the identity in (1) is satisfied.

In this section, we extend the density evolution analysis for LDPC codes with degree-degree correlations. It is known that the density evolution analysis is generally difficult to be applied to the multi-edge type LDPC codes as the densities of various types are convolved. However, by using the conditional probabilities derived in the previous section, we can average over the (convolved) densities of various edge types into a single node type.

Now we derive the density evolution equations in the setting where $G$ is fixed and $n\to\infty$. Consider using a degree-degree correlated LDPC code over a binary erasure channel with the erasure probability $\delta$. Let $\alpha_{x}^{(i)}$ be the probability that the variable end of a randomly selected edge with degree $x$ is not decoded after the $i^{th}$ iteration, and $\beta_{y}^{(i)}$ be the probability that the check end of a randomly selected edge with degree $y$ is not decoded after the $i^{th}$ iteration. Analogous to the AND-OR argument in [8, 9], we have

Clearly, $\alpha_{x}^{(0)}=\delta$ for all $x$ (as every variable bit is erased independently with probability $\delta$ through the erase channel). Similarly,

Combining these two equations, we have a system of nonlinear recursive equations:

with $\alpha_{x}^{(0)}=\delta$ for all $x$.

Let $\gamma_{x}^{(i)}$ be the probability that a randomly selected variable node with degree $x$ is successfully decoded after the $i^{th}$ iteration. Note that a randomly selected variable node is not decoded after the $i^{th}$ iteration if and only if the variable node is erased and all the check ends of its $x$ edges are not decoded after the $i^{th}$ iteration. Thus,

Let $\gamma^{(i)}$ be the probability that a randomly selected variable node is successfully decoded after the $i^{th}$ iteration. Then

As in [10], we are interested in the maximum tolerable erasure probability $\delta^{*}$ such that for all $\delta<\delta^{*}$,

Since the capacity of the BEC with the erasure probability $\delta$ is known to be $1-\delta$ [27], we know that $\frac{k}{n}\leq 1-\delta^{*}$. In view of (2), we have

In view of (III) and (23), a sufficient condition for (27) is

for all $x$. In the following theorem, we show a lower bound for $\delta^{*}$. The proof can be found in Appendix B.

In this paper, we proposed two constructions of degree-degree correlated LDPC codes and derived the density evolution equations for such LDPC codes. For the block construction, our numerical results show that adding a negative degree-degree correlation can achieve a much higher maximum tolerable erasure probability than LDPC codes with independent degree distributions. Moreover, adding a negative degree-degree correlation could lead to better designs of LDPC codes with the UEP property. The general construction (with an arbitrary bivariate degree-degree distribution) provides a much larger ensemble of LDPC codes than block construction. It can lead to performance improvement over the existing LDPC codes with independent degree-degree distributions.

Our future work will extend our (density evolution) analysis for degree-degree correlated LDPC codes to more general multi-edge type LDPC codes. This will include convolutional LDPC codes (see, e.g., [29, 30]) with multiple node types.