# Design of Nonbinary LDPC Cycle Codes with Large Girth from Circulants and Finite Fields

Authors: Hengzhou Xu; Huaan Li; Jixun Gao; Guixiang Zhang; Hai Zhu; Xiao-Dong Zhang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

In this paper, we study a class of nonbinary LDPC (NBLDPC) codes whose parity-check matrices have column weight 2, called NBLDPC cycle codes. We propose a design framework of2,ρ-regular binary quasi-cyclic (QC) LDPC codes and then construct NBLDPC cycle codes of large girth based on circulants and finite fields by randomly choosing the nonzero field elements in their parity-check matrices. For enlarging the girth values, our approach is twofold. First, we give an exhaustive search of circulants with column/row weight ρ and design a masking matrix with good cycle distribution based on the edge-node relation in undirected graphs. Second, according to the designed masking matrix, we construct the exponent matrix based on finite fields. The iterative decoding performances of the constructed codes on the additive white Gaussian noise (AWGN) channel are finally provided.


---

## Body

## 1. Introduction

Nonbinary low-density parity-check (NBLDPC) codes based on modulo arithmetics were first discovered by Gallager in 1960s [1] and redefined over finite fields GF q by Davey and MacKay in 1998 [2]. Similar to binary LDPC codes, NBLDPC codes also have the ability of approaching capacity when decoded with the iterative algorithms. Moreover, NBLDPC codes have much better performance than binary LDPC codes for the short and moderate code lengths. As much more low-complexity decoding algorithms were proposed [3–8], NBLDPC codes provide a promising coding scheme for 6G communications [9].As shown in [10], NBLDPC codes over larger finite fields will have much better performance for a constant code length. However, when the finite field size is sufficiently large, the performance improvement is little. Moreover, when the finite field size is equal or greater than 64, the column weights of the parity-check matrices of good NBLDPC codes tend to 2. Since NBLDPC cycle codes perform well over various channels [11–13], it is worth studying NBLDPC codes over large finite fields whose parity-check matrices have column weight 2, referred to as NBLDPC cycle codes. As an important cycle codes, 2,ρ-regular NBLDPC codes also perform well under iterative decoding; lots of methods for constructing such codes were proposed [14–17]. Among these works on the construction of NBLDPC codes, the codes can be mainly classified into two categories: the first one is constructed by means of computer search under the algorithms satisfying certain rules, and the other one is constructed based on combinatorial designs, graph theory, matrix theory, and finite fields [18]. Simulation results show that they all have good performance. For a given code rate and length, it is of great interest to study which one of them has the best error performance.Cycle structure plays an important role in binary/nonbinary LDPC codes. Research results show that NBLDPC codes with large girth have good iterative performance [19]. In general, NBLDPC codes with large girth have large Hamming minimum distance, and it can be ensured that NBLDPC codes have good performance in the waterfall and error-floor region. Hence, it is interesting to construct LDPC cycle codes with large girth.In this paper, we focus on the construction of2,ρ-regular quasi-cyclic LDPC (QC-LDPC) codes with large girth. We first proposed the construction framework of 2,ρ-regular QC-LDPC codes based on the edge-node relation in undirected graphs and transfer the construction of 2,ρ-regular QC-LDPC codes into two main parts, i.e., circulants and exponent matrices. In the first part, we find circulants with good cycle distribution by performing an exhaustive search. In order to prune the search space of circulants, isomorphism theory of circulants is proposed. For the second part, we directly employ finite fields to construct exponent matrices of QC-LDPC codes. Here, the employed finite fields are divided two types, i.e., prime fields and finite fields of characteristic 2. Finally, numerical results to show the good performance of our proposed codes are provided.The rest of this paper is organized as follows. Section 2 introduces the definitions of LDPC codes and their associated Tanner graphs. Section 3 presents the design framework of2,ρ-regular QC-LDPC codes. Design of NBLDPC cycle codes with large girth is proposed in Section 4, and numerical results are also provided in this section. Finally, Section 5 concludes this paper.


## 2. Preliminaries

### 2.1. LDPC Codes

A binaryγ,ρ-regular LDPC code is generated by the null space of an m×n sparse parity-check matrix H over GF (2), and the matrix H has the following properties: (1) each column has γ 1’s; (2) each row has ρ 1’s; (3) γ≪m and ρ≪n. If the sparse matrix H is over GF (q) for q being a prime power, then LDPC codes generated by such H are called nonbinary codes or q-ary codes. Binary LDPC codes are referred to as quasi-cyclic (QC) [20], if their parity-check matrices H have the following form
(1)H=Ip1,1Ip1,2Ip1,3⋯Ip1,ρIp2,1Ip2,2Ip2,3⋯Ip2,ρIp3,1Ip3,2Ip3,3⋯Ip3,ρ⋮⋮⋮⋱⋮Ipγ,1Ipγ,2Ipγ,3⋯Ipγ,ργQ×ρQ,where for 1≤i≤γ,1≤j≤ρ,−1≤pi,j≤Q−1, Ipi,j is a Q×Q circulant permutation matrix (CPM) formed by cyclically shifting each row of a Q×Q identity matrix I to the right (or left) by pi,jmodQ positions, and I−1 is a zero matrix of size Q×Q. Obviously, I0 is an identity matrix of size Q×Q. For example, if Q=4, then
(2)I0=1000010000100001,I1=100010001000,I2=0010000110000100,I3=0001100001000010.We can easily see that the positions of 1’s ofH in (1) are uniquely determined by the following matrix P, called exponent matrix (or permutation shift matrix),
(3)P=p1,1p1,2p1,3⋯p1,ρp2,1p2,2p2,3⋯p2,ρp3,1p3,2p3,3⋯p3,ρ⋮⋮⋮⋱⋮pγ,1pγ,2pγ,3⋯pγ,ρ.It is not hard to see that the correspondence betweenP and H is one-to-one. It is noticeable that the parameter Q is called expansion factor (or lifting degree) [21]. By replacing 1’s in a CPM Ipi,j of H in (1) with the same nonzero field element in finite field GF (q), the resulting code is nonbinary QC-LDPC codes [22].


### 2.2. Tanner Graph

Apart from the matrix representation, an LDPC code can be also described in a simple and intuitive way, i.e., a graphical model called Tanner graph [23]. In fact, the Tanner graph of an LDPC code with the parity-check matrix H=hs,t is a bipartite graph in which the two classes of nodes are variable nodes (representing the code-bit nodes) and check nodes (representing the constraint nodes), respectively. An edge in a Tanner graph connects the check node s to the variable node t if and only if the row -s and column -t element hs,t in H is nonzero. A cycle in a Tanner graph is a sequence of the connected check nodes and variable nodes which start and end at the same node in the graph and contain no other nodes more than once. The cycle length is simply the number of the contained edges (or nodes), and the length of the shortest cycle is referred to as girth of the Tanner graph (or an LDPC code). As an example, Figure 1 shows the Tanner graph of Hb (or Hnb) and an associate cycle of length 6 (6-cycle for short).Figure 1
Tanner graph ofHb (or Hnb): (a) Hb over GF (2); (b) Hnb over GF (4); (c) Tanner graph.
(a)(b)(c)It is well-known that the iterative decoding algorithm converges to the optimal solution provided that the Tanner graph of an LDPC code is free of cycles [24]. In other words, short cycles, especially, the cycles of length 4, affect the decoding performance when decoded with the iterative algorithms based on belief propagation. In fact, there exist many cycles in an LDPC code with finite length. Hence, in order to avoid short cycles or obtain LDPC codes with large girth, many construction methods and techniques are proposed [25–33].


## 2.1. LDPC Codes

