A class of quasi-cyclic LDPC codes over GF (2m)

2524

IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 57, NO. 9, SEPTEMBER 2009

A Class of Quasi-Cyclic LDPC Codes over GF(2𝑚 ) Christian Spagnol and William Marnane

Abstract—Low Density Parity Check (LDPC) codes over GF(2𝑚 ) are an extension of binary LDPC codes. Performances of GF(2𝑚 ) LDPC codes have been shown to be higher than binary LDPC codes, but the complexity of the encoders/decoders increases. Hence there is a substantial lack of implementations for LDPC codes over GF(2𝑚 ) codes. This paper presents a class of quasi-cyclic LDPC codes over GF(2𝑚 ). These codes can alleviate the encoding/decoding complexity without excessive loss of performances. It is shown how, from a performance point of view, such codes are better than 𝑚 times bigger binary codes and as good as 2𝑚 longer binary codes. Index Terms—Low density parity check codes, quasi-cyclic codes, permutational codes, FPGA.

I. I NTRODUCTION

I

NTEREST in non-binary LDPC codes started with the work of Gallager [1] where arbitrary-alphabet LDPC codes using modulo-q arithmetic were introduced. A generalization of binary LDPC codes and their decoding algorithm to finite fields (Galois Fields,) of GF(2𝑚 ) type have been presented in [2]. For this class of LDPC codes the non-zero entries in the parity check matrix H are elements in GF(2𝑚 ). It has been shown how, with properly chosen values for the entries, random LDPC codes over GF(2𝑚 ) out-perform binary LDPC codes and turbo codes [2]. It is also known how increasing the order of the Galois field increases the performances of the codes. A detailed analysis under iterative decoding of coset LDPC codes over GF(q) when used over arbitrary discrete-memoryless channel ( in particular for non-binary and asymmetric channels) has been presented by Bennetan et al. [3]. This letter introduces an extension over GF(2𝑚 ) of a class of quasi-cyclic binary codes. The suitability of these codes with respect to encoding and decoding is discussed. The encoding benefits, especially, are described and the building block for encoding circuits is presented. A discussion on the performance advantages of quasi-cyclic over GF(2𝑚 ) LDPC code when compared with longer binary codes is presented. Three different codes, from a very small code (𝑁 = 160) to a medium size one (𝑁 = 2408) are considered. We show how, even if the complexity grows, the use of quasicyclic GF(2𝑚 ) LDPC codes is of interest due to the error correction capabilities of these class of codes, and the fact that they are comparable to binary codes which have much higher routing complexity. Paper approved by T.-K. Truong, the Editor for Coding Theory and Techniques of the IEEE Communications Society. Manuscript received December 17, 2007; revised August 20, 2008 and January 6, 2009 The authors are with the Dept. of Electrical and Electronic Engineering, University College Cork, Ireland (e-mail: {c.spagnol, l.marnane}@ue.ucc.ie). Digital Object Identifier 10.1109/TCOMM.2009.09.070644

