Recursive method for generating column weight 3 low-density parity-check codes based on three-partite graphs

Morteza Esmaeili; Mahnaz Ahmadi; T. Aaron Gulliver

Recursive method for generating column weight 3 low-density parity-check codes based on three-partite graphs

View Fulltext

Author(s): Morteza Esmaeili ^{1, 2, 3} ; Mahnaz Ahmadi ¹ ; T. Aaron Gulliver ²
- Affiliations: 1: Department of Mathematical Sciences, Isfahan University of Technology, 84156-83111 Isfahan, Iran;
  2: Department of Electrical and Computer Engineering, University of Victoria, Victoria, BC, Canada;
  3: School of Mathematics, Institute for Research in Fundamental Sciences, Isfahan, Iran
Source: Volume 8, Issue 17, 27 November 2014, p. 3202 – 3213
DOI: 10.1049/iet-com.2014.0235 , Print ISSN 1751-8628, Online ISSN 1751-8636

Received 12/03/2014, Accepted 26/07/2014, Revised 17/07/2014, Published 01/10/2014

In this study, a method is presented to construct column weight 3 (CW3) low-density parity-check (LDPC) codes using three-partite graphs. Let G_b be a bipartite graph and N_g be the set of all minimum length cycles in G_b . Using G_b and N_g , a three-partite graph denoted G(G_b , N_g ), or simply G_t , is formed. Let T be the set of length 3 cycles in G_t and T^a be the set of three element subsets of vertices in G_t such that each of these subsets form a subgraph with no edges in G_t and has precisely one element in each section of G_t . Furthermore, let H be the binary matrix in which the set of rows represent the set of vertices of G_t , the columns represent the elements of V:= T ∪ T^a , and h_ij = 1 if and only if the ith vertex of G_t belongs to the jth three element set in V. Then H is a CW3 binary matrix. Using the Tanner graph representing H , a recursive construction for CW3 LDPC codes is provided. Applying a simple restriction on T and T^a , codes free of length 4 cycles are generated. Euclidean and finite geometry codes are used as the base codes for generating new CW3 LDPC codes. Results are presented which show that these new codes perform well in an additive white Gaussian noise (AWGN) channel with the iterative sum-product decoding algorithm.

References

1. 1)
  - D. Declercq , M. Fossorier . Decoding algorithms for nonbinary LDPC codes over GF(q). IEEE Trans. Commun. , 4 , 633 - 643
2. 2)
  - 14. Fan, J., Xiao, Y.: ‘A method of counting the number of cycles in LDPC codes’. Proc. Int. Conf. Signal Processing, Beijing, China, November 2006, pp. 1–4.
3. 3)
  - Y. Kou , S. Lin , M. Fossorier . Low-density parity-check codes based on finite geometries: a rediscovery and new results. IEEE Trans. Inf. Theory , 2711 - 2736
4. 4)
  - 16. Halford, T.R., Chugg, K.M.: ‘An algorithm for counting short cycles in bipartite graphs’, IEEE Trans. Inf. Theory, 2006, 52, (1), pp. 287–292 (doi: 10.1109/TIT.2005.860472).
5. 5)
  - 17. Esmaeili, M., Gholami, M.: ‘Structured qc LDPC codes with girth 18 and column-weight J ≥ 3’, Int. J. Electron. Commun. (AEUE), 2010, 64, pp. 202–217 (doi: 10.1016/j.aeue.2008.11.013).
6. 6)
  - L. Lan , L. Zeng , Y.Y. Tai , L. Chan , S. Lin , K. Abdel-Ghaffar . Construction of quasi-cyclic LDPC codes for AWGN and binary erasure channels: a finite field approach. IEEE Trans. Inf. Theory , 7 , 2429 - 2458
7. 7)
  - M. Fossorier . Quasi-cyclic low-density parity-check codes from circulant permutation matrices. IEEE Trans. Inf. Theory , 8 , 1788 - 1793
8. 8)
  - T. Richardson , R. Urbanke . The capacity of low-density parity check codes under message-passing decoding. IEEE Trans. Inf. Theory , 599 - 618
9. 9)
  - 31. Zhou, B., Kang, J., Song, S., Lin, S., Abdel-Ghaffar, K.A.S., Xu, M.: ‘Construction of non-binary QC-LDPC codes by arrays and array dispersions’, IEEE Trans. Commun., 2009, 57, (6), pp. 1652–1662 (doi: 10.1109/TCOMM.2009.06.070313).
10. 10)
  - U. Wachsmann , R.F.H. Fischer , J.B. Huber . Multilevel codes: theoretical concepts and practical design rules. IEEE Trans. Inf. Theory , 1361 - 1391
11. 11)
  - 32. Chen, C., Bai, B., Li, Z., Yang, X., Li, L.: ‘Nonbinary cyclic LDPC codes derived from idempotents and modular Golomb rulers’, IEEE Trans. Commun., 2012, 60, (3), pp. 661–668 (doi: 10.1109/TCOMM.2012.013112.110133).