A binaryγ,ρ-regular LDPC code is generated by the null space of an m×n sparse parity-check matrix H over GF (2), and the matrix H has the following properties: (1) each column has γ 1’s; (2) each row has ρ 1’s; (3) γ≪m and ρ≪n. If the sparse matrix H is over GF (q) for q being a prime power, then LDPC codes generated by such H are called nonbinary codes or q-ary codes. Binary LDPC codes are referred to as quasi-cyclic (QC) [20], if their parity-check matrices H have the following form
(1)H=Ip1,1Ip1,2Ip1,3⋯Ip1,ρIp2,1Ip2,2Ip2,3⋯Ip2,ρIp3,1Ip3,2Ip3,3⋯Ip3,ρ⋮⋮⋮⋱⋮Ipγ,1Ipγ,2Ipγ,3⋯Ipγ,ργQ×ρQ,where for 1≤i≤γ,1≤j≤ρ,−1≤pi,j≤Q−1, Ipi,j is a Q×Q circulant permutation matrix (CPM) formed by cyclically shifting each row of a Q×Q identity matrix I to the right (or left) by pi,jmodQ positions, and I−1 is a zero matrix of size Q×Q. Obviously, I0 is an identity matrix of size Q×Q. For example, if Q=4, then
(2)I0=1000010000100001,I1=100010001000,I2=0010000110000100,I3=0001100001000010.We can easily see that the positions of 1’s ofH in (1) are uniquely determined by the following matrix P, called exponent matrix (or permutation shift matrix),
(3)P=p1,1p1,2p1,3⋯p1,ρp2,1p2,2p2,3⋯p2,ρp3,1p3,2p3,3⋯p3,ρ⋮⋮⋮⋱⋮pγ,1pγ,2pγ,3⋯pγ,ρ.It is not hard to see that the correspondence betweenP and H is one-to-one. It is noticeable that the parameter Q is called expansion factor (or lifting degree) [21]. By replacing 1’s in a CPM Ipi,j of H in (1) with the same nonzero field element in finite field GF (q), the resulting code is nonbinary QC-LDPC codes [22].


## 2.2. Tanner Graph

Apart from the matrix representation, an LDPC code can be also described in a simple and intuitive way, i.e., a graphical model called Tanner graph [23]. In fact, the Tanner graph of an LDPC code with the parity-check matrix H=hs,t is a bipartite graph in which the two classes of nodes are variable nodes (representing the code-bit nodes) and check nodes (representing the constraint nodes), respectively. An edge in a Tanner graph connects the check node s to the variable node t if and only if the row -s and column -t element hs,t in H is nonzero. A cycle in a Tanner graph is a sequence of the connected check nodes and variable nodes which start and end at the same node in the graph and contain no other nodes more than once. The cycle length is simply the number of the contained edges (or nodes), and the length of the shortest cycle is referred to as girth of the Tanner graph (or an LDPC code). As an example, Figure 1 shows the Tanner graph of Hb (or Hnb) and an associate cycle of length 6 (6-cycle for short).Figure 1
Tanner graph ofHb (or Hnb): (a) Hb over GF (2); (b) Hnb over GF (4); (c) Tanner graph.
(a)(b)(c)It is well-known that the iterative decoding algorithm converges to the optimal solution provided that the Tanner graph of an LDPC code is free of cycles [24]. In other words, short cycles, especially, the cycles of length 4, affect the decoding performance when decoded with the iterative algorithms based on belief propagation. In fact, there exist many cycles in an LDPC code with finite length. Hence, in order to avoid short cycles or obtain LDPC codes with large girth, many construction methods and techniques are proposed [25–33].


## 3. Design Framework of2,ρ-Regular Binary QC-LDPC Codes

### 3.1. Edge-Node Relation in Undirected Graphs

LetG=V,E be an undirected graph, where V is a set of nodes and E is some subset of the pairs (called edges) a,b:a,b∈V,a≠b. A cycle of G=V,E has distinct nodes (or edges), and an edge in a cycle has two distinct nodes. If we treat the nodes and edges of G=V,E as the check nodes and variable nodes, respectively, then a bipartite graph GB can be obtained. Consider a cycle of length k (denoted by k-cycle for short) in G=V,E. This k-cycle will be turned into a 2k-cycle in the above bipartite graph GB. In other words, the girth of GB is double that of G=V,E. Based on this process, we can construct bipartite graphs (or Tanner graphs) with large girth from an undirected graph. In order to make it clearly, we give an example.Consider the following4×4 matrix
(4)B4×4=1110011110111101.It is easy to plot the Tanner graph ofB4×4, given in Figure 2. By treating the nodes and edges of the Tanner graph in Figure 2 as the check nodes and variable nodes, respectively, we can construct a new bipartite graph, given in Figure 3. We can see from Figures 2 and 3 that a 4-cycle in the Tanner graph of B4×4 becomes a 8-cycle in the bipartite graph.Figure 2
Tanner graph ofB4×4.Figure 3
A new bipartite graph constructed from the Tanner graph ofB4×4.


### 3.2. Construction Framework of2,ρ-Regular Binary QC-LDPC Codes

In this subsection, we will present the framework for constructing2,ρ-regular binary QC-LDPC codes by using the edge-node relation in an undirected graph in Section 3.1. In order to design 2,ρ-regular codes, the node degree of G=V,E should be ρ. Furthermore, to guarantee 2,ρ-regular codes are quasi-cyclic, the incidence matrix of G=V,E should possess quasi-cyclic structure. In conclusion, the incidence matrix of G=V,E is ρ,ρ-regular and quasi-cyclic. Hence, in order to obtain 2,ρ-regular binary QC-LDPC codes with large girth, we need to design a ρ,ρ-regular quasi-cyclic matrix with large girth. For convenience, this ρ,ρ-regular quasi-cyclic matrix is called base matrix. Next, we will give the construction framework.First, we design aρ,ρ-regular base matrix B of size L×L. By employing the edge-node relation in Section 3.1, we can transfer the Tanner graph of B into a new bipartite graph, and the incidence matrix BM of such a bipartite graph is obtained. It is obvious that BM is a 2,ρ-regular quasi-cyclic matrix of size 2L×ρL. Second, we construct an exponent matrix P of size 2L×ρL, and the corresponding expansion factor is Q. Third, we use BM to mask the exponent matrix P, and a 2L×ρL array HM of Q×Q CPMs is constructed. The null space of HM gives a 2,ρ-regular binary QC-LDPC code of length ρLQ.


## 3.1. Edge-Node Relation in Undirected Graphs

LetG=V,E be an undirected graph, where V is a set of nodes and E is some subset of the pairs (called edges) a,b:a,b∈V,a≠b. A cycle of G=V,E has distinct nodes (or edges), and an edge in a cycle has two distinct nodes. If we treat the nodes and edges of G=V,E as the check nodes and variable nodes, respectively, then a bipartite graph GB can be obtained. Consider a cycle of length k (denoted by k-cycle for short) in G=V,E. This k-cycle will be turned into a 2k-cycle in the above bipartite graph GB. In other words, the girth of GB is double that of G=V,E. Based on this process, we can construct bipartite graphs (or Tanner graphs) with large girth from an undirected graph. In order to make it clearly, we give an example.Consider the following4×4 matrix
(4)B4×4=1110011110111101.It is easy to plot the Tanner graph ofB4×4, given in Figure 2. By treating the nodes and edges of the Tanner graph in Figure 2 as the check nodes and variable nodes, respectively, we can construct a new bipartite graph, given in Figure 3. We can see from Figures 2 and 3 that a 4-cycle in the Tanner graph of B4×4 becomes a 8-cycle in the bipartite graph.Figure 2
Tanner graph ofB4×4.Figure 3
A new bipartite graph constructed from the Tanner graph ofB4×4.


## 3.2. Construction Framework of2,ρ-Regular Binary QC-LDPC Codes

