# Design LDPC Codes without Cycles of Length 4 and 6

Authors: Jun Fan; Yang Xiao; Kiseon Kim
Journal: Research Letters in Communications
 (2008)

---

## Abstract

We present an approach for constructing LDPC codes without cycles of length 4 and 6. Firstly, we design 3 submatrices with different shifting functions given by the proposed schemes, then combine them into the matrix specified by the proposed approach, and, finally, expand the matrix into a desired parity-check matrix using identity matrices and cyclic shift matrices of the identity matrices. The simulation result in AWGN channel verifies that the BER of the proposed code is close to those of Mackay's random codes and Tanner's QC codes, and the good BER performance of the proposed can remain at high code rates.


---

## Body

## 1. Introduction

LDPC codes can
be described by a bipartite graph called Tanner graph [1], and the girth of a
Tanner graph is the length of the shortest cycle in the graph. Girths in the
Tanner graphs of LDPC codes prevent the sum-product algorithm from converging [2–10].
Further, cycles, especially short cycles, degrade the performance of LDPC decoders,
because they affect the independence of the extrinsic information exchanged in
the iterative decoding [2, 3]. Hence, LDPC codes with large girth are desired.
Most methods for designing LDPC codes are based on random construction
techniques, the lack of structure implied by this randomness presents serious
disadvantages in terms of storing and accessing a large parity-check matrix,
encoding data, and analyzing code performance (e.g., determining a code’s
distance properties). Recent research results [4–10] about LDPC codes with
large girths show that there are many possible ways to construct the LDPC codes
with large girths. However, some of the code constructions [4–10] are not
satisfied for application due to the complicated constraints for the structures
of parity-check matrices. To solve the problem, this letter provides a
different construction of LDPC codes with large girth. The column weight of our
codes is 3 and the row weight is v (v>3). The BER performance of the proposed
codes is near to those of Mackay’s random codes and Tanner’s QC codes.This letter is
structured as follows. In Section2, we analyze the figures of 4-cycles and
6-cycles in the parity-check matrix.Section3 presents the design algorithm of the parity-check matrix.
Section 4 provides three lemmas show that the proposed codes do not contain 4-cycles
and 6-cycles. Section 5 evaluates
the BER performance of the proposed codes for AWGN channels via computer
simulations. Finally, In Section 6 we make some conclusions.


## 2. Definitions of the Cycles

An(n,j,k) LDPC code has the parity-check matrix H of n columns, where H has j ones in each column, k ones in each row, and
zeros elsewhere, then the (n,j,k) parity-check matrix has m=nj/k rows [1, 2]. A bipartite graph with m check nodes and n−m bit nodes can be created with the edges
between the bit and check nodes if there are corresponding
1s in the parity-check matrix H.
Such a graph is frequently called a Tanner graph [1, 11]. A cycle in a Tanner
graph refers to a finite set of connected edges, the edge starts and ends at
the same node, and it satisfies the condition that no node (except the initial
and final node) appears more than once [4–10, 12]. The length of a cycle is
simply the number of edges of the cycle.A cycle also
can be shown in a tree. Figure1 shows a 4-cycle in a tree, and Figure 2 shows
a 6-cycle in a tree. Figures 1 and 2 are
not general descriptions for a 4-cycle and 6-cycle in a tree. It is also
possible that a 4-cycle or a 6-cycle starts from a variable (bit) node, similar
to the trees in Figures 1 and 2. In a tree, check nodes represent rows in
parity-check matrix, and variable (bit) nodes represent columns. We try to
design a parity-check matrix without 4-cycles and 6-cycles.Figure 1
A 4-cycle in tree.Figure 2
A 6-cycle in tree.


### 2.1. Figures of 4-Cycles in Parity-Check Matrix

