Construction of Protograph-Based Partially Doped Generalized LDPC Codes

Let $\mathbb{x}=\{x_{1},{\cdots},x_{k}\},x_{i}\in\{0,1\}$ be a $k$-bit binary message vector, which is encoded via an $(n,k)$ linear code, forming an $n$-bit codeword $\mathbb{c}=\{c_{1},{\cdots},c_{n}\},c_{i}\in\{0,1\}$. The codeword passes through a memoryless BEC, where each bit is either erased with a probability $\epsilon$ or correctly received.
Protograph LDPC codes [25] are defined by a relatively small bipartite graph $G=(V,C,E)$ representing a protograph, where $V=\{v_{1},{\cdots},v_{n_{v}}\}$ is a set of VNs and $C=\{c_{1},{\cdots},c_{n_{c}}\}$ is a set of check nodes (CNs). Let $E$ be a set of edges $e$, where $e=(v,c)$ connects a VN $v\in V$ and a CN $c\in C$. The bipartite graph can also be expressed in terms of an $n_{c}\times n_{v}$-sized base matrix ${\mathbb{B}}_{n_{c}\times n_{v}}=\{b_{i,j}\},i\in[n_{c}],j\in[n_{v}]$, where $b_{i,j}\in\{0,1,2,{\cdots}\}$ and $[A]$ is a set of positive integers less than or equal to a positive integer $A$. The rows represent the CNs and the columns represent the VNs in the protograph. Each entry $b_{i,j}$ of the base matrix represents the number of edges connected between a VN and a CN. If there are no edges connected between $v_{j}$ and $c_{i}$, the entry $b_{i,j}$ is zero. The variable (check) node degree $deg(v_{j})$ ($deg(c_{i})$) is defined as the number of edges incident to itself. A protograph LDPC code is constructed by copy-and-permute operation of $G$. The bipartite graph $G$ is copied by the lifting factor $N$ and copies of each edge $e=(v,c)\in E$ are permuted among copies of $v$ and $c$. In general, the large value of $N$ guarantees the sparseness of the code.

Conventionally, a protograph doped GLDPC code ensemble is constructed by replacing (doping) a CN of a protograph with a GC node that has a parity-check constraint from an $(n_{i},k_{i},d_{min}^{i})$ linear code (component code), where $n_{i}$ ($k_{i}$) is the code length (dimension) and $d_{min}^{i}$ is the minimum distance of the component code for a CN $c_{i}$. The condition for replacement is that the CN degree should be exactly equal to the length of the component code, i.e., $deg(c_{i})=n_{i}$. Note that the original CN has the parity-check constraint of an $(n_{i},k_{i})=(deg(c_{i}),deg(c_{i})-1)$ SPC code. The code rate $R$ of protograph doped GLDPC codes is $R=1-\frac{m_{proto}}{n_{v}}$, where $m_{proto}=\sum_{i=1}^{n_{c}}(n_{i}-k_{i})$. While the minimum distance of an SPC node is 2, the VNs connected to the GC node are protected by parity-check constraints of the component code with the minimum distance larger than two. Fig. 1 shows the protograph doped GLDPC code of the code rate ${3}/{7}$ by replacing an SPC node with the $(7,4)$ Hamming code constraints.

The asymptotic performance of the protograph doped GLDPC codes is evaluated by the PEXIT analysis. The PEXIT analysis tracks down the mutual information of extrinsic messages and a priori error probabilities of the VNs, CNs, and GC nodes of protograph GLDPC codes. For an exact PEXIT analysis, tracking down each mutual information corresponding to edges of the component code is needed, i.e., multi-dimensional EXIT computation [27]. However, in terms of code optimization, where lots of EXIT computation is required, it is beneficial to reduce the complexity of the EXIT computation in GC nodes by averaging the a priori and extrinsic mutual information of the GC nodes. The EXIT and PEXIT analyses of the protograph doped GLDPC codes over the BEC in terms of average mutual information are given in [32, 28, 29].
The PEXIT process is given in Alg. 1. Let $I_{ch}(j)$ be the channel information from the erasure channel for the protograph VN $v_{j}$. In addition, $I_{EV}(i,j)$ $(I_{EC}(i,j))$ is the extrinsic information sent from $v_{j}$ ($c_{i}$) to $c_{i}$ ($v_{j}$) and $I_{AV}(i,j)$ $(I_{AC}(i,j))$ is the a priori mutual information of $v_{j}$ ($c_{i}$) sent from $c_{i}$ ($v_{j}$), where $c_{i}$ is an SPC node. For GC nodes, we use the notations $I_{AGC}(i)$ and $I_{EGC}(i,j)$ for a priori and extrinsic information. Let $N(c_{i})$ ($N(v_{j})$) be a set of variable (check) nodes incident to $c_{i}$ ($v_{j}$), i.e., neighborhood of $c_{i}$ ($v_{j}$). Finally, $I_{APP}(j)$ is a posteriori probability of $v_{j}$. To explain (1) in Alg. 1, if $c_{i}$ is a GC node with the $(n_{i},k_{i})$ Hamming code, the PEXIT of the GC node is computed from a closed form using the property of the simplex code, which is the dual code of a Hamming code. Also, $I_{AGC}(i)=\frac{1}{n_{i}}\sum_{j\in N(c_{i})}b_{i,j}\times I_{EV}(i,j)$ is the average a priori mutual information for a GC node to compute the PEXIT message. In (1), we have