In this subsection, we will present the framework for constructing2,ρ-regular binary QC-LDPC codes by using the edge-node relation in an undirected graph in Section 3.1. In order to design 2,ρ-regular codes, the node degree of G=V,E should be ρ. Furthermore, to guarantee 2,ρ-regular codes are quasi-cyclic, the incidence matrix of G=V,E should possess quasi-cyclic structure. In conclusion, the incidence matrix of G=V,E is ρ,ρ-regular and quasi-cyclic. Hence, in order to obtain 2,ρ-regular binary QC-LDPC codes with large girth, we need to design a ρ,ρ-regular quasi-cyclic matrix with large girth. For convenience, this ρ,ρ-regular quasi-cyclic matrix is called base matrix. Next, we will give the construction framework.First, we design aρ,ρ-regular base matrix B of size L×L. By employing the edge-node relation in Section 3.1, we can transfer the Tanner graph of B into a new bipartite graph, and the incidence matrix BM of such a bipartite graph is obtained. It is obvious that BM is a 2,ρ-regular quasi-cyclic matrix of size 2L×ρL. Second, we construct an exponent matrix P of size 2L×ρL, and the corresponding expansion factor is Q. Third, we use BM to mask the exponent matrix P, and a 2L×ρL array HM of Q×Q CPMs is constructed. The null space of HM gives a 2,ρ-regular binary QC-LDPC code of length ρLQ.


## 4. Design of Nonbinary LDPC Cycle Codes with Large Girth

In order to construct2,ρ-regular binary QC-LDPC codes with large girth, we only design a base matrix and a corresponding exponent matrix based on the construction framework in Section 3.2. By replacing the nonzero element in the parity-check matrices of binary QC-LDPC cycle codes with the nonzero field elements, nonbinary LDPC cycle codes can be obtained. In this paper, we do not optimize the nonzero field elements and adopt the optimized row elements in [34]. Next, we will provide the construction of the base matrices and exponent matrices.


### 4.1. Exhaustive Search of Circulants Based on Isomorphism Theory

In this paper, we employ the circulant as the base matrix. It can be seen from the construction framework in Section3.2 that the size of the base matrix is not too large since the code lengths of NBLDPC codes are short or moderate. In the following, we will give the design of the circulants.A circulant is a square matrix whosei-th row is generated by cyclically shifting the first row to the right (or left) by i−1 positions. Hence, the first row of a circulant is referred to as the generator of the circulant. For a circulant of size L×L, each row (or column) is a rightward (or downward) cyclic-shift of its above (or left) row (or column), and the first row (or column) is the rightward (or downward) cyclic-shift of the last row (or column). Therefore, the rows and columns of a circulant have the same weight. It is clear that the row (or column) weight is associated with the row weight of the generator.Consider a circulantC of size L×L, and its generator is G=g1,g2,⋯,gL where gi∈0,1 for 1≤i≤L. Let ρ be the number of the nonzero components of G. Hence, C is ρ,ρ-regular. We select the nonzero components from g1,g2,⋯,gL and record their subscripts in a set S, called location set in this paper. Then, the location set S has ρ elements. Without loss of generality, the location set S is denoted by
(5)S=s1,s2,⋯,sρ,where 1≤si<sj≤L for 1≤i<j≤ρ. It is obvious that the generator G and the location set S have a one-to-one correspondence. Based on the isomorphism theory of LDPC codes (or their parity-check matrices) in [16, 35, 36], we can directly give the isomorphism theory of the circulants as follows.Theorem 1.
LetS1=s1,1,s1,2,⋯,s1,ρ and S2=s2,1,s2,2,⋯,s2,ρ be two location sets of the circulants C1 and C2 of size L×L, respectively. Then, C1 is isomorphic to C2, denoted by C1≅C2, if S2 is derived from S1 with either of the following two methods.
(1)
Forr∈0,1,⋯,L−1, the elements of S2 are derived from these of S1 by adding a constant r to the elements of S1 modulo L, i.e., s2,i=s1,i+rmodL for 1≤i≤ρ(2)
Suppose thatr and L are coprime. The elements of S2 are derived from these of S1 using s2,i=r·s1,imodL for 1≤i≤ρNote that in the calculation process, if the element inS1 and S2 equals 0, it actually equals L. Moreover, in the case (2) of Theorem 1, the number of r can be determined by a well-known function, called Euler’s phi function, i.e.,
(6)ϕL=L∏rL1−1r.IfC1≅C2, we say S1 is isomorphic to S2, denoted by S1≅S2.In general, the size of the employed circulants in this paper is not large. Hence, we can make an exhaustive search of the circulants by using the computer. The search space of the location sets of theL×L circulants with row/column weight ρ is
(7)Lρ=L!L−ρ!·ρ!.Based on the case (1) in Theorem1, we can see that all the location sets of the L×L circulants have the following isomorphic form: S=s1=1,s2,⋯,sρ, where 2≤si<sj≤L for 2≤i<j≤ρ. Hence, the search space of such location sets S is
(8)L−1ρ−1=L−1!L−ρ!·ρ−1!.That is, an exhaustive search of such location sets (or circulants) is feasible. Here, we do not provide the specific exhaustive search algorithm. Combined with the cycle-counting algorithms [37–39], the optimal L×L circulants with row/column weight ρ can be found. In this paper, the optimal ones are such circulants whose Tanner graphs have fewer short cycles and larger girths. In order to facilitate the readers, some optimal circulants are presented in Table 1.Table 1
Some optimalL×L circulants with row/column weight ρ and location set S.
LρLocation setSLρLocation setSLρLocation setSLρLocation setS44{0, 1, 2, 3}55{0, 1, 2, 3, 4}66{0, 1, 2, 3, 4, 5}77{0, 1, 2, 3, 4, 5, 6}54{0, 1, 2, 3}65{0, 1, 2, 3, 4}76{0, 1, 2, 3, 4, 5}87{0, 1, 2, 3, 4, 5, 6}64{0, 1, 2, 3}75{0, 1, 2, 3, 4}86{0, 1, 2, 3, 4, 5}97{0, 1, 2, 3, 4, 5, 6}74{0, 1, 2, 4}85{0, 1, 2, 3, 5}96{0, 1, 2, 3, 4, 6}107{0, 1, 2, 3, 4, 5, 7}84{0, 1, 2, 4}95{0, 1, 2, 3, 5}106{0, 1, 2, 3, 5, 6}117{0, 1, 2, 3, 4, 6, 7}94{0, 1, 2, 4}105{0, 1, 2, 3, 6}116{0, 1, 2, 4, 5, 7}127{0, 1, 2, 3, 4, 7, 9}104{0, 1, 2, 5}115{0, 1, 2, 4, 7}126{0, 1, 2, 3, 5, 8}137{0, 1, 2, 3, 4, 6, 9}114{0, 1, 2, 5}125{0, 1, 2, 4, 7}136{0, 1, 2, 3, 5, 9}147{0, 1, 2, 3, 5, 6, 9}124{0, 1, 3, 7}135{0, 1, 2, 4, 7}146{0, 1, 2, 3, 5, 9}157{0, 1, 2, 4, 5, 8, 10}134{0, 1, 3, 9}145{0, 1, 2, 4, 7}156{0, 1, 2, 3, 6, 10}167{0, 1, 2, 3, 5, 8, 12}144{0, 1, 4, 6}155{0, 1, 2, 4, 7}166{0, 1, 2, 3, 6, 10}177{0, 1, 2, 3, 5, 8, 12}154{0, 1, 3, 7}165{0, 1, 2, 5, 8}176{0, 1, 2, 3, 6, 10}187{0, 1, 2, 3, 5, 8, 12}164{0, 1, 3, 7}175{0, 1, 2, 4, 12}186{0, 1, 2, 4, 8, 13}197{0, 1, 2, 3, 5, 9, 14}174{0, 1, 3, 7}185{0, 1, 2, 5, 11}196{0, 1, 2, 4, 7, 11}207{0, 1, 2, 3, 6, 10, 15}184{0, 1, 3, 7}195{0, 1, 2, 6, 9}206{0, 1, 2, 4, 7, 12}217{0, 1, 2, 4, 8, 11, 16}194{0, 1, 3, 8}205{0, 1, 2, 5, 14}216{0, 1, 2, 4, 7, 12}227{0, 1, 2, 4, 6, 14, 17}204{0, 1, 3, 14}215{0, 1, 4, 14, 16}226{0, 1, 2, 4, 8, 13}237{0, 1, 2, 3, 8, 13, 17}214{0, 1, 3, 9}225{0, 1, 3, 7, 12}236{0, 1, 2, 4, 7, 15}247{0, 1, 2, 4, 7, 15, 19}224{0, 1, 3, 9}235{0, 1, 3, 8, 14}246{0, 1, 2, 4, 12, 19}257{0, 1, 2, 4, 7, 12, 16}234{0, 1, 3, 10}245{0, 1, 3, 11, 20}256{0, 1, 2, 4, 9, 15}267{0, 1, 2, 4, 7, 13, 18}244{0, 1, 3, 10}255{0, 1, 3, 15, 21}266{0, 1, 2, 5, 9, 15}277{0, 1, 2, 4, 7, 12, 21}254{0, 1, 3, 10}265{0, 1, 3, 7, 12}276{0, 1, 2, 5, 13, 22}287{0, 1, 2, 4, 7, 17, 21}264{0, 1, 3, 11}275{0, 1, 3, 7, 18}286{0, 1, 4, 15, 20, 22}297{0, 1, 2, 4, 7, 12, 16}274{0, 1, 4, 10}285{0, 1, 3, 13, 24}296{0, 1, 2, 4, 18, 23}307{0, 1, 2, 4, 7, 15, 25}284{0, 1, 3, 12}295{0, 1, 3, 7, 19}306{0, 1, 2, 5, 14, 24}305{0, 1, 3, 12, 25}


