• Vol 10, No 5 (2019)
  • Electrical, Electronics, and Computer Engineering

A New Method for Building Low-Density-Parity-Check Codes

Tehami Mohammed Amine, Djebbari Ali

Corresponding email: chahoub_88@yahoo.com


Cite this article as:
Amine, T.M., Ali, D. 2019. A New Method for Building Low-Density-Parity-Check Codes. International Journal of Technology. Volume 10(5), pp. 953-960
30
Downloads
Tehami Mohammed Amine Telecommunications and Digital Signal Processing Laboratory, Djillali liabes University of Sidi Bel Abbes, Algeria
Djebbari Ali Telecommunications and Digital Signal Processing Laboratory, Djillali liabes University of Sidi Bel Abbes, Algeria
Email to Corresponding Author

Abstract
image

This paper proposes a new method for building low-density-parity-check codes, exempt of cycle of length 4, based on a circulant permutation matrix, which needs very little memory for storage it in the encoder and a dual diagonal structure is applied to guarantee that parity check bits can be recursively computed with linear calculation complexity. The Bit Error Rate performance of the new low-density-parity-check codes was compared to the uncoded bi-phase-shift-keying over additive-white-gaussian-noise channel. This simulation shows that the proposed codes are very efficient over additive-white-gaussian-noise. The proposed codes ensure a very low encoding complexity and reduce the memory storage required for the parity-check matrix, which can be more easily built than others codes used in channel coding.

Circulant permutation matrix; Dual-diagonal matrix; Girth; Low-density-parity-check codes; Parity-check matrix

Introduction

Because of their prodigious performance, low-density-parity-check (LDPC) codes are now considered optimal (Gallager, 1962). These codes are a part of linear block codes which have acquired considerable importance in error correcting performances (Yahya et al., 2009). LDPC codes can be presented by specific parity check matrix H that includes a high density of 0’-s and a low density of 1’-s (Mackay, 1999). The Tanner graph (Tanner, 1981) is a bipartite graph comprising two groups of nodes: the variable nodes and check nodes. Variable nodes depicting columns and rows are represented by check nodes and connections between these two sets are known as edges (Tanner, 1981; Juwono et al., 2013). In the Tanner graph, a cycle is defined as a path which starts and ends at the same node, if the graph contains a cycle; its minimum length is known as ‘girth’ (Tanner, 1981). Cycles especially those of length 4 decrease the bit-error-rate (BER) performance of LDPC codes, because of their impact on the independence of extrinsic information exchanged in the decoding process (Johnson & Weller, 2001). Gallager codes are classified: as regular if the weight of columns and rows (i.e. density of 1’s) is constant and as irregular if column weight and row weight are variable (Yahya et al., 2009).

The construction of these codes is of two types; the first is random construction that is flexible in design and construction (Mackay, 1999). The parity-check matrix is a superposition and/or concatenation of sub-matrices and this construction has significant drawbacks in term of the stocking and accessing a large parity-check matrix. As random building does not guarantee small cycle lengths, a second form of construction was developed; this is known as deterministic construction (Moura el al., 2004; Shin et al., 2014).

In this paper, we depict a particular category of LDPC codes, excluding cycles of length 4, which can be linearly coded by matrix H. The parity check matrix is divided into two sections: the first, which matches to the parity bits, is a dual-diagonal structure (Guolei & Dong, 2010) and the second, which matches the information bits, is a quasi-cyclic structure. For that reason, this new LDPC code is classified as irregular code.

This paper is organized as follows. Section 2 discusses the construction of the new LDPC code based on a quasi-cyclic and a dual diagonal matrix. In section 3, we propose a deterministic rule for constructing parity-check matrix with various rates. Section 4 describes the LDPC reduced-complexity encoding method, and section 5 discusses decoding complexity. Section 6 specifies the advantages of the proposed method, followed by conclusions in Section 7.

Conclusion

To address quality of reception and implementation constraints, LDPC code must be constructed with a low error floor, linear encoding and less complex decoding. This paper proposes a new method for constructing parity-check matrix that include girths of length 4, for different rates. Memory requirements are significantly reduced by the use of the quasi-cyclic matrices and dual- diagonal, which reduce encoding complexity.

References

3GPP2, 2008. C.S0084-001-0 v3.0, Physical Layer for Ultra Mobile Broadband (UMB) Air Interface Specification. Version 3.0.

Asvial , M., Dewandaru, G., Rachman, A.N., 2015. Modification of Round Robin and Best CQI Scheduling Method for 3GPP LTE Downlink. International Journal of Technology, Volume 6(2), pp. 130–138