II. LDPC OVER GF(2𝑚 ) In this paper we focus on GF(2𝑚 ) LDPC codes applied to the binary-input AWGN channel. A major drawback of LDPC over GF(2𝑚 ) codes is their decoding complexity that increases with the order of the field. A straightforward implementation of the non-binary belief propagation decoder has a very large decoding complexity [2], but recent implementations of the algorithm greatly reduced such complexity [4], [5]. From a hardware point of view the main problem of implementing LDPC decoders is not the computational complexity but the routing complexity [6]. In general, for the GF(2𝑚 ) case the messages passing along the edges are probability weight vectors. Hence, every message passed between nodes is a vector of 2𝑚 elements that must be represented with a finite number of bits. This means a drastic increase in the size of buses connecting the computation units, thus increasing the difficulty of optimally routing these buses while keeping the area consumption to a minimum. Due to this, using codes with some regularity is even more important and carries more benefits in the case of LDPC over GF(2𝑚 ) than in the binary case. For this reason quasicyclic codes [7] are considered. The idea of using quasicyclic codes over GF(2𝑚 ) is also considered in [8]. III. Q UASI - CYCLIC LDPC C ODES A quasi-cyclic code of index 𝑡 is a linear block code C in which a cyclic shift of any codeword in C by 𝑡 positions is also a codeword. The generator matrix G for these codes can be decomposed in 𝑡 circulant matrices each of dimension [𝑝 × 𝑝]. Each of these circulant matrices can be represented by a polynomial in the field 𝐺𝐹 (2𝑚 )[𝑥]/(𝑥𝑝 + 1). These are called the generator polynomials. The parity check matrix associated with a quasi-cyclic code C is also composed of circulant matrices. Hence a parity check matrix H for a quasicyclic code, of dimension 𝑀 × 𝑁 can be constructed by assembly circulant matrices, each of dimension 𝑝 × 𝑝 with 𝑡 × 𝑝 = 𝑁 and stacking vertically 𝛼 circulant matrix with 𝛼 × 𝑝 = 𝑀. A. Implementation aspects Implementation of binary quasi-cyclic LDPC codes has been studied in many previous works. Reduced complexity encoding scheme that takes advantage of the representation of such codes has been presented in [9]. Decoding architectures that capitalize on the structure of the H matrix have been presented in [10], [11]. The advantages associated with binary quasi-cyclic LDPC codes can be carried over in the case of the GF(2𝑚 ) quasi-cyclic codes since the structure of the H and G matrices is unchanged. In the case of GF(2𝑚 ) codes

c 2009 IEEE 0090-6778/09$25.00 ⃝

SPAGNOL and MARNANE: A CLASS OF QUASI-CYCLIC LDPC CODES OVER GF(2𝑀 )

2525

trary number of generators is a combination of the architecture presented here. B. A class of binary Quasi-cyclic codes In this section a particular family of quasi-cyclic matrices [12] is presented. These codes have 𝑡 = 2𝛼 fixing the rate at 1/2. The structure of such codes is: ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ H =⎢ ⎢ ⎢ ⎢ ⎢ ⎣

hh Fig. 1. Design schematic of a 1-generator quasi-cyclic encoder, 𝑡 = 2. The message word u is loaded serially.

the decoder will have the same structure but the computational blocks will be different and the encoder will be required to compute operations in GF(2𝑚 ). We present how the scheme of the encoder for quasi-cyclic LDPC codes can be easily modified to work for quasi-cyclic codes over GF(2𝑚 ). The hardware implementation of 1-generator quasi-cyclic codes, with rate 1/2, will be discussed in this section. The hardware encoder of a rate 1/2 1-generator quasicyclic code with 𝑡 = 2 is shown in Fig. 1, where 𝑒𝑖 represents the 𝑖-th entry value of the first row of the circulant matrix that forms the G matrix. In this case the storage requirement is one 𝐾-stage shift register (for a rate 1/2 1-generator quasicyclic code we have 𝑝 = 𝐾). In general, for 1-generator quasi-cyclic code with 𝑡 > 2, (𝑡 − 1) 𝑝-stage shift registers are required. The generator matrix of the code is dense, so it can be expected that approximately half the entries in each row of the parity part of G are non-zeros entries. Therefore, the logic requirement for the encoder is 𝑝/2 multipliers over GF(2𝑚 ) and a block that compute the addition of 𝑝/2 GF(2𝑚 ) values. In general, for 1-generator quasi-cyclic dual code with 𝑡 > 2, (𝑡 − 1) 𝑝/2-input addition ports and 𝑝/2(𝑡 − 1) multipliers are required. In Fig. 1 the message word is read in serially, so it takes 𝐾 clock cycles to fully load the register and another 𝐾 clock cycles to produce the parity part of the codeword. The data input rate of a serial loaded decoder is equal to half the data output rate. An encoder where the message word is loaded into the register in parallel requires just one clock cycle to load the message word and 𝐾 clock cycles to produce the rest of the codeword. The hardware encoder for quasi-cyclic code with an arbi-

