2009 IEEE Symposium on Industrial Electronics and Applications (ISIEA 2009), October 4-6, 2009, Kuala Lumpur, Malaysia

A New Quasi-Cyclic Low Density Parity Check Codes

Abid Yahya and Othman Sidek

Collaborative MicroElectronic Design Excellence Center Universiti Sains Malaysia

14300 Nibong Tebal, Pulau Penang, Malaysia

M. F. M. Salleh

School of Electrical and Electronic Engineering Universiti Sains Malaysia 14300 Nibong Tebal, Pulau Penang, Malaysia

Farid Ghani

School of Computer and Communication Engineering, Universiti Malaysia Perlis, Perlis, Malaysia

Abstract— This paper proposes a new technique for constructing the Quasi-Cyclic low density parity check (QC-LDPC) codes based on row division method. The new codes offer more flexibility in term of girth, code rates and codeword length. In this method of code construction, the rows are used to form as the distance graph. Then they are transformed to a parity-check matrix in order to acquire the desired girth. The new QC-LDPC codes show good bit-error rate performance as compared to the renowned Mackay codes for given values of /b oE N by 0.12 dB at

BER of 710− .

Keywords — Bit error rate; Communication channels; Encoding; Error correction coding; QC-LDPC

I. INTRODUCTION Low Density Parity Check (LDPC) codes [1] have acquired considerable attention due to its near-capacity error execution and powerful channel coding technique with an adequately long codeword length. LDPC codes are designated by a parity check H matrix comprising largely 0’s and has a low density of 1’s. The parity check matrix weight (number of ones in each column or row) for LDPC codes can be either regular or irregular. LDPC code is considered regular if the number of ones is constant in each column or row. Whereas, it is irregular if the number of ones in each column or row varies. Tanner [2] represents LDPC codes effectively using a bipartite graph (called as Tanner graph). The Tanner graph provides complete representation of the codes and helps to explain the decoding process. In Tanner graph the nodes of the graph are separated into two sets i.e. the variable nodes ( v -nodes) and check nodes ( c -nodes). Rows in the LDPC parity check matrix are represented by check nodes and columns are represented by variable nodes. There is an edge between the vertices presenting check node and variable node. A cycle in a graph of vertices and edges is defined as a sequence of associated

edges which commences from a vertex and finishes at the same vertex, and meets the condition that no vertex comes out more than once [3]. The number of edges on a cycle is called the length of the cycle. The length of the shortest cycle in a graph is called the girth of the graph. LDPC codes construction require parameters such as row and column weights, rate, girth and code length. LDPC codes are classified into two types of constructions. The first one is random construction that offers flexibility in term of design and construction. This method has been used in LDPC codes construction as presented in [4-5]. The lack of row-column connection regularity in random construction increases decoder interconnection complexity. This presents serious disadvantages in terms of storing and accessing a large parity-check matrix, encoding data, and analyzing code performance. These problems can be overcome with the second type of code construction. In this method the codes are designed using an algebraic structure as presented in [6-8]. This construction structure has regular interconnection patterns, which reduces hardware complexity for encoders and decoders. From a short to moderate block lengths, the algebraically constructed QC-LDPC codes perform significantly better as compared to the random regular LDPC codes. However, the drawbacks of the algebraic structure codes are limitation in terms of code rate, codeword length and code girth. The codes performance is inferior to the random generated codes when using longer block length. In order to reduce hardware implementation complexity, the algebraic structured codes have been explicated by confining the codes construction as presented in [6-7]. Tanner in [8] investigates a class of LDPC block codes that guarantee to have a large girth. These quasi-cyclic group- algebraic structured regular LDPC codes have highly symmetric graph for lengths of 1055 or less. A novel technique for designing structured quasi-cyclic generalized LDPC (G-LDPC) codes is presented by Liva et al. in [9]. This technique for shorter codes design is based on the insertion of powerful constraint nodes in the

978-1-4244-4683-4/09/$25.00 ©2009 IEEE 239

2009 IEEE Symposium on Industrial Electronics and Applications (ISIEA 2009), October 4-6, 2009, Kuala Lumpur, Malaysia

LDPC bipartite graph. It is found that the approach in that work to design the low rate quasi-cyclic G-LDPC codes produces good performance in both the error floor and waterfall regions on the AWGN channel. Huang et al. in [10] constructed the LDPC codes from graphical models with girths 16 and 18 having the row-weights of 4 and 3. Simulation results obtained from that work is better than the randomly constructed LDPC codes for short to moderate block lengths. However, for large lengths the randomly generated LDPC codes outperform the codes proposed in [10]. In this work, the new QC-LDPC codes with large girth are developed. The method is derived from the basic idea of Bit-Filling (BF) and Progressive Edge-Growth algorithms as proposed by Campello et al. [11] and Hu et al. [12], respectively. In order to keep the row weight to be dependent on the group size, the weight of any column or row is forced to be not smaller than 2. In addition, we also developed a new scheme for determining the degree of variable-nodes distribution which affects the error correcting performance.

