IEEE International Symposium on Information Theory (ISIT)

New low-density parity-check codes with large girth based on hypergraphs

Irina E. Bocharova, Florian Hug, Rolf Johannesson, Boris D. Kudryashov, Roman V. Satyukov

Published Jun 1, 2010• 8 citations

Abstract

The relation between low-density parity-check (LDPC) codes and hypergraphs supports searching for powerful LDPC codes based on hypergraphs. On the other hand, coding theory methods can be used in searching for hypergraphs with large girth. Moreover, compact representations of hypergraphs based on convolutional codes can be found. Algorithms for iteratively constructing LDPC codes with large girth and for determining their minimum distance are introduced. New quasi-cyclic (QC) LDPC codes are presented, some having both optimal girth and optimal minimum distance.

DOI: 10.1109/isit.2010.5513639

Related papers

Searching for Voltage Graph-Based LDPC Tailbiting Codes With Large Girth

Irina E. Bocharova, Florian Hug, Rolf Johannesson +2 more

arXiv:1108.0840IEEE Transactions on Information TheoryNov 18, 201180 citations

Some voltage graph-based LDPC tailbiting codes with large girth

Irina E. Bocharova, Florian Hug, Rolf Johannesson +2 more

The relation between the parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and the biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Algorithms for searching iteratively for LDPC block codes with large girth are presented and constructions based on Steiner Triple Systems and short QC block codes are introduced, leading to new QC regular LDPC block codes with girth up to 24.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20118 citations

On the Construction of Multitype Quasi-Cyclic Low-Density Parity-Check Codes With Different Girth and Length

Farzaneh Abedi, Mohammad Gholami

IEEE AccessJan 1, 20212 citations

A necessary and sufficient condition for determining the girth of quasi-cyclic LDPC codes

Xiaofu Wu, Xiaohu You, Chunming Zhao

The parity-check matrix of a quasi-cyclic low- density parity-check (QC-LDPC) code can be compactly represented by a polynomial parity-check matrix. By using this compact representation, we derive a necessary and sufficient condition for determining the girth of QC-LDPC codes in a systematic way. The new condition avoids an explicit enumeration of cycles for determining the girth of codes, and thus can be well employed to generate QC-LDPC codes with large girth.

IEEE Transactions on CommunicationsJun 1, 200829 citations

Quasi-Cyclic Low Density Parity Check Codes

M.P.C. Fossorier

Jan 1, 20030 citations

A Compact Construction for LDPC Codes using Permutation Polynomials

O.Y. Takeshita

IEEE International Symposium on Information Theory (ISIT)Jul 1, 200612 citations

IEEE International Symposium on Information Theory (ISIT)

New low-density parity-check codes with large girth based on hypergraphs

Irina E. Bocharova, Florian Hug, Rolf Johannesson, Boris D. Kudryashov, Roman V. Satyukov

Published Jun 1, 2010• 8 citations

Publisher

Abstract

DOI: 10.1109/isit.2010.5513639

Related papers

Searching for Voltage Graph-Based LDPC Tailbiting Codes With Large Girth

Irina E. Bocharova, Florian Hug, Rolf Johannesson +2 more

The relation between parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Using the principle of tailbiting, compact representations of bipartite graphs based on convolutional codes can be found. Bounds on the girth and the minimum distance of LDPC block codes constructed in such a way are discussed. Algorithms for searching iteratively for LDPC block codes with large girth and for determining their minimum distance are presented. Constructions based on all-one matrices, Steiner Triple Systems, and QC block codes are introduced. Finally, new QC regular LDPC block codes with girth up to 24 are given.The relation between parity-check matrices of quasi-cyclic (QC) low-density parity-check (LDPC) codes and biadjacency matrices of bipartite graphs supports searching for powerful LDPC block codes. Using the principle of tailbiting, compact representations of bipartite graphs based on convolutional codes can be found. Bounds on the girth and the minimum distance of LDPC block codes constructed in such a way are discussed. Algorithms for searching iteratively for LDPC block codes with large girth and for determining their minimum distance are presented. Constructions based on all-one matrices, Steiner Triple Systems, and QC block codes are introduced. Finally, new QC regular LDPC block codes with girth up to 24 are given.

arXiv:1108.0840IEEE Transactions on Information TheoryNov 18, 201180 citations

Some voltage graph-based LDPC tailbiting codes with large girth

Irina E. Bocharova, Florian Hug, Rolf Johannesson +2 more

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20118 citations

On the Construction of Multitype Quasi-Cyclic Low-Density Parity-Check Codes With Different Girth and Length