For two positive integers $a$ and $b$, we also have $\binom{a}{b}=\prod_{i=0}^{b-1}\frac{a-i}{b-i}$ and ${a\brack b}=\prod_{i=0}^{b-1}\frac{2^{a}-2^{i}}{2^{b}-2^{i}}$, where $\binom{a}{0}=1$ and ${a\brack 0}=1$. The PEXIT process searches for the minimum $\epsilon$ to successfully decode, i.e., $I_{APP}(j)=1,$ for all $j\in[n_{v}]$, in an asymptotic sense.
Now, we briefly explain the decoding process of GLDPC codes over the BEC [13]. The VNs process the conventional message-passing decoding over the BEC by sending correct extrinsic messages to the CNs if any of the incoming bits from their neighborhood is not erased. The SPC nodes send correct extrinsic messages to the VNs if all of their incoming messages are correctly received, and send erasure messages otherwise. In this paper, the decoding of GC nodes is processed by the maximum likelihood (ML) decoder. For each iteration, a GC node $c_{i}$ with the $(n_{i},k_{i})$ component code receives the set of erasure locations $\{e_{i}\}$ from $N(c_{i})$. Let $H_{GC}$ be the parity-check matrix (PCM) of the component code and $H_{e}$ be the submatrix of $H_{GC}$ indexed with $\{e_{i}\}$. The decoder computes the Gaussian-elimination operation of $H_{e}$, making it into a reduced row echelon form $H_{e}^{reduced}$. If rank($H_{e}^{reduced}$)$=|\{e_{i}\}|$, the GC node solves all the input erasures and otherwise, the decoder corrects the erasures corresponding to the rows with weight 1 from $H_{e}^{reduced}$. The decoding complexity can be further reduced if the GC node exploits bounded distance decoding; however, the degradation of asymptotic performance is not negligible, as shown in [7].

First, we define the partial doping for variable nodes using the addition of GC nodes to a lifted protograph, that is, the addition of rows for the parity check matrix by the component code, where each GC node is incident to variable nodes copied from single protograph variable node. Also, we define a partially doped protograph variable node as a protograph variable node incident to the added GC nodes. While the term doping in conventional GLDPC codes is used in the perspective of check nodes, we use the term partial doping in the perspective of variable nodes. Let ${\mathbb{B}}_{n_{c}\times n_{v}}$ be an $n_{c}\times n_{v}$ base matrix, where some protograph variable nodes are partially doped with a $(\mu,\kappa)$ component code after the lifting process. Let $x=0,1,2,{\cdots}$ be the number of the partially doped protograph variable nodes, where each protograph variable node is doped by $N/\mu$ component codes after the lifting process. Then, a proposed protograph-based PD-GLDPC code is defined with parameters $({\mathbb{B}}_{n_{c}\times n_{v}},\mu,\kappa,N,x)$. We assume that the component code used in the paper is the $(\mu,\kappa)$ Hamming code and that $\mu$ divides the lifting factor $N$ such that $N=\mu\beta$, where $\beta$ is a non-negative integer. The variable nodes copied from $x$ protograph variable nodes in the base matrix are partially doped by the GC nodes. That is, in the proposed PD-GLDPC code construction, the $N/\mu$ GC nodes are connected to the $N$ variable nodes lifted from each protograph variable node. Thus, the proposed construction method can choose the protograph variable nodes to protect by partial doping. An example of the proposed construction is given in Fig. 3, which illustrates the doping process by a $(7,4)$ component Hamming code over a $2\times 3$ base matrix.