In Figure1,
two 1s (we mark them as m1 and m2) in row a belong to column b and c, respectively, two 1s (we mark them as m3 and m4) in row d belong to column b and c, respectively, so the figure of the 4-cycle in
the parity-check matrix as shown in Figure 3. If there is no figure as shown in
Figure 3 in parity-check matrix, there is no 4-cycle in the LDPC code. We
denote 4-cycles as G4(m1,m2,m3,m4).Figure 3
A 4-cycle in a parity-check matrix.


### 2.2. Figures of 6-Cycles in Parity-Check Matrix

Figure4 shows
that m1 and m2 in row a belong to column b and c, respectively, m3 in column b belongs to row d, m4 in column c belongs to row e, m5 in row d and m6 in row e belong to column f,
where m1, m2, m3, m4, m5, m6 represent six 1s in 6-cycle, as shown in Figure
4. We denote 6-cycles as G6(m1,m2,m3,m4,m5,m6).Figure 4
A 6-cycle in a parity-check matrix.From Figure4 we know that six 1s in a 6-cycle belong to 3
rows and 3 columns equally, so we can get the number of 6-cycles with different
figures to be 6 from Figure 5.Figure 5
Six kinds of 6-cycles with different figures.Figure5 shows
six different kinds of figures of 6-cycles. If there is no figure as shown in
Figure 5 in the parity-check matrix, there is no 6-cycle in the LDPC code.


## 2.1. Figures of 4-Cycles in Parity-Check Matrix

In Figure1,
two 1s (we mark them as m1 and m2) in row a belong to column b and c, respectively, two 1s (we mark them as m3 and m4) in row d belong to column b and c, respectively, so the figure of the 4-cycle in
the parity-check matrix as shown in Figure 3. If there is no figure as shown in
Figure 3 in parity-check matrix, there is no 4-cycle in the LDPC code. We
denote 4-cycles as G4(m1,m2,m3,m4).Figure 3
A 4-cycle in a parity-check matrix.


## 2.2. Figures of 6-Cycles in Parity-Check Matrix

Figure4 shows
that m1 and m2 in row a belong to column b and c, respectively, m3 in column b belongs to row d, m4 in column c belongs to row e, m5 in row d and m6 in row e belong to column f,
where m1, m2, m3, m4, m5, m6 represent six 1s in 6-cycle, as shown in Figure
4. We denote 6-cycles as G6(m1,m2,m3,m4,m5,m6).Figure 4
A 6-cycle in a parity-check matrix.From Figure4 we know that six 1s in a 6-cycle belong to 3
rows and 3 columns equally, so we can get the number of 6-cycles with different
figures to be 6 from Figure 5.Figure 5
Six kinds of 6-cycles with different figures.Figure5 shows
six different kinds of figures of 6-cycles. If there is no figure as shown in
Figure 5 in the parity-check matrix, there is no 6-cycle in the LDPC code.


## 3. Design Algorithm of Parity-Check Matrix

If there is a
parity-check matrixH,
row weight is v (v>3), column weight is 3. We design three
submatrices D, E, F,
combine them into matrix H1, H1=[DEF],
transpose H1 into H2,
expand H2 into desired parity-check matrix H using identity matrices and cyclic shift
matrices of the identity matrix randomly.


### 3.1. Design Algorithm of SubmatrixD

The design algorithm ofD is as following.(1)
Design a matrixD0 with the dimension v×v2. D0(1,1)=D0(2,1)=D0(3,1)=⋯=D0(v,1)=1,
other elements are “0”
(1)D0=[10000⋯010⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮10000⋯0]v×v2.(2)
LetD1=D01, D2=D02, D3=D03,…,Dv2−1=D0v2−1, where D0k represents circularly shift D0 in (1) for k right-shifting steps circularly.(3)
LetD=[D0,D1,D2,…,Dv2−1]T and its dimension is v3×v2.


### 3.2. Design Algorithm of SubmatrixE