Berrou, C., 2010. Code and Turbo-code. Bretagne: ENST Bretagne Edition

Divsalar, D., Dolinar, S., Jones, C.R., Andrews, K., 2009. Capacity-approaching Protograph Codes. IEEE Journal on Selected Areas in Communications, Volume 27(6), pp. 876–888

Fossorier, M.P.C., 2004. Quasi-cyclic Low-density Parity-check Codes from Circulant Permutation Matrices. IEEE Transaction on Information Theory, Volume 50(8), pp. 1788?1793

Gallager, R.G., 1962. Low-density Parity-check Codes. IRE Transaction on Information Theory, Volume 4, pp. 21–28

Guolei, Q., Dong, Z., 2010. Design of Structured LDPC Codes with Quasi-Cyclic and Rotation Architecture. In: IEEE Third International Conference on Advanced Computer Theory and Engineering, Chengdu, China, pp. 655–657

Johnson, S.J., Weller, S.R., 2001. Regular Low Density Parity Check Codes from Combinatorial Design. In: IEEE Information Theory Workshop, Cairns, Queensland, Australia, pp. 90–92

Juwono, F.H., Triprasetyo, Y., Gunawan, D., 2013. Exploiting LDPC Codes for Improving the Performance of Clipped-OFDM System. International Journal of Technology, Volume 4(1), pp. 93–99

Lin, C.Y., Wei, C.C., Ku, M.K., 2008. Efficient Encoding for Dual Diagonal Structured LDPC Codes based on Parity Bit Prediction and Correction. In: IEEE Asia Pacific Conference on Circuits and Systems, Macao, China, pp. 1648–1651

Liu, K., Fei, Z., Kuang, J., Li, X., 2009. A Novel Algorithm for Removing Cycles in Quasi-Cyclic LDPC Codes. In: IEEE 20th International Symposium on Personal, Indoor and Mobile Radio Communications, Tokyo, Japan, pp. 1054–1058

MacKay, D., 1999. Good Codes based on Very Sparse Matrices. IEEE Transactions on Information Theory, Volume 45(2), pp. 399–431

Malema, G., Liebelt, M., 2007. Quasi-Cyclic LDPC Codes of Column-weight Two using a Search Algorithm. EURASIP Journal on Applied Signal Processing, Volume 1(1), pp. 1–8

Mao, Y., Banihasherni, A.H., 2001. A Heuristic Search for Good Low-density Parity-check Codes at Short Block Lengths. In: IEEE International Conference on Communication, Helsinki, Finland, pp. 41–44

Moura, J.M.F., Lu, J., Zhang, H., 2004. Structured Low-density Parity-check Codes. IEEE Signal Processing Magazine, Volume 21(1), pp. 42–55

O’Sullivan, M.E., 2006. Algebraic Construction of Sparse Matrices with Large Girth. IEEE Transaction on Information Theory, Volume 52(2), pp. 718–727

Ping, L., Leung, W.K., Phamdo, N., 1999. Low Density Parity Check Codes with Semi-random Parity Check Matrix. Electronic Letter, Volume 35(1), pp. 38–39

Richardson, T., Kudekar, S., 2018. Design of Low-density Parity Check Codes for 5G New Radio. IEEE Communications Magazine, Volume 56(3), pp. 28–34

Shin, B., Park, H., Hong, S., No, J.S., Kim, S.H., 2014. Quasi-cyclic LDPC Codes using Overlapping Matrices and Their Layered Decoders. AEU-International Journal of Electronics and Communications, Volume 68(5), pp. 379–383

Song, H., Liu, J., Kumar, B.V.K.V., 2002. Low Complexity LDPC Codes for Partial Response Channels. In: IEEE Proceedings on Global Telecommunication Conference, Taipei, Taiwan, pp. 1294–1299

Song, H., Liu, J., Kumar, B.V.K.V., 2004. Large Girth Cycle Codes for Partial Response Channels.  IEEE Transaction on Magnetics, Volume 40(4), pp. 3084–3086

Suryanegara, M., Miyazaki, K., 2012. Towards 4G Mobile Technology: Identifying Windows of Opportunity for a Developing Country. International Journal of Technology, Volume 3(1), pp. 85–92

Tanner, R., 1981. A Recursive Approach to Low Complexity Codes. IEEE Transaction on Information Theory, Volume 27(5), pp. 533–547

Yahya, A., Sidek, O., Salleh, M.F.M., Ghani, F., 2009. A New Quasi-Cyclic Low Density Parity Check Codes. In: IEEE Symposium on Industrial Electronics & Applications (ISIEA), Kuala Lumpur, Malaysia, Volume 1, pp. 239–242