Abstract: representations in our earlier work. The convergence

Abstract: One of the most
advanced classes of channel codes is the class of Low Density Parity Check (LPDC)
codes, specified by parity check matrix ‘A’. The structured regular
construction of matrix ‘A’ makes the hardware implementation simpler and
reduces decoder complexity. We proposed a novel flexible method to construct structured
regular LDPC codes, based on Gray-code representations in our earlier work. The
convergence in Sum Product Algorithm depends on the length of cycles in Tanner
graph of LDPC codes, i.e., the decoder performance of these codes can be
improved by avoiding short cycles in A-matrix. In this paper, a method to avoid short cycles is presented. The computational
complexities of LDPC codes with column-weight two is low and are efficient for
data storage and partial response channels. The BER performance of the obtained Gray-code based column-weight two
LDPC codes  is reported and it is noticed
that they are comparable to that of QC-LDPC codes and Gallager’s  random codes.Keywords: Gray codes, Tanner graph, Short cycles, Girth, Gallager
codes, Column-weight two QC-LDPC codes, BER. I. Introduction     In 1962, Robert Gallager proposed Low-Density
Parity-Check codes. The error correcting performance of LDPC codes have been
shown to be close to Shannon’s channel capacity limits 1 2. Unfortunately,
Gallager’s remarkable discovery was mostly ignored by coding researchers for
almost 20 years due to the high complexity and memory requirements of the
encoding and decoding operations. LDPC codes are rediscovered by David MacKay in
1996 3 and he showed their capacity-approaching performance using iterative
decoding techniques.      Some of the parameters have to be
considered in the construction of parity check matrix. Structured construction
reduces hardware complexity and the cost of encoders and decoders 456. Large
girth tends to improve the code performance by speeding up the convergence of
iterative decoding where as small ones especially of length four degrade the
performance 7. Hence, LDPC codes with large girth are preferred. Different
methods for constructing LDPC codes with large girth are available in
literature. The minimum distance is an important property of the code which
dictates error rate performance achievable under optimal decoding. Minimum
distance of the code grows linearly with code length, ‘n’ for column weight ?3
and logarithmically with column weight of two 1. Thus, the performance
of column-weight two codes is lower comparatively. But, column-weight two codes
are more suitable for partial response channels. They can be employed in the
systems where the inter-symbol-interference (ISI) is prominent. These codes are
suitable for high-speed applications such as magnetic recording or optical
communication 8 9. Their structure can usually be exploited for an
efficient implementation and they can be encoded with low complexity. They exhibit
better block error performance 9. Concatenation of Reed-Solomon codes with
column-weight two LDPC codes promise better error correcting codes for data
storage applications 10. There
are several suggested methods for constructing column-weight two LDPC codes.
Graphical models are used in 10 to construct girth 10 and 20 codes. However,
the suggested graphical models are limited to 1/2 and 1/3 code rates. In 10, QC-LDPC
codes are constructed but limited to girth 12. In 11, finite geometry is used
to construct a (k,k) quasi-cyclic LDPC code which is then converted into
a (2,k) LDPC code, where k is the row-weight and 2 is the
column-weight. The size and the rate of the obtained codes are limited by the
finite geometry approach which does not have flexibility in size and matrix configuration.
In 12, the distance graph is
converted into a Tanner graph to construct column-weight two codes. In
this paper, we have used our novel flexible algorithm proposed in 13 to
construct column-weight two structured regular LDPC codes, based on Gray-Code representations
(GC-LDPC), without short cycles, and reported their performance with respect to
different row weights, code rates, code lengths and number of iterations.  The
rest of the paper is organized as follows: Section II presents the proposed
algorithm for constructing flexible Gray-Code based LDPC codes. Construction of
column-weight two codes with different girths is briefed in sections III and IV.
In section V, the proposed algorithm to construct parity check matrix without short
cycles is presented. Bit Error Rate (BER) performance of obtained codes is
presented in Section VI. Section VII has concluding remarks.        II. CODE CONSTRUCTION ALGORITHMLet
‘A’ be the parity-check matrix with ‘m’ parity-check equations, i.e., A is m ×
n matrix, where ‘n’ is the code length.  Let
‘Y’ be the decimal point set of these parity check equations i.e., the elements
of point set ‘Y’ be Y = {Y1, Y2, Y3 ,………., Y?,
Y?+1 } where ‘?’ is the row weight of A-matrix. The elements of this
set can be selected using the following equation:Case 1: For row-weight ‘?’ even: Select Y1=0,
point set Y = {Y1, Y2, Y3, ………., Y?,
Y?+1 }. The remaining elements of set Y can be selected by using the
following equation,Y i + 1 = 2Yi + 1;               for i = 1,2,3,…..,?+1Case 2: For row-weight ‘?’ odd: Select Y1=1,
point set Y = {Y1, Y2, Y3 ,………., Y?}.
The remaining elements of set Y can be selected by using the same equation,Y i + 1 = 2Yi + 1;               for i = 1,2,3,…..,? The proposed method is based on
Gallager’s method of construction of LDPC codes. For (?, ?) LDPC code, where
‘?’ is row-weight and ‘?’ is column-weight, the A-matrix is constructed by
concatenating ‘?’ number of sub-matrices vertically. The transpose of A-matrix
is given below:A? = A1, A2, A3,……..,A?      Finally, these matrix elements are
represented in Gray codes. The proposed algorithm gives the systematic way of
selecting the decimal numbers using the design equation. Table 1 shows the
various code rates, lengths and densities of A-matrix with column-weight two
and column-weight three codes, for different row-weights. Table 1 Code
rates, densities and code lengths under different row-weight ? and
column-weight ? 

Row-weight
(?)

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

 
 
Density of H
 

 
 
Code
length  (n)

Column-weight(?)

? = 2

? = 3

Code rate
(1-?/?)

Code-rate
(1-?/?)

4

0.200

20

0.500

0.250

5

0.200

25

0.600

0.400

6

0.142

42

0.666

0.500

7

0.142

49

0.714

0.571

8

0.111

72

0.750

0.625

9

0.111

81

0.777

0.666

10

0.090

110

0.800

0.700

 III. COLUMN-WEIGHT TWO LDPC CODES WITH
GIRTH 8 The parity check matrix ‘A’ of
column-weight two is constructed with two sub-matrices A1 and A2
as discussed below:Construction
of  A1:    
The point set ‘Y’ can be selected according to the required row-weight.
The elements of this set form the first row of A1. The subsequent
rows of A1 are obtained by cyclically shifting the elements of first
row, to right, until the first row repeats. Construction
of A2:      The
elements of the first row of A1, in reverse order, form the first
row of A2. The subsequent rows are obtained by cyclically shifting
the elements of first row, to right, until the first row of A2
repeats. The A-matrix is
obtained by concatenating these A1 and A2 sub-matrices
vertically as, A? = A1,
A2Illustration:    
The sub-matrix A1, for row-weight 4, can be constructed using
the first five decimal values from the designed point set. The first row of A1
is formed directly from the point set. The second and subsequent rows are
obtained by circularly shifting the first and preceding rows to the right,
respectively, as shown below: Similarly, A2 is constructed as discussed
before. The A-matrix is obtained by concatenating these A1 and A2
sub-matrices vertically as, A? = A1, A2. The girth
obtained with this construction method is eight, which can be verified with the
corresponding structure graph.  Code
expansion:The matrix ‘A’ constructed for any
selected value of ?, is called a ‘base matrix’ of row-weight ‘?’ and it is a
matrix with minimum size 2? × ?2. Let the size of this matrix be (m×n).
For example, 6´9 is the minimum size of the matrix
for ?=3
and it is a base matrix for row-weight 3. The base matrix can be expanded to different
levels as shown in the Table 2. In expansion level 1, each ‘1’ in base matrix,
is replaced by a corresponding ?´? matrix in
which it appears and a ‘0’ is replaced by a ?´? zero matrix. The size of expanded matrix in level 1
will be (m? × n?). This is the base matrix for expansion level 2. Let the size
of this matrix be (p × q). In expansion level 2, each ‘1’ in the expanded
matrix of level 1, is replaced by a (p? × q?)  block of a base matrix and a ‘0’ is
replaced by zero matrix of same size. The same procedure is followed for
expansion of level 3 and so on. The minimum distance of the
code is at least one more than the ?. Table 2 Code Size
and Code Rates for (n, 2, ?) Code
with Girth Eight 

?

Min.
size

Level
1

Level
2

Level
3

Code-rate

3

6´9

18´27

54×81

162×243

1/3

5

10×25

50×125

250×625

1,250×3,125

3/5

7

14×49

98×343

686×2,401

4,802×16,807

5/7

  IV. CONSTRUCTION OF COLUMN-WEIGHT TWO CODES WITH
GIRTH 12 It is reported in 10 that decoding performance
improves with higher girth. Hence, we modified our proposed algorithm to achieve
a girth of 12. The proposed method is based on block-wise construction. All the
elements of the selected set are arranged in a column to get an elementary
block C1. Some minor modifications are made on the elementary block
C1 to obtain the other blocks C2 and C3. The
following steps indicate the construction method: 
The
elements of point set ‘Y’, arranged vertically, form column of C1. 
The
bottom element of C1 is shifted to the top row and other
subsequent rows are shifted down to their succeeding rows to obtain block
C2. 
Similarly,
the top two elements of C1, are shifted to the bottom and the
remaining elements are shifted up, to their preceding rows to obtain block
C3.
By concatenating
three C1 blocks horizontally, the sub-matrix A1 is
formed.
Similarly, the
sub-matrix A2 is obtained by horizontal concatenation of C1,
C2 and C3.
Finally, the decimal elements
of the designed blocks are represented in their corresponding Gray codes
to obtain the column-weight two matrix ‘A’ as below:
 As
an illustration, let required row weight be ?=3 and i=7 for a (n, 2, ?) code. The elements of block
C1 are, Y = {Y1, Y2, Y3,………., Y7}.
Representing these elements in 7-bit Gray code, the size of block C1
is 7×7. The elements of block C2 are Y = {Y7, Y1,
Y2, … Y6}. Similarly, block C3 is constructed using set Y
= {Y3, Y4, … Y1, Y2}. Matrix ‘A’ is
constructed using these three blocks. The code can be expanded as explained in
section III. V. PROPOSED ALGORITHM TO
CONSTRUCTA-MATRIX WITHOUT SHORT
CYCLES OF 4 AND 6 Short
cycles in parity check matrix: If the number of 1’s that
are in common between any two columns is greater than ‘1’, then 4-length cycle
exists. To avoid 4-length cycle, no two rows must share ‘1’ in more than one
column. In Figure 1(a), the decimal values Yi in row ra
and Yi in row rb, belonging to the column cc should
not share any other decimal value Yj in any other column cd
in the same rows, where 1 ? (i, j) ? ?. If there are no four edges connecting Yi
and Yj as shown, then there is no 4-cycle in the LDPC code. Similarly,
Figure 1 (b) shows the shape of a 6-cycle. Here, Yi , Yj  and Yk are the integers
selected from the design equation to construct A-matrix where 1?  (i, j, k) 
? ?.(a)                                                       (b)                                                    Figure 1: Shapes of
4-cycle and 6-cycle                                  Figure 2.
Shapes of all possible 6-cycles     
The possible six different shapes of 6-cycles are shown in Figure 2. If
A-matrix does not contain the set of edges connected in any one of the shown
types, then there is no 6-cycle in the LDPC code. In any of these six different
shapes, it can be observed that, if the length of the longest edge is the sum
of the lengths of the smaller edges, then there exists 6-length cycle. In this
section, we prove that the proposed algorithm is free of short cycles of 4 and
6. Lemma-1: If A-matrix is constructed using the proposed method, there is no 4-length
cycle in ‘A’.Proof:
         1              3              7              15            31                                                            1              3              7              15            31            31            1              3              7              15                                                            31            1              3              7              1515            31            1              3              7          A1                                                                15            31            1              3              7               
A17              15            31            1              3                                                              7              15            31            1              33              7              15            31            1                                                              3              7              15            31            1             

 