### 4.2. Review of Finite Fields Based QC-LDPC Codes and Their Exponent Matrices

In this subsection, we will review the finite field based method for constructing QC-LDPC codes, and provide two classes of exponent matrices of these QC-LDPC codes [18].


#### 4.2.1. A General Construction of QC-LDPC Codes Based on Finite Fields of Characteristic 2

Let GFq be a finite field with q=2t with t≥2, and let α be a primitive element of GF q. For each nonzero element αi with 0≤i≤q−2, we define the location vector vαi as a q−1-tuple over GF (2),
(9)vαi=v1,v2,⋯,vq−1,whose components correspond to the nonzero elements α0,α1,⋯,αq−2 of GF q, where the i-th component vi is set to 1 and all the other q−2 components are 0. Hence, based on the nonzero element αi of GF q, we can uniquely form a q−1×q−1 square matrix Mαi whose j-th row is obtained by cyclically shifting every component of the q−1-ary location vector vαij−1 places to the right (or left) for 0≤i≤q−2,1≤j≤q−1. The resulting square matrix Mαi is a CPM, and it is also referred to as the q−1-fold matrix dispersion (or expansion) of the nonzero field element αi over GF (2) [18].Consider aγ×ρ matrix P over GF q,
(10)P=p1p2p3⋮pγ=p1,2p1,3⋯p1,ρp2,2p2,3⋯p2,ρp3,2p3,3⋯p3,ρ⋮⋮⋱⋮pγ,2pγ,3⋯pγ,ρ,whose rows satisfy the following two constraints: (1) for 1≤i<γ,0≤k,l≤q−2 and k≠l, αkpi and αlpi have at most one position where both of them have the same element of GF q (i.e., they differ in at least ρ−1 positions); (2) for 1≤i,j<γ,i≠j, and 0≤k,l≤q−2,αkpi and αlpj differ in at least ρ−1 positions. These constraints are called α-multiplied row constraints in [18]. By replacing each of its entry pi,j with the binary matrix Mpi,j, we obtain a γ×ρ array Hγ,ρ of q−1×q−1 CPMs. Then, the null space of Hγ,ρ gives a binary γ,ρ-regular QC-LDPC code. Moreover, the α-multiplied row constraints ensure the Tanner graph of this code free of cycle of length 4. Hence, the constructed QC-LDPC codes have girth at least 6.According to the definition in Section 2, we can see that the aboveγ×ρ matrix P is the exponent matrix, and the associate expansion factor is q−1. A framework for constructing such matrix P based on two arbitrary subsets of a finite field was proposed in [40]. Let η be a nonzero element in GF q and α be a primitive element. For 1≤γ,ρ≤q, let T1=αi1,αi2,⋯,αiγ and T2=αj1,αj2,⋯,αjρ be two arbitrary subsets of elements in GF q with ik and jl in the set −∞,0,1,2,⋯,q−2,i1<i2<⋯<iγ, and j1<j2<⋯<jρ. The γ×ρ matrix P can be formed by
(11)Pη=ηαik+αjl1≤k≤γ,1≤l≤ρ.Under this framework, some well-known constructions of QC-LDPC codes based on finite fields and combinatorial designs are special cases [14, 41, 42]. For example, when T1=T2=GFq, Pη is a Latin square over GF q [43].


#### 4.2.2. Construction of QC-LDPC Codes Based on Prime Fields

Letp be a prime. Consider a p×p matrix
(12)P=p1,1p1,2⋯p1,pp2,1p2,2⋯p2,p⋮⋮⋱⋮pp,1pp,2⋯pp,p,where pi,j=i−1·j−1modp for 1≤i≤p and 1≤j≤p. We select a γ×ρ submatrix from P and replace its elements ps,t with the CPMs Ips,t for 1≤s≤γ and 1≤t≤ρ. The following γ×ρ array HPγ×ρ of p×p CPMs over GF (2) is obtained.
(13)HPγ×ρ=Ips,t1≤s≤γ,1≤t≤ρ.Actually, the null space ofHPγ×ρ gives a γ,ρ-regular QC-LDPC code of length pρ with girth at least 6. Notice that the exponent matrix of this code is Pγ×ρ and the expansion factor is p. How to select good γ rows and ρ columns of CPMs from P in (12) can be found in [44, 45].


### 4.3. Nonbinary LDPC Cycle Codes and Numerical Results

