# Construction and Decoding of Rate-Compatible Globally Coupled LDPC Codes

Authors: Ji Zhang; Baoming Bai; Xijin Mu; Hengzhou Xu; Zhen Liu; Huaan Li
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

This paper presents a family of rate-compatible (RC) globally coupled low-density parity-check (GC-LDPC) codes, which is constructed by combining algebraic construction method and graph extension. Specifically, the highest rate code is constructed using the algebraic method and the codes of lower rates are formed by successively extending the graph of the higher rate codes. The proposed rate-compatible codes provide more flexibility in code rate and guarantee the structural property of algebraic construction. It is confirmed, by numerical simulations over the AWGN channel, that the proposed codes have better performances than their counterpart GC-LDPC codes formed by the classical method and exhibit an approximately uniform gap to the capacity over a wide range of rates. Furthermore, amodified two-phase local/global iterative decoding scheme for GC-LDPC codes is proposed. Numerical results show that the proposed decoding scheme can reduce the unnecessary cost of local decoder at low and moderate SNRs, without any increase in the number of decoding iterations in the global decoder at high SNRs.


---

## Body

## 1. Introduction

Globally coupled low-density parity-check (GC-LDPC) codes, which were proposed by Li et al. in [1–4], are a special type of LDPC codes designed for correcting random symbol errors and bursts of errors or erasures. They have a different structure from the conventional LDPC block codes and the spatially coupled LDPC (SC-LDPC) codes [5–12]. From the perspective of the Tanner graph, a GC-LDPC code using a group ofglobal check nodes (CNs) couples (or connects) a set of disjoint Tanner graphs calledlocal graphs. We refer to such codes as CN-based globally coupled LDPC (CN-GC-LDPC) codes. Due to the special structure, CN-GC-LDPC codes not only perform well on both the additive white Gaussian noise (AWGN) channel and the binary erasure channel (BEC) but also are effective for correcting burst erasures.For time-varying channels, from the wireless communication theory, we need to adapt the rate according to the available channel state information (CSI); such an error control strategy is referred to as rate adaptability [13]. Rate-compatible (RC) channel codes with incremental redundancy are often used in conjunction with the HARQ strategy [14–20]. Most recently, RC-LDPC codes have been adopted by the 3rd Generation Partnership Project (3GPP) as the channel coding scheme for 5G enhanced mobile broadband (eMBB) data channel [21]. Such codes with a wide range of rates and block lengths are a family of nested codes which can be interpreted as a graph extension of high-rate codes [17, 22, 23].Unlike the SC-LDPC codes which have some conventional design methods for RC-LDPC codes, such as puncturing variable nodes from the codes with low rate and extending variable nodes to the codes with high rate, the classical GC-LDPC codes are mostly restricted to invariant code rate [11, 20, 22–25]. And the existing construction methods of GC-LDPC codes are not flexible enough for RC code design. In this paper, we present a family of RC CN-GC-LDPC codes. The proposed construction is based on combining algebraic construction method and graph extension. The highest rate code, which can be called the mother code, is constructed using the algebraic method. And the codes of lower rates are formed by successively extending the graph of the higher rate. Compared to the original CN-GC-LDPC codes, the proposed family of RC CN-GC-LDPC codes not only provides more flexibility in code rate and allows more efficient encoding but also guarantees the structural property of algebraic construction. Examples show that the proposed codes perform well and exhibit an approximately uniform gap to the capacity over a wide range of rates.Furthermore, localization is a significant advantage of CN-GC-LDPC codes which allows us to process a consecutive sequence by some local sequences. If a decoder usestwo-phase local/global iterative scheme, its decoding latency and memory requirements are much less than those of the classical decoding scheme without performance degradation [1, 2, 26, 27]. However, the local decoder performs a plenty of useless operations at low and moderate SNRs, which causes the unnecessary cost of the decoder. In light of this case, we present amodified two-phase local/global iterative decoding scheme for CN-GC-LDPC codes which reduces the unnecessary cost of the local decoder at low and moderate SNRs.The remainder of this paper is organized as follows. In Section2, we give a brief introduction to CN-GC-LDPC codes. In Section 3, we introduce the concept of graph extension through a four-edge-type LDPC code and propose a simple construction method of four-edge-type LDPC code family. In Section 4, we present amodified two-phase local/global iterative decoding scheme for CN-GC-LDPC codes. Numerical results for RC GC-LDPC codes are presented in Section 5. Finally, Section 6 concludes this paper.


## 2. Background

### 2.1. CN-Based QC-GC-LDPC Codes

A CN-based QC-GC-LDPC codeCgc is constructed using a base matrix Bgc which consists of two subarrays as shown:(1)
B
g
c
=
b
j
,
k
0
≤
j
<
m
t
+
s
,
0
≤
k
<
n
t
=
B
0
B
1
⋱
B
i
⋱
B
t
-
1
X
g
c
.The upper subarray of Bgc is a t×t diagonal array with m×n matrices Bi on its main diagonal and the lower part is an s×nt matrix Xgc, where 0≤i≤t-1. So, Bgc is an (mt+s)×nt matrix.Consider a finite field GF(q) and let α be a primitive element of GF(q). Let Hgc,qc denote the parity-check matrix of CN-based QC-GC-LDPC code. We can use the base matrix Bgc and (q-1)-fold dispersion to form Hgc,qc as follows: for each entry bj,k in Bgc, if bj,k=0, then replace bj,k=0 by the (q-1)×(q-1) zero matrix (ZM); otherwise, assume bj,k=αl with 0≤l<q-1, and then replace bj,k by a (q-1)×(q-1) circulant permutation matrix (CPM) whose first row has a single 1-component at the lth element. The resultant Hgc,qc is an (mt+s)(q-1)×nt(q-1) matrix over GF(2). The null space of Hgc,qc gives a CN-based QC-GC-LDPC code.From the perspective of graph, letGi be the Tanner graph associated with Bi for 0≤i≤t-1. We call Gl a local Tanner graph. The different Gi are pairwise disjoint (for 0≤j, k≤t-1, and j≠k, Gj and Gk are disjoint). The s global CNs connect all these local graphs, composing the Tanner graph associated with Bgc, denoted as Ggc, as shown in Figure 1 (in this figure, the edge labels are ignored). We see that the s global CNs provide the only connections between any two disjoint local Tanner graphs.Figure 1
The Tanner graph of CN-based QC-GC-LDPC codes.


### 2.2. The Basic Method of Code Construction

