Low-density parity-check (LDPC) codes (Gallager, 1962,
1963) are a group of linear block codes which are introduced
by a low density parity check matrix H = (hi,j)mxn such
that the number of nonzero components is too lesser than zero components. LDPC
codes have a remarkable performance with iterative decoding that is very close
to the Shannon limit over additive white Gaussian noise (AWGN) channels. Minimum
distance in LDPC codes with column weight j = 2 increases logarithmically and
in LDPC codes with column weight j = 3 increases linearly (Gallager,
1962). The LDPC codes with column weight j = 2 have several advantages:
encoding and decoding of these codes are simply performed, because have low
complexity and also have good performance in trivial reflex channel (Song
et al., 2002). There are several method for construction of LDPC
codes with column weight j = 2. One of them is based on graph. Malema
and Liebelt (2007) presented a method for this construction based on distance
graph which these codes have high girth. Tao and Zheng presented a method for
construction of (2,k)-LDPC codes from (k,k)-LDPC codes in Tao
et al. (2011). The LDPC codes with girth 16 and rate 1/2 (and also
with girth 20 and rate 1/3) constructed by Zhang and Moura
(2003) based on graphical method. By improving of this method, the LDPC
codes constructed with girth almost g = 24 and variable rates (Esmaeili
and Gholami, 2009).
CONSTRUCTION OF 2-COLUMN WEIGHT LDPC CODES BASED ON A BIPARTITE GRAPH
LDPC codes are a group of linear block codes which are introduced by a low density parity check matrix H = hi,jmxn such that the number of nonzero components is too lesser than zero components. The number of nonzero components in each row and each column shows the row weight and column weight and denoted by k and j, respectively.
LDPC codes can be describe by a bipartite graph called Tanner graph (Tanner,
1981). These are composed of two sets of nodes, namely, variable nodes and
check nodes. Each variable node represents a bit in a code word and each check
node corresponds to a parity-check constraint. If a variable node is constrained
by a check node, we connect these two nodes by an edge. Figure
1 shows a parity check matrix and it s corresponding Tanner graph. Note
that the row and column weight is equal to degree of each check node and variable
A cycle in Tanner graph is a finite set of nodes and edges such that initial
and final nods coincide at the same point and no node appears more than once
(except the initial and final node).
||(a) A parity check matrix and its Tanner graph and (b) A new
parity check matrix an its bipartite tanner graph obtained from part A
The girth of the code is the length of the shortest cycle in its factor graph
and it is a crucial parameter. Cycles, especially short cycles, degrade the
performance of LDPC decoders. Because they affect the independence of the extrinsic
information exchanged in the iterative decoding. Obviously the length of cycles
in Tanner graph and check matrix is even and the minimum possible girth is 4.
Base of construction of LDPC codes: First we recall a definition. A finite geometry with m points and n lines satisfies the following properties:
|| Each line is composed of j points
||There is one and only one line between any two points
||Each point lies on k lines
||Any pair of lines has at most one common point
Kou et al. (2001) presented a method for construction
of LDPC codes based on finite geometry.
Method of construction: Consider a LDPC code and its Tanner. Tanner
graph of this code is a finite geometry, because contains the finite number
of points and lines. A new bipartite graph is constructed from the Tanner graph
of this code, such that check and variable nodes of this Tanner graph form the
vertices of one part of this new bipartite graph and edges of initial Tanner
graph form the vertices of the another part of the new bipartite graph. The
parity check matrix corresponding to this new bipartite graph forms a 2-weight
LDPC code, because each line in the initial Tanner graph exactly from 2 points.
This construction can continue recursively. The girth in new LDPC code is twofold
the girth in initial LDPC code. In fact by considering a LDPC codes with girth
g, we can construct a 2-column weight LDPC code with girth 2g. This method can
be used for each bipartite graph. Here we give an example.
Consider a parity check matrix of a (2,3)-LDPC code. This matrix and its Tanner graph have been shown in Fig. 1a. The girth of this matrix and Tanner graph is 8. one example of this cycle has been shown in Fig. 1b. The 9 column and 6 rows are corresponding to 9 variable nodes and 6 check nodes, respectively.
We can create a new bipartite graph from this Tanner graph. The vertices and
edges in Tanner graph of Fig. 1a are as check nodes and variable
nodes in the new bipartite respectively.
|| Simulation result and performance comparison
|| List of some codes constructed by our approach
Figure 1b shows the bipartite graph which obtained from Tanner
graph in Fig. 1a. The girth of graph in the Fig.
1b is 16. The matrix corresponding to this graph has been shown in Fig.
1b. The 18 column of this matrix are corresponding to 18 edges in initial
Tanner graph which are shown by l1,l2,....,l18
and 15 rows of this matrix are corresponding to 15 vertexes of initial Tanner
graph. The matrix corresponding to Tanner graph in Fig. 1b
is considered as a parity check matrix of 2-column weight LDPC code.
In general, in this construction by considering a bipartite graph with m and n vertices in two parts of graph and l edges, we can create a new bipartite graph with m+n vertexes in one part of graph and l vertices in the another part of graph such that degree of each vertex of the part with l vertices is 2. The girth in new LDPC code is twofold the girth in initial LDPC code. Consider a complete bipartite graph Kn,n. This graph has 2n vertexes and n2 edges. Therefore the parity check matrix of this 2-column weight LDPC code is a 2nxn2 matrix and rate of this matrix is at least:
From this construction, we can construct LDPC codes with column weight j = 2 and high girth. Table 1 show some 2-column weight LDPC codes which obtained from this method. The size of initial parity check matrix and the size of the new parity check matrix were shown by m1xn1 and m2xn2, respectively.
Bit Error Rate (BER) performance of a non-binary LDPC code with column weight j = 2 and 12 girth obtained from this method over additive white Gaussian noise (AWGN) channel, Binary phase-shift keying (BPSK) modulation and 20 repeat has been simulated which has been shown in Fig. 2. This code was turned to a non-binary code in F16 randomly such that the girth of the non-binary code growed to 14 and 16. The simulation results show that this code has better performance than random Mackay codes.
In this study, a method was presented for construction of LDPC codes with column
weight j = 2 base of graph. These codes are constructed by applying the Tanner
graph of every LDPC code. Then, by recursive and deriving from such codes, we
design 2-column weight LDPC codes with girth twofold. The girth in new LDPC
code is twofold the girth in initial LDPC code. High girth effect the independence
of the extrinsic information exchanged in the iterative decoding. Also the simulation
results show that this code has better performance than random Mackay codes.