The new QC-LDPC codes perform better than the codes developed by MacKay [4] and the PEG codes [12], regardless of the constraints impose since the codes are designed based on quasi-cyclic structure. At BER of 710− , the new QC-LDPC codes achieved of 0.1 dB and 0.12 dB coding gain as compared to the progressive-edge growth (PEG) codes [12] and Mackay codes [4] respectively.

II. PROPOSED METHOD FOR GENERATING QC-LDPC CODES

The BF [11] algorithm designs a LDPC code by connecting rows and columns of a code one at a time without violating the girth condition. In the BF algorithm, the number of row connections is almost uniformly distributed by first selecting randomly the rows with the least number of connections. The resultant codes are either having a fixed row or fixed column weight. The structure of the row-column connections in the BF algorithm is, therefore, almost random and hence increases the complexity of the decoder [11]. In order to simplify the hardware implementation, the BF algorithm must be modified to incorporate some form of structured decoder interconnections. In the proposed algorithm, the restructuring of the interconnections is invented by splitting the rows with the group size. Such a division guarantees a concentrated node degree distribution and reduces the hardware complexity. The proposed algorithm for the construction of a new QC-LDPC (N, j, k) code is as described in the following steps;

1. For an efficient encoding the codeword’s rows are splitted into sub rows with respect to group size.

1 2( , , .. )kC b p p p= (1)

where b and p represent the information and parity check bits respectively.

2. The constraint of group’s number on row weight size persists the rows-column (RC) connections to generate variety of codes.

1

k

i=ψ = χ∑ (2)

3. Rows in the subsequent groups are placed in descending order which satisfies the least desired distance to search for each group.

Figure 1 shows the resulting matrix of the new QC-LDPC codes. The first five rows represent the first group. In these rows five unshifted identity sub-matrices corresponding to five connections of group 1 rows are formed. Rows in the first group are connected in regular order. The bottom five rows, the identity sub-matrices are shifted except the first one. The sub-matrices have size equal to the row groups. Each row group consists of a sub-matrix in each connection.

Figure 1. Matrix representation of a (25, 2, 5) code

Referring to Figure 1, the following facts are deduced;

1. For regular codes it is easy to construct the parity check matrix due to its uniform distribution of 1’s and 0’s from the column formation. 2. The RC connections cut down hardware implementation cost and complexity as compared to the connection of individual columns and rows. The complexity of directing within groups computes on the transposition employed to connect rows and columns between groups. This modifies handling, when messages are communicated between functioning nodes. 3. Adopting the Algebraic method of [13] in determining the girth upper bounds and also find the code dimensions in a graph given a base matrix for QC-LDPC codes. 4. Check nodes are used to form a cyclic graph, which is then transformed to a parity-check matrix.

240

2009 IEEE Symposium on Industrial Electronics and Applications (ISIEA 2009), October 4-6, 2009, Kuala Lumpur, Malaysia

III. RESULTS AND DISCUSSION

In this section, error performance comparison of QC-LDPC codes with other renowned codes is presented. Simulation results in Figure 2 show that new QC-LDPC codes with girth 8 and codeword length 200 outperform the LDPC codes constructed by PEG algorithm in [12] with same code rate. The PEG-LDPC codes are using smaller girth (6 in this simulation), than the proposed QC-LDPC code (girth 8). From Figure 2, at BER of 610− with block error rate of 410− , the proposed QC-LDPC code achieves 0.1dB coding gain over the PEG-LDPC codes [12] for 80 maximum numbers of iterations. Codes obtained using PEG method perfume well at short lengths with column-weight of at least three. However, PEG codes are not easily implementable due to their pseudorandom interconnections. This work also compares the performance of the new QC-LDPC codes with some other renowned best performing codes such as the short block codes presented by Mackay [4] and Hu et al. using the PEG algorithm [12]. For regular codes of block length 1008, both Mackay and PEG algorithm obtain a girth of 8. However, using the proposed method with block length 1008 we managed to obtain the girth of 10. Figure 3 shows the BER performances of LDPC regular codes with block length of 1008 and with 80 iterations. The new QC-LDPC codes perform as well as MacKay’s and almost as well as PEG codes, regardless of its constraints since it is designed as in quasi-cyclic structure. At BER of 710− , the new QC-LDPC code has an extra coding gain of about 0.1 dB with respect to PEG code. However, it performs significantly better than the MacKay code throughout. Figure 4 shows the bit error plots for the proposed large girth QC-LDPC codes with code rate of 0.4, for short to longer block lengths. For comparison, the error performance of the randomly constructed codes and the codes proposed by Huang et al. in [10] are also included in this Figure. The simulation results in Figure 4 show that the large girth QC-LDPC codes perform significantly better than the randomly constructed LDPC codes as well as the codes proposed in [10], for short to longer block lengths. The substantial BER performance gain for large girth QC-LDPC codes is obtained due to its simple encoding. In addition, the proposed codes demonstrate that a larger gain can be achieved by increasing the block length. For instance, the new QC-LDPC code with block length 11664 achieves about 0.65 dB coding gain at BER