Li et al. presented two types of CN-based QC-GC-LDPC codes and their construction methods in [1, 2, 4]. In this subsection, we briefly review the construction method for the first type of QC-GC-LDPC codes in [1]. Let GF(q) be a nonbinary (NB) field with q elements, where q is a power of a prime. Let α be a primitive element of GF(q). Then, the powers of α, namely, α0,α1,α2,…,αq-2, give all the nonzero elements of GF(q) and αq-1=α0=1. We construct the following matrix Brs over GF(q) using the method in [2]:(2)Brs=α0-1α-1⋯αq-2-1αq-2-1α0-1⋯αq-3-1⋮⋮⋱⋮α-1α2-1⋯α0-1.Supposeq-1 can be factored as the product of two positive integers l and r; that is, q-1=lr. The matrix Brs which has a cyclic structure is then an lr×lr square matrix. The first l rows in Brs comprise an l×lr matrix, denoted by W0. Then, W0 can be partitioned into r submatrices of size l×l, denoted by W0,0,W0,1,…,W0,r-1. Based on the cyclic structure of Brs, we can obtain the next l rows in Brs by cyclically shifting all the rows of W0=[W0,0,W0,1,…,W0,r-1]l positions to right, denoted by W1=[W0,r-1,W0,0,…,W0,r-3,W0,r-2]. And so, the matrix Brs can be partitioned into r submatrices of size l×lr, denoted by W0,W1,…,Wi,…,Wr-1, where Wi=[W0,r-i,…,W0,r-1,W0,0,…,W0,r-i-1], 0<i≤r-1. Hence, we can form the following block-cyclic structured matrix BW from Brs:(3)BW=W0,0W0,1⋯W0,r-1W0,r-1W0,0⋯W0,r-2⋮⋮⋱⋮W0,1W0,2⋯W0,0.For0≤j<r and 1≤m, n≤l, we take an m×n submatrix R0,j from W0,j. For the submatrix R0,j, we restrict the locations of its entries in W0,j to be identical (i.e., for 0≤j1, j2<r, the entries of R0,j1 and R0,j2 are taken from identical locations in W0,j1 and W0,j2). Then, we form the following r×r array BR of m×n submatrices over GF(q) with a block-cyclic structure:(4)BR=R0,0R0,1⋯R0,r-1R0,r-1R0,0⋯R0,r-2⋮⋮⋱⋮R0,1R0,2⋯R0,0.We denote the set of rows in the first row blocks ofBR by Γ=[R0,0,R0,1,…,R0,r-1]. So, BR is a submatrix of BW. In forming the r×r array BR of m×n submatrices over GF(q) given by (4), there are l-m rows in each row-block and (l-n) columns in each column-block of BW which are unused. We denote the set of r(l-m) unused rows of BW in each row-block by Π1. So, there are r sections which have a total of l components in each row of Π1. For each section in row, we remove l-n components which are not used in forming the array BR from BW. We denote the set of r(l-m) rows by Π1∗. The rows in set Π1∗ and the rows in set Γ are disjoint. Let s and t be two positive integers with 1≤s≤r(l-m) and 1≤t≤r. We remove the last r-t sections from Π1∗ and take s rows from the remaining sections of Π1∗ to form an s×nt matrix Xgc over GF(q). By taking the t×t diagonal array from the main diagonal of BR and appending the matrix Xgc to the bottom of them, we form the following base matrix of a QC-GC-LDPC code:(5)
B
g
c
,
r
s
=
R
0,0
R
0,0
⋱
R
0,0
X
g
c
.Each entry in the upper subarray ofBgc,rs is equal to R0,0 which is an m×n matrix, and such subarray is calledlocal part. Note that we can use t different member matrices in the set {R0,0,R0,1,…,R0,r-1} as the matrices on the main diagonal of t×t upper subarray of Bgc,rs as well. And we call the lower subarray of Bgc,rsglobal part. The (q-1)-fold dispersion of Bgc,rs results in an (mt+s)×nt array Hgc of (q-1)×(q-1) CPMs and/or ZMs. The null space of Hgc gives a CN-based QC-GC-LDPC code whose Tanner graph has a girth of at least 6.LetRgc be the design rate of a (d¯v,d_v;d¯c,d_c) binary CN-GC-LDPC code, where d¯v and d_v denote the VNs (variable nodes) degrees oflocal part andglobal part, respectively, and d¯c and d_c denote the CNs degrees oflocal part andglobal part, respectively. Then, Rgc=1-(d¯v+d_v)(tm+s)/(tmd¯c+sd_c), 1≤d¯v≤m, 1≤d_v≤s, 1≤d¯c≤n, and 1≤d_c≤nt. For d¯v=m, d_v=s, d¯c=n, and d_c=nt, Rgc is equal to 1-m/n-s/nt.Example 1.
Consider the prime fieldGF(127) for the code construction. Suppose we choose two sets of parameters, l=42, r=3, m=5, n=40, t=3, s=1 and l=21, r=6, m=3, n=21, t=6, s=1. Based on the construction method described above, we form two binary matrices of size 2016×15120 and 2394×15876, respectively. We denote those two matrices as Hgc,1(126,126) and Hgc,2(126,126). For Hgc,1(126,126), it has two column weights, 5 and 6, and two row weights, 39 and 120. The null space of Hgc,1(126,126) gives (15120,13104) CN-based QC-GC-LDPC code C1 with a rate of 0.8667. The Tanner graph of C1 contains 3,165,498 cycles of length 6 and 545,198,472 cycles of length 8. For Hgc,2(126,126), it has two column weights, 3 and 4, and two row weights, 21 and 125. The null space of Hgc,2(126,126) gives (15876,13494) CN-based QC-GC-LDPC code C2 with a rate of 0.85. The Tanner graph of C2 contains 198,828 cycles of length 6 and 21,715,639 cycles of length 8.


## 2.1. CN-Based QC-GC-LDPC Codes

A CN-based QC-GC-LDPC codeCgc is constructed using a base matrix Bgc which consists of two subarrays as shown:(1)
B
g
c
=
b
j
,
k
0
≤
j
<
m
t
+
s
,
0
≤
k
<
n
t
=
B
0
B
1
⋱
B
i
⋱
B
t
-
1
X
g
c
.The upper subarray of Bgc is a t×t diagonal array with m×n matrices Bi on its main diagonal and the lower part is an s×nt matrix Xgc, where 0≤i≤t-1. So, Bgc is an (mt+s)×nt matrix.Consider a finite field GF(q) and let α be a primitive element of GF(q). Let Hgc,qc denote the parity-check matrix of CN-based QC-GC-LDPC code. We can use the base matrix Bgc and (q-1)-fold dispersion to form Hgc,qc as follows: for each entry bj,k in Bgc, if bj,k=0, then replace bj,k=0 by the (q-1)×(q-1) zero matrix (ZM); otherwise, assume bj,k=αl with 0≤l<q-1, and then replace bj,k by a (q-1)×(q-1) circulant permutation matrix (CPM) whose first row has a single 1-component at the lth element. The resultant Hgc,qc is an (mt+s)(q-1)×nt(q-1) matrix over GF(2). The null space of Hgc,qc gives a CN-based QC-GC-LDPC code.From the perspective of graph, letGi be the Tanner graph associated with Bi for 0≤i≤t-1. We call Gl a local Tanner graph. The different Gi are pairwise disjoint (for 0≤j, k≤t-1, and j≠k, Gj and Gk are disjoint). The s global CNs connect all these local graphs, composing the Tanner graph associated with Bgc, denoted as Ggc, as shown in Figure 1 (in this figure, the edge labels are ignored). We see that the s global CNs provide the only connections between any two disjoint local Tanner graphs.Figure 1
The Tanner graph of CN-based QC-GC-LDPC codes.


## 2.2. The Basic Method of Code Construction

Li et al. presented two types of CN-based QC-GC-LDPC codes and their construction methods in [1, 2, 4]. In this subsection, we briefly review the construction method for the first type of QC-GC-LDPC codes in [1]. Let GF(q) be a nonbinary (NB) field with q elements, where q is a power of a prime. Let α be a primitive element of GF(q). Then, the powers of α, namely, α0,α1,α2,…,αq-2, give all the nonzero elements of GF(q) and αq-1=α0=1. We construct the following matrix Brs over GF(q) using the method in [2]:(2)Brs=α0-1α-1⋯αq-2-1αq-2-1α0-1⋯αq-3-1⋮⋮⋱⋮α-1α2-1⋯α0-1.Supposeq-1 can be factored as the product of two positive integers l and r; that is, q-1=lr. The matrix Brs which has a cyclic structure is then an lr×lr square matrix. The first l rows in Brs comprise an l×lr matrix, denoted by W0. Then, W0 can be partitioned into r submatrices of size l×l, denoted by W0,0,W0,1,…,W0,r-1. Based on the cyclic structure of Brs, we can obtain the next l rows in Brs by cyclically shifting all the rows of W0=[W0,0,W0,1,…,W0,r-1]l positions to right, denoted by W1=[W0,r-1,W0,0,…,W0,r-3,W0,r-2]. And so, the matrix Brs can be partitioned into r submatrices of size l×lr, denoted by W0,W1,…,Wi,…,Wr-1, where Wi=[W0,r-i,…,W0,r-1,W0,0,…,W0,r-i-1], 0<i≤r-1. Hence, we can form the following block-cyclic structured matrix BW from Brs:(3)BW=W0,0W0,1⋯W0,r-1W0,r-1W0,0⋯W0,r-2⋮⋮⋱⋮W0,1W0,2⋯W0,0.For0≤j<r and 1≤m, n≤l, we take an m×n submatrix R0,j from W0,j. For the submatrix R0,j, we restrict the locations of its entries in W0,j to be identical (i.e., for 0≤j1, j2<r, the entries of R0,j1 and R0,j2 are taken from identical locations in W0,j1 and W0,j2). Then, we form the following r×r array BR of m×n submatrices over GF(q) with a block-cyclic structure:(4)BR=R0,0R0,1⋯R0,r-1R0,r-1R0,0⋯R0,r-2⋮⋮⋱⋮R0,1R0,2⋯R0,0.We denote the set of rows in the first row blocks ofBR by Γ=[R0,0,R0,1,…,R0,r-1]. So, BR is a submatrix of BW. In forming the r×r array BR of m×n submatrices over GF(q) given by (4), there are l-m rows in each row-block and (l-n) columns in each column-block of BW which are unused. We denote the set of r(l-m) unused rows of BW in each row-block by Π1. So, there are r sections which have a total of l components in each row of Π1. For each section in row, we remove l-n components which are not used in forming the array BR from BW. We denote the set of r(l-m) rows by Π1∗. The rows in set Π1∗ and the rows in set Γ are disjoint. Let s and t be two positive integers with 1≤s≤r(l-m) and 1≤t≤r. We remove the last r-t sections from Π1∗ and take s rows from the remaining sections of Π1∗ to form an s×nt matrix Xgc over GF(q). By taking the t×t diagonal array from the main diagonal of BR and appending the matrix Xgc to the bottom of them, we form the following base matrix of a QC-GC-LDPC code:(5)
B
g
c
,
r
s
=
R
0,0
R
0,0
⋱
R
0,0
X
g
c
.Each entry in the upper subarray ofBgc,rs is equal to R0,0 which is an m×n matrix, and such subarray is calledlocal part. Note that we can use t different member matrices in the set {R0,0,R0,1,…,R0,r-1} as the matrices on the main diagonal of t×t upper subarray of Bgc,rs as well. And we call the lower subarray of Bgc,rsglobal part. The (q-1)-fold dispersion of Bgc,rs results in an (mt+s)×nt array Hgc of (q-1)×(q-1) CPMs and/or ZMs. The null space of Hgc gives a CN-based QC-GC-LDPC code whose Tanner graph has a girth of at least 6.LetRgc be the design rate of a (d¯v,d_v;d¯c,d_c) binary CN-GC-LDPC code, where d¯v and d_v denote the VNs (variable nodes) degrees oflocal part andglobal part, respectively, and d¯c and d_c denote the CNs degrees oflocal part andglobal part, respectively. Then, Rgc=1-(d¯v+d_v)(tm+s)/(tmd¯c+sd_c), 1≤d¯v≤m, 1≤d_v≤s, 1≤d¯c≤n, and 1≤d_c≤nt. For d¯v=m, d_v=s, d¯c=n, and d_c=nt, Rgc is equal to 1-m/n-s/nt.Example 1.
Consider the prime fieldGF(127) for the code construction. Suppose we choose two sets of parameters, l=42, r=3, m=5, n=40, t=3, s=1 and l=21, r=6, m=3, n=21, t=6, s=1. Based on the construction method described above, we form two binary matrices of size 2016×15120 and 2394×15876, respectively. We denote those two matrices as Hgc,1(126,126) and Hgc,2(126,126). For Hgc,1(126,126), it has two column weights, 5 and 6, and two row weights, 39 and 120. The null space of Hgc,1(126,126) gives (15120,13104) CN-based QC-GC-LDPC code C1 with a rate of 0.8667. The Tanner graph of C1 contains 3,165,498 cycles of length 6 and 545,198,472 cycles of length 8. For Hgc,2(126,126), it has two column weights, 3 and 4, and two row weights, 21 and 125. The null space of Hgc,2(126,126) gives (15876,13494) CN-based QC-GC-LDPC code C2 with a rate of 0.85. The Tanner graph of C2 contains 198,828 cycles of length 6 and 21,715,639 cycles of length 8.