Combined with Sections3.2, 4.1, and 4.2, we can easily construct a binary QC-LDPC cycle code. Based on the replacement of the nonzero elements in finite fields, nonbinary LDPC cycle codes can be constructed. In order to show the advantages of our proposed construction methods, we next provide some examples.Example 1.
Consider the all-one matrix (or circulant) of size4×4. It is clear that there is only one such circulant for ρ=4 and L=4. The following 8×16 matrix B8×16 can be obtained based on the construction framework in Section 3.2.
(14)7ptB8×16=11110000000000000000111100000000000000001111000000000000000011111000100010001000010001000100010000100010001000100001000100010001.
Based on the prime field GF (31), we can construct an8×16 array HP8×16,1 of 31×31 CPMs in the form of (13) by choosing the 8 rows and 16 columns from the exponent matrix P in equation (12). The indices of the chosen 8 rows and 16 columns from P are {3, 4, 5, 10, 15, 17, 24, 28} and {1, 4, 5, 6, 7, 8, 9, 10, 11, 15, 16, 19, 26, 28, 29, 30}, respectively. The row and column selection method is based on the proposed method in [45]. By employing B8×16 to mask HP8×16,1, we can obtain an array HMP8×16,1 of 31×31 CPMs. By replacing the 1’s of each row in HMP8×16,1 with nonzero elements of GF (64) in the corresponding rows of Table 2, a 2,4-regular matrix HM,64P8×16,1 over GF (64) is obtained. Note that the numbers in Table 2 are the power numbers of α, where α is a primitive element of GF (64) created by using the primitive polynomial px=1+x+x6. The null space of HM,64P8×16 gives a 2,4-regular (496,248) LDPC cycle code over GF (64). The girth of this code is 16, and the number of 16-cycles is 775. For comparison, we reconstruct the irregular (504,252) QC-LDPC code over GF (64) based on finite field GF (64) and the masking matrix Bmask4,8 in [15]. The average column and row weights in the parity-check matrix of (504,252) QC-LDPC code over GF (64) are 2.5 and 5, respectively. Moreover, we also design a comparable (2,4)-regular (496,248) LDPC code over GF (64) based on the progressive edge-growth (PEG) algorithm in [46], called PEG-LDPC code. Note that the nonzero elements of the parity-check matrix of the (2,4)-regular (496,248) PEG-LDPC code over GF (64) are randomly chosen. When decoded with the fast-Fourier-transform (FFT) based Q-ary sum-product algorithm (QSPA) with 50 iterations, the bit/word error rates (BERs/WERs) of these three nonbinary LDPC codes are shown in Figure 4. In the simulations, the transmissions on the BPSK modulated AWGN channel are assumed. We can see that at the BER of 2×10−6, the proposed nonbinary (496,248) LDPC cycle code outperforms the (504,252) QC-LDPC code over GF (64) and the (2,4)-regular (496,248) PEG-LDPC code over GF (64) about 0.45 dB and 0.1 dB, respectively.Table 2
The nonzero field elements in the parity-check matrix of the proposed 64-ary496,248 LDPC cycle code in Example 1.
Row indexNonzero field elementsRow indexNonzero field elementsRow indexNonzero field elements137922027018443037919403719957184406718044771844080184479199037100184471109372212184470139193701418074415223709160447181791903718372209194418702093722021193790220223792344701824074418259370222619937027223709289223702993722030379220313792203222937033718440343709223503722936744018370447183890371939379220400919374144718042371990439370194437922045091937461993704701937948180447490199375022379051370922521870445309372254447018557044185690372257919370582293705991937060044187611870446293701963220937647018446518440766193790679372206818704469092237703722097118744072701844730223797470441875901937763709197793702278037922793790227090371981744180820441878393722084440718859223708691937087229037880187448993722090180744913722909202237993370922949223709544071896091937977441809891937099744180100372209101022937102220379103440718104229037105220379106447180107371909108093722109937190110441807111372290112701844113018447114372209115093719116718044117902237118037199119092237120193790121370229122370922123074418124193709125744180126744018127937220128441807129718044130037229131704418132037922133044187134441870135937022136937190137093722138184470142018744143441807144937019145018744146180744147199370148441807149370199150190937151037229152718440153440718154037922155180744156447018157037919158223790159718440160037919161018744162037922163718440164372290165093722166037199167184470168902237169037919170440187171901937172903719173937190174447180175190379176022937177903719178018744179018447180370922181937022182037229183370229184092237185919370186447180187199037188370922189184470190223790191371909192379190193037199194220379195701844196371909197937220198229037199441807200223790201718044202019937203044187204901937205718044206371909207744180208440187209193709210441807211193709212180744213379220214093722215223709216193790217744180218440718219440718220370199221229037222441870223199370224180447225372290226229370227193790228184470229919370230184470231187044232447180233441807234372290235229370236229037237440187238037229239372209240371909241018744242193709243229037244447180245937190246372209247447180248199037Figure 4
The error performances of the proposed (496,248) LDPC cycle code over GF (64), the comparable (504,252) irregular QC-LDPC code over GF (64) constructed from finite field GF (64) in [15], and (2,4)-regular (496,248) LDPC code over GF (64) constructed based on the progressive edge-growth (PEG) algorithm in [46]. The transmissions on the BPSK modulated AWGN channel are assumed.In the above example, we can see that the constructed nonbinary LDPC cycle code is not quasi-cyclic because of the randomly chosen nonzero field elements in its parity-check matrix. Hence, we next show the performances of the proposed nonbinary QC-LDPC cycle codes.Example 2.
Consider the prime field GF (19), we can easily construct an8×16 matrix P8×16,2 over GF (19) based on the exponent matrix P in equation (12) and the construction framework in Section 3.2. The indices of the chosen 8 rows and 16 columns from P are {1, 2, 4, 5, 7, 8, 14, 15} and {1, 2, 3, 4, 5, 6, 7, 9, 10, 13, 14, 15, 16, 17, 18, 19}, respectively. The row and column selection method is also based on the proposed method in [45]. By dispersing each entry of P8×16,2 into the corresponding CPMs of size 19×19, an 8×16 array HP8×16,2 of 19×19 CPMs is obtained. By employing B8×16 in equation (14) to mask the array HP8×16,2, we can construct an array HMP8×16,2 of 19×19 CPMs. By replacing the 1’s of each CPM in HMP8×16,2 with the same nonzero element of GF (256) in the corresponding row of Table 3, a (2,4)-regular matrix HM,256P8×16,2 over GF (256) is obtained. It is noticeable that the numbers in Table 3 are the power numbers of α, where α is a primitive element of GF (256) created by using the primitive polynomial px=1+x2+x3+x4+x8. The null space of HM,256P8×16,2 gives a (2,4)-regular (304,152) LDPC cycle code over GF (256). The girth of this code is 16, and the number of 16-cycles is 969. Since the nonzero field elements of a CPM in HM,256P8×16,2 are the same, and the resulting (304,152) LDPC cycle code over GF (256) is quasi-cyclic.
For comparison, we construct the (3,6)-regular (2432,1216) LDPC code over GF (2) based on the progressive edge-growth (PEG) algorithm in [46]. The error performances of these two LDPC codes are shown in Figure 5. In the simulations, the employed decoding algorithms of the constructed (304,152) QC-LDPC cycle code over GF (256) and the (2432,1216) LDPC code over GF (2) are the QSPA (50 iterations) and the sum-product algorithm (SPA) with 50 iterations, respectively. The transmissions on the BPSK modulated AWGN channel are assumed. We can see that the constructed (304,152) QC-LDPC cycle code over GF (256) can outperform the (2432,1216) LDPC code over GF (2) about 0.75 dB at the BER of 10−6.Table 3
The nonzero field elements in the corresponding CPMs of the parity-check matricesHM,256P8×16,2 in Example 2.
Row indexNonzero field elements1018281722173018283401670127440127016954016901286172818207817218208401691280Figure 5
The error performances of the constructed (304,152) QC-LDPC cycle code over GF (256) and the comparable (2432,1216) LDPC code over GF (2) constructed based on the progressive edge-growth (PEG) algorithm in [46]. The transmissions on the BPSK modulated AWGN channel are assumed.


## 4.1. Exhaustive Search of Circulants Based on Isomorphism Theory