Note that for the proposed protograph-based PD-GLDPC codes, the a priori (extrinsic) EXIT of the GC node is computed from the extrinsic (a priori) EXIT of single protograph variable node. While the EXIT of variable nodes and SPC nodes for the proposed protograph-based PD-GLDPC codes is the same as that of the conventional protograph GLDPC codes described in Alg. 1, the EXIT of the GC nodes in the proposed codes is changed to (2) whereas the conventional protograph GLDPC codes use (1).
In general, as the portion of degree-2 variable nodes in the LDPC codes increases, the asymptotic performance is enhanced [37], but their minimum distance decreases and then the error floor becomes worse. Although the proposed protograph-based PD-GLDPC code construction method enables the partial doping for any variable nodes in the given protographs, we focus only on partial doping for degree-2 variable nodes as follows. First, we construct the original base matrix ${\mathbb{H}_{proto}}$ with the large portion of degree-2 variable nodes. Then, we partially dope some of the protograph variable nodes of degree-2 to increase the minimum distance and improve their performance. Thus, regular protographs of degree-2 variable nodes and irregular protographs with many degree-2 variable nodes are used for the construction of the proposed protograph-based PD-GLDPC codes. In terms of irregular ensemble LDPC codes, a large portion of degree-2 variable nodes enables the LDPC code to achieve the capacity approaching performance [38]. On the other hand, by reasonably selecting the number of partially doped variable nodes for degree-2, the property of the linear minimum distance growth with the length of the LDPC code can be guaranteed. Thus, when we design the proposed protograph-based PD-GLDPC codes, balancing the partial doping over degree-2 variable nodes enables both the existence of a typical minimum distance and a good asymptotic performance.

The existence of a typical minimum distance in the given LDPC codes guarantees that their minimum distance grows linearly with the block length of the code in an asymptotic sense [34]. It was proved in [35] that a protograph LDPC code has a typical minimum distance if there is no cycle consisting of only degree-2 variable nodes in the protograph. Furthermore, in [36], the condition for a typical minimum distance of the conventional protograph GLDPC codes was given as follows. Assuming that there are no degree-2 variable nodes with double edges, i.e., no type 1 degree-2 variable nodes defined in [36], the neighborhoods of a check node $c_{i}$ that satisfy $d^{i}_{min}\geq N^{(dv2)}(c_{i})$ are removed along with its edges, where $N^{(dv2)}(c_{i})$ is the number of degree-2 variable nodes among the neighborhoods of $c_{i}$. This process is repeated until no further degree-2 variable nodes remain. Then, the GLDPC code has a typical minimum distance if all degree-2 variable nodes are removed.
The proposed protograph-based PD-GLDPC code also has a similar approach to that of the conventional protograph GLDPC codes in [36]. However, since a GC node of the proposed protograph-based PD-GLDPC code is not well defined by a protograph node, the derivation of the weight enumerator of the proposed codeword is quite different from that of the conventional GLDPC code. Thus, the condition for the existence of the typical minimum distance of the proposed protograph-based PD-GLDPC codes is slightly different from that of the conventional protograph LDPC code. That is, the degree-2 variable nodes to be partially doped are initially excluded before the degree-2 variable node removing process stated in [35], because those variable nodes should be changed to the variable nodes of degrees higher than two by partial doping. Thus, we can regard the degree-2 variable nodes to be partially doped as the variable nodes with higher degrees. Then, we have the following theorem for the proposed protograph-based PD-GLPDC codes.

The existence of the typical minimum distance of the proposed protograph-based PD-GLDPC code guarantees that the minimum distance of the proposed code grows linearly with the code length of the LDPC code, and thus the proposed code has low error floor for the large code length. In the next section, we use Theorem 1 as the constraint to optimize the protograph in order to guarantee the existence of the typical minimum distance of the proposed protograph-based PD-GLDPC code.

The main difference between the proposed protograph-based PD-GLDPC codes and the conventional protograph GLDPC codes is the perspective of doping. While the conventional protograph GLDPC code replaces an entire row, i.e., a protograph check node by the parity check matrix of the component code, the proposed protograph-based PD-GLDPC code appends some rows incident to the variable nodes copied from single protograph variable node. The focus of the conventional protograph GLDPC code is to choose a certain protograph check node, whereas the protograph-based PD-GLDPC code is focusing on choosing which protograph variable nodes are further protected by partial doping. The constraint for the conventional protograph GLDPC code is that the check nodes to be replaced should have the degree equal to the component code length, while the constraint for the proposed protograph-based PD-GLDPC codes is that the lifting size of a protograph should be the multiple of the component code length.
The selection of the check nodes to be replaced in the conventional protograph GLDPC codes is generally difficult since it requires a combinatory search of either the best threshold, minimum distance, or convergence speed. Also, since many SPC nodes of a given base matrix connect the variable nodes with various degrees, it is very difficult to select the variable nodes to be partially doped for further protection in the conventional protograph GLDPC codes.
Furthermore, the conventional protograph GLDPC code construction has two limitations in terms of PEXIT analysis and doping granularity. First, the PEXIT analysis of the conventional protograph GLDPC codes is not accurate because the PEXIT of the GC node is derived from averaged EXIT of $\mu$ (component code length) protograph variable nodes. Using a MAP-oriented computation as in Alg. 1, the GC node outputs a single value that represents the extrinsic mutual information for the $\mu$ protograph variable nodes. Thus, a GC node averages up the a priori mutual information of the $\mu$ neighborhood protograph variable nodes and outputs uniform extrinsic mutual information, which is similar to the EXIT analysis of a random ensemble LDPC code [28]. Since each GC node receives a priori inputs from $\mu$ different protograph variable nodes, the EXIT analysis is not accurate. Thus, the higher variance of the a priori mutual information from the average, the greater the deviation of the code between the threshold and the actual decoding performance. On the other hand, since the EXIT of a GC node in the proposed protograph-based PD-GLDPC code requires the a priori mutual information of the same protograph variable node, there is no deviation since the $\mu$ mutual information has the same value, which makes the PEXIT of the proposed code more accurate.
The second limitation is that the conventional protograph GLDPC codes have large doping granularity of protograph variable nodes compared to that of the proposed one. By replacing a single protograph GC node by a component code with parameters $(\mu,\kappa)$, the $\mu$ protograph variable nodes are doped. Whereas, for every partial doping of $\beta$ GC nodes in the proposed protograph-based PD-GLDPC code, the variable nodes copied from single protograph variable node are partially doped. In other words, the doping granularity is one, which is smaller than the conventional protograph GLDPC codes.
In summary, compared to the conventional protograph GLDPC codes, the proposed protograph-based PD-GLDPC code is more accurate in the PEXIT analysis and has the smaller doping granularity.