## 3. Rate-Compatible GC-LDPC Codes

In this section, we first introduce the concept of graph extension through a four-edge-type LDPC code. Then, we present a construction method of RC GC-LDPC codes.


### 3.1. Four-Edge-Type LDPC Codes

The Tanner graph of a four-edge-type LDPC code is illustrated in Figure2. We partition the VNs into t sections, denoted by p(0),p(1),…,p(t-1), each containing Ns VNs. Every p(i) is then split into two parts: the mother VNs pm(i) of length Nm(i) and the extended VNs pe(i) of length Ne(i); that is, p(i)=[pm(i),pe(i)]. We denote the corresponding coded symbols of VNs as a vector v of size N. At the ith section, we denote the corresponding symbol vectors of pm(i) and pe(i) as vm(i)=[vm,j(i)]0≤j<Nm(i) and ve(i)=[ve,j(i)]0≤j<Ne(i), respectively. Then, we denote by qg the Mg CNs in the lower part which are called global CNs. In the upper part, we partition the CNs into t sections, each containing Ms CNs, denoted by q(0),q(1),…,q(t-1). We split each section of such CNs into two parts: the mother CNs qm(i) of length Mm(i) and the extended CNs qe(i) of length Me(i), where 0≤i<t. We refer to the edges connecting pm(i) and qm(i) as the type 1 edges, the edges connecting pm(i) and qe(i) as the type 2 edges, the edges connecting pe(i) and qe(i) as the type 3 edges, and the edges connecting pm(i) and qg as the type 4 edges.Figure 2
The Tanner graph of four-edge-type LDPC codes.From Figure2, we can see that the mother VN not only is connected to the global CNs by the type 4 edges but also is connected to the mother CNs and the extended CNs by the type 1 edges and the type 2 edges, respectively. However, the extended VNs which have the same number of the extended CNs only are connected to the extended CNs by the type 3 edges. This means that we can form GC-LDPC codes by connecting the mother CNs and the global CNs to the mother VNs in the graph. By extending the new nodes and then increasing new edges of type 2 and type 3, we can continuously form the new GC-LDPC codes. Note that the type 2 edges are the only edges connecting the mother nodes and the extended nodes, so they are quite different from the type 1 edges. Since there are four different types of edges in the Tanner graph, we refer to such LDPC codes asfour-edge-type LDPC codes.For0≤i<t, the submatrices which correspond to the four types of edges are denoted by(6)Hmi=hm,j,ki0≤j<Mmi,0≤k<Nmi,Hm→ei=hm→e,j,ki0≤j<Mei,0≤k<Nmi,Hei=he,j,ki0≤j<Mei,0≤k<Nei,Hm→gi=hm→g,j,ki0≤j<Mg,0≤k<Nmi.Then, the parity-check matrix HFET of four-edge-type LDPC codes can be represented by(7)
H
F
E
T
=
H
m
0
0
H
m
→
e
0
H
e
0
H
m
1
0
H
m
→
e
1
H
e
1
⋱
H
m
t
-
1
0
H
m
→
e
t
-
1
H
e
t
-
1
H
m
→
g
0
0
H
m
→
g
1
0
⋯
H
m
→
g
t
-
1
0
.Analogous to GC-LDPC codes, we call the upper subarraylocal part and the lower subarrayglobal part. We extract Hm(i), Hm→e(i), and He(i) from HFET to form an Mlocal(i)×Nlocal(i) matrix over GF(q) as follows:(8)Hlocali=Hmi0Hm→eiHei,where 0 is an all-zero matrix, Mlocal(i)=Mm(i)+Me(i), and Nlocal(i)=Nm(i)+Ne(i) for 0≤i<t. So, the corresponding base matrix of Hlocal(i) and HFET is Bi and Bgc, respectively.Then, the four-edge-type LDPC code satisfies the following parity-check equation:(9)vmiveiHlocalTi=0,vmiHm→gTi=0.We denote the LDPC code given by the null space ofHFET as CFET and the LDPC code given by the null space of Hlocal(i) as Clocal(i), respectively (where 0≤i<t). Notice that He(i) is square and has a full rank for 0≤i<t, and the entries above He(i) have to be all zero to achieve rate compatibility; thus, Clocal(i) is a RC-LDPC code [16]. We extract Hm(i) and Hm→g(i) from HFET to form an (Mg+∑iMm(i))×∑iNm(i) matrix A over GF(q) as follows: (10)
A
=
H
m
0
H
m
1
⋱
H
m
t
-
1
H
m
→
g
0
H
m
→
g
1
⋯
H
m
→
g
t
-
1
.Then, based on (8) and (9), we have(11)vm0vm1⋯vmt-1AT=0.This means thatHFET is a RC parity-check matrix obtained progressively by extension, in order of decreasing rate [17]. Furthermore, all the mother VNs are connected to qg and there are no edges connecting p(i) and q(j) for i≠j; thus, the four-edge-type LDPC codes can be viewed as a type of RC CN-based QC-GC-LDPC codes.


### 3.2. Construction of Rate-Compatible GC-LDPC Codes