In this paper, we employ the circulant as the base matrix. It can be seen from the construction framework in Section3.2 that the size of the base matrix is not too large since the code lengths of NBLDPC codes are short or moderate. In the following, we will give the design of the circulants.A circulant is a square matrix whosei-th row is generated by cyclically shifting the first row to the right (or left) by i−1 positions. Hence, the first row of a circulant is referred to as the generator of the circulant. For a circulant of size L×L, each row (or column) is a rightward (or downward) cyclic-shift of its above (or left) row (or column), and the first row (or column) is the rightward (or downward) cyclic-shift of the last row (or column). Therefore, the rows and columns of a circulant have the same weight. It is clear that the row (or column) weight is associated with the row weight of the generator.Consider a circulantC of size L×L, and its generator is G=g1,g2,⋯,gL where gi∈0,1 for 1≤i≤L. Let ρ be the number of the nonzero components of G. Hence, C is ρ,ρ-regular. We select the nonzero components from g1,g2,⋯,gL and record their subscripts in a set S, called location set in this paper. Then, the location set S has ρ elements. Without loss of generality, the location set S is denoted by
(5)S=s1,s2,⋯,sρ,where 1≤si<sj≤L for 1≤i<j≤ρ. It is obvious that the generator G and the location set S have a one-to-one correspondence. Based on the isomorphism theory of LDPC codes (or their parity-check matrices) in [16, 35, 36], we can directly give the isomorphism theory of the circulants as follows.Theorem 1.
LetS1=s1,1,s1,2,⋯,s1,ρ and S2=s2,1,s2,2,⋯,s2,ρ be two location sets of the circulants C1 and C2 of size L×L, respectively. Then, C1 is isomorphic to C2, denoted by C1≅C2, if S2 is derived from S1 with either of the following two methods.
(1)
Forr∈0,1,⋯,L−1, the elements of S2 are derived from these of S1 by adding a constant r to the elements of S1 modulo L, i.e., s2,i=s1,i+rmodL for 1≤i≤ρ(2)
Suppose thatr and L are coprime. The elements of S2 are derived from these of S1 using s2,i=r·s1,imodL for 1≤i≤ρNote that in the calculation process, if the element inS1 and S2 equals 0, it actually equals L. Moreover, in the case (2) of Theorem 1, the number of r can be determined by a well-known function, called Euler’s phi function, i.e.,
(6)ϕL=L∏rL1−1r.IfC1≅C2, we say S1 is isomorphic to S2, denoted by S1≅S2.In general, the size of the employed circulants in this paper is not large. Hence, we can make an exhaustive search of the circulants by using the computer. The search space of the location sets of theL×L circulants with row/column weight ρ is
(7)Lρ=L!L−ρ!·ρ!.Based on the case (1) in Theorem1, we can see that all the location sets of the L×L circulants have the following isomorphic form: S=s1=1,s2,⋯,sρ, where 2≤si<sj≤L for 2≤i<j≤ρ. Hence, the search space of such location sets S is
(8)L−1ρ−1=L−1!L−ρ!·ρ−1!.That is, an exhaustive search of such location sets (or circulants) is feasible. Here, we do not provide the specific exhaustive search algorithm. Combined with the cycle-counting algorithms [37–39], the optimal L×L circulants with row/column weight ρ can be found. In this paper, the optimal ones are such circulants whose Tanner graphs have fewer short cycles and larger girths. In order to facilitate the readers, some optimal circulants are presented in Table 1.Table 1
Some optimalL×L circulants with row/column weight ρ and location set S.
LρLocation setSLρLocation setSLρLocation setSLρLocation setS44{0, 1, 2, 3}55{0, 1, 2, 3, 4}66{0, 1, 2, 3, 4, 5}77{0, 1, 2, 3, 4, 5, 6}54{0, 1, 2, 3}65{0, 1, 2, 3, 4}76{0, 1, 2, 3, 4, 5}87{0, 1, 2, 3, 4, 5, 6}64{0, 1, 2, 3}75{0, 1, 2, 3, 4}86{0, 1, 2, 3, 4, 5}97{0, 1, 2, 3, 4, 5, 6}74{0, 1, 2, 4}85{0, 1, 2, 3, 5}96{0, 1, 2, 3, 4, 6}107{0, 1, 2, 3, 4, 5, 7}84{0, 1, 2, 4}95{0, 1, 2, 3, 5}106{0, 1, 2, 3, 5, 6}117{0, 1, 2, 3, 4, 6, 7}94{0, 1, 2, 4}105{0, 1, 2, 3, 6}116{0, 1, 2, 4, 5, 7}127{0, 1, 2, 3, 4, 7, 9}104{0, 1, 2, 5}115{0, 1, 2, 4, 7}126{0, 1, 2, 3, 5, 8}137{0, 1, 2, 3, 4, 6, 9}114{0, 1, 2, 5}125{0, 1, 2, 4, 7}136{0, 1, 2, 3, 5, 9}147{0, 1, 2, 3, 5, 6, 9}124{0, 1, 3, 7}135{0, 1, 2, 4, 7}146{0, 1, 2, 3, 5, 9}157{0, 1, 2, 4, 5, 8, 10}134{0, 1, 3, 9}145{0, 1, 2, 4, 7}156{0, 1, 2, 3, 6, 10}167{0, 1, 2, 3, 5, 8, 12}144{0, 1, 4, 6}155{0, 1, 2, 4, 7}166{0, 1, 2, 3, 6, 10}177{0, 1, 2, 3, 5, 8, 12}154{0, 1, 3, 7}165{0, 1, 2, 5, 8}176{0, 1, 2, 3, 6, 10}187{0, 1, 2, 3, 5, 8, 12}164{0, 1, 3, 7}175{0, 1, 2, 4, 12}186{0, 1, 2, 4, 8, 13}197{0, 1, 2, 3, 5, 9, 14}174{0, 1, 3, 7}185{0, 1, 2, 5, 11}196{0, 1, 2, 4, 7, 11}207{0, 1, 2, 3, 6, 10, 15}184{0, 1, 3, 7}195{0, 1, 2, 6, 9}206{0, 1, 2, 4, 7, 12}217{0, 1, 2, 4, 8, 11, 16}194{0, 1, 3, 8}205{0, 1, 2, 5, 14}216{0, 1, 2, 4, 7, 12}227{0, 1, 2, 4, 6, 14, 17}204{0, 1, 3, 14}215{0, 1, 4, 14, 16}226{0, 1, 2, 4, 8, 13}237{0, 1, 2, 3, 8, 13, 17}214{0, 1, 3, 9}225{0, 1, 3, 7, 12}236{0, 1, 2, 4, 7, 15}247{0, 1, 2, 4, 7, 15, 19}224{0, 1, 3, 9}235{0, 1, 3, 8, 14}246{0, 1, 2, 4, 12, 19}257{0, 1, 2, 4, 7, 12, 16}234{0, 1, 3, 10}245{0, 1, 3, 11, 20}256{0, 1, 2, 4, 9, 15}267{0, 1, 2, 4, 7, 13, 18}244{0, 1, 3, 10}255{0, 1, 3, 15, 21}266{0, 1, 2, 5, 9, 15}277{0, 1, 2, 4, 7, 12, 21}254{0, 1, 3, 10}265{0, 1, 3, 7, 12}276{0, 1, 2, 5, 13, 22}287{0, 1, 2, 4, 7, 17, 21}264{0, 1, 3, 11}275{0, 1, 3, 7, 18}286{0, 1, 4, 15, 20, 22}297{0, 1, 2, 4, 7, 12, 16}274{0, 1, 4, 10}285{0, 1, 3, 13, 24}296{0, 1, 2, 4, 18, 23}307{0, 1, 2, 4, 7, 15, 25}284{0, 1, 3, 12}295{0, 1, 3, 7, 19}306{0, 1, 2, 5, 14, 24}305{0, 1, 3, 12, 25}


## 4.2. Review of Finite Fields Based QC-LDPC Codes and Their Exponent Matrices

In this subsection, we will review the finite field based method for constructing QC-LDPC codes, and provide two classes of exponent matrices of these QC-LDPC codes [18].


### 4.2.1. A General Construction of QC-LDPC Codes Based on Finite Fields of Characteristic 2