In general, as the portion of degree-2 VNs in the LDPC codes increases, the asymptotic performance is enhanced [37], but their minimum distance decreases and then the error floor becomes worse. For the construction of PD-GLDPC codes in this subsection, we exploit the balance of the portion of degree-2 VNs, where we focus on the partial doping only for degree-2 VNs. The brief construction method is as follows. First, we construct the original base matrix ${\mathbb{B}_{n_{c}\times n_{v}}}$ with the large portion of degree-2 VNs. Then, we partially dope some of the protograph VNs of degree-2 to increase the minimum distance and improve their performance. Thus, irregular protographs with several degree-2 VNs are used for the construction of the proposed PD-GLDPC codes. In terms of irregular LDPC code ensembles, a large portion of degree-2 VNs enables the LDPC code to achieve the capacity approaching performance [38]. On the other hand, by reasonably selecting the number of partially doped VNs of degree-2, the property of the linear minimum distance growth with the length of the LDPC code can be guaranteed. Thus, when we design the proposed PD-GLDPC codes, balancing the partial doping over degree-2 VNs enables both the existence of a typical minimum distance and a good asymptotic performance. Optimization of irregular protograph LDPC code ensembles is made by initially obtaining the degree distribution of the random LDPC code ensemble using differential evolution [30] and constructing the protograph via the progressive edge growth (PEG) [39] algorithm for the construction of the proposed PD-GLPDC codes from irregular protographs. In this subsection, in order to make the CN degrees as even as possible, we try to construct the protograph from the degree distribution of a random LDPC code ensemble. We define $G_{c}$ as the optimized protograph of the conventional LDPC code and $G_{p}$ as the initial irregular protograph that is used to construct the PD-GLDPC code. That is, we can regard $G_{p}$ as the protograph corresponding to $H_{proto}$ in Fig. 4. In order to compare FER performances of the conventional LDPC code and the proposed PD-GLDPC code under the same degree distribution, $G_{c}$ is constructed to have the same VN degree distribution as the PD-GLDPC code constructed from $G_{p}$ after lifting by $N$.
Let $\lambda_{G_{c}}(x)$ and $\rho_{G_{c}}(x)$ be the VN and CN degree distributions of an irregular LDPC code ensemble to construct $G_{c}$, which is the optimized protograph for the conventional LDPC codes. In this subsection, we assume the degree distributions $\lambda_{G_{c}}(x)=\lambda_{2}x+\lambda_{3}x^{2}+\lambda_{4}x^{3}+\lambda_{5}x^{4}+\lambda_{6}x^{5}+\lambda_{l}x^{l-1}$ and $\rho_{G_{c}}(x)=\rho_{r-1}x^{r-2}+\rho_{r}x^{r-1}$, where $\lambda_{i}$ and $\rho_{i}$ are the portions of edges of VNs and CNs of degree-$i$. Using the optimized degree distributions of $\lambda_{G_{c}}(x)$ and $\rho_{G_{c}}(x)$, a protograph $G_{c}$ is constructed by the PEG algorithm. For the description of the protographs that construct the conventional LDPC codes and the proposed PD-GLDPC codes, let ${\mathbb{D}}^{\mathbb{dv}}=(a_{1},{\cdots},a_{max})$ be a $|\mathbb{dv}|$-sized vector defining the numbers of protograph VNs, where $a_{i}$ is the number of protograph VNs of degree $l_{i}$ and $\mathbb{dv}=\{l_{1},l_{2},{\cdots},l_{max}\}$ is a set of VN degrees that exist in the protograph.