We now present a method to construct RC GC-LDPC codes. Because the extended VNs are not connected toqg, the construction of RC GC-LDPC codes can be realized by successively extending the graph oflocal part. The successive extension of the parity-check matrices oflocal part in the jth section is shown in Figure 3.Figure 3
Parity-check matrix extension in thejth section oflocal part.Assume that we intend to construct a family of four-edge-type LDPC codes containingf member codes C={CFET,0,CFET,1,…,CFET,f-1}. The corresponding target rate set R={RFET,0,RFET,1,…,RFET,f-1} is given. We denote HFET,i as the MFET,i×NFET,i parity-check matrix of CFET,i, where 0≤i<f. At thelocal part of HFET,i, there are t submatrices on the main diagonal of size Mlocal,i(j)×Nlocal,i(j) and we denote each submatrix as Hlocal,i(j), where 0≤i<f and 0≤j<t. So, Hlocal,0(j) is the mother matrix of Hlocal,1(j). And the code rate of CFET,0 is(12)RFET,0=1-RankHFET,0∑jNlocal,0j.SupposeHFET,0 has a full rank:(13)RFET,0=1-Mg+∑jMlocal,0j∑jNlocal,0j.By adding Me,1(j) new rows and Ne,1(j) new columns to mother matrix Hlocal,0(j), we obtain an extended matrix Hlocal,1(j). The upper part of Hlocal,1(j) is composed of a mother matrix Hlocal,0(j) and an all-zero matrix of size Mlocal,0(j)×Ne,1(j). The lower part of Hlocal,1(j) is composed of a matrix Hm→e,1(j) of size Me,1(j)×Nlocal,0(j) and a matrix He,1(j) of size Me,1(j)×Ne,1(j). Thus, the t updated submatrices on the main diagonal of HFET,0 form thelocal part of HFET,1. Then, we partition theglobal part of HFET,0 into t submatrices of size Mg×Nlocal,0(j) and we denote each submatrix as Hm→g,0(j), where 0≤j<t. By adding Mg×Ne,1(j) all-zero matrix to the right of Hm→g,0(j), we form an extended matrix Hm→g,1(j), where 0≤j<t. We combine the t extended submatrices to compose theglobal part of HFET,1. Suppose HFET,1 has a full rank; we have(14)RFET,1=1-Mg+∑jMlocal,1j∑jNlocal,1j=1-Mg+∑jMlocal,0j+∑jMe,1j∑jNlocal,0j+∑jNe,1j.Recursively, for the code CFET,i+1, we can obtain its parity-check matrix HFET,i+1 from the previously generated parity-check matrix HFET,i for CFET,i, 0≤i≤f-2. Suppose HFET,i+1 has a full rank; the rate of the code CFET,i+1 satisfies(15)RFET,i+1=1-Mg+∑jMlocal,i+1j∑jNlocal,i+1j=RFET,i-∑jNe,i+1j∑jNlocal,ij·RFET,i2-RFET,i.In particular, it is not necessary for HFET,1 to be a full-rank matrix for constructing the RC GC-LDPC codes. Using elementary row and column operations of HFET,i, we have (16)
H
F
E
T
,
i
-
1
0
H
e
,
i
0
H
e
,
i
1
H
M
E
,
i
⋱
H
e
,
i
t
-
1
,where (17)HME,i=Hm→e,i0Hm→e,i1⋱Hm→e,it-1and 0<i≤f-1. Consider He,i(j) as a nonsingular matrix, where 0≤j≤t-1; the rank Rank(HFET,i) of HFET,i can be written as (18)RankHFET,i=RankHFET,i-1+∑j=0t-1Me,ij=RankHFET,0+∑k=1i∑j=0t-1Me,kj,where 0<i≤f-1. And it is clear to see that HFET,i can be a full-rank matrix if and only if HFET,0 is a full-rank matrix. The construction for the parity-check matrix of the RC GC-LDPC codes is described in detail in Algorithm 1.Algorithm 1:Algorithm for constructing RC GC-LDPC codes.
Input: q, t, s, f, and R Output: HFET ( 1 ) Using the construction method described in Section 2 to form an MFET,0×NFET,0 matirx HFET,0 which specify a GC-LDPC code CFET,0 with rate RFET,0. ( 2 )  for  i=0:f-2  do ( 3 ) Use HFET,i as the mother matrix. ( 4 )  for  j=0:t-1  do ( 5 ) Generate a matrix Hm→e,i+1(j) of size Me,i+1(i)×Nlocal,i(j). ( 6 ) Generate a matrix He,i+1(j) of size Me,i+1(j)×Ne,i+1(j) which is square and has a full rank. ( 7 )  for  j=0:t-1  do ( 8 ) Compose the parity-check matrix Hlocal,i+1(j) of the form Hlocal,i+1j=Hlocal,ij0Hm→e,i+1jHe,i+1j. ( 9 )  for  j=0:t-1  do ( 10 ) Compose the matrix Hm→g,i+1(j) of the form Hm→g,i+1j=Hm→g,ij0. where 0 is an all-zero matrix of size Mg×Ne,i+1(j). ( 11 ) Compose the matrix HFET,i+1 of the form HFET,i+1=Hlocal,i+10⋱Hlocal,i+1t-1Hm→g,i+10⋯Hm→g,i+1t-1. update i:i=i+1.Furthermore, the RC CN-based QC-GC-LDPC codes with extension structure allow more efficient encoding. Especially for0≤j≤t-1 and 0≤i≤f-1, if He,i(j) is an identity matrix, the encoding of such RC CN-based QC-GC-LDPC codes is more efficient: after encoding the mother VNs, the encoding of the extended VNs only involves XOR operations on the precode output symbols.Example 2.
Consider the prime field GF(193) for code construction. Letl=64, r=3, m=5, n=27, t=3, and s=1. Based on the construction method described in Section 2, we form a 3072×15552 binary matrix Hgc,3(192,192). It has one column weight 6, two row weights, 27 and 81. Based on base graph 1 in 5G standard, we construct a masking matrix Dlocal of size 960×5184 for each submatrix on the main diagonal at the local part of Hgc,3(192,192) [28]. Particularly, the first 2×192 columns of Dlocal are punctured columns. The degree distribution for Dlocal is λ(x)=0.0127+0.0759x+0.7975x2+0.0506x3+0.0633x4, ρ(x)=0.0380x2+0.962x18. λ and ρ are the variable and check degree distributions from the edge perspective. We can construct a 3072×15552 matrix HFET,0 using Dlocal to mask each submatrix on the main diagonal at the local part of Hgc,3(192,192). Suppose f=20. Based on the construction method described in Algorithm 1, we construct a family of four-edge-type LDPC codes. Particularly, by applying graph extension, we obtain the protomatrix of Hm→e,i(j) and He,i(j), where 1≤i≤19 and 0≤j≤2. Particularly, pe(j) and qe(k) are connected by one edge if and only if k=j. In the terminologies of protograph construction, lifting the protograph of Hm→e,i(j) and He,i(j) is equivalent to dispersing the base matrix of them [11]. Then, we can use the method in [29] to find circulants for the protomatrix of Hm→e,i(j) and He,i(j). Based on the construction method described in Algorithm 1, we construct a family of four-edge-type LDPC codes. And we refer to its ith member as CFET,i, where 0≤i≤19. Consider that the four-edge-type LDPC code is constructed based on finite field which guarantees the structural property of algebraic construction, and the Tanner graphs of such codes have a girth of at least 6. The parameters of such family of four-edge-type LDPC codes are summarized in Table 1 and the diagram of its matrix is shown in Figure 4.Table 1
Parameters of a RC GC-LDPC code.
Member Size Code rate N (bits) Degree distribution pair H F E T , 0 3072 × 15552 0.8667 14400 λ x = 0.0189 x + 0.0849 x 2 + 0.7925 x 3 + 0.0472 x 4 + 0.0566 x 5 ρ x = 0.0283 x 2 + 0.7170 x 18 + 0.2547 x 80 H F E T , 1 3648 × 16128 0.8333 14976 λ x = 0.0088 + 0.0175 x + 0.0789 x 2 + 0.5614 x 3 + 0.2193 x 4 + 0.0526 x 5 + 0.0614 x 6 ρ ( x ) = 0.0263 x 2 + 0.0702 x 7 + 0.6667 x 18 + 0.2368 x 80 H F E T , 2 4224 × 16704 0.8025 15552 λ x = 0.0163 + 0.0163 x + 0.0732 x 2 + 0.2927 x 3 + 0.4878 x 4 + 0.0488 x 5 + 0.065 x 7 ρ x = 0.0244 x 2 + 0.065 x 7 + 0.0732 x 8 + 0.6179 x 18 + 0.2195 x 80 H F E T , 4 5376 × 17856 0.7471 16704 λ x = 0.0286 + 0.0143 x + 0.0429 x 2 + 0.1429 x 3 + 0.4286 x 4 + 0.2143 x 5 + 0.0571 x 7 + 0.0714 x 9 ρ x = 0.0214 x 2 + 0.05 x 6 + 0.0571 x 7 + 0.0643 x 8 + 0.0714 x 9 + 0.5429 x 18 + 0.1929 x 80 H F E T , 8 7680 × 20160 0.6566 19008 λ x = 0.0468 + 0.0117 x + 0.0175 x 2 + 0.1170 x 3 + 0.0877 x 4 + 0.2456 x 5 + 0.3275 x 6 + 0.0702 x 11 + 0.076 x 12 ρ ( x ) = 0.0175 x 2 + 0.1228 x 6 + 0.0936 x 7 + 0.1053 x 8 + 0.0585 x 9 + 0.4444 x 18 + 0.1579 x 80 H F E T , 19 14016 × 26496 0.4924 25344 λ x = 0.0802 + 0.0084 x + 0.0338 x 3 + 0.1055 x 4 + 0.0759 x 5 + 0.0591 x 6 + 0.0338 x 7 + 0.1899 x 8 + 0.2532 x 9 + 0.0759 x 17 + 0.0844 x 19 ρ x = 0.0127 x 2 + 0.0422 x 4 + 0.1772 x 5 + 0.1477 x 6 + 0.0675 x 7 + 0.0759 x 8 + 0.0422 x 9 + 0.3207 x 18 + 0.1139 x 80 The first2×192 columns of Hlocal,i(j) and Hm→g(j) are punctured columns, where 0≤i≤19 and 0≤j≤2. λ ( i ) and ρ(i) are the variable and check degree distributions from the edge with HFET,i, respectively, where i=0,1,2,4,8,19.Figure 4
Extension structure of parity-check matrix of the RC GC-LDPC codes in Example2.Example 3.
In order to improve flexibility of code rate, we can puncture the parity bits from a family of four-edge-type LDPC codes. Based onHFET,1 presented in Example 2, for instance, we set the last 98 columns from He,1(j) as punctured columns, where 0≤j≤2. Then, we obtain (14682,12480) GC-LDPC code with a rate of 0.85 and denote it as C3.


