Degree-degree Correlated Low-density Parity-check Codes and Their Extensions

I. INTRODUCTION

LOW-density parity-check (LDPC) codes, first introduced by R. Gallager in 1962 [2], have been widely used in practice, including the 5G new radio wireless communication standard (see, e.g., [3], [4]), application-specific integrated circuit (ASIC) implementation, and flash-memory systems (see, e.g., [5], [6]). Crucial for efficient and reliable communication systems, especially in 5G applications, LDPC codes offer improved error correction capabilities and higher throughput. Their flexible structure enables efficient implementation in ASICs, supporting the diverse and high-performance demands of 5G networks [7]. A recent application of LDPC codes for rate-diverse multiple access is detailed in [8].

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 [9]). In particular, for an (n, k)-LDPC code, there are k information bits in a codeword of n bits. The n × 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 × (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 × (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 [10]. 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., [11]–[14]). For a BEC with the erasure probability δ, each bit in a codeword is erased independently with probability δ. To recover the erased code bits, one can apply an iterative decoding (peeling) algorithm described below. One first adds the values of the non-erased variable nodes to the check nodes connected to them. Then remove all these nonerased nodes and their edges. The remaining bipartite graph only consists 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. Once decoded, it becomes a non-erased variable node and can be removed in the same way as the initial non-erased variable nodes. The process is repeated until no more erased variable nodes can be decoded.

A probabilistic framework for analyzing the iterative algorithm is known as the density evolution method [12]–[14]. 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 [15]–[19]. 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 important ensemble of random LDPC codes is the class of irregular LDPC codes that are characterized by the generating function of the (excess) degree distribution of the variable nodes [TeX:] $$\lambda(z)$$ and the generating function of the (excess) degree distribution of the check nodes [TeX:] $$\rho(z)$$. From these two generating functions, the number of stubs (or known as sockets) for each node is specified, and a random bipartite graph is then generated by randomly pairing these stubs. Such a method of generating a random bipartite graph is known as the configuration model in the book [20]. For an irregular LDPC code over a BEC with the erasure probability δ, it is known (see, e.g., [13]) that every code bit can be recovered (with high probability) if

for all [TeX:] $$z \in(0, \delta).$$ The largest δ stisfying (1) is called the maximum tolerable erasure probability [TeX:] $$\delta^*$$ (also known as the percolation threshold). The optimization problem is to find the two degree distributions [TeX:] $$\lambda(z) \text{ and } \rho(z)$$ so that [TeX:] $$\delta^*$$ can be maximized with a given code rate k/n.

LDPC codes are known to be (nearly) capacity-achieving codes when the degree distributions are optimized [21]–[23]. However, the optimized degree distributions are in general highly irregular [13], [23]–[25], 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. To further improve the performance of LDPC codes, the framework of multi-edge type LDPC (MET-LDPC) codes was proposed in [26]. Instead of using a single edge type in the irregular LDPC codes, there are multiple edge types in the MET-LDPC codes. Stubs of the same edge type are paired together to from edges in the bipartite graph. For an MET-LDPC codes with [TeX:] $$n_e$$ edge types, one has the freedom to specify the probability of a node to have [TeX:] $$d_k$$ type k edges, [TeX:] $$k=1,2, \cdots, n_e.$$ However, these probabilities need to be carefully chosen so that the number of stubs of the same type at the variable nodes is the same as that at the check nodes (the socket count equality constraint in [26]). Moreover, such a generalization also complicates the analysis as both the degree distributions of the variable nodes and the check nodes are now functions with [TeX:] $$n_e$$ variables. As the densities of various edge types are convolved [26], the density evolution method is generally difficult to be applied to the MET-LDPC codes, and one has to resort to approximation algorithms (see, e.g., [27]). However, the optimal percolation thresholds found by approximation algorithms are often different from the true ones [27]. Another drawback of MET-LDPC codes is that it is not straightforward to improve the performance directly from a good irregular LDPC code with two given degree distributions [TeX:] $$\lambda(z) \text{ and } \rho(z)$$.

Our idea to alleviate the problems of MET-LDPC codes is to exploit degree-degree correlations of bipartite graphs. In an irregular LDPC code, the two degree distributions [TeX:] $$\lambda(z) \text{ and } \rho(z)$$ of the two ends of a randomly selected edge are assumed to be independent. Instead of characterizing a random ensemble of LDPC codes by two independent degree distributions, we characterize it by a general degree-degree bivariate distribution (of the two ends of a randomly selected edge). An ensemble of LDPC codes with a given degree-degree bivariate distribution is called a degree-degree correlated LDPC code in this paper.

By classifying edges with the same degrees in the variable end and the check end into one specific type of edges, a degree-degree correlated LDPC code can be viewed as a variant of MET-LDPC codes with multiple variable node types and multiple check node types. Note that the original METLDPC codes in [26] has only one check node type. Degreedegree correlated LDPC codes have the following advantages over the MET-LDPC codes: (i) The bivariate distribution automatically satisfies the socket count equality constraints, (ii) the density evolution analysis is a simple extension of that for irregular LDPC codes, (iii) the exact percolation threshold can be easily computed for a BEC, and (iv) it is straightforward to improve the performance directly from a good irregular LDPC code with two given degree distributions [TeX:] $$\lambda(z) \text{ and } \rho(z).$$

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) [20], 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 [28]. 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 case of the multi-edge type LDPC codes in [26].

· 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 [16] 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 [29], the maximum tolerable erasure probability can be extended from 0.49553 to 0.49568.

· Generalization: We propose generalizing degree-degree correlated LDPC codes to MET-LDPC codes with multiple variable node types and multiple check node types. Unlike the original construction of MET-LDPC codes that have fixed edge types in [26], the ensemble of our MET-LDPC codes is generated with independently selected edge types. Since edge types are independently selected, they can be averaged using conditional probabilities, as in our analysis for degree-degree correlated LDPC codes. As illustrative examples, we show how convolutional LDPC codes (see, e.g., [30], [31]) and the spatially coupled IRSA with multiple classes of users and receivers [32], [33] can be constructed using this extension.

The rest of the paper is organized as follows. In Section II, we propose two constructions for degree-degree correlated random LDPC codes. In Section III, we conduct the density evolution analysis for LDPC codes with degree-degree correlations. In Section IV, we generalize degree-degree correlated LDPC codes to MET-LDPC codes with independently selected edge types, and this includes the convolutional LDPC codes and spatially coupled IRSA with multiple classes of users and receivers. We evaluate the performance of the degree-degree correlated LDPC codes in Section V. The paper concludes in Section VI, where we discuss potential future research directions.