𝐻11 𝐼

0 ⋅⋅⋅ 0 𝐻21

0 .. .

0 ⋅⋅⋅ .. .. . . 𝐼 .. .. .. . . .

0

⋅⋅⋅ 0

𝐻12

𝐼

0 .. .

0 .. .

𝐻22

0

𝐼

𝐼 𝐻𝛼1

0

0 .. .

0 ⋅⋅⋅ . 𝐼 .. .. .. . . .. .. . .

0

𝐼

0

⋅ ⋅ ⋅ 0 𝐻𝛼2

0 .. . 𝐼

⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ (1) ⎥ ⎥ ⎥ ⎥ ⎦

Where 0 indicates the 𝑝 × 𝑝 zero matrix and 𝐼 the 𝑝 × 𝑝 identity matrix. It is evident that these two particular matrices are circulant matrices. The matrices 𝐻𝑖𝑐 with 𝑐 ∈ {1, 2} and 𝑖 ∈ {1, ⋅ ⋅ ⋅ , 𝛼} are circulant matrices generated by a binomial 𝑐 𝑐 𝑝𝑐𝑖 = 𝑥𝑎𝑖 + 𝑥𝑏𝑖 . Where 𝑎𝑐𝑖 and 𝑏𝑐𝑖 represent the position of the 𝑐 ones in the 𝐻𝑖 matrix. The choice of using a binomial instead of a generic polynomial, fixes the code to be a (3,6) regular LDPC code. Moreover fixing the value of 𝑝 the dimension of the code can be changed by the value of 𝛼 and vice-versa. This family of H matrices has been chosen because if the polynomials representing the circulant matrices satisfy certain conditions then the Tanner graph does not contain any cycle of length less than eight, as demonstrated in [12], thus performing better than other quasi-cyclic codes with smaller girth. It is of particular interest that these conditions can be easily met even for small codes. Hence it is possible to construct short codes suitable for implementation on devices where the resources are restricted (e.g. wireless sensors) that achieve higher performances than random codes of the same size. This particular type of codes is of interest because they provide good performance and are hardware friendly. IV. P ERFORMANCE OF QUASI - CYCLIC LDPC OVER GF(2𝑚 ) NOTE: All simulations presented here have been obtained using a log likelihood domain decoder with a maximum limit of 15 repetitions. For every SNRdB point a minimum of 20 block errors has been found. Error bars are plotted on plots in this paper. The error associated with the Frame Error rate is defined in [13]. We consider this an important aspect of the performances graph often overlooked in publications. In this section performance results for some quasicyclic LDPC code over GF(2𝑚 ) are presented. Three different codes, from a very small code (𝑁 = 160) to a medium size one (𝑁 = 2408) are investigated. We consider the class of quasi-cyclic LDPC codes presented in previous section due to their well known structure. A GF(2𝑚 ) code with the same dimension of a quasi-cyclic binary code is obtained by maintaining the structure of the H matrix but changing the binary coefficients of the polynomials that represent the circulant matrices with elements in GF(2𝑚 ). In this contribution such elements are chosen randomly using a uniform distribution.

2526

Fig. 2. Performance comparison of a N=808 r=1/2 quasi-cyclic codes GF(8) against a quasi-cyclic code of same length and two codes three times longer (𝑁 = 2424) one random and one quasi-cyclic

IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 57, NO. 9, SEPTEMBER 2009

Fig. 3. Performance comparison of a N=160 and N=480 quasi-cyclic codes GF(8) against quasi-cyclic codes of same length and two codes three times longer