## 3.1. Four-Edge-Type LDPC Codes

The Tanner graph of a four-edge-type LDPC code is illustrated in Figure2. We partition the VNs into t sections, denoted by p(0),p(1),…,p(t-1), each containing Ns VNs. Every p(i) is then split into two parts: the mother VNs pm(i) of length Nm(i) and the extended VNs pe(i) of length Ne(i); that is, p(i)=[pm(i),pe(i)]. We denote the corresponding coded symbols of VNs as a vector v of size N. At the ith section, we denote the corresponding symbol vectors of pm(i) and pe(i) as vm(i)=[vm,j(i)]0≤j<Nm(i) and ve(i)=[ve,j(i)]0≤j<Ne(i), respectively. Then, we denote by qg the Mg CNs in the lower part which are called global CNs. In the upper part, we partition the CNs into t sections, each containing Ms CNs, denoted by q(0),q(1),…,q(t-1). We split each section of such CNs into two parts: the mother CNs qm(i) of length Mm(i) and the extended CNs qe(i) of length Me(i), where 0≤i<t. We refer to the edges connecting pm(i) and qm(i) as the type 1 edges, the edges connecting pm(i) and qe(i) as the type 2 edges, the edges connecting pe(i) and qe(i) as the type 3 edges, and the edges connecting pm(i) and qg as the type 4 edges.Figure 2
The Tanner graph of four-edge-type LDPC codes.From Figure2, we can see that the mother VN not only is connected to the global CNs by the type 4 edges but also is connected to the mother CNs and the extended CNs by the type 1 edges and the type 2 edges, respectively. However, the extended VNs which have the same number of the extended CNs only are connected to the extended CNs by the type 3 edges. This means that we can form GC-LDPC codes by connecting the mother CNs and the global CNs to the mother VNs in the graph. By extending the new nodes and then increasing new edges of type 2 and type 3, we can continuously form the new GC-LDPC codes. Note that the type 2 edges are the only edges connecting the mother nodes and the extended nodes, so they are quite different from the type 1 edges. Since there are four different types of edges in the Tanner graph, we refer to such LDPC codes asfour-edge-type LDPC codes.For0≤i<t, the submatrices which correspond to the four types of edges are denoted by(6)Hmi=hm,j,ki0≤j<Mmi,0≤k<Nmi,Hm→ei=hm→e,j,ki0≤j<Mei,0≤k<Nmi,Hei=he,j,ki0≤j<Mei,0≤k<Nei,Hm→gi=hm→g,j,ki0≤j<Mg,0≤k<Nmi.Then, the parity-check matrix HFET of four-edge-type LDPC codes can be represented by(7)
H
F
E
T
=
H
m
0
0
H
m
→
e
0
H
e
0
H
m
1
0
H
m
→
e
1
H
e
1
⋱
H
m
t
-
1
0
H
m
→
e
t
-
1
H
e
t
-
1
H
m
→
g
0
0
H
m
→
g
1
0
⋯
H
m
→
g
t
-
1
0
.Analogous to GC-LDPC codes, we call the upper subarraylocal part and the lower subarrayglobal part. We extract Hm(i), Hm→e(i), and He(i) from HFET to form an Mlocal(i)×Nlocal(i) matrix over GF(q) as follows:(8)Hlocali=Hmi0Hm→eiHei,where 0 is an all-zero matrix, Mlocal(i)=Mm(i)+Me(i), and Nlocal(i)=Nm(i)+Ne(i) for 0≤i<t. So, the corresponding base matrix of Hlocal(i) and HFET is Bi and Bgc, respectively.Then, the four-edge-type LDPC code satisfies the following parity-check equation:(9)vmiveiHlocalTi=0,vmiHm→gTi=0.We denote the LDPC code given by the null space ofHFET as CFET and the LDPC code given by the null space of Hlocal(i) as Clocal(i), respectively (where 0≤i<t). Notice that He(i) is square and has a full rank for 0≤i<t, and the entries above He(i) have to be all zero to achieve rate compatibility; thus, Clocal(i) is a RC-LDPC code [16]. We extract Hm(i) and Hm→g(i) from HFET to form an (Mg+∑iMm(i))×∑iNm(i) matrix A over GF(q) as follows: (10)
A
=
H
m
0
H
m
1
⋱
H
m
t
-
1
H
m
→
g
0
H
m
→
g
1
⋯
H
m
→
g
t
-
1
.Then, based on (8) and (9), we have(11)vm0vm1⋯vmt-1AT=0.This means thatHFET is a RC parity-check matrix obtained progressively by extension, in order of decreasing rate [17]. Furthermore, all the mother VNs are connected to qg and there are no edges connecting p(i) and q(j) for i≠j; thus, the four-edge-type LDPC codes can be viewed as a type of RC CN-based QC-GC-LDPC codes.


## 3.2. Construction of Rate-Compatible GC-LDPC Codes