510− with respect to Huang et al. codes with block length 11555.

2 2.5 3 3.5 4 4.5 5 5.510

-8

10-7

10-6

10-5

10-4

10-3

10-2

10-1

100

Eb/N0 (dB)

Err

or R

ate

PEG-LDPC

QC-LDPCPEG-LDPC

QC-LDPC

Bit Error Rate

Block Error Rate

Figure 2. Error rate of QC-LDPC and other renowned codes at code rate 0.4

0 0.5 1 1.5 2 2.5 3 3.5 4 4.510

-8

10-7

10-6

10-5

10-4

10-3

10-2

10-1

100

Eb/N0 (dB)

Err

or R

ate

Mackay

PEGQC-LDPC

Figure 3. BER performance comparison of QC-LDPC codes with other renowned codes

241

2009 IEEE Symposium on Industrial Electronics and Applications (ISIEA 2009), October 4-6, 2009, Kuala Lumpur, Malaysia

0.5 1 1.5 2 2.5 3 3.5 4 4.5 510

-8

10-7

10-6

10-5

10-4

10-3

10-2

10-1

100

Eb/N0 (dB)

BE

R

N=155,RandomN=155,[Huang et al.]

N=128,Proposed QC-LDPC

N=905,Random

N=905,[Huang et al.]N=686,Proposed QC-LDPC

N=11555,Random

N=11555,[Huang et al.]N=11664,Proposed QC-LDPC

Figure 4. Performance of QC-LDPC codes from short to longer block lengths

IV. CONCLUSION

This paper investigates the potential of large girth Quasi-Cyclic low density parity check codes and compares with renowned codes. Performance evaluation of the newly obtained codes has been established in term of BER and BLER for a given value of /b oE N . The newly constructed QC-LDPC codes have both theoretical as well as practical implications.

REFERENCES [1] R. G. Gallager, Low-Density Parity-Check Code. Cambridge, MA: MIT Press, 1963. [2] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Transactions on Information Theory, vol. IT-27, pp. 533–547, 1981. [3] N. Deo, Graph Theory with Applications to Engineering and Computer Science. Prentice Hall, Englewood Cliffs, NJ, 1974. [4] D. Mackay and R. Neal, “Near Shannon Limit Performance of Low Density Parity Check Codes,” Electronic Letters, vol. 32, no.18, pp. 1645-1646, 1996. [5] S. Chung, G. D. Forney, J. J. Richardson, and R. Urbanke, “On the design of low-density parity-check codes within 0.0045db of the Shannon limit,” IEEE Communication Letters, vol. 5, pp. 58–60, 2001. [6] M. P. C. Fossorier, “Quasi-cyclic low density parity check codes from circulant permutation matrices,” IEEE Transactions on Information Theory, vol. 50, no.8, pp. 1788-1794, 2004. [7] N. Miladinovic and M. Fossorier, “Systematic recursive construction of LDPC codes,” IEEE Communications Letters, vol. 8, no.5, pp. 302-304, 2004. [8] R. M. Tanner, “Minimum-distance bounds by graph analysis,” IEEE Transactions on Information Theory, Vol. 47, no.2, pp. 808–821, 2001. [9] G. Liva, W. E. Ryan, and M. Chiani, “Quasi-Cyclic Generalized LDPC Codes with Low Error Floors,” IEEE Transactions on Communications, vol. 56, no.1, pp 49-57, 2008. [10] C.M. Huang, J.F Huang, and C.C. Yang, “Construction of Quasi-Cyclic LDPC Codes from Quadratic Congruences,” IEEE Communications Letters, Vol. 12, no. 4, pp.313-315, 2008. [11] J. Campello, D. S. Modha, and S. Rajagopalan, “Designing LDPC codes using bit-filling,” Proceedings of IEEE International Conference

on Communications (ICC ’01), vol. 1, pp. 55–59, Helsinki, Finland, June 2001. [12] X.Y. Hu, E.Eleftheriou and D. M. Arnold, “Regular and irregular progressive edge-growth tanner graphs,” IEEE Transactions on Information Theory, vol. 51, no.1, pp. 386-398. 2005. [13] Y.Wang, J. S. Yedidia, and S. C. Draper, “Construction of high-girth QC-LDPC codes,” 5th International Symposium on Turbo Codes and Related Topics, pp.180-185, 2008.

242