Let GFq be a finite field with q=2t with t≥2, and let α be a primitive element of GF q. For each nonzero element αi with 0≤i≤q−2, we define the location vector vαi as a q−1-tuple over GF (2),
(9)vαi=v1,v2,⋯,vq−1,whose components correspond to the nonzero elements α0,α1,⋯,αq−2 of GF q, where the i-th component vi is set to 1 and all the other q−2 components are 0. Hence, based on the nonzero element αi of GF q, we can uniquely form a q−1×q−1 square matrix Mαi whose j-th row is obtained by cyclically shifting every component of the q−1-ary location vector vαij−1 places to the right (or left) for 0≤i≤q−2,1≤j≤q−1. The resulting square matrix Mαi is a CPM, and it is also referred to as the q−1-fold matrix dispersion (or expansion) of the nonzero field element αi over GF (2) [18].Consider aγ×ρ matrix P over GF q,
(10)P=p1p2p3⋮pγ=p1,2p1,3⋯p1,ρp2,2p2,3⋯p2,ρp3,2p3,3⋯p3,ρ⋮⋮⋱⋮pγ,2pγ,3⋯pγ,ρ,whose rows satisfy the following two constraints: (1) for 1≤i<γ,0≤k,l≤q−2 and k≠l, αkpi and αlpi have at most one position where both of them have the same element of GF q (i.e., they differ in at least ρ−1 positions); (2) for 1≤i,j<γ,i≠j, and 0≤k,l≤q−2,αkpi and αlpj differ in at least ρ−1 positions. These constraints are called α-multiplied row constraints in [18]. By replacing each of its entry pi,j with the binary matrix Mpi,j, we obtain a γ×ρ array Hγ,ρ of q−1×q−1 CPMs. Then, the null space of Hγ,ρ gives a binary γ,ρ-regular QC-LDPC code. Moreover, the α-multiplied row constraints ensure the Tanner graph of this code free of cycle of length 4. Hence, the constructed QC-LDPC codes have girth at least 6.According to the definition in Section 2, we can see that the aboveγ×ρ matrix P is the exponent matrix, and the associate expansion factor is q−1. A framework for constructing such matrix P based on two arbitrary subsets of a finite field was proposed in [40]. Let η be a nonzero element in GF q and α be a primitive element. For 1≤γ,ρ≤q, let T1=αi1,αi2,⋯,αiγ and T2=αj1,αj2,⋯,αjρ be two arbitrary subsets of elements in GF q with ik and jl in the set −∞,0,1,2,⋯,q−2,i1<i2<⋯<iγ, and j1<j2<⋯<jρ. The γ×ρ matrix P can be formed by
(11)Pη=ηαik+αjl1≤k≤γ,1≤l≤ρ.Under this framework, some well-known constructions of QC-LDPC codes based on finite fields and combinatorial designs are special cases [14, 41, 42]. For example, when T1=T2=GFq, Pη is a Latin square over GF q [43].


### 4.2.2. Construction of QC-LDPC Codes Based on Prime Fields

Letp be a prime. Consider a p×p matrix
(12)P=p1,1p1,2⋯p1,pp2,1p2,2⋯p2,p⋮⋮⋱⋮pp,1pp,2⋯pp,p,where pi,j=i−1·j−1modp for 1≤i≤p and 1≤j≤p. We select a γ×ρ submatrix from P and replace its elements ps,t with the CPMs Ips,t for 1≤s≤γ and 1≤t≤ρ. The following γ×ρ array HPγ×ρ of p×p CPMs over GF (2) is obtained.
(13)HPγ×ρ=Ips,t1≤s≤γ,1≤t≤ρ.Actually, the null space ofHPγ×ρ gives a γ,ρ-regular QC-LDPC code of length pρ with girth at least 6. Notice that the exponent matrix of this code is Pγ×ρ and the expansion factor is p. How to select good γ rows and ρ columns of CPMs from P in (12) can be found in [44, 45].


## 4.2.1. A General Construction of QC-LDPC Codes Based on Finite Fields of Characteristic 2

Let GFq be a finite field with q=2t with t≥2, and let α be a primitive element of GF q. For each nonzero element αi with 0≤i≤q−2, we define the location vector vαi as a q−1-tuple over GF (2),
(9)vαi=v1,v2,⋯,vq−1,whose components correspond to the nonzero elements α0,α1,⋯,αq−2 of GF q, where the i-th component vi is set to 1 and all the other q−2 components are 0. Hence, based on the nonzero element αi of GF q, we can uniquely form a q−1×q−1 square matrix Mαi whose j-th row is obtained by cyclically shifting every component of the q−1-ary location vector vαij−1 places to the right (or left) for 0≤i≤q−2,1≤j≤q−1. The resulting square matrix Mαi is a CPM, and it is also referred to as the q−1-fold matrix dispersion (or expansion) of the nonzero field element αi over GF (2) [18].Consider aγ×ρ matrix P over GF q,
(10)P=p1p2p3⋮pγ=p1,2p1,3⋯p1,ρp2,2p2,3⋯p2,ρp3,2p3,3⋯p3,ρ⋮⋮⋱⋮pγ,2pγ,3⋯pγ,ρ,whose rows satisfy the following two constraints: (1) for 1≤i<γ,0≤k,l≤q−2 and k≠l, αkpi and αlpi have at most one position where both of them have the same element of GF q (i.e., they differ in at least ρ−1 positions); (2) for 1≤i,j<γ,i≠j, and 0≤k,l≤q−2,αkpi and αlpj differ in at least ρ−1 positions. These constraints are called α-multiplied row constraints in [18]. By replacing each of its entry pi,j with the binary matrix Mpi,j, we obtain a γ×ρ array Hγ,ρ of q−1×q−1 CPMs. Then, the null space of Hγ,ρ gives a binary γ,ρ-regular QC-LDPC code. Moreover, the α-multiplied row constraints ensure the Tanner graph of this code free of cycle of length 4. Hence, the constructed QC-LDPC codes have girth at least 6.According to the definition in Section 2, we can see that the aboveγ×ρ matrix P is the exponent matrix, and the associate expansion factor is q−1. A framework for constructing such matrix P based on two arbitrary subsets of a finite field was proposed in [40]. Let η be a nonzero element in GF q and α be a primitive element. For 1≤γ,ρ≤q, let T1=αi1,αi2,⋯,αiγ and T2=αj1,αj2,⋯,αjρ be two arbitrary subsets of elements in GF q with ik and jl in the set −∞,0,1,2,⋯,q−2,i1<i2<⋯<iγ, and j1<j2<⋯<jρ. The γ×ρ matrix P can be formed by
(11)Pη=ηαik+αjl1≤k≤γ,1≤l≤ρ.Under this framework, some well-known constructions of QC-LDPC codes based on finite fields and combinatorial designs are special cases [14, 41, 42]. For example, when T1=T2=GFq, Pη is a Latin square over GF q [43].


## 4.2.2. Construction of QC-LDPC Codes Based on Prime Fields

Letp be a prime. Consider a p×p matrix
(12)P=p1,1p1,2⋯p1,pp2,1p2,2⋯p2,p⋮⋮⋱⋮pp,1pp,2⋯pp,p,where pi,j=i−1·j−1modp for 1≤i≤p and 1≤j≤p. We select a γ×ρ submatrix from P and replace its elements ps,t with the CPMs Ips,t for 1≤s≤γ and 1≤t≤ρ. The following γ×ρ array HPγ×ρ of p×p CPMs over GF (2) is obtained.
(13)HPγ×ρ=Ips,t1≤s≤γ,1≤t≤ρ.Actually, the null space ofHPγ×ρ gives a γ,ρ-regular QC-LDPC code of length pρ with girth at least 6. Notice that the exponent matrix of this code is Pγ×ρ and the expansion factor is p. How to select good γ rows and ρ columns of CPMs from P in (12) can be found in [44, 45].


## 4.3. Nonbinary LDPC Cycle Codes and Numerical Results