II. CONSTRUCTION OF DEGREE-DEGREE CORRELATED RANDOM LDPC CODES

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 [13]. 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 [TeX:] $$p_X(x)$$ (resp. [TeX:] $$p_Y(y)$$) be the degree distribution of a randomly selected variable node X (resp. check node Y ). Also, let [TeX:] $$\mathrm{E}[X]=\sum_x x p_X(x)$$ (resp. [TeX:] $$\mathrm{E}[Y]=\sum_y y p_Y(y)$$ be the average degree of a randomly selected variable node (resp. check node). Following the argument for the configuration model in [20], we generate [TeX:] $$n p_X(x)$$ variable nodes with degree (stub) [TeX:] $$x \text { and }(n-k) p_Y(y)$$ check nodes with degree (stub) y. Then the total number of stubs for variable nodes is [TeX:] $$\sum_x n x p_X(x)$$, and the total number of stubs for check nodes is [TeX:] $$\sum_y(n-k) y p_Y(y)$$. Suppose that

In this paper, we let

when the identity in (2) is satisfied. Note that the code rate k/n is simply 1 − 1/G.

A. Block Construction

In this section, our construction for such a bipartite graph is similar to the block construction of degree-degree correlated random networks in [28]. Assume that (2) holds. We arrange the [TeX:] $$n \mathrm{E}[X]$$ stubs of the variable nodes in descending order and partition the [TeX:] $$n \mathrm{E}[X]$$ stubs into b blocks evenly, each with [TeX:] $$n \mathrm{E}[X] / b$$ stubs. In each block of [TeX:] $$n \mathrm{E}[X] / b$$ stubs, we randomly select [TeX:] $$q n \mathrm{E}[X] / b$$ stubs as type 1 stubs, where the parameter q is a design parameter for controlling the degreedegree correlation. The remaining [TeX:] $$(1-q) n \mathrm{E}[X] / b$$ stubs in that block are classified as type 2 stubs. Similarly, we arrange the [TeX:] $$(n-k) \mathrm{E}[Y]$$ stubs of the check nodes in descending order and partition the [TeX:] $$(n-k) \mathrm{E}[Y]$$ stubs into b blocks evenly, each with [TeX:] $$(n-k) \mathrm{E}[Y] / b$$ stubs. In each block of [TeX:] $$(n-k) \mathrm{E}[Y] / b$$ stubs, we randomly select [TeX:] $$q(n-k) \mathrm{E}[Y] / b$$ stubs as type 1 stubs and the remaining [TeX:] $$(1-q)(n-k) \mathrm{E}[Y] / b$$ stubs as type 2 stubs. These two types of stubs will be connected differently to form degree-degree correlation.

Consider a permutation π of [TeX:] $$\{1,2, \cdots, b\}$$ For [TeX:] $$i=1,2, \cdots, b$$ we randomly select a type 1 stub from the ith block of variable nodes and another type 1 stub from the [TeX:] $$\pi(i)$$th block of check nodes and connect these two stubs to form an edge. Repeat the process until all the type 1 stubs are connected. For type 2 stubs, the connection is independent, i.e., we randomly select a type 2 stub of variable nodes and another type 2 stub of check nodes and connect these two stubs to form an edge. It is clear that the marginal distribution of the degree of the variable end (of a randomly selected edge) is

and the marginal distribution of the degree of the check end (of a randomly selected edge) is

Assume that all the nodes with the same degree are in one common block. Let [TeX:] $$S_X(i)$$ (resp. [TeX:] $$S_Y(i)$$), [TeX:] $$i=1,2, \cdots, b,$$ be the set of degrees in the ith block of variable nodes (resp. check nodes). Now we compute the conditional probability [TeX:] $$\mathrm{P}\left(Y_e=y \mid X_e=x\right).$$ Suppose that [TeX:] $$x \in S_X(i)$$ for some i. If [TeX:] $$y \notin S_Y(\pi(i)),$$ then an edge with degree x at the variable end and degree y at the check end can only be formed by type 2 stubs. The number of type 2 stubs of the check nodes with degree y is [TeX:] $$(1-q)(n-k) y p_Y(y),$$ and the total number of type 2 stubs is [TeX:] $$(1-q)(n-k) \mathrm{E}[Y].$$ The probability that a stub of the variable nodes is of type 2 is 1 − q. Thus, for [TeX:] $$x \in S_X(i)$$ and [TeX:] $$y \notin S_Y(\pi(i)),$$

If [TeX:] $$y \in S_Y(\pi(i)),$$ then an edge with degree x at the variable end and degree y at the check end can also be formed by type 1 stubs. The number of type 1 stubs of the check nodes with degree y is [TeX:] $$q(n-k) y p_Y(y),$$ and the total number of type 1 stubs in the [TeX:] $$\pi(i)$$th block of check nodes is [TeX:] $$q(n-k) \mathrm{E}[Y] / b.$$ The probability that a stub of the variable nodes is of type 1 is q. Adding the probability formed by type 1 stubs in (6), we have for [TeX:] $$x \in S_X(i) \text { and } y \in S_Y(\pi(i)),$$

Then, we have from (4), (5), (6), and (7) that for [TeX:] $$x \in S_X(i),$$

Example 1: (Two types of degrees) Suppose that there are n/3 variable nodes with degree 2d, and 2n/3 variable nodes with degree d. Also, there are (n − k)/3 check nodes with degree 2Gd, and 2(n − k)/3 check nodes with degree Gd, where G = n/(n − k) is a positive integer. Using the construction in Section II-A, we have E[X] = 4d/3, E[Y] = 4Gd/3 so that the condition in (2) is satisfied. Now we partition the stubs into two blocks, i.e., b = 2. The first block consists of variable nodes with degree 2d (resp. check nodes with degree 2Gd), and the second block consists of variable nodes with degree d (resp. check nodes with degree Gd). For the permutation π with π(1) = 2 and π(2) = 1, we have from (4) and (8) that

Note that the degree-degree correlation can be computed as follows:

Thus, the degree-degree correlation is negatively correlated for the permutation π with π(1) = 2 and π(2) = 1. On the other hand, it is positively correlated for the permutation π with π(1) = 1 and π(2) = 2. An illustration of the construction of the bipartite graph is shown in Fig. 1, where the red (resp. black) edges are formed by type 1 (resp. 2) stubs.

B. General Construction

In this section, we propose a general construction from the degree-degree bivariate distribution [TeX:] $$\mathrm{P}\left(X_e=x, Y_e=y\right).$$ Given such a bivariate distribution, we first compute the two marginal distributions:

and

Then we use the marginal distribution in (11) and (4) to compute the degree distribution of X:

Similarly, we have from the marginal distribution in (12) and (5) that

From (13) and (14), we have

Choose n and k so that the condition in (3) is satisfied. It then follows from (3), (4), and (5) that

Note that [TeX:] $$n x p_X(x)$$ is the number of stubs of variable nodes with degree x, and [TeX:] $$(n-k) y p_Y(y)$$ is the number of stubs of check nodes with degree y. Among these stubs, we can randomly select [TeX:] $$n x p_X(x) \mathrm{P}\left(Y_e=y \mid X_e=x\right)$$ stubs from the variable nodes and [TeX:] $$(n-k) y p_Y(y) \mathrm{P}\left(X_e=x \mid Y_e=y\right)$$ stubs from the check nodes, and connect them at random (as in the configuration model). As the number of edges between a variable node with degree x and a check node with degree y is [TeX:] $${nxp}_X(x) \mathrm{P}\left(Y_e=y \mid X_e=x\right)$$ and the total number of edges is [TeX:] $$n \mathrm{E}[X],$$ the probability that a randomly selected edge has degree x in its variable end and degree y in its check end is (cf. (17))

It is of interest to point out the connections between our construction and the multi-edge type LDPC codes in [26]. By classifying edges with degree x in the variable end and degree y in the check end into one specific type of edges, our construction is a special case of the multi-edge type LDPC codes in [26]. However, as pointed out in [26], [34], 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). By using the degree-degree bivariate distribution, we will show in Section III that one can average over the (convolved) densities of various edge types into a single node type (that only depends on its node degree). Thus, the computational complexity of the density evolution method can be greatly reduced.