We now present a method to construct RC GC-LDPC codes. Because the extended VNs are not connected toqg, the construction of RC GC-LDPC codes can be realized by successively extending the graph oflocal part. The successive extension of the parity-check matrices oflocal part in the jth section is shown in Figure 3.Figure 3
Parity-check matrix extension in thejth section oflocal part.Assume that we intend to construct a family of four-edge-type LDPC codes containingf member codes C={CFET,0,CFET,1,…,CFET,f-1}. The corresponding target rate set R={RFET,0,RFET,1,…,RFET,f-1} is given. We denote HFET,i as the MFET,i×NFET,i parity-check matrix of CFET,i, where 0≤i<f. At thelocal part of HFET,i, there are t submatrices on the main diagonal of size Mlocal,i(j)×Nlocal,i(j) and we denote each submatrix as Hlocal,i(j), where 0≤i<f and 0≤j<t. So, Hlocal,0(j) is the mother matrix of Hlocal,1(j). And the code rate of CFET,0 is(12)RFET,0=1-RankHFET,0∑jNlocal,0j.SupposeHFET,0 has a full rank:(13)RFET,0=1-Mg+∑jMlocal,0j∑jNlocal,0j.By adding Me,1(j) new rows and Ne,1(j) new columns to mother matrix Hlocal,0(j), we obtain an extended matrix Hlocal,1(j). The upper part of Hlocal,1(j) is composed of a mother matrix Hlocal,0(j) and an all-zero matrix of size Mlocal,0(j)×Ne,1(j). The lower part of Hlocal,1(j) is composed of a matrix Hm→e,1(j) of size Me,1(j)×Nlocal,0(j) and a matrix He,1(j) of size Me,1(j)×Ne,1(j). Thus, the t updated submatrices on the main diagonal of HFET,0 form thelocal part of HFET,1. Then, we partition theglobal part of HFET,0 into t submatrices of size Mg×Nlocal,0(j) and we denote each submatrix as Hm→g,0(j), where 0≤j<t. By adding Mg×Ne,1(j) all-zero matrix to the right of Hm→g,0(j), we form an extended matrix Hm→g,1(j), where 0≤j<t. We combine the t extended submatrices to compose theglobal part of HFET,1. Suppose HFET,1 has a full rank; we have(14)RFET,1=1-Mg+∑jMlocal,1j∑jNlocal,1j=1-Mg+∑jMlocal,0j+∑jMe,1j∑jNlocal,0j+∑jNe,1j.Recursively, for the code CFET,i+1, we can obtain its parity-check matrix HFET,i+1 from the previously generated parity-check matrix HFET,i for CFET,i, 0≤i≤f-2. Suppose HFET,i+1 has a full rank; the rate of the code CFET,i+1 satisfies(15)RFET,i+1=1-Mg+∑jMlocal,i+1j∑jNlocal,i+1j=RFET,i-∑jNe,i+1j∑jNlocal,ij·RFET,i2-RFET,i.In particular, it is not necessary for HFET,1 to be a full-rank matrix for constructing the RC GC-LDPC codes. Using elementary row and column operations of HFET,i, we have (16)
H
F
E
T
,
i
-
1
0
H
e
,
i
0
H
e
,
i
1
H
M
E
,
i
⋱
H
e
,
i
t
-
1
,where (17)HME,i=Hm→e,i0Hm→e,i1⋱Hm→e,it-1and 0<i≤f-1. Consider He,i(j) as a nonsingular matrix, where 0≤j≤t-1; the rank Rank(HFET,i) of HFET,i can be written as (18)RankHFET,i=RankHFET,i-1+∑j=0t-1Me,ij=RankHFET,0+∑k=1i∑j=0t-1Me,kj,where 0<i≤f-1. And it is clear to see that HFET,i can be a full-rank matrix if and only if HFET,0 is a full-rank matrix. The construction for the parity-check matrix of the RC GC-LDPC codes is described in detail in Algorithm 1.Algorithm 1:Algorithm for constructing RC GC-LDPC codes.
Input: q, t, s, f, and R Output: HFET ( 1 ) Using the construction method described in Section 2 to form an MFET,0×NFET,0 matirx HFET,0 which specify a GC-LDPC code CFET,0 with rate RFET,0. ( 2 )  for  i=0:f-2  do ( 3 ) Use HFET,i as the mother matrix. ( 4 )  for  j=0:t-1  do ( 5 ) Generate a matrix Hm→e,i+1(j) of size Me,i+1(i)×Nlocal,i(j). ( 6 ) Generate a matrix He,i+1(j) of size Me,i+1(j)×Ne,i+1(j) which is square and has a full rank. ( 7 )  for  j=0:t-1  do ( 8 ) Compose the parity-check matrix Hlocal,i+1(j) of the form Hlocal,i+1j=Hlocal,ij0Hm→e,i+1jHe,i+1j. ( 9 )  for  j=0:t-1  do ( 10 ) Compose the matrix Hm→g,i+1(j) of the form Hm→g,i+1j=Hm→g,ij0. where 0 is an all-zero matrix of size Mg×Ne,i+1(j). ( 11 ) Compose the matrix HFET,i+1 of the form HFET,i+1=Hlocal,i+10⋱Hlocal,i+1t-1Hm→g,i+10⋯Hm→g,i+1t-1. update i:i=i+1.Furthermore, the RC CN-based QC-GC-LDPC codes with extension structure allow more efficient encoding. Especially for0≤j≤t-1 and 0≤i≤f-1, if He,i(j) is an identity matrix, the encoding of such RC CN-based QC-GC-LDPC codes is more efficient: after encoding the mother VNs, the encoding of the extended VNs only involves XOR operations on the precode output symbols.Example 2.
Consider the prime field GF(193) for code construction. Letl=64, r=3, m=5, n=27, t=3, and s=1. Based on the construction method described in Section 2, we form a 3072×15552 binary matrix Hgc,3(192,192). It has one column weight 6, two row weights, 27 and 81. Based on base graph 1 in 5G standard, we construct a masking matrix Dlocal of size 960×5184 for each submatrix on the main diagonal at the local part of Hgc,3(192,192) [28]. Particularly, the first 2×192 columns of Dlocal are punctured columns. The degree distribution for Dlocal is λ(x)=0.0127+0.0759x+0.7975x2+0.0506x3+0.0633x4, ρ(x)=0.0380x2+0.962x18. λ and ρ are the variable and check degree distributions from the edge perspective. We can construct a 3072×15552 matrix HFET,0 using Dlocal to mask each submatrix on the main diagonal at the local part of Hgc,3(192,192). Suppose f=20. Based on the construction method described in Algorithm 1, we construct a family of four-edge-type LDPC codes. Particularly, by applying graph extension, we obtain the protomatrix of Hm→e,i(j) and He,i(j), where 1≤i≤19 and 0≤j≤2. Particularly, pe(j) and qe(k) are connected by one edge if and only if k=j. In the terminologies of protograph construction, lifting the protograph of Hm→e,i(j) and He,i(j) is equivalent to dispersing the base matrix of them [11]. Then, we can use the method in [29] to find circulants for the protomatrix of Hm→e,i(j) and He,i(j). Based on the construction method described in Algorithm 1, we construct a family of four-edge-type LDPC codes. And we refer to its ith member as CFET,i, where 0≤i≤19. Consider that the four-edge-type LDPC code is constructed based on finite field which guarantees the structural property of algebraic construction, and the Tanner graphs of such codes have a girth of at least 6. The parameters of such family of four-edge-type LDPC codes are summarized in Table 1 and the diagram of its matrix is shown in Figure 4.Table 1
Parameters of a RC GC-LDPC code.
Member Size Code rate N (bits) Degree distribution pair H F E T , 0 3072 × 15552 0.8667 14400 λ x = 0.0189 x + 0.0849 x 2 + 0.7925 x 3 + 0.0472 x 4 + 0.0566 x 5 ρ x = 0.0283 x 2 + 0.7170 x 18 + 0.2547 x 80 H F E T , 1 3648 × 16128 0.8333 14976 λ x = 0.0088 + 0.0175 x + 0.0789 x 2 + 0.5614 x 3 + 0.2193 x 4 + 0.0526 x 5 + 0.0614 x 6 ρ ( x ) = 0.0263 x 2 + 0.0702 x 7 + 0.6667 x 18 + 0.2368 x 80 H F E T , 2 4224 × 16704 0.8025 15552 λ x = 0.0163 + 0.0163 x + 0.0732 x 2 + 0.2927 x 3 + 0.4878 x 4 + 0.0488 x 5 + 0.065 x 7 ρ x = 0.0244 x 2 + 0.065 x 7 + 0.0732 x 8 + 0.6179 x 18 + 0.2195 x 80 H F E T , 4 5376 × 17856 0.7471 16704 λ x = 0.0286 + 0.0143 x + 0.0429 x 2 + 0.1429 x 3 + 0.4286 x 4 + 0.2143 x 5 + 0.0571 x 7 + 0.0714 x 9 ρ x = 0.0214 x 2 + 0.05 x 6 + 0.0571 x 7 + 0.0643 x 8 + 0.0714 x 9 + 0.5429 x 18 + 0.1929 x 80 H F E T , 8 7680 × 20160 0.6566 19008 λ x = 0.0468 + 0.0117 x + 0.0175 x 2 + 0.1170 x 3 + 0.0877 x 4 + 0.2456 x 5 + 0.3275 x 6 + 0.0702 x 11 + 0.076 x 12 ρ ( x ) = 0.0175 x 2 + 0.1228 x 6 + 0.0936 x 7 + 0.1053 x 8 + 0.0585 x 9 + 0.4444 x 18 + 0.1579 x 80 H F E T , 19 14016 × 26496 0.4924 25344 λ x = 0.0802 + 0.0084 x + 0.0338 x 3 + 0.1055 x 4 + 0.0759 x 5 + 0.0591 x 6 + 0.0338 x 7 + 0.1899 x 8 + 0.2532 x 9 + 0.0759 x 17 + 0.0844 x 19 ρ x = 0.0127 x 2 + 0.0422 x 4 + 0.1772 x 5 + 0.1477 x 6 + 0.0675 x 7 + 0.0759 x 8 + 0.0422 x 9 + 0.3207 x 18 + 0.1139 x 80 The first2×192 columns of Hlocal,i(j) and Hm→g(j) are punctured columns, where 0≤i≤19 and 0≤j≤2. λ ( i ) and ρ(i) are the variable and check degree distributions from the edge with HFET,i, respectively, where i=0,1,2,4,8,19.Figure 4
Extension structure of parity-check matrix of the RC GC-LDPC codes in Example2.Example 3.
In order to improve flexibility of code rate, we can puncture the parity bits from a family of four-edge-type LDPC codes. Based onHFET,1 presented in Example 2, for instance, we set the last 98 columns from He,1(j) as punctured columns, where 0≤j≤2. Then, we obtain (14682,12480) GC-LDPC code with a rate of 0.85 and denote it as C3.


## 4. Local/Global Two-Phase Decoding Scheme

For classical iterative decoding scheme, the decoder includes all the VNs in a block and performs total decoding operations in one phase [30]. We refer to such an iterative decoding scheme asone-phase iterative scheme. In contrast to classical iterative decoding scheme, Li et al. devised atwo-phase local/global iterative scheme for CN-GC-LDPC codes [1, 2]. Taking advantage of the cascading structure oflocal part, we can splitlocal part into t independent sections. And each section can use an independent decoder at the local phase. If all sections oflocal part are successfully decoded and the locally decoded codeword satisfies the parity-check constraints inglobal part, the locally decoded codeword would be delivered to the user. If it does not, the global decoder starts to process the received codeword from the local decoder. In a good channel environment, we only need to use a group of (t or less) local decoders to process a group of (t or less) consecutive received sections in parallel. This means that we can process a consecutive sequence by some local sequences for a GC-LDPC code. The advantage of this decoding scheme is that lower latency and less memory requirements are required by the decoder. We refer to such a scheme asnormal two-phase local/global iterative scheme. However, in a bad channel environment, we find that the local decoder performs a plenty of useless operations, which causes the unnecessary cost of the decoder. Therefore, we present amodified two-phase local/global iterative decoding scheme for CN-GC-LDPC codes.


### 4.1. Modified Local/Global Two-Phase Iterative Decoding Scheme

Letz=(z0,z1,…,zt-1) be the received sequences. Firstly, in local phase of decoding, t received sequences are decoded by t independent decoders with the maximum iteration number Imax1. If all the sections are successfully decoded and the locally decoded codeword satisfies the parity-check constraints inglobal part, the locally decoded codeword could be delivered to the user. If one of the decoders fails to decode a received section, we switch the decoding from the local phase to the global phase. If all sections are successfully decoded, but the locally decoded codeword does not satisfy the parity-check constraints inglobal part, save the decoded information (LLRs) and return to the local decoder. We set the maximum iteration number of local decoders to Imax2. Then, if one of the decoders fails to decode a received section or the locally decoded codeword does not satisfy the parity-check constraints inglobal part, we switch the decoding from local phase to global phase.In global phase of decoding, a global decoder is activated. It processes the received vectorz with the channel information and the combined decoded information (LLRs) of successfully decoded sections as inputs. And the diagram ofmodified two-phase local/global decoding iterative scheme is illustrated in Figure 5.Figure 5
Modified local/global two-phase iterative decoding scheme.We define the order of decoding complexity as the number of operations required per information bit and denote the order of decoding complexity for the normal two-phase decoding algorithm asOnormal. Suppose the number of operations for one iteration of global part is OG and the number of operations for one iteration in the jth section of local part is OL(j), where 0<j≤t-1. As stated in [1–3], we have(19)Onormal=1KOGIG+∑j=0t-1OLjILj,where K is the length of the information bits, IL(j)(0≤IL(j)≤Imax) is the number of iterations involving updates of variables in the jth section of the local part, and IG is the number of iterations involving updates of variables in the global part. Then, the order of decoding complexity of the modified two-phase decoding algorithm, which is denoted as Omodified, can be summarized as(20)Omodified=1K∑j=0t-1OLjIL1j+IL2j+OGIG,where IL1(j)(0≤IL1(j)≤Imax1) and IL2(j)(0≤IL2(j)≤Imax2) are the number of iterations involving updates of variables in the jth section of the local part in which maximum iterations number is Imax1 and Imax2, respectively. As can be seen, in a bad channel environment, few sections are successfully decoded at first local phase. And each successfully decoded section performs not more than Imax1 iteration operations. So, we have(21)Onormal≈1KOGIG+∑j=0t-1OLjImax,Omodified≈1KOGIG+OL0Imax10.Considering Imax1(0)≪Imax, we have Omodified≪Onormal. Moreover, in a good channel environment, most successfully decoded sections satisfy the parity-check constraints inglobal part. Not more than (Imax1+Imax2) iteration operations are required in each successfully decoded section. For Imax=Imax1+Imax2, we have Omodified≈Onormal.


## 4.1. Modified Local/Global Two-Phase Iterative Decoding Scheme

Letz=(z0,z1,…,zt-1) be the received sequences. Firstly, in local phase of decoding, t received sequences are decoded by t independent decoders with the maximum iteration number Imax1. If all the sections are successfully decoded and the locally decoded codeword satisfies the parity-check constraints inglobal part, the locally decoded codeword could be delivered to the user. If one of the decoders fails to decode a received section, we switch the decoding from the local phase to the global phase. If all sections are successfully decoded, but the locally decoded codeword does not satisfy the parity-check constraints inglobal part, save the decoded information (LLRs) and return to the local decoder. We set the maximum iteration number of local decoders to Imax2. Then, if one of the decoders fails to decode a received section or the locally decoded codeword does not satisfy the parity-check constraints inglobal part, we switch the decoding from local phase to global phase.In global phase of decoding, a global decoder is activated. It processes the received vectorz with the channel information and the combined decoded information (LLRs) of successfully decoded sections as inputs. And the diagram ofmodified two-phase local/global decoding iterative scheme is illustrated in Figure 5.Figure 5
Modified local/global two-phase iterative decoding scheme.We define the order of decoding complexity as the number of operations required per information bit and denote the order of decoding complexity for the normal two-phase decoding algorithm asOnormal. Suppose the number of operations for one iteration of global part is OG and the number of operations for one iteration in the jth section of local part is OL(j), where 0<j≤t-1. As stated in [1–3], we have(19)Onormal=1KOGIG+∑j=0t-1OLjILj,where K is the length of the information bits, IL(j)(0≤IL(j)≤Imax) is the number of iterations involving updates of variables in the jth section of the local part, and IG is the number of iterations involving updates of variables in the global part. Then, the order of decoding complexity of the modified two-phase decoding algorithm, which is denoted as Omodified, can be summarized as(20)Omodified=1K∑j=0t-1OLjIL1j+IL2j+OGIG,where IL1(j)(0≤IL1(j)≤Imax1) and IL2(j)(0≤IL2(j)≤Imax2) are the number of iterations involving updates of variables in the jth section of the local part in which maximum iterations number is Imax1 and Imax2, respectively. As can be seen, in a bad channel environment, few sections are successfully decoded at first local phase. And each successfully decoded section performs not more than Imax1 iteration operations. So, we have(21)Onormal≈1KOGIG+∑j=0t-1OLjImax,Omodified≈1KOGIG+OL0Imax10.Considering Imax1(0)≪Imax, we have Omodified≪Onormal. Moreover, in a good channel environment, most successfully decoded sections satisfy the parity-check constraints inglobal part. Not more than (Imax1+Imax2) iteration operations are required in each successfully decoded section. For Imax=Imax1+Imax2, we have Omodified≈Onormal.


## 5. Numerical Results

In this section, we first present the simulation performance for RC GC-LDPC codes over the AWGN channel. Then, we compare the decoding complexity of different decoding schemes presented in Section4. The decoding latency with different decoding schemes is also discussed.


### 5.1. Error-Correcting Performance

We now provide the simulated BER and BLER performances for RC GC-LDPC codes over the AWGN channel with QPSK signaling. It is assumed that all the simulations are performed using the belief propagation (BP) algorithm with the maximum iteration number 50, if not specified. The BER and BLER performances for different code rates are plotted in Figure6 together with the corresponding Shannon limits. The iterative decoding thresholds achieved by the proposed RC GC-LDPC codes are summarized in Table 2. It can be seen that the gaps between the iterative decoding thresholds and the Shannon limits are very small. Figure 7 depicts the BER and BLER performances of Examples 1, 2, and 3. We then see that the proposed RC GC-LDPC codes are better than the QC-GC-LDPC codes formed by the classical method in Section 2.Table 2
Parameters of a RC GC-LDPC code.
Member Code rate Protograph threshold (dB) Shannon limit (dB) Gap to capacity (dB) H F E T , 0 0.8667 3.1919 2.7381 0.4538 H F E T , 1 0.8333 2.7292 2.3167 0.4125 H F E T , 2 0.8025 2.4967 2.0491 0.4476 H F E T , 4 0.7471 2.0461 1.5853 0.4608 H F E T , 8 0.6566 1.4321 0.9605 0.4716 H F E T , 19 0.4924 0.4879 0.1435 0.3444Figure 6
The BER and BLER performances for different code rates ofCFET,0, CFET,2, CFET,4, CFET,8, and CFET,19 over the AWGN channel with QPSK signaling.Figure 7
The BER and BLER performances of QC-GC-LDPC codes ofC1, C2, CFET,0, and C3 over the AWGN channel with QPSK signaling.


### 5.2. Decoding Complexity

Figures8 and 9 depict the average iteration number of C1 and CFET,0 withone-phase,normal two-phase local/global, andmodified two-phase local/global iterative schemes based on the BP decoding algorithm, respectively. For both C1 and CFET,0, the maximum iteration number ofone-phase iterative scheme is set to 50. The maximum iteration numbers in local decoder and global decoder ofnormal two-phase local/global iterative scheme with them are 50 and 100, respectively. Formodified two-phase local/global iterative scheme, Imax1, Imax2, and the maximum iteration number in global decoder of C1 are 30, 20, and 50, respectively. And Imax1, Imax2, and the maximum iteration number in global decoder of CFET,0 are 60, 40, and 100, respectively. Based on Figures 8 and 9, we conclude that thenormal two-phase local/global iterative scheme requires a significantly higher number of iterations thanmodified two-phase local/global iterative scheme at local phase and needs approximately the same iteration number as the modified scheme at global phase, especially at low and moderate SNRs. At high SNRs,two-phase local/global iterative scheme requires a smaller number of iterations thanone-phase iterative scheme without performance hit.Figure 8
Average iteration number ofone-phase,normal two-phase local/global, andmodified two-phase local/global iterative scheme based on BP decoding algorithm with C1.Figure 9
Average iteration number ofone-phase,normal two-phase local/global, andmodified two-phase local/global iterative scheme based on BP decoding algorithm with CFET,0.Figures10 and 11 depict the decoding complexity of C1 and CFET,0 withone-phase,normal two-phase local/global, andmodified two-phase local/global iterative schemes based on BP decoding algorithm, respectively. All operations associated with modulo-2 arithmetic have been neglected as conventionally done. The decoding complexity associated with BP algorithm is evaluated based on the forward and backward recursions proposed in [7]. For C1, the total complexity associated with one iteration of BP consists of 877,338real multiplications, 104,328real divisions, and 282,366real additions at global phase. At local phase, it consists of 237,258real multiplications, 29,736real divisions, and 79,002real additions in each local decoder. For CFET,0, the total complexity associated with one iteration of BP consists of 559,872real multiplications, 76,608real divisions, and 198,720real additions at global phase. At local phase, it consists of 129,984real multiplications, 20,352real divisions, and 20,352real additions in each local decoder. Based on Figures 10 and 11, we conclude that thenormal two-phase local/global iterative scheme requires significantly more operations thanmodified two-phase local/global iterative scheme at low and moderate SNRs.Figure 10
Decoding complexity ofC1 withone-phase,normal two-phase local/global, andmodified two-phase local/global iterative scheme based on BP decoding algorithm.Figure 11
Decoding complexity ofCFET,0 withone-phase,normal two-phase local/global, andmodified two-phase local/global iterative scheme based on BP decoding algorithm.