Farzaneh Abedi, Mohammad Gholami

Multitype quasi-cyclic (QC) low-density parity-check (LDPC) codes are a class of protograph LDPC codes lifted cyclically from protographs with multiple edges, represented by two weight and slope matrices. For a given weight-matrix, an approach is proposed to find the maximum-achievable girth $g_{\max }$ of the corresponding multitype QC-LDPC codes by some inevitable chains having less complexity than the existing methods. This advantage leads to some new patterns of the weight matrices such that the corresponding codes have some improvements in terms of the maximum-achievable girths or the minimum-distance upper-bounds. In continue, for a given weight-matrix with maximum-achievable girth $g_{\max }$ , some slope-matrices are constructed by a depth-first search algorithm for which the corresponding multitype QC-LDPC codes with even girth $g$ , $g\le g_{\max }$ , have smaller lengths, higher rates, or larger minimum-distances than the state-of-the-art achievements. Simulation results show that the constructed codes have some error-rate advantages than PEG, random-like, CCSDS, and 802.11n/ac IEEE standard LDPC codes.Multitype quasi-cyclic (QC) low-density parity-check (LDPC) codes are a class of protograph LDPC codes lifted cyclically from protographs with multiple edges, represented by two weight and slope matrices. For a given weight-matrix, an approach is proposed to find the maximum-achievable girth$g_{\max }$of the corresponding multitype QC-LDPC codes by some inevitable chains having less complexity than the existing methods. This advantage leads to some new patterns of the weight matrices such that the corresponding codes have some improvements in terms of the maximum-achievable girths or the minimum-distance upper-bounds. In continue, for a given weight-matrix with maximum-achievable girth$g_{\max }$, some slope-matrices are constructed by a depth-first search algorithm for which the corresponding multitype QC-LDPC codes with even girth$g$,$g\le g_{\max }$, have smaller lengths, higher rates, or larger minimum-distances than the state-of-the-art achievements. Simulation results show that the constructed codes have some error-rate advantages than PEG, random-like, CCSDS, and 802.11n/ac IEEE standard LDPC codes.

IEEE AccessJan 1, 20212 citations

A necessary and sufficient condition for determining the girth of quasi-cyclic LDPC codes

Xiaofu Wu, Xiaohu You, Chunming Zhao

IEEE Transactions on CommunicationsJun 1, 200829 citations

Quasi-Cyclic Low Density Parity Check Codes

M.P.C. Fossorier

In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than , and a relatively mild necessary and sufficient condition for the code to have a girth of or is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than , and a relatively mild necessary and sufficient condition for the code to have a girth of or is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum distance or the number of redundant check sums should be considered. To this end, a necessary condition for the codes investigated to reach their maximum possible minimum Hamming distance is proposed.

Jan 1, 20030 citations

A Compact Construction for LDPC Codes using Permutation Polynomials

O.Y. Takeshita

A construction is proposed for low density parity check codes using quadratic permutation polynomials over finite integer rings. Graph isomorphisms and automorphisms are identified and used in an efficient search for good codes. Graphs with girth as large as 12 were found. Upper bounds on the minimum Hamming distance are found algorithmically. The bounds indicate that the minimum distance grows with block length. One of the new codes has a similar error performance as the best known PEG LDPC code. Finally, the new codes are quasi-cyclicA construction is proposed for low density parity check codes using quadratic permutation polynomials over finite integer rings. Graph isomorphisms and automorphisms are identified and used in an efficient search for good codes. Graphs with girth as large as 12 were found. Upper bounds on the minimum Hamming distance are found algorithmically. The bounds indicate that the minimum distance grows with block length. One of the new codes has a similar error performance as the best known PEG LDPC code. Finally, the new codes are quasi-cyclic

IEEE International Symposium on Information Theory (ISIT)Jul 1, 200612 citations

g_{\max }

of the corresponding multitype QC-LDPC codes by some inevitable chains having less complexity than the existing methods. This advantage leads to some new patterns of the weight matrices such that the corresponding codes have some improvements in terms of the maximum-achievable girths or the minimum-distance upper-bounds. In continue, for a given weight-matrix with maximum-achievable girth

g_{\max }

, some slope-matrices are constructed by a depth-first search algorithm for which the corresponding multitype QC-LDPC codes with even girth

g

g\le g_{\max }

, have smaller lengths, higher rates, or larger minimum-distances than the state-of-the-art achievements. Simulation results show that the constructed codes have some error-rate advantages than PEG, random-like, CCSDS, and 802.11n/ac IEEE standard LDPC codes.