Example 2: (Two types of degrees) Consider the following bivariate distribution:

where [TeX:] $$0 \leq p_2 \leq 1 / 2$$ and [TeX:] $$0 \leq p_1 \leq 1-2 p_2.$$

From (15), it follows that

Thus, the condition in (3) is satisfied.

From (20), we know that

It is easy to see that (22) recovers (9) by letting [TeX:] $$p_1=\frac{1-q}{4},$$ [TeX:] $$p_2=\frac{1+q}{4}, d_1=2 d \text { and } d_2=d.$$ As such, the construction in this example is more general than that in Example 1.

Similarly, from (20), it follows that

To construct a random LDPC code with the six input parameters [TeX:] $$p_1, p_2, d_1, d_2, G \text {, and } n$$ in this example, one can classify the [TeX:] $$n \mathrm{E}[X]$$ edges (with [TeX:] $$\mathrm{E}[X]$$ in (21)) into the four edge types (x, y) (with degree x in the variable end and degree y in the check end): [TeX:] $$\left(d_1, G d_1\right),\left(d_1, G d_2\right),\left(d_2, G d_1\right)$$ and [TeX:] $$\left(d_2, G d_2\right).$$ For each edge type, connect the stubs in the variable nodes and the stubs in check nodes by using the configuration model. An illustration of the construction is shown in Fig. 2, where the bold lines represent edges connected among the four edge types.

III. DENSITY EVOLUTION IN CORRELATED LDPC CODES

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 [TeX:] $$n \rightarrow \infty.$$ Consider using a degree-degree correlated LDPC code over a binary erasure channel with the erasure probability δ. Let [TeX:] $$\alpha_x^{(i)}$$ be the probability that the variable end of a randomly selected edge with degree x is not decoded after the ith iteration, and [TeX:] $$\beta_y^{(i)}$$ be the probability that the check end of a randomly selected edge with degree y is not decoded after the ith iteration. Analogous to the AND-OR argument in [11], [12], we have

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

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

with [TeX:] $$\alpha_x^{(0)}=\delta$$ for all x.

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

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

As in [13], we are interested in the maximum tolerable erasure probability [TeX:] $$\delta^*$$ such that for all [TeX:] $$\delta \lt \delta^* \text {, }$$

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

In view of (28) and (25), a sufficient condition for (29) is

for all x. In the following theorem, we show a lower bound for [TeX:] $$\delta^*.$$

Theorem 1: Let [TeX:] $$d_{v, \min }$$ be the minimum degree of a variable node and [TeX:] $$d_{c, \max }$$ be the maximum degree of a check node. If [TeX:] $$d_{v, \min } \geq 2$$ and [TeX:] $$\delta\lt 1 /\left(d_{c, \text { max }}-1\right),$$ then [TeX:] $$\lim _{i \rightarrow \infty} \alpha_x^{(i)} \rightarrow 0$$ for all x.

Proof. Note from (25) that

Since [TeX:] $$\alpha_x^{(0)}=\delta,$$ one can easily show by induction (from (25) and (24)) that for all i

Let [TeX:] $$\alpha_{\max }^{(i)}=\max _x \alpha_x^{(i)} \text { and } \beta_{\max }^{(i)}=\max _y \beta_y^{(i)}.$$ Using the inequality that [TeX:] $$(1-z)^k \geq 1-k z \text { for all } z \geq 0,$$ we have from (25) that

It follows from (33) that

On the other hand, we have from (24) and (35) that

Since we assume that [TeX:] $$\left(d_{c, \max }-1\right) \delta\lt 1,$$ it follows from (36) that

Thus,

Since [TeX:] $$d_{v, \min } \geq 2 \text { and }\left(d_{c, \max }-1\right) \delta\lt 1,$$ we have from (38) and [TeX:] $$\alpha_x^{(0)}=\delta$$ that

Thus, [TeX:] $$\alpha_{\max }^{(i)}$$ converges to 0 when [TeX:] $$i \rightarrow \infty.$$

IV. EXTENSIONS

A. MET-LDPC Codes with Independently Selected Edge Types

In this section, we extend the framework for DDC-LDPC codes. For a DDC-LDPC code, we can classify (i) the variable nodes with degree x as type x variable nodes, (ii) the check nodes with degree y as type y check nodes, and (iii) the edges between a variable node with degree x and a check node with degree y as type (x, y) edges. Viewing it this way, the DDCLDPC code can be considered as a MET-LDPC code with multiple types of variable nodes and check nodes. Inspired by this perspective, we propose to generalize DDC-LDPC codes to MET-LDPC codes with multiple variable node types and multiple check node types. Unlike the original construction of MET-LDPC codes that have fixed edge types in [26], the ensemble of our MET-LDPC codes is generated with independently selected edge types. As edge types are independently selected, they can be averaged using conditional probabilities as described in Section III, thereby significantly reducing the number of recursive equations required for density evolution.

Specifically, we assume there are [TeX:] $$n_V$$ types of variable nodes, [TeX:] $$n_C$$ types of check nodes, and [TeX:] $$n_E$$ types of edges. We specify the following probabilities:

· [TeX:] $$p_0(v)$$: The probability that a randomly selected variable node is of type [TeX:] $$v, v=1,2, \cdots, n_V.$$

· [TeX:] $$p_1(d \mid v)$$: The probability that a type v variable node has degree d.

· [TeX:] $$p_2(e \mid v)$$: The probability that an edge of a type v variable node is a type e edges, [TeX:] $$e=1,2, \cdots, n_E.$$

· [TeX:] $$q_0(c)$$: The probability that a randomly selected check node is of type [TeX:] $$c, c=1,2, \cdots, n_C.$$

· [TeX:] $$q_1(d \mid c)$$: The probability that a type c check node has degree d.

· [TeX:] $$q_2(e \mid c)$$: The probability that an edge of a type c check node is a type e edges, [TeX:] $$e=1,2, \cdots, n_E.$$

When n and n − k are large, there are roughly [TeX:] $$n p_0(v)$$ type v variable nodes and [TeX:] $$(n-k) q_0(c)$$ type c check nodes. The expected degree of a type v variable node (resp. a type c check node) is [TeX:] $$\sum_d d p_1(d \mid v)$$ (resp. [TeX:] $$\sum_d d q_1(d \mid c)$$). The expected number of type e edges of a type v variable node is then [TeX:] $$\sum_d d p_1(d \mid v) p_2(e \mid v).$$ Similarly, the expected number of type e edges of a type c check node is [TeX:] $$\sum_d d q_1(d \mid c) q_2(e \mid c).$$ To construct a (n, k)-LDPC code, the number of type e edges of the n variable nodes must be the same as that of the n − k check nodes for all [TeX:] $$e=1,2, \cdots, n_E.$$ This leads to the following socket (stub) count equality constraints:

[TeX:] $$e=1,2, \cdots, n_E.$$ As in [26], stubs of the same edge type are randomly paired together (as in the configuration model) to from edges in the bipartite graph.

One key property that does not exist in the original METLDPC codes in [26] is the conditional probabilities defined in the following lemma. We will use the results from this lemma to simplify the derivation of the density evolution equations.

Lemma 2: Let [TeX:] $$p(c \mid v)$$ be the probability that a randomly selected edge of a type v variable node is connected to a type c check node. Then

Let [TeX:] $$p(v \mid c)$$ be the probability that a randomly selected edge of a type c check node is connected to a type v variable node. Then

Proof. We follow the standard argument for the configuration model [20]. Note that the expected number of type e stubs of type c check nodes is

Summing over all the [TeX:] $$n_C$$ types of check nodes, we know that the expected total number of type e stubs of check nodes is

Given that a randomly selected edge of a type v variable node is a type e edge, the probability that it is connected to a type c check node is

Thus, summing over all [TeX:] $$n_E$$ types, we derive (41).

The argument for (42) is the same and thus omitted.

Now we extend the density evolution analysis in Section III. Note that once we obtain the connection probabilities in Lemma 2, edge types no longer play a role in the analysis, and we do not need to track the densities of edge types.

Consider using such a random LDPC code over a binary erasure channel with the erasure probability δ. Denote by [TeX:] $$\alpha_v^{(i)}$$ the probability that the variable end of a randomly selected edge is a type v variable node and it is not decoded after the ith iteration. Clearly, [TeX:] $$\alpha_v^{(0)}=\delta$$ for all v (as every variable bit is erased independently with probability δ through the erasure channel). Similarly, denote by [TeX:] $$\beta_c^{(i)}$$ the probability that the check end of a randomly selected edge is a type c check node and it is not decoded after the ith iteration. Let

be the excess degree distribution of a type v variable node and

be its generating function. Also, let

be the excess degree distribution of a type c check node and

Analogous to the density evolution analysis in Section III, we can extend (24) and (25) as follows:

and

B. Convolutional LDPC Codes

Convolutional LDPC codes that exploit spatial coupling were shown to have better performance than regular LDPC codes (see, e.g., [30], [31]). In this section, we show how to construct a convolutional LDPC code from the MET-LDPC code described in Section IV-A.

Consider an irregular (n, k)-LDPC code characterized by the generation functions of the two degree distributions [TeX:] $$\lambda(z)$$ and [TeX:] $$\rho(z).$$ Note that [TeX:] $$\lambda(z)$$ and [TeX:] $$\rho(z)$$ need to be chosen to meet the socket count equality constraint in (2). This irregular LDPC code is viewed as a base random bipartite graph for the construction of a convolutional (nL, kL)-LDPC code.

For the MET construction of the (nL, kL)-LDPC code, there are L types of variable nodes, L types of check nodes, and L types of edges. We specify the following probability.

· [TeX:] $$p_0(v)$$: The probability that a randomly selected variable node is of type v is equal to 1/L, for [TeX:] $$v=1,2, \cdots, L.$$

· [TeX:] $$p_1(d \mid v)$$: The probability that a type v variable node has degree d is characterized by the generating function of the excess degree distribution [TeX:] $$\lambda(z)$$, for [TeX:] $$v=1,2, \cdots, L.$$

· [TeX:] $$p_2(e \mid v)$$: The probability that an edge of a type v variable node is a type e edges is [TeX:] $$1-\eta$$ if e = v, and η if e = ((v + 1) mod L), for [TeX:] $$v=1,2, \cdots, L.$$

· [TeX:] $$q_0(c)$$: The probability that a randomly selected check node is of type c is equal to 1/L, for [TeX:] $$c=1,2, \cdots, L.$$

· [TeX:] $$q_1(d \mid c)$$: The probability that a type c check node has degree d is characterized by the generating function of the excess degree distribution [TeX:] $$\rho(z)$$, for [TeX:] $$c=1,2, \cdots, L.$$

· [TeX:] $$q_2(e \mid c)$$: The probability that an edge of a type c check node is a type e edges is 1 if e = c, for [TeX:] $$c=1,2, \cdots, L.$$ That is, type e edges are connected to type e check nodes.

When n and n−k are very large, there are roughly n type v variable nodes and n − k type c check nodes. Intuitively, one may view type v variable nodes are the set of variable nodes indexed from n(v − 1) + 1 to nv, [TeX:] $$v=1,2, \cdots, L.$$ and type c check nodes are the set of check nodes indexed from [TeX:] $$(n-k)(c-1)+1 \text { to }(n-k) c, c=1,2, \cdots, L.$$ As such, we can view the construction of the (nL, kL)-LDPC code as a concatenation of L copies of the irregular (n, k)-LDPC codes. However, the trick is to rewire some edges to make these L copies convoluted. With probability η, an edge in the vth copy is rewired randomly to the ((v + 1) mod L)th copy.

It is easy to see that all the socket count equality constraints in (40) are satisfied from the socket count equality constraint in (2).

To make such a MET-LDPC code a convolutional LDPC code, we puncture type L variable nodes and remove all the edges connected to type L variable nodes. Such a puncturing yields a [TeX:] $$n(L-1) \times(n-k) L$$ parity-check matrix. Since type 1 edges between type L variable nodes and type 1 check nodes are removed, it is easy to see that for [TeX:] $$v=1,2, \cdots, L-1,$$

On the other hand, for [TeX:] $$c=2, \cdots, L-1,$$

For c = v = 1, we have [TeX:] $$p(v \mid c)=1$$ (since type 1 edges between type L variable nodes and type 1 check nodes are removed). For c = L, v = L − 1, we also have [TeX:] $$p(v \mid c)=1$$ (since type L edges between type L variable nodes and type L check nodes are removed). The puncturing step is crucial in improving the performance. The insight for that is like the the double-zipper ZigZag decoding algorithm (see, e.g., [36], [37]) that starts the decoding from the two ends and then propagates toward to the central part of the code.

For [TeX:] $$v=1, 2, \cdots, L-1,$$ we still have [TeX:] $$\lambda_v(z)=\lambda(z).$$ With the type 1 edges between type L variable nodes and type 1 check nodes being removed, we have [TeX:] $$\rho_1(z)=\rho((1-\eta) z+\eta).$$ On the other hand, since the type 1 edges between type L variable nodes and type L check nodes are removed, we have [TeX:] $$\rho_L(z)=\rho(\eta z+(1-\eta)).$$ For [TeX:] $$c=2, 3, \cdots, L-1,$$ we still have [TeX:] $$\rho_c(z)=\rho(z).$$ For [TeX:] $$v=1,2, \cdots, L-1,$$ let [TeX:] $$\alpha_v^{(i)}$$ be the probability that the variable end of a randomly selected edge is a type v variable node and it is not decoded after the ith iteration. For [TeX:] $$c=1, 2, \cdots, L,$$ let [TeX:] $$\beta_c^{(i)}$$ be the probability that the check end of a randomly selected edge is a type c check node and it is not decoded after the ith iteration. Now the density evolution equations in (47) and (48) can be written as follows:

and

The base graphs for the convolutional LDPC codes can also be extended to the degree-degree correlated LDPC codes in Section II-B. Specifically, we can construct a convolutional LDPC code with L copies by viewing (i) the variable nodes at the vth copy with degree x as type (v, x) variable nodes, (ii) the check nodes at the cth copy with degree y as type (c, y) check nodes, and (iii) the edges between a variable node at the vth copy with degree x and a check node at the cth copy with degree y as type ((v, x), (c, y)) edges. Denote by [TeX:] $$\alpha_{v, x}^{(i)}$$ the probability that the variable end of a randomly selected edge is a type (v, x) variable node and it is not decoded after the ith iteration. Also, [TeX:] $$\alpha_{v, x}^{(0)}=\delta$$ for all v, x (as every variable bit is erased independently with probability δ through the erasure channel). Similarly, denote by [TeX:] $$\beta_{c, y}^{(i)}$$ the probability that the check end of a randomly selected edge is a type (c, y) check node and it is not decoded after the ith iteration. The generating function of the excess degree distribution of a type (v, x) variable node is

Also, the generating function of the excess degree distribution of a type (c, y) check node is

Analogous to the previous density evolution analysis for convolutional LDPC codes, we have

and

where [TeX:] $$p(c \mid v) \text { and } p(v \mid c)$$ are specified in (49) and (50), respectively.

As discussed in the survey paper [38], protograph-based LDPC codes (see, e.g., [39]–[41]) can be viewed as a sub-ensemble within the ensemble of convolutional LDPC codes, sharing the same joint degree distribution on variable nodes and check nodes. This similarity arises because a protograph-based LDPC code is constructed through a ‘copyand- permute’ operation on a given bipartite graph with multiple edges, known as the protograph. This operation is akin to the construction of convolutional LDPC codes discussed in this paper. The key distinction between convolutional LDPC codes and protograph-based LDPC codes is that the former comprises an ensemble of random bipartite graphs, whereas the latter is a structured deterministic bipartite graph. Given that different protographs can result in distinct thresholds, choosing the most effective protograph can improve threshold performance. This method is likely to achieve a superior threshold compared to the convolutional LDPC code, whose threshold represents the average over all possible protographs. Intuitively, a protograph-based LDPC code can be considered an optimized realization selected from the ensemble of convolutional LDPC codes. Consequently, protograph-based LDPC codes are more suited for practical applications and have thus become the de facto standard in LDPC code design. We note that our DDC-LDPC code’s design process, utilizing density evolution analysis, can serve as a beneficial preliminary step in the following methodology: (i) Identify the optimal marginal degree distributions for variable nodes and check nodes to maximize the threshold, as outlined in [42]. (ii) With these marginal degree distributions established, design the best joint degree distribution. (iii) Using the joint degree distribution, design the best (or at least a reasonably good) protograph. In each step, the threshold may improve.

C. Poisson Degree Distributions of the Check Nodes

In this section, we consider a special class of the METLDPC code in Section IV-A, where the degree distributions of the check nodes are Poisson. Consider a MET-LDPC code with [TeX:] $$n_V$$ types of variable nodes, [TeX:] $$n_C$$ types of check nodes, and [TeX:] $$n_C$$ types of edges. For this, we specify the following probabilities.

· [TeX:] $$p_0(v)$$: The probability that a randomly selected variable node is of type v, [TeX:] $$v=1,2, \cdots, n_V.$$

· [TeX:] $$p_1(d \mid v)$$: The probability that a type v variable node has degree d is characterized by the generating function of the excess degree distribution [TeX:] $$\lambda_v(z), v=1,2, \cdots, n_V$$

· [TeX:] $$p_2(e \mid v)$$: The probability that an edge of a type v variable node is a type e edges, [TeX:] $$e=1,2, \cdots, n_C.$$

· [TeX:] $$q_0(c)$$: The probability that a randomly selected check node is of type c, [TeX:] $$c=1,2, \cdots, n_C.$$

· [TeX:] $$q_1(d \mid c)$$: The probability that a type c check node has degree d is [TeX:] $$e^{-\nu_c \frac{\nu_c^d}{d!}},$$ i.e., it is a Poisson distribution with mean [TeX:] $$\nu_c.$$

· [TeX:] $$q_2(e \mid c)$$: The probability that an edge of a type c check node is a type e edges is 1 if [TeX:] $$e=c, e=1,2, \cdots, n_C.$$ That is, type e edges are connected to type e check nodes.

Note that the expected number of type c edges connected to variable nodes is [TeX:] $$n \sum_{v=1}^{n_V} p_0(v) \sum_d d p_1(d \mid v) p_2(c \mid v).$$ On the other hand, the expected number of type c edges connected to check nodes is [TeX:] $$(n-k) q_0(c) \nu_c.$$ To satisfy the socket count equality constraints in (40), we choose

where G = n/(n − k) is defined in (3). The generating function of a Poisson degree distribution with mean [TeX:] $$\nu_c$$ is [TeX:] $$e^{-\nu_c(1-z)}.$$ It is well-known (see, e.g., [20]) that the excess degree distribution of a Poisson degree distribution is also Poisson with the same mean. Thus, we have

Note from Lemma 2 that

and

where we use (57) in the last identity.

Now the density evolution equations in (47) and (48) can be written as follows:

and

where [TeX:] $$\xi_v=\sum_d d p_1(d \mid v)$$ is the mean degree of a type v variable node. The recursive equations in (61) and (62) were previously derived in [33] for irregular repetition slotted ALOHA (IRSA) [32] with multiple classes of users and mutiple classes of receivers.

V. NUMERICAL RESULTS

A. Block Construction

In this section, we evaluate the performance of random LDPC codes generated by the block construction in Section II-A. Consider using the randomly generated LDPC code in Example 1 for a BEC with the erasure probability δ. In this numerical experiment, we set G = 3, d = 3.

In Fig. 3, we plot the maximum tolerable erasure probability [TeX:] $$\delta^*(q)$$ as a function of the parameter q (with the step size of 0.01) for two permutations: the negatively correlated one with [TeX:] $$\pi(1)=2, \pi(2)=1$$ (the orange curve), and the positively correlated one with [TeX:] $$\pi(1)=1, \pi(2)=2$$ (the blue curve). Recall that when q = 0, it reduces to the independent case. As shown in Fig. 3, adding a negative degree-degree correlation can lead to a much larger maximum tolerable erasure probability than that of the independent case. In particular, when q = 0.37, we find that the maximum tolerable erasure probability [TeX:] $$\delta^*(q)$$ is 0.3066, which is larger than [TeX:] $$\delta^*(q)=0.2741$$ for q = 0. However, adding a positive degree-degree correlation does not improve the maximum tolerable erasure probability in this numerical experiment.

To explain these numerical results, we note that LDPC codes with positive degree-degree correlations tend to form a giant component in the bipartite graph (as nodes with large degrees tend to connect to nodes with large degrees), and that makes the decoding of the LDPC code difficult. On the other hand, LDPC codes with negative degree-degree correlations are less likely to form a giant component. As such, one can exploit the negative degree-degree correlation by increasing q to improve the maximum tolerable erasure probability. However, when q is increased to 1, the bipartite graph gradually decouples into two separate bipartite graphs (from the block construction). Each has its own maximum tolerable erasure probability. When q is close to 1, the maximum tolerable erasure probability is dominated by the bipartite graph with a smaller maximum tolerable erasure probability. Due to these two effects, the orange curve for the case with a negative degree-degree correlation is unimodal (with only one peak).

In order to verify the effectiveness of the asymptotic results derived from the density evolution equations, we conduct extensive simulations. For our simulations, we generate degreedegree correlated LDPC codes with n = 18, 000 variable nodes and n−k = 6, 000 check nodes by using the construction in Example 1. Then we simulate the LDPC codes over a BEC with an erasure probability δ. After that, we perform iterative decoding (peeling decoder) for the LDPC codes (until there are no check nodes with degree 1). In Fig. 4, we plot the probability that a randomly selected variable node is successfully decoded, i.e., [TeX:] $$\lim _{i \rightarrow \infty} \gamma^{(i)} \text { with } \gamma^{(i)}$$ in (28), as a function of the erasure probability δ from 0 to 0.4 with respect to various parameters q = 0, 0.2, 0.4, 0.6, 0.8. This is done under the condition of a negatively correlated permutation [TeX:] $$\pi(1)=2, \pi(2)=1.$$ Each data point is the average of 100 experiments. The five solid curves represent the theoretical results of [TeX:] $$\lim _{i \rightarrow \infty} \gamma^{(i)}$$, and the five dotted curves represent the corresponding simulation results. As shown in Fig. 4, the simulation results and the asymptotic results match very well. Also, we observe the largest maximum tolerable erasure probability occurs when q = 0.4 (the yellow curve). This result is consistent with that of Fig. 3. Additionally, we made a new discovery: for [TeX:] $$q \geq 0.4$$, the curve exhibits two turning points. One occurs as [TeX:] $$\lim _{i \rightarrow \infty} \gamma^{(i)}$$ drops from 1, representing the largest maximum tolerable erasure probability. Another turning point arises after reaching this maximum tolerable erasure probability. This nonlinear nature of the density evolution is not observed in the independent case (q = 0). The underlying reasons for this phenomenon are further elucidated in Fig. 5.

Finally, we examine the effect of degree on the decoding probabilities of variable nodes. The variable nodes in Example 1 exhibit two types of degrees: and 2d. In Fig. 5 and Fig. 6, we plot the probability that a randomly selected variable node with degree x is successfully decoded, i.e., [TeX:] $$\lim _{i \rightarrow \infty} \gamma_x^{(i)},$$ as a function of the erasure probability δ for different values of q. These plots are generated under the conditions of a negatively correlated permutation [TeX:] $$\pi(1)=2, \pi(2)=1$$ (in Fig. 5) and a positively correlated permutation [TeX:] $$\pi(1)=1, \pi(2)=2$$ (in Fig. 6), respectively. The solid curve (resp. dashed curve) represents the decoding probability for a variable node with degree d (resp. 2d).

In Fig. 5, it is well known that the decoding probability for variable nodes with a large degree is higher than that for nodes with a small degree under negatively correlated conditions. This characteristic is referred to as the unequal error protection (UEP) property. One significant finding from our experiments is that the degree-degree correlation plays a critical role in UEP. Recall that the degree-degree correlation in Example 1 is −q. As shown in Fig. 5, increasing q increases the gap between the curve for [TeX:] $$\lim _{i \rightarrow \infty} \gamma_d^{(i)}$$ and the curve for [TeX:] $$\lim _{i \rightarrow \infty} \gamma_{2d}^{(i)}$$. In particular, for q = 0.8 (the two green curves), the gap is the largest among the five choices of q. Even when the erasure probability exceeds the upper bound 1/G = 1/3, variable nodes with degree 2d can still have a very high decoding probability. This is at the cost of sacrificing the decoding probability of variable nodes with degree d. Given that the two blocks of degree d and degree 2d are coupled, the trends of the two curves for [TeX:] $$\lim _{i \rightarrow \infty} \gamma_d^{(i)}$$ and [TeX:] $$\lim _{i \rightarrow \infty} \gamma_{2d}^{(i)}$$ influence each other. As demonstrated in Fig. 4, this coupling leads to the formation of curves with two turning points. On the other hand, the two curves for q = 0.4 are very close to each other. Even though they have the largest maximum tolerable erasure probability [TeX:] $$\delta^*$$, they are not suitable for LDPC codes with the UEP property.

In Fig. 6, we note that for all δ values (this figure focuses on the corresponding decoding probabilities [TeX:] $$\lim _{i \rightarrow \infty} \gamma_d^{(i)}$$ and [TeX:] $$\lim _{i \rightarrow \infty} \gamma_{2d}^{(i)}$$ for δ from 0.1 to 0.3), when [TeX:] $$q \leq 0.4,$$ the solid curves are consistently above the dashed curves for the same q. This implies that when positively correlated, the decoding probability for variable nodes with a large degree is typically higher than that with a small degree. Interestingly, for all δ, the dashed curves shift above the solid curves when [TeX:] $$q\gt 0.4$$. As illustrated in Fig. 6, beyond the maximum tolerable erasure probability [TeX:] $$\delta^*$$, variable nodes with degree d can exhibit higher decoding probabilities. This is because nodes with smaller degrees are less likely to form a giant component, thereby facilitating LDPC code decoding. This effect is due to the positive degree-degree correlation in LDPC codes. Furthermore, observe that when [TeX:] $$q\gt 0.8$$, increasing q widens the gap between the curve for [TeX:] $$\lim _{i \rightarrow \infty} \gamma_d^{(i)}$$ and the curve for [TeX:] $$\lim _{i \rightarrow \infty} \gamma_{2 d}^{(i)},$$ indicative of LDPC codes with the UEP property.

B. General Construction for Performance Improvement

In this section, we show that the LDPC codes from the general construction in Section II-B can lead to further performance improvement.

In [29], Shokrollahi and Storn proposed a construction of the LDPC code with the following (independent) bivariate distribution:

where [TeX:] $$p_{X_e}(2)=0.2633, p_{X_e}(3)=0.1802, p_{X_e}(7)=0.2700,p_{X_e}(30)=0.2865, \text{ and } p_{Y_e}(8)=0.6341, p_{Y_e}(9)=0.3659.$$

It is easy to verify that G = 2. It was shown in [29] that the maximum tolerable erasure probability [TeX:] $$\delta^*=0.49553.$$ For this example, we find the bivariate distribution [TeX:] $$\mathrm{P}\left(X_e=\right.\left.2, Y_e=8\right)=0.1534, \mathrm{P}\left(X_e=3, Y_e=8\right)=0.1789,$$ [TeX:] $$\mathrm{P}\left(X_e=7, Y_e=8\right)=0.1035$$ such that it has the same marginal distributions [TeX:] $$p_{X_e}(x) \text { and } p_{Y_e}(y) \text {. }$$ The maximum tolerable erasure probability [TeX:] $$\delta^*$$ for such a bivariate distribution is 0.49568, which is larger than 0.49553 for the LDPC code in [29].

Another example is the LDPC code in Example 3.64 of the book [42]. The maximum tolerable erasure probability [TeX:] $$\delta^*$$ for that LDPC code is 0.47410. Using the general construction in Section II-B, we find the bivariate distribution [TeX:] $$\mathrm{P}\left(X_e=2, Y_e=8\right)=0,$$ [TeX:] $$\mathrm{P}\left(X_e=3, Y_e=8\right)=0.274,$$ [TeX:] $$\mathrm{P}\left(X_e=7, Y_e=8\right)=0.007$$ such that it has the same marginal distributions [TeX:] $$p_{X_e}(x) \text { and } p_{Y_e}(y) \text {. }$$ We can extend the maximum tolerable erasure probability [TeX:] $$\delta^*$$ to 0.48077.

C. Convolutional LDPC Codes

In this section, we evaluate the performance of random convolutional LDPC codes. We consider a randomly generated convolutional LDPC code constructed according to Section IV-B, which is used for a BEC with the erasure probability δ. In this numerical experiment, we set G = 2, d = 3, and η = 0.5 in (51) and (52), allowing us to derive the following density evolution equations:

and

Corresponding to different L values, we select five instances of LDPC codes for our numerical experiments. These codes are constructed as per Section IV-B, incorporating various degree distribution pairs and considering the degreedegree correlation as defined in Example 2. For G = 2, we find that when using a bivariate distribution with [TeX:] $$p_1=0.155, p_2=0.345,$$ the irregular LDPC code achieves the maximum tolerable erasure probability. This is included in Table I below for comparison. We also employ the conventional LDPC code as a benchmark. The five degree distribution pairs are:

(i) The (3,6)-Regular LDPC code: [TeX:] $$\lambda(z)=z^2, \rho(z)=z^5.$$

(ii) The irregular LDPC code in Example 2 with the bivariate distribution specified by [TeX:] $$p_1=0.25, p_2=0.25$$ (with independent degree distribution): [TeX:] $$\lambda(z)=0.5 z^2+0.5 z^5,$$ [TeX:] $$\rho(z)=0.5 z^5+0.5 z^{11}.$$