31            15            7              3              1                                                              31            15            7              3              11              31            15            7              3                                                              1              31            15            7              33              1              31            15            7          A2                                                               3              1              31            15            7                A27              3              1              31            15                                                            7              3              1              31            1515            7              3              1              31                                                            15            7              3              1              31                               Figure
3                                                                                                                   
Figure 4     In Figure 3, the element ‘1’
(Yi) belonging to row 1 and another ‘1’ (Yi) belonging to
row 7, both appear in the first column. Let the length of the edge, {Yi, Yi}, connecting these two elements be L1.
It can be noticed that there is no other edge of length L1 connecting
any of the same elements Yj, i.e., {Yj, Yj}, that belong to the same rows, namely, 1 and
7. Hence, in the proposed construction method, there are no 4-cycles in
the matrix A.                 Lemma-2: If a matrix ‘A’
is constructed by proposed method,
there he longest edge is no 6- cycle in A. Proof:
In Figure 4, let
{Yi,
Yi}
be the edge connecting two 1’s in first column and we assume that the edge
connecting two same elements {Yk, Yk} is the longest
length among the three edges. It can be noticed that, there is no other edge
connecting any of the two same elements such that the sum of the two edges is
equal to the longest edge. In the devised algorithm, there is no other edge
that forms 6-cycle. Thus, there are no short cycles of 6 in the parity check
matrix.    VI. PERFORMANCE SimulationsThe base matrix constructed using Gray
code representations results in codes that are too small for practical use. An
expansion method is therefore needed to get larger codes. Each “0” entry in the
matrix is replaced by a p´p zero sub-matrix
and each “1” entry is replaced by a shifted p´p identity
sub-matrix. The expanded code is larger than the base matrix by a factor of p
and has girth at least that of the base matrix. Using shifted identity
sub-matrices simplifies addressing in hardware implementation 14.Decoding
performance of obtained codes was measured using bit-error rate (BER)
simulations on AWGN channel with BPSK modulation. The received waveform was demodulated
and decoded by Logarithmic Sum-Product Algorithm. Obtained codes show good BER
performances approaching BER of 10-4 between 3 and 4 dB SNR.  Fig. 5 shows
performance of these codes with different number of row weights and different
lengths, but with the same column weights of two. To demonstrate the
error-correcting performance, we constructed rate-1/2 LDPC codes using the
proposed method. For the purpose of comparison, we also constructed Gallager’s
codes and QC-LDPC codes. Both codes are good codes for comparison and are
constructed with the same parameters as that of proposed codes.The GC-LDPC codes are obtained using the
proposed method. Performance curves of (1600, 2, 4) GC-LDPC codes are compared
to those of QC-LDPC codes 12 of same size and rate and shown in Fig. 6. The obtained
codes perform similar to QC-LDPC codes up to 4.0 dB SNR. The advantage of GC-LDPC
codes is their regular structure which makes it much easier to implement their
encoders and decoders.Fig.
7 shows the performance comparison of obtained codes with that of (1600, 2, 4)
random Gallager’s codes. The BER performance of the proposed codes is very
close to Gallager’s random codes and QC-LDPC codes. In 15, LDPC codes are
constructed using MacKay encoder which is also comparable to these codes.                                                                                                                                                                                                Fig. 5.  GC-LDPC codes for                                        Fig. 6.
GC-LDPC and QC-LDPC codes                     
Fig. 7. GC-LDPC and Gallager’s codes                                                        different row weights                                                             of same
lengths                                                                 of
same lengths                                                                              
                                                                                                                                                                                                                                                             
                                                                                                                                                 VII. Conclusion

Construction of structured regular
column-weight two LDPC codes based on Gray-code representations is described.
These codes are systematically constructed and are generated using a set of
decimals selected from the defined equation. The construction method provides
the flexibility in rates and lengths. As the short cycles in parity check matrix
degrade the performance of LDPC decoder, the devised algorithm also provides a method for constructing LDPC codes
without short cycles 4 and 6. The BER performance of column weight two codes is
presented, and it is noticed that they are comparable to the standard column-weight
two QC- LDPC codes and Gallager’s random codes.