A. Comparison with equivalent binary length codes In the following figures the performances of the GF(2𝑚 ) codes are compared with the binary codes from which the codes have been obtained and with codes (quasi-cyclic and randomly generated) with dimension 𝑚 times bigger. Such decision is justified by the consideration that the channel under test is binary and the codewords are transmitted using BPSK modulation for both types of codes. The output of the GF(2𝑚 ) encoder must be converted in binary before modulation and this requires 𝑚 bits for each GF(2𝑚 ) coded symbol. The total number of {−1, 1} symbols sent trough the channel is 𝑚𝑁 . Hence from a channel point of view the GF(2𝑚 ) code has equivalent binary length of a 𝑚-times longer binary code. Fig. 2 presents a comparison between a binary quasicyclic LDPC code with 𝑁 = 808 and the GF(23 ) code obtained from it. Fig. 2 also presents the comparison between the performance of the GF(23 ) with 𝑁 = 808 quasicyclic LDPC code and the performances of two (3,6) binary codes of dimension 𝑁 = 2424, one quasi-cyclic and the other random like. The latter has been generated using the optimal permutation method. We can see how the quasicyclic GF(23 ) code performs better than the original binary code and of the two binary codes of dimension three times bigger. To verify if the considerations presented for the previous code are valid for different length codes and different size fields, a really small code (𝑁 = 160) and a code of medium length (𝑁 = 2408) are considered in Fig. 3. The code with 𝑁 = 2408 is defined over GF(23 ) and the code with 𝑁 = 160 is defined over GF(24 ). The comparison of such GF(2𝑚 ) codes with binary codes with the same length and with three/four times longer codes (random and quasi-cyclic) confirms the observations made previously. Even with a small code really high gain can be achieved against the same length binary code. It can also be seen how the quasi-cyclic code over GF(24 ) of dimension 𝑁 = 160 performs close to a 𝑁 = 2408 binary quasi-cyclic code. Finally, also for the code with length 𝑁 = 2408 a considerable gain in dB can be achieved using a GF(23 ) code. The code

Fig. 4. Performance comparison of a 𝑁 = 808, 𝑟 = 1/2 quasi-cyclic codes over GF(8) versus a quasi-cyclic binary code with 𝑁 = 6464, 𝑟 = 1/2 and a randomly generated code with 𝑁 = 6464, 𝑟 = 1/2. The random code is a regular (3, 6) obtained with the optimal permutation method. The quasicyclic code is of the same structure of the smaller code.

outperform both the binary code with same length and binary codes with three times bigger dimension. An interesting characteristic of the performances presented in the previous figures is that the quasi-cyclic GF(23 ) codes don’t show any sign of the error floor that can be seen for the binary quasi-cyclic codes. B. Comparison with 2𝑚 longer codes From a computational point of view the decoding algorithm for a GF(2𝑚 ) codes is more than 2𝑚 times more demanding. For this reason a comparison of the performances of the quasicyclic code over GF(23 ) with 𝑁 = 808 versus a binary quasicyclic code of dimension 𝑁 = 6464 code obtained from the same construction is presented in Fig. 4. In the same figure the performances of a randomly generated code of length 𝑁 = 6464 can also be seen. The graph suggests that when the decoding complexity of the codes is similar the GF(23 ) code still performs slightly better than the eight times longer binary codes. This consideration might not necessarily be true for other random codes generated with more advanced methods,

SPAGNOL and MARNANE: A CLASS OF QUASI-CYCLIC LDPC CODES OVER GF(2𝑀 )

but it is an important result that increases the interest on quasicyclic over GF(2𝑚 ) codes for hardware implementations. In fact, even if the two codes have the similar computational requirement there are other aspects to consider. It has been mentioned how one major problem of implementing LDPC decoders is the complexity of routing the wires. This complexity increases with the number of edges in the graph. All codes considered are regular (3,6) codes hence the number of edges on the binary code is eight times bigger than the number of edges for GF(23 ) code since it has three times more variables nodes. From an implementation point of view this means more complex routing, memory addressing, ROM size etc. Similar reasoning regarding the memory requirement by the encoder can be done. These considerations together with the good performances of quasi-cyclic GF(23 ) codes justify the interest in such codes even if the computational complexity of the decoder for LDPC over GF(23 ) codes is higher. V. C ONCLUSION AND F UTURE W ORK In this contribution a new family of GF(2𝑚 ) LDPC codes, obtained from binary quasi-cyclic LDPC, has been introduced. It has been showed how the quasi-cyclic LDPC over GF(2𝑚 ) codes outperform binary codes up to 2𝑚 times longer. Moreover we presented how the encoder for binary quasi-cyclic LDPC codes can be modified to encode quasicyclic LDPC over GF(2𝑚 ) codes. In this study the entries of the H matrix have been chosen randomly and the results obtained are encouraging. Of interest for future studies is to investigates methods to optimize such choice. The possibility of increasing the performances of the codes just by picking optimal values for the coefficients is of great interest because this will allow to obtain better codes without increasing the overall complexity. Methods that will be investigated are optimal row-column weight, maximal entropy and application of the density propagation algorithm.