(iii) The irregular LDPC code in Example 2 with the bivariate distribution specified by [TeX:] $$p_1=0.155, p_2=0.345$$: [TeX:] $$\lambda(z)=0.5 z^2+0.5 z^5, \rho(z)=0.5 z^5+0.5 z^{11}.$$

(iv) The LDPC code by Shokrollahi and Storn [29]: [TeX:] $$\lambda(z)=0.26328 z+0.18020 z^2+0.27000 z^6+0.28649 z^{29},$$ [TeX:] $$\rho(z)=0.63407 z^7+0.36593 z^8 \text {. }$$

(v) The LDPC code in Example 3.64 of the book [42]: [TeX:] $$\lambda(z)=0.106257 z+0.486659 z^2+0.010390 z^{10}+0.396694 z^{19},$$ [TeX:] $$\rho(z)=0.5 z^7+0.5 z^8.$$

The maximum tolerable erasure probabilities [TeX:] $$\delta^*$$ as determined by numerical solutions to the density evolution equations for L = 2, 5, 10, 20, 50, 200 in the above five cases are presented in Table I. Numerical results indicate that irrespective of the degree distribution set, the maximum tolerable erasure probabilities [TeX:] $$\delta^*$$ for the convolutional LDPC code consistently outperform those for the conventional LDPC code.

To validate the asymptotic results derived from the density evolution equations, we carry out extensive simulations. In these simulations, we generate three MET constructions of (nL, kL)-LDPC codes for L = 2, 5, 10, where all base random bipartite graphs are irregular LDPC codes with n = 6000 variable nodes and n − k = 3000 check nodes. All base irregular LDPC codes are characterized by the generating functions of Case (ii). To create L copies of (nL, kL)-LDPC code convolutionally for L = 2, 5, 10, we randomly rewire some edges from the vth copy to the ((v +1) mod L)th copy with probability η = 0.5, and puncture type L variable nodes along with their connected edges. After constructing these graphs, we simulate each one over a binary erasure channel with an erasure probability δ, and then we perform iterative decoding (using the peeling decoder) for these LDPC codes until there are no check nodes with degree 1 remaining.

In Fig. 7, we plot the probability that the variable end of a randomly selected edge corresponds to a type v variable node and that it is not decoded after the ith iteration, i.e., [TeX:] $$\lim _{i \rightarrow \infty} \alpha_v^{(i)},$$ as a function of the erasure probability δ ranging from 0 to 1, with respect to L = 2, 5, 10 when [TeX:] $$p_1=p_2=0.25.$$ All the base irregular LDPC codes are characterized by the generating functions of Case (ii), i.e., [TeX:] $$\lambda(z)=0.5 z^2+0.5 z^5, \rho(z)=0.5 z^5+0.5 z^{11}.$$ Each data point represents the average of 100 experiments. The three solid curves depict the theoretical results of [TeX:] $$\lim _{i \rightarrow \infty} \alpha_v^{(i)},$$ and the three dotted curves represent the corresponding simulation results. In the L = 2 case, we plot the decoding result of type 1 variable nodes, while in the L = 5, 10 cases, we plot the decoding results of type 2 variable nodes. As shown in Fig. 7, there is a strong alignment between the simulation results and the asymptotic results, thereby confirming the effectiveness of the asymptotic results derived from the density evolution equations.

Next, we use the bivariate distribution specified by [TeX:] $$p_1=0.155 \text{ and } P_2=0.345$$ to evaluate the performance of random convolutional LDPC codes with degree-degree correlation. Also, we set G = 2, x = 6, 3, y = 12, 6, η = 0.5 in (22), (23), (55) and (56), and display the results of the density evolution equations in Fig. 8.

In Fig. 8, all the base irregular LDPC codes are characterized by the generating functions of Case (iii), i.e., [TeX:] $$\lambda(z)=0.5 z^2+0.5 z^5, \rho(z)=0.5 z^5+0.5 z^{11}.$$ In this numerical experiment, we plot the probability that the variable end of a randomly selected edge is a type v variable node, and it is not decoded after the ith iteration, i.e., [TeX:] $$\lim _{i \rightarrow \infty} \alpha_v^{(i)},$$ as a function of the erasure probability δ ranging from 0 to 1. For L = 2, 5, 10, we obtain numerical results comparing the bivariate distribution specified by [TeX:] $$p_1=0.155, p_2=0.345$$ (the solid curve) to that specified by [TeX:] $$p_1=p_2=0.25$$ (the dashed curve, representing independent degree distribution). In the L = 2 case, we plot the decoding result of type 1 variable nodes, while in the L = 5, 10 cases, we plot the decoding results of type 2 variable nodes. As observed in Fig. 8 and Table I, when [TeX:] $$L \geq 10,$$ the maximum tolerable erasure probability [TeX:] $$\delta^*$$ under Cases (ii) and (iii) are almost identical. This indicates that as L increases, the influence of the degreedegree correlation of the base graph gradually diminishes. The phenomenon can be attributed to the potent influence that the correlation, driven by the upper-level convolutional (“copyand permute”) structure, exerts on the decoding probability. The convolutional structure exhibits a “wave”-like decoding process, progressing from the outer stages toward the inner stages. This influence significantly outweighs the impact of the base graph’s degree-degree correlation (at the lower level). Consequently, optimizing the degree-degree correlation within the base graph does not significantly enhance the performance of convolutional LDPC codes.

VI. CONCLUSION

In this paper, we proposed two constructions of degreedegree 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 degreedegree correlation can achieve a much higher maximum tolerable erasure probability than LDPC codes with independent degree distributions. Moreover, adding a negative degreedegree 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. In our extensions, we expanded the degree-degree correlated LDPC codes to multi-edge type LDPC codes and further to convolutional LDPC codes. Our numerical results demonstrate that, regardless of the degree-degree correlation controlling parameter q, utilizing spatial coupling offers improved performance when the number of copies L approaches infinity (i.e., the code rate of LDPC codes is close to k/n).

Interpreting the numerical results, such as thresholds, of degree-degree correlated LDPC codes, is challenging due to two main reasons: (i) The equations derived from the density evolution analysis are highly nonlinear, and (ii) these equations are interconnected through the degree-degree correlation or edge types. One possible approach to tackle this issue is to use the mathematical framework in [43], [44]. Results related to this line of research will be reported separately.