12. 12)
  - S.-Y. Chung , G.D. Forney , T.J. Richardson , R.L. Urbanke . On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit. IEEE Commun. Lett. , 2 , 58 - 60
13. 13)
  - 9. Esmaeili, M., Tadayon, M.H.: ‘A novel approach to generating long LDPC codes using two configurations’, IET Commun., 2008, 2, (4), pp. 587–597 (doi: 10.1049/iet-com:20070324).
14. 14)
  - 18. Salahshouri, Z.: ‘Construction of LDPC codes based on finite fields and algebraic structures’. MS Thesis, Faculty of Applied Sciences, Malek Ashtar University of Technology, Iran, 2011.
15. 15)
  - R. Gallager . Low-density parity-check codes. IRE Trans. Inf. Theory , 21 - 28
16. 16)
  - 28. Neal, R.M.: ‘Software for LDPC Codes’ (Dept. of Statistics and Department of Computer Science, University of Toronto), http://www.cs.toronto.edu/~radford/ftp/LDPC-2006-02-08/index.html.
17. 17)
  - H. Tang , J. Xu , S. Lin , K. Abdel-Ghaffar . Codes on finite geometries. IEEE Trans. Inf. Theory , 2 , 572 - 596
18. 18)
  - 15. Chen, R., Huang, H., Xiao, G.: ‘Relation between parity-check matrices and cycles of associated Tanner graphs’, IEEE Commun. Lett., 2007, 11, (8), pp. 674–676 (doi: 10.1109/LCOMM.2007.07613).
19. 19)
  - 30. Zhou, B., Kang, J., Tai, Y.Y., Lin, S., Ding, Z.: ‘High performance non-binary QC-LDPC codes on Euclidean geometries’, IEEE Trans. Commun., 2009, 57, (5), pp. 1298–1311 (doi: 10.1109/TCOMM.2009.05.070240).
20. 20)
  - 29. Song, S., Zhou, B., Lin, S., Abdel-Ghaffar, K.A.S.: ‘A unified approach to the construction of binary and nonbinary QC-LDPC codes based on finite fields’, IEEE Trans. Commun., 2009, 57, (1), pp. 84–93 (doi: 10.1109/TCOMM.2009.0901.060129).
21. 21)
  - 3. Kang, J., Huang, Q., Zhang, L., Zhou, B., Lin, S.: ‘Quasi-cyclic codes: an algebraic construction’, IEEE Trans. Commun., 2010, 58, pp. 1383–1396 (doi: 10.1109/TCOMM.2010.05.090211).
22. 22)
  - T.J. Richardson , M.A. Shokrollahi , R.L. Urbanke . Design of capacity-approaching irregular low-density parity-check codes. IEEE Trans. Inf. Theory , 619 - 637
23. 23)
  - 19. Ahmadi, M.: ‘Graph based regular LDPC codes’. MS Thesis, Faculty of Applied Sciences, Malek Ashtar University of Technology, Iran, 2011.
24. 24)
  - 12. Tao, X., Zheng, L., Liu, W., Liu, D.: ‘Recursive design of high girth (2, k) LDPC codes from (k, k) LDPC codes’, IEEE Commun. Lett., 2011, 15, (1), pp. 70–72 (doi: 10.1109/LCOMM.2010.112310.101867).
25. 25)
  - 11. Malema, G.A., Liebelt, M.: ‘High girth column-weight-two LDPC codes based on distance graphs’, Eurasip J. Wirel. Commun. Networking, 2007, 2007, Article ID 48158, doi: 10.1155/2007/48158.
26. 26)
  - 27. Zhou, B., Zhang, L., Huang, Q., Lin, S., Xu, M.: ‘Constructions of high performance non-binary QC-LDPC codes’. Proc. IEEE Inf. Theory Workshop, Porto, Portugal, May 2008, pp. 71–75.
27. 27)
  - G. Ungerboeck . Channel coding with multilevel/phase signals. IEEE Trans. Inf. Theory , 55 - 67
28. 28)
  - R. Tanner . A recursive approach to low complexity codes. IEEE Trans. Inf. Theory , 5 , 533 - 547
29. 29)
  - D.J.C. MacKay . Good error-correcting codes based on very sparse matrices. IEEE Trans. Inf. Theory , 2 , 399 - 431
30. 30)
  - D.J.C. MacKay , R.M. Neal . Near Shannon limit performance of low density parity check codes. Electron. Lett. , 8 , 1645 - 1646
31. 31)
  - E. Zehavi . 8-PSK trellis codes for a Rayleigh channel. IEEE Trans. Commun. , 5 , 873 - 884
32. 32)
  - H. Imai , S. Hirakawa . A new multilevel coding method using error-correcting codes. IEEE Trans. Inf. Theory , 371 - 377

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Recursive method for generating column weight 3 low-density parity-check codes based on three-partite graphs

References

Related content