### 5.3. Decoding Latency

The decoding delay in a data transmission system is defined as the delay incurred in receiving the coded bits before decoding takes place and the ensuing decoder processing delay in [31]. In this paper, we assume that all schemes being compared have approximately the same decoding complexity, but the decoder processing time is negligible. Forone-phase iterative scheme, no information symbols are decoded until an entire block is received. Thus, the maximum decoding delay experienced by an information bit when LDPC code is used forone-phase iterative scheme is the arrival time of one incoming block. Suppose its number of iterations is Itotal. Then, the total decoding latency in received symbols and the total number of soft received values that must be stored in the decoder memory at any given time (decoding latency for short) can be represented by ItotalN, where N is the total number of symbols. Fortwo-phase local/global iterative scheme, all information symbols are assigned to t local decoders. Suppose the number of iterations in global phase is Iglobal. For the jth local decoder intwo-phase local/global iterative scheme, suppose the number of iterations is Ij. So, IglobalN+∑j=0t-1IjNlocal represents the decoding latency oftwo-phase local/global iterative scheme. By using t local decoders in fully parallel local phase decoding, the maximum decoding delay experienced by an information bit is the arrival time of each incoming block in local decoder. Then, the decoding latency reduces to IglobalN+max{IjNlocal,0≤j≤t-1}. Note that Iglobal decreases with the increase of SNR. At moderate and high SNRs, the decoding latency approaches max{IjNlocal,0≤j≤t-1} when Iglobal→0. Since Nlocal≪N and Itotal≈max{Ij,0≤j≤t-1}, then max{IjNlocal,0≤j≤t-1}≪ItotalN. This means that latency and memory requirements oftwo-phase local/global iterative scheme are much less than for theone-phase iterative scheme when the channel environment is better.


## 5.1. Error-Correcting Performance

We now provide the simulated BER and BLER performances for RC GC-LDPC codes over the AWGN channel with QPSK signaling. It is assumed that all the simulations are performed using the belief propagation (BP) algorithm with the maximum iteration number 50, if not specified. The BER and BLER performances for different code rates are plotted in Figure6 together with the corresponding Shannon limits. The iterative decoding thresholds achieved by the proposed RC GC-LDPC codes are summarized in Table 2. It can be seen that the gaps between the iterative decoding thresholds and the Shannon limits are very small. Figure 7 depicts the BER and BLER performances of Examples 1, 2, and 3. We then see that the proposed RC GC-LDPC codes are better than the QC-GC-LDPC codes formed by the classical method in Section 2.Table 2
Parameters of a RC GC-LDPC code.
Member Code rate Protograph threshold (dB) Shannon limit (dB) Gap to capacity (dB) H F E T , 0 0.8667 3.1919 2.7381 0.4538 H F E T , 1 0.8333 2.7292 2.3167 0.4125 H F E T , 2 0.8025 2.4967 2.0491 0.4476 H F E T , 4 0.7471 2.0461 1.5853 0.4608 H F E T , 8 0.6566 1.4321 0.9605 0.4716 H F E T , 19 0.4924 0.4879 0.1435 0.3444Figure 6
The BER and BLER performances for different code rates ofCFET,0, CFET,2, CFET,4, CFET,8, and CFET,19 over the AWGN channel with QPSK signaling.Figure 7
The BER and BLER performances of QC-GC-LDPC codes ofC1, C2, CFET,0, and C3 over the AWGN channel with QPSK signaling.


## 5.2. Decoding Complexity

Figures8 and 9 depict the average iteration number of C1 and CFET,0 withone-phase,normal two-phase local/global, andmodified two-phase local/global iterative schemes based on the BP decoding algorithm, respectively. For both C1 and CFET,0, the maximum iteration number ofone-phase iterative scheme is set to 50. The maximum iteration numbers in local decoder and global decoder ofnormal two-phase local/global iterative scheme with them are 50 and 100, respectively. Formodified two-phase local/global iterative scheme, Imax1, Imax2, and the maximum iteration number in global decoder of C1 are 30, 20, and 50, respectively. And Imax1, Imax2, and the maximum iteration number in global decoder of CFET,0 are 60, 40, and 100, respectively. Based on Figures 8 and 9, we conclude that thenormal two-phase local/global iterative scheme requires a significantly higher number of iterations thanmodified two-phase local/global iterative scheme at local phase and needs approximately the same iteration number as the modified scheme at global phase, especially at low and moderate SNRs. At high SNRs,two-phase local/global iterative scheme requires a smaller number of iterations thanone-phase iterative scheme without performance hit.Figure 8
Average iteration number ofone-phase,normal two-phase local/global, andmodified two-phase local/global iterative scheme based on BP decoding algorithm with C1.Figure 9
Average iteration number ofone-phase,normal two-phase local/global, andmodified two-phase local/global iterative scheme based on BP decoding algorithm with CFET,0.Figures10 and 11 depict the decoding complexity of C1 and CFET,0 withone-phase,normal two-phase local/global, andmodified two-phase local/global iterative schemes based on BP decoding algorithm, respectively. All operations associated with modulo-2 arithmetic have been neglected as conventionally done. The decoding complexity associated with BP algorithm is evaluated based on the forward and backward recursions proposed in [7]. For C1, the total complexity associated with one iteration of BP consists of 877,338real multiplications, 104,328real divisions, and 282,366real additions at global phase. At local phase, it consists of 237,258real multiplications, 29,736real divisions, and 79,002real additions in each local decoder. For CFET,0, the total complexity associated with one iteration of BP consists of 559,872real multiplications, 76,608real divisions, and 198,720real additions at global phase. At local phase, it consists of 129,984real multiplications, 20,352real divisions, and 20,352real additions in each local decoder. Based on Figures 10 and 11, we conclude that thenormal two-phase local/global iterative scheme requires significantly more operations thanmodified two-phase local/global iterative scheme at low and moderate SNRs.Figure 10
Decoding complexity ofC1 withone-phase,normal two-phase local/global, andmodified two-phase local/global iterative scheme based on BP decoding algorithm.Figure 11
Decoding complexity ofCFET,0 withone-phase,normal two-phase local/global, andmodified two-phase local/global iterative scheme based on BP decoding algorithm.


## 5.3. Decoding Latency

The decoding delay in a data transmission system is defined as the delay incurred in receiving the coded bits before decoding takes place and the ensuing decoder processing delay in [31]. In this paper, we assume that all schemes being compared have approximately the same decoding complexity, but the decoder processing time is negligible. Forone-phase iterative scheme, no information symbols are decoded until an entire block is received. Thus, the maximum decoding delay experienced by an information bit when LDPC code is used forone-phase iterative scheme is the arrival time of one incoming block. Suppose its number of iterations is Itotal. Then, the total decoding latency in received symbols and the total number of soft received values that must be stored in the decoder memory at any given time (decoding latency for short) can be represented by ItotalN, where N is the total number of symbols. Fortwo-phase local/global iterative scheme, all information symbols are assigned to t local decoders. Suppose the number of iterations in global phase is Iglobal. For the jth local decoder intwo-phase local/global iterative scheme, suppose the number of iterations is Ij. So, IglobalN+∑j=0t-1IjNlocal represents the decoding latency oftwo-phase local/global iterative scheme. By using t local decoders in fully parallel local phase decoding, the maximum decoding delay experienced by an information bit is the arrival time of each incoming block in local decoder. Then, the decoding latency reduces to IglobalN+max{IjNlocal,0≤j≤t-1}. Note that Iglobal decreases with the increase of SNR. At moderate and high SNRs, the decoding latency approaches max{IjNlocal,0≤j≤t-1} when Iglobal→0. Since Nlocal≪N and Itotal≈max{Ij,0≤j≤t-1}, then max{IjNlocal,0≤j≤t-1}≪ItotalN. This means that latency and memory requirements oftwo-phase local/global iterative scheme are much less than for theone-phase iterative scheme when the channel environment is better.


## 6. Conclusion

In this paper, we introduced the graph extension through a four-edge-type LDPC code and presented a family of RC GC-LDPC codes; they are constructed by combining algebraic method and graph extension. It was shown that the proposed family of RC CN-GC-LDPC codes can provide more flexibility in code rate and guarantee the structural property of algebraic construction. It is confirmed, by numerical simulations over the AWGN channel, that the proposed RC GC-LDPC codes outperform their counterpart QC-GC-LDPC codes formed by the method in [1, 2] in terms of waterfall performance and exhibit an approximately uniform gap to the capacity over a wide range of rates. Moreover, we presented amodified two-phase local/global iterative scheme which can reduce unnecessary cost of local decoders at low and moderate SNRs.



---

*Source: 4397671-2018-05-02.xml*