The design algorithm ofE is as following.(1)
Design a
matrixE0 with the dimension v×v2. E0(1,1)=E0(2,2)=E0(3,3)=⋯=E0(v,v)=1,
other elements are 0s
(2)E0=[10⋯00⋯001⋱⋮⋮⋮⋮⋮⋱⋱0⋮⋮⋮0⋯010⋯0]v×v2.(2)
LetE1=[E0,E0,…,E0]T,
the number of E0 included in E1 is v.(3)
LetE2=E1v, E3=E12v,…,Ev=E1(v−1)v, where E1k represents circularly right-shifting E1 for k steps.(4)
LetE=[E1,E2,…,Ev]T with the dimension v3×v2.


### 3.3. Design Algorithm of SubmatrixF

The design algorithm ofF is as following.(1)
Designing a matrixF0 with dimension v×v2.  F0(1,1)=F0(2,v+1)=F0(3,2v+1)=⋯=F0(v,v2−v+1)=1,
other elements are “0.” For v=4, we can get F0 by the following way: (3)F0=[1000000000000000000010000000000000000000100000000000000000001000]v×v2.(2)
LetF1=F01, F2=F02, F3=F03,…,Fv−1=F0v−1, where F0k represents F0 with circularly right-shifting k steps.(3)
LetFv=[F0,F1,…,Fv−1]T.(4)
LetF=[Fv,Fv,…,Fv]T, there are v copies of Fv in F, so the dimension of F is v3×v2.We can getH1 by the following way:(4)H1=[D0E0F0⋮⋮⋮Dv−1E0Fv−1DvE2F0⋮⋮⋮Dv2−1EvFv−1]v3×3v2. Let H2=H1T, then the dimension of H2 is 3v2×v3.


### 3.4. Expansion ofH2

The expansion algorithm is as follows.(1)
Select an identity matrixI with dimension p×p,
(5)I=[10⋯001⋯0⋮⋮⋱000⋯1]p×p.(2)
LetI1=I1, I2=I2,…,Ip−1=Ip−1,
where Ik represents the matrix I with circularly right-shifting k steps.(3)
Exchanging the 1s inH2 by the elements in the matrix set {I,I1,I2,…,Ip−1} randomly and exchanging 0s by null matrices
with the same dimension as I,
then we get the parity-check matrix H,
whose dimension is 3pv2×pv3.From the structure of the parity-check matrixH,
we can see that the proposed code is a deterministic LDPC code, so the proposed code has the advantage
for encoding. To get the LDPC code with the large length (3pv2), we can expand the H by selecting the desired dimension p of the identity matrix I in (5) with stochastically shifting.


## 3.1. Design Algorithm of SubmatrixD

The design algorithm ofD is as following.(1)
Design a matrixD0 with the dimension v×v2. D0(1,1)=D0(2,1)=D0(3,1)=⋯=D0(v,1)=1,
other elements are “0”
(1)D0=[10000⋯010⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮⋮10000⋯0]v×v2.(2)
LetD1=D01, D2=D02, D3=D03,…,Dv2−1=D0v2−1, where D0k represents circularly shift D0 in (1) for k right-shifting steps circularly.(3)
LetD=[D0,D1,D2,…,Dv2−1]T and its dimension is v3×v2.


## 3.2. Design Algorithm of SubmatrixE

The design algorithm ofE is as following.(1)
Design a
matrixE0 with the dimension v×v2. E0(1,1)=E0(2,2)=E0(3,3)=⋯=E0(v,v)=1,
other elements are 0s
(2)E0=[10⋯00⋯001⋱⋮⋮⋮⋮⋮⋱⋱0⋮⋮⋮0⋯010⋯0]v×v2.(2)
LetE1=[E0,E0,…,E0]T,
the number of E0 included in E1 is v.(3)
LetE2=E1v, E3=E12v,…,Ev=E1(v−1)v, where E1k represents circularly right-shifting E1 for k steps.(4)
LetE=[E1,E2,…,Ev]T with the dimension v3×v2.


## 3.3. Design Algorithm of SubmatrixF

