Maximum-girth slope-based quasi-cyclic (2, k≥5) low-density parity-check codes
Maximum-girth slope-based quasi-cyclic (2, k≥5) low-density parity-check codes
- Author(s): M. Esmaeili and M. Gholami
- DOI: 10.1049/iet-com:20080013
For access to this article, please select a purchase option:
Buy article PDF
Buy Knowledge Pack
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.
Thank you
Your recommendation has been sent to your librarian.
- Author(s): M. Esmaeili 1 and M. Gholami 1
-
-
View affiliations
-
Affiliations:
1: Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, Iran
-
Affiliations:
1: Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, Iran
- Source:
Volume 2, Issue 10,
November 2008,
p.
1251 – 1262
DOI: 10.1049/iet-com:20080013 , Print ISSN 1751-8628, Online ISSN 1751-8636
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:
Subjects: Combinatorial mathematics; Codes
References
-
-
1)
- H. Tang , J. Xu , S. Lin , K. Abdel-Ghaffar . Codes on finite geometries. IEEE Trans. Inf. Theory , 2 , 572 - 596
-
2)
- http://www.cs.toronto.edu/~Radford/ldpc.software.html.
-
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)
- M.E. O'sullivan . Algebraic construction of sparse matrices with large girth. IEEE Trans. Inf. Theory , 2 , 718 - 727
-
5)
- H. Song , J. Liu , B.V.K.V. Kumar . Large girth cycle codes for partial response channels. IEEE Trans. Magn. , 3084 - 3086
-
6)
- M.P.C. Fossorier . Quasi-cyclic low-density parity-check codes from circulant permutation matrices. IEEE Trans. Inf. Theory , 8 , 1788 - 1793
-
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)
- D.J.C. Mackay . Good error-correcting codes based on very sparse matrices. IEEE Trans. Inf. Theory , 2 , 399 - 431
-
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)
- 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)
- S. Myung , K. Yang , J. Kim . Quasi-cyclic LDPC codes for fast encoding. IEEE Trans. Inf. Theory , 8 , 2894 - 2901
-
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)
- 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)
- T. Richardson , M. Shokrollahi , R. Urbanke . Design of capacity-approaching irregular low-density parity-check codes. IEEE Trans. Inf. Theory , 2 , 619 - 637
-
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)
- 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)
- 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)
- S. Lin , D.J. Costello . (1983) Error control coding: fundamentals and applications.
-
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)
- M.R. Tanner . A recursive approach to low complexity codes. IEEE Trans. Inf. Theory , 5 , 533 - 547
-
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)
- 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)
- 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)
- 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)
- 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)
- 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)
- J. Hu , T.M. Duman . Low density parity check codes over wireless relay channels. IEEE Trans. Wirel. Commun. , 9 , 3384 - 3394
-
28)
- R.G. Gallager . (1963) Low-density parity-check codes.
-
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)
- B. Vasic , O. Milenkovic . Combinatorial constructions of low-density parity-check codes for iterative decoding. IEEE Trans. Inf. Theory , 6 , 1156 - 1176
-
31)
- D.J.C. Mackay , R.M. Neal . Near Shannon limit performance of low-density parity-check codes. Electron. Lett. , 18 , 1645 - 1646
-
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)
- 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)
- Johanson, S.J., Weller, S.R.: `Quasi-cyclic LDPC codes from difference families', 3rdAusCTW, 4–5 February 2002, Canberra, Australia.
-
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
-
1)