Combined with Sections3.2, 4.1, and 4.2, we can easily construct a binary QC-LDPC cycle code. Based on the replacement of the nonzero elements in finite fields, nonbinary LDPC cycle codes can be constructed. In order to show the advantages of our proposed construction methods, we next provide some examples.Example 1.
Consider the all-one matrix (or circulant) of size4×4. It is clear that there is only one such circulant for ρ=4 and L=4. The following 8×16 matrix B8×16 can be obtained based on the construction framework in Section 3.2.
(14)7ptB8×16=11110000000000000000111100000000000000001111000000000000000011111000100010001000010001000100010000100010001000100001000100010001.
Based on the prime field GF (31), we can construct an8×16 array HP8×16,1 of 31×31 CPMs in the form of (13) by choosing the 8 rows and 16 columns from the exponent matrix P in equation (12). The indices of the chosen 8 rows and 16 columns from P are {3, 4, 5, 10, 15, 17, 24, 28} and {1, 4, 5, 6, 7, 8, 9, 10, 11, 15, 16, 19, 26, 28, 29, 30}, respectively. The row and column selection method is based on the proposed method in [45]. By employing B8×16 to mask HP8×16,1, we can obtain an array HMP8×16,1 of 31×31 CPMs. By replacing the 1’s of each row in HMP8×16,1 with nonzero elements of GF (64) in the corresponding rows of Table 2, a 2,4-regular matrix HM,64P8×16,1 over GF (64) is obtained. Note that the numbers in Table 2 are the power numbers of α, where α is a primitive element of GF (64) created by using the primitive polynomial px=1+x+x6. The null space of HM,64P8×16 gives a 2,4-regular (496,248) LDPC cycle code over GF (64). The girth of this code is 16, and the number of 16-cycles is 775. For comparison, we reconstruct the irregular (504,252) QC-LDPC code over GF (64) based on finite field GF (64) and the masking matrix Bmask4,8 in [15]. The average column and row weights in the parity-check matrix of (504,252) QC-LDPC code over GF (64) are 2.5 and 5, respectively. Moreover, we also design a comparable (2,4)-regular (496,248) LDPC code over GF (64) based on the progressive edge-growth (PEG) algorithm in [46], called PEG-LDPC code. Note that the nonzero elements of the parity-check matrix of the (2,4)-regular (496,248) PEG-LDPC code over GF (64) are randomly chosen. When decoded with the fast-Fourier-transform (FFT) based Q-ary sum-product algorithm (QSPA) with 50 iterations, the bit/word error rates (BERs/WERs) of these three nonbinary LDPC codes are shown in Figure 4. In the simulations, the transmissions on the BPSK modulated AWGN channel are assumed. We can see that at the BER of 2×10−6, the proposed nonbinary (496,248) LDPC cycle code outperforms the (504,252) QC-LDPC code over GF (64) and the (2,4)-regular (496,248) PEG-LDPC code over GF (64) about 0.45 dB and 0.1 dB, respectively.Table 2
The nonzero field elements in the parity-check matrix of the proposed 64-ary496,248 LDPC cycle code in Example 1.
Row indexNonzero field elementsRow indexNonzero field elementsRow indexNonzero field elements137922027018443037919403719957184406718044771844080184479199037100184471109372212184470139193701418074415223709160447181791903718372209194418702093722021193790220223792344701824074418259370222619937027223709289223702993722030379220313792203222937033718440343709223503722936744018370447183890371939379220400919374144718042371990439370194437922045091937461993704701937948180447490199375022379051370922521870445309372254447018557044185690372257919370582293705991937060044187611870446293701963220937647018446518440766193790679372206818704469092237703722097118744072701844730223797470441875901937763709197793702278037922793790227090371981744180820441878393722084440718859223708691937087229037880187448993722090180744913722909202237993370922949223709544071896091937977441809891937099744180100372209101022937102220379103440718104229037105220379106447180107371909108093722109937190110441807111372290112701844113018447114372209115093719116718044117902237118037199119092237120193790121370229122370922123074418124193709125744180126744018127937220128441807129718044130037229131704418132037922133044187134441870135937022136937190137093722138184470142018744143441807144937019145018744146180744147199370148441807149370199150190937151037229152718440153440718154037922155180744156447018157037919158223790159718440160037919161018744162037922163718440164372290165093722166037199167184470168902237169037919170440187171901937172903719173937190174447180175190379176022937177903719178018744179018447180370922181937022182037229183370229184092237185919370186447180187199037188370922189184470190223790191371909192379190193037199194220379195701844196371909197937220198229037199441807200223790201718044202019937203044187204901937205718044206371909207744180208440187209193709210441807211193709212180744213379220214093722215223709216193790217744180218440718219440718220370199221229037222441870223199370224180447225372290226229370227193790228184470229919370230184470231187044232447180233441807234372290235229370236229037237440187238037229239372209240371909241018744242193709243229037244447180245937190246372209247447180248199037Figure 4
The error performances of the proposed (496,248) LDPC cycle code over GF (64), the comparable (504,252) irregular QC-LDPC code over GF (64) constructed from finite field GF (64) in [15], and (2,4)-regular (496,248) LDPC code over GF (64) constructed based on the progressive edge-growth (PEG) algorithm in [46]. The transmissions on the BPSK modulated AWGN channel are assumed.In the above example, we can see that the constructed nonbinary LDPC cycle code is not quasi-cyclic because of the randomly chosen nonzero field elements in its parity-check matrix. Hence, we next show the performances of the proposed nonbinary QC-LDPC cycle codes.Example 2.
Consider the prime field GF (19), we can easily construct an8×16 matrix P8×16,2 over GF (19) based on the exponent matrix P in equation (12) and the construction framework in Section 3.2. The indices of the chosen 8 rows and 16 columns from P are {1, 2, 4, 5, 7, 8, 14, 15} and {1, 2, 3, 4, 5, 6, 7, 9, 10, 13, 14, 15, 16, 17, 18, 19}, respectively. The row and column selection method is also based on the proposed method in [45]. By dispersing each entry of P8×16,2 into the corresponding CPMs of size 19×19, an 8×16 array HP8×16,2 of 19×19 CPMs is obtained. By employing B8×16 in equation (14) to mask the array HP8×16,2, we can construct an array HMP8×16,2 of 19×19 CPMs. By replacing the 1’s of each CPM in HMP8×16,2 with the same nonzero element of GF (256) in the corresponding row of Table 3, a (2,4)-regular matrix HM,256P8×16,2 over GF (256) is obtained. It is noticeable that the numbers in Table 3 are the power numbers of α, where α is a primitive element of GF (256) created by using the primitive polynomial px=1+x2+x3+x4+x8. The null space of HM,256P8×16,2 gives a (2,4)-regular (304,152) LDPC cycle code over GF (256). The girth of this code is 16, and the number of 16-cycles is 969. Since the nonzero field elements of a CPM in HM,256P8×16,2 are the same, and the resulting (304,152) LDPC cycle code over GF (256) is quasi-cyclic.
For comparison, we construct the (3,6)-regular (2432,1216) LDPC code over GF (2) based on the progressive edge-growth (PEG) algorithm in [46]. The error performances of these two LDPC codes are shown in Figure 5. In the simulations, the employed decoding algorithms of the constructed (304,152) QC-LDPC cycle code over GF (256) and the (2432,1216) LDPC code over GF (2) are the QSPA (50 iterations) and the sum-product algorithm (SPA) with 50 iterations, respectively. The transmissions on the BPSK modulated AWGN channel are assumed. We can see that the constructed (304,152) QC-LDPC cycle code over GF (256) can outperform the (2432,1216) LDPC code over GF (2) about 0.75 dB at the BER of 10−6.Table 3
The nonzero field elements in the corresponding CPMs of the parity-check matricesHM,256P8×16,2 in Example 2.
Row indexNonzero field elements1018281722173018283401670127440127016954016901286172818207817218208401691280Figure 5
The error performances of the constructed (304,152) QC-LDPC cycle code over GF (256) and the comparable (2432,1216) LDPC code over GF (2) constructed based on the progressive edge-growth (PEG) algorithm in [46]. The transmissions on the BPSK modulated AWGN channel are assumed.


## 5. Conclusion

This paper proposed a design framework of binary QC-LDPC cycle codes and constructed nonbinary LDPC (NBLDPC) cycle codes based on circulants and finite fields. The presented construction method consists of three parts. First, the masking matrices are designed based on circulants and the point-line relation in graph theory. Second, the exponent matrices of binary QC-LDPC cycle codes are constructed from finite fields and the designed masking matrices. Third, by replacing 1’s in the parity-check matrices of binary QC-LDPC cycle codes with the nonzero field elements, NBLDPC cycle codes are obtained. Numerical results show that the constructed NBLDPC cycle codes have good iterative decoding performance.



---

*Source: 4099918-2021-09-23.xml*