The design algorithm ofF is as following.(1)
Designing a matrixF0 with dimension v×v2.  F0(1,1)=F0(2,v+1)=F0(3,2v+1)=⋯=F0(v,v2−v+1)=1,
other elements are “0.” For v=4, we can get F0 by the following way: (3)F0=[1000000000000000000010000000000000000000100000000000000000001000]v×v2.(2)
LetF1=F01, F2=F02, F3=F03,…,Fv−1=F0v−1, where F0k represents F0 with circularly right-shifting k steps.(3)
LetFv=[F0,F1,…,Fv−1]T.(4)
LetF=[Fv,Fv,…,Fv]T, there are v copies of Fv in F, so the dimension of F is v3×v2.We can getH1 by the following way:(4)H1=[D0E0F0⋮⋮⋮Dv−1E0Fv−1DvE2F0⋮⋮⋮Dv2−1EvFv−1]v3×3v2. Let H2=H1T, then the dimension of H2 is 3v2×v3.


## 3.4. Expansion ofH2

The expansion algorithm is as follows.(1)
Select an identity matrixI with dimension p×p,
(5)I=[10⋯001⋯0⋮⋮⋱000⋯1]p×p.(2)
LetI1=I1, I2=I2,…,Ip−1=Ip−1,
where Ik represents the matrix I with circularly right-shifting k steps.(3)
Exchanging the 1s inH2 by the elements in the matrix set {I,I1,I2,…,Ip−1} randomly and exchanging 0s by null matrices
with the same dimension as I,
then we get the parity-check matrix H,
whose dimension is 3pv2×pv3.From the structure of the parity-check matrixH,
we can see that the proposed code is a deterministic LDPC code, so the proposed code has the advantage
for encoding. To get the LDPC code with the large length (3pv2), we can expand the H by selecting the desired dimension p of the identity matrix I in (5) with stochastically shifting.


## 4. The Demonstration of the Code with Girth 8

In Section3,
we present a method for constructing parity-check
matrix H with girth 8 based on the submatrices’
shifting. In this section, we add three lemmas with theoretic proofs showing
that the parity-check matrix H does not contain 4-cycles and 6-cycles.Lemma 1.
If a matrixH1 is constructed by (4), there is no 4-cycle in H1.Proof.
We can know from Figure3 that if there are 4-cycles
in the matrix H1 in (4), the edges connecting {m1,m3} and {m2,m4} must be in two different submatrices of D, E, F, because m1 and m2 are in the same row. The following formula
must be true:
(6)L(m1,m3)=L(m2,m4).
In the
submatrixD,
the lengths L(m1,m3) and L(m2,m4) could be 1,2,…,v−1.
In the submatrix E,
the lengths L(m1,m3) and L(m2,m4) could be v,2v,…,(v−1)×v.
In the submatrix F,
the lengths L(m1,m3) and L(m2,m4) could be v2,2v2,…,(v−1)×v2. We can easily know that L(m1,m3)≠L(m2,m4),
so there is no 4-cycle in the matrix H1.Lemma 2.
If a matrixH1 is constructed by (4), there is no 6-cycle in H1.Proof.
As shown in Figure4, if there are 6-cycles in the
matrix H1, the edges connecting {m1,m3},  {m2,m4}, and {m5,m6} must be in D, E, and F, respectively. Without loss of generality, we assume that L(m2,m4) is the longest length among the three lengths.
The following formula must be true:
(7)L(m1,m3)+L(m5,m6)=L(m2,m4).
In the
submatrixD,
the lengths L(m1,m3), L(m5,m6) and L(m2,m4) could be 1,2,…,v−1.
In the submatrix E,
the length of L(m1,m3), L(m5,m6), and L(m2,m4) could be v,2v,…,(v−1)×v. In the submatrix F,
the lengths L(m1,m3), L(m5,m6), and L(m2,m4) could be v2,2v2,…,(v−1)×v2. We can know that the edge of L(m2,m4) must be in F,
or else
(8)L(m1,m3)+L(m5,m6)>L(m2,m4). We know that
(9)1+v≤L(m1,m3)+L(m5,m6)≤(v−1)(v+1), and L(m2,m4)≥v2,
so
(10)L(m1,m3)+L(m5,m6)<L(m2,m4). Thus there is no 6-cycle in the matrix H1,
which means H to be free from 6-cycles.We know thatH2=H1T, so the matrix H2 is also free of 4-cycles and 6-cycles.Lemma 3.
If there is no 4-cycle and 6-cycle in
the matrixH2,
there is no 4-cycle and 6-cycle in the parity-check matrix H.Proof.
If there is a 4-cycleG4(m1,m2,m3,m4) in the parity-check matrix H,
from Figure 3 we can know that m1, m2, m3, and m4 must be in four different identity matrices or
cyclic shift matrices of identity matrices. Since an identity matrix I and a cyclic shift matrix of the I in H means a “1” in H2,
there is a 4-cycle in H2.
However, we know that there is no 4-cycle in H2,
so there is no 4-cycle in the parity-check matrix H.
Using the same method, we can know that there is no 6-cycle G6(m1,m2,m3,m4,m5,m6) in the parity-check matrix H.


