Abstract: We present a method for construction of LDPC codes with 2-column weight. This method is based on graph. By considering a LDPC code, we can construct a 2-column weight LDPC code. In this method, we obtain a parity check matrix mxn from a parity check matrix with m rows and n columns for a LDPC code. The girth g in initial check matrix increases to 2g in new check matrix. This increasing is effective in decoding of code. From the simulation result, we observe that the new LDPC code has better performance than Mackay and nil codes in the field Fq.
INTRODUCTION
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 node, respectively.
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).
| Fig. 1(a-b): | (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.
| Fig. 2: | Simulation result and performance comparison |
| Table 1: | 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.
SIMULATION RESULTS
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.
CONCLUSION
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.