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

(?)

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.