2527

ACKNOWLEDGMENTS Special thanks to the I.R.C.S.E.T. that supported this project. The authors would like to thank the Boole Centre for Research in Informatics and the Irish Centre for High-End Computing for the use of their computer clusters. Moreover we would like to thank M. O’Sullivan for providing opinions and assistance during the work. R EFERENCES [1] R. Gallager, “Low density parity check codes,” 1963, Ph.D. thesis, MIT Press, Cambridge, MA. [2] M. Davey and D. MacKay, “Low-density parity-check codes over GF(q)," IEEE Commun. Lett., vol. 2, no. 6, pp. 165-167, 1998. [3] A. Bennatan and D. Burshtein, “Design and analysis of nonbinary LDPC codes for arbitrary discrete-memoryless channels," IEEE Trans. Inform. Theory, vol. 52, no. 2, pp. 549-583, Feb. 2006. [4] C. Spagnol, E. Popovici, and W. Marnane, “Hardware implementation of GF(2𝑚 ) LDPC decoders," to appear in IEEE Trans. Circuit Systems I. [5] A. Voicila, D. Declercq, F. Verdier, M. Fossorier, and P. Urard, “Lowcomplexity, low-memory EMS algorithm for non-binary LDPC codes," in Proc. IEEE International Conf. Commun. ICC, pp. 671-676, 2007. [6] C. Blanksby and A. J. Howland, “A 690-mw 1-Gb/s 1024-b, rate-1/2 low-density parity-check code decoder," IEEE J. Solid-State Circuits, vol. 37, no. 3, pp. 404-412, 2002. [7] R. Townsend and J. E. J. Weldon, “Self-orthogonal quasi-cyclic codes," IEEE Trans. Inform. Theory, vol. 13, no. 2, pp. 183-195, 1967. [8] L. Zeng, L. Lan, Y. Y. Tai, B. Zhou, S. Lin, and K. Abdel-Ghaffar, “Construction of nonbinary cyclic, quasi-cyclic and regular LDPC codes: a finite geometry approach," IEEE Trans. Commun., vol. 56, no. 3, pp. 378-387, 2008. [9] L. C. Zongwang Li, L. Zeng, S. Lin, and W. H. Fong, “Efficient encoding of quasi-cyclic low density parity check codes," IEEE Trans. Commun., vol. 54, no. 1, pp. 71-81, 2006. [10] C. Spagnol, E. Popovici, and W. Marnane, “Reduced complexity, FPGA implementation of quasi-cyclic LDPC decoder," in Proc. IEEE European Conf. Circuit Theory Design (ECCTD), vol. 1, pp. 289-292, 2005. [11] Y. Chen and K. K. Parhi, “Overlapped message passing for quasi-cyclic low-density parity check codes," IEEE Trans. Circuits Syst. I, vol. 51, no. 6, pp. 1106-1113, 2004. [12] M. Rossi and M. Sala, “On a class of quasi-cyclic codes," in Proc. Effective Methods Algebraic Geometry Conf. (MEGA), 2005. [13] D. MacKay, S. Wilson, and M. Davey, “Comparison of constructions of irregular Gallager codes," IEEE Trans. Commun., vol. 47, no. 10, pp. 1449-1454, 1998.