## 5. Performance Evaluation

To demonstrate the error-correcting
performance, we constructed two rate-1/2 LDPC codes by the proposed method. For the purpose of comparison, we also construct
two classes of Tanner’s
QC codes and Mackay’s random codes [10, 11, 13].
We get Mackay’s random codes from [13]. Tanner’s QC codes are constructed by
the method introduced in Tanner’s paper [10, 11]. Both Mackay’s
random codes and constructed Tanner’s QC codes
for the comparison are good codes. The selected
codes’ parameters are given in Table 1.Table 1
Parameters of example codes with rate-1/2.
kjNRgNew⋅1080⋅5406310801/28Mac⋅1074⋅5376310081/26QC⋅1074⋅5376310021/28Table1 lists the typical values of the row weight k, the column weight j, the code length N,
the code rate R, and the girth g for the three codes. The girths of the LDPC codes in
Table 1 are tested by the approach of [12]. Table 2 lists the typical values of the
proposed codes for different high code and code lengths. In Tables 1 and 2, the New⋅n⋅m means the proposed code with the code length n and m parity check
bits, so do the Mac⋅n⋅m and Qc⋅n⋅m.Table 2
Parameters of our codes with high-rate.
kjNRgNew⋅5103⋅17019351030.678New⋅5000⋅150010350000.78New⋅5184⋅129612351840.758We simulate
the proposed code’s error-correcting performance with the assumption that each
code is modulated by BPSK and transmitted over additive white Gaussian noise
(AWGN) channel. All the codes are decoded with the sum-product algorithm [2, 3].
Figure 6 shows the simulated BER versus signal-to-noise ratio (Eb/N0). As shown
in Figure 6. The BER performance of the proposed codes is very close to
MacKay's random codes and Tanner’s QC codes. From Figure 7, it can be seen that
the proposed codes also have a good BER performance at high code rates 0.67,
0.7, and 0.75. The BER curves of the two codes of at high code rates 0.67, 0.7
are close since two LDPC codes with different code lengths may have approximate
minimum weights [10]. In the expansion algorithm of the proposed code, we replace
“1” in H2 by the elements in the set {I,I1,I2,…,Ip−1} randomly, which will lead to the minimum
weights of the obtained codes to be different, the shorter codes may have
larger minimum weights.Figure 6
BER performance comparison of our code, Mackay’s random code and Tanner’s QC
code.Figure 7
BER performance of
our codes at high code rate.


## 6. Conclusions

In this paper,
we proposed a QC LDPC code without girth-4 and girth-6, three lemmas are
provided to prove the short girths’ properties of the proposed codes.
Simulation verified the good error-correcting performance of the proposed code,
whose BER performance is near to those of Tanner’s QC codes and MacKay’s random
codes [10, 11, 13]. The good BER performance can remain at high code rates.



---

*Source: 354137-2008-04-03.xml*