Maximum-girth slope-based quasi-cyclic (2, k≥5) low-density parity-check codes

Access Full Text

Maximum-girth slope-based quasi-cyclic (2, k≥5) low-density parity-check codes

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Communications — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Published

A class of maximum-girth geometrically structured regular (n, 2, k≥5) (column-weight 2 and row-weight k) quasi-cyclic low-density parity-check (LDPC) codes is presented. The method is based on cylinder graphs and the slope concept. It is shown that the maximum girth achieved by these codes is 12. A low-complexity algorithm producing all such maximum-girth LDPC codes is given. The shortest constructed code has a length of 105. The minimum length n of a regular (2, k) LDPC code with girth g=12 determined by the Gallager bound has been achieved by the constructed codes. From the perspective of performance these codes outperform the column-weight 2 LDPC codes constructed by the previously reported methods. These codes can be encoded using an erasure decoding process.

Inspec keywords: cyclic codes; graph theory; computational complexity; parity check codes

Other keywords: erasure decoding process; quasicyclic code; maximum-girth slope; Gallager bound; cylinder graphs; low-density parity-check codes; LDPC code; slope concept

Subjects: Combinatorial mathematics; Codes

References

    1. 1)
      • H. Tang , J. Xu , S. Lin , K. Abdel-Ghaffar . Codes on finite geometries. IEEE Trans. Inf. Theory , 2 , 572 - 596
    2. 2)
      • http://www.cs.toronto.edu/~Radford/ldpc.software.html.
    3. 3)
      • B. Vasic , K. Pedagani , M. Ivkovic . High-rate girth-eight low-density parity-check codes on rectangular integer lattices. IEEE Trans. Commun. , 8 , 1248 - 1252
    4. 4)
      • M.E. O'sullivan . Algebraic construction of sparse matrices with large girth. IEEE Trans. Inf. Theory , 2 , 718 - 727
    5. 5)
      • H. Song , J. Liu , B.V.K.V. Kumar . Large girth cycle codes for partial response channels. IEEE Trans. Magn. , 3084 - 3086
    6. 6)
      • M.P.C. Fossorier . Quasi-cyclic low-density parity-check codes from circulant permutation matrices. IEEE Trans. Inf. Theory , 8 , 1788 - 1793
    7. 7)
      • Hocevar, D.E.: `Efficient encoding for a family of quasi-cyclic LDPC codes', Proc. IEEE Global Telecommunications Conf., 1–5 December 2003, 7, p. 3996–4000.
    8. 8)
      • D.J.C. Mackay . Good error-correcting codes based on very sparse matrices. IEEE Trans. Inf. Theory , 2 , 399 - 431
    9. 9)
      • Song, H., Liu, J., Kumar, B.V.K.V.: `Low complexity LDPC codes for magnetic recording', IEEE Globecom 2002, November 2002, Taipei, Taiwan, R.O.C..
    10. 10)
      • C. Di , D. Proietti , I.E. Teletar , T. Richardson , R. Urbanke . Finite-length analysis of low-density parity-check codes on the binary erasure channel. IEEE Trans. Inf. Theory , 1570 - 1579
    11. 11)
      • S. Myung , K. Yang , J. Kim . Quasi-cyclic LDPC codes for fast encoding. IEEE Trans. Inf. Theory , 8 , 2894 - 2901
    12. 12)
      • M. Esmaeili , M.H. Tadayon . A novel approach to generating long low-density parity-check codes using two configurations. IET Commun. , 4 , 587 - 597
    13. 13)
      • H. Pishro-Nik , N. Rahnavard , J. Ha , F. Fekri , A. Adibi . Low-density parity-check codes for volume holographic memory systems. J. Appl. Opt. , 861 - 870
    14. 14)
      • T. Richardson , M. Shokrollahi , R. Urbanke . Design of capacity-approaching irregular low-density parity-check codes. IEEE Trans. Inf. Theory , 2 , 619 - 637
    15. 15)
      • Gabidulin, E., Moinian, A., Honary, B.: `Generalized construction of Quasi-Cyclic regular LDPC codes based on permutation matrices', Proc. IEEE Int. Symp. Inform. Theory, July 2006, p. 679–683.
    16. 16)
      • Orlitsky, A., Urbanke, R., Vishwanathan, K., Zhang, J.: `Stopping sets and the girth of Tanner graphs', Proc. 2002 IEEE Int. Symp. Inf. Theory, June/July 2002, Lausanne, Switzerland, p. 2.
    17. 17)
      • Lan, L., Zeng, L.-Q., Tai, Y.Y., Lin, S., Abdel-Ghaffar, K.: `Constructions of quasi-cyclic LDPC codes for the AWGN and binary erasure channels based on finite fields and affine mappings', Proc. Int. Symp. Inform. Theory, 4–9 September 2005, p. 2285–2289.
    18. 18)
      • S. Lin , D.J. Costello . (1983) Error control coding: fundamentals and applications.
    19. 19)
      • R. Lucas , M.P.C. Fossorier , Y. Kou , S. Lin . Iterative decoding of one-step majority logic decodable codes based on belief propagation. IEEE Trans. Commun. , 6 , 931 - 937
    20. 20)
      • M.R. Tanner . A recursive approach to low complexity codes. IEEE Trans. Inf. Theory , 5 , 533 - 547
    21. 21)
      • Zhang, H., Moura, J.M.F.: `The design of structured regular LDPC codes with large girth', Proc. IEEE Globecom, December 2003, San Francisco, CA, p. 4022–4026.
    22. 22)
      • Luby, M., Mitzenmacher, M., Shokrollahi, A., Spielman, D., Stemann, V.: `Practical erasure resilient codes', Proc. 29th Annu. ACM Symp. Theory of Computing, (STOC), 1997, p. 150–159.
    23. 23)
      • R.M. Tanner , D. Sridhara , A. Sridharan , T.E. Fuja , D.J. Costello . LDPC block and convolutional codes based on circulant matrices. IEEE Trans. Inf. Theory , 12 , 2966 - 2984
    24. 24)
      • Mackay, D.J.C., Neal, R.M.: `Good codes based on very sparse matrices', Proc. 5th IMA Conf. Cryptography and Coding, 1995, 1025, LNCS, p. 100–111.
    25. 25)
      • H. Tang , J. Xu , Y. Kou , S. Lin , K. Abdel-Ghaffar . On algebraic construction of Gallager and circulant low-density parity-check codes. IEEE Trans. Inf. Theory , 6 , 1269 - 1279
    26. 26)
      • Song, H., Liu, J., Kumar, B.V.K.V.: `Low complexity LDPC codes for partial response channels', IEEE Globecom 2002, 2002, Taipei, Taiwan, 2, p. 1294–1299.
    27. 27)
      • J. Hu , T.M. Duman . Low density parity check codes over wireless relay channels. IEEE Trans. Wirel. Commun. , 9 , 3384 - 3394
    28. 28)
      • R.G. Gallager . (1963) Low-density parity-check codes.
    29. 29)
      • Y. Kou , S. Lin , M. Fossorier . Low-density parity-check codes based on finite geometries: are discovery and new results. IEEE Trans. Inf. Theory , 7 , 2711 - 2736
    30. 30)
      • B. Vasic , O. Milenkovic . Combinatorial constructions of low-density parity-check codes for iterative decoding. IEEE Trans. Inf. Theory , 6 , 1156 - 1176
    31. 31)
      • D.J.C. Mackay , R.M. Neal . Near Shannon limit performance of low-density parity-check codes. Electron. Lett. , 18 , 1645 - 1646
    32. 32)
      • L. Chen , J. Xu , I. Djurdjevic , S. Lin . Near-Shannon-limit quasi-cyclic low-density parity-check codes. IEEE Trans. Commun. , 7 , 1038 - 1042
    33. 33)
      • Zhang, H., Moura, J.M.F.: `Large-girth LDPC codes based on graphical models', Proc. IEEE SPAWC, June 2003, Rome, Italy, p. 100–104.
    34. 34)
      • Johanson, S.J., Weller, S.R.: `Quasi-cyclic LDPC codes from difference families', 3rdAusCTW, 4–5 February 2002, Canberra, Australia.
    35. 35)
      • M.R. Sadeghi , A.H. Banihashemi , D. Panario . Low density parity check lattices: construction and performance analysis. IEEE Trans. Inf. Theory , 10 , 4481 - 4495
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com_20080013
Loading

Related content

content/journals/10.1049/iet-com_20080013
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading