Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1709.00825

Lower bounds on the lifting degree of single-edge and multiple-edge QC-LDPC codes by difference matrices

Farzane Amirzade, Mohammad‐Reza Sadeghi

Published Sep 4, 2017• 2 citations
arXivHTMLPDF

Abstract

In this paper, we define two matrices named as "difference matrices", denoted by $D$ and $DD$ which significantly contribute to achieve regular single-edge QC-LDPC codes with the shortest length and the certain girth as well as regular and irregular multiple-edge QC-LDPC codes. Making use of these matrices, we obtain necessary and sufficient conditions to have single-edge $(m,n)$-regular QC-LDPC codes with girth 6, 10 and 12. Additionally, for girth 6, we achieve all non-isomorphic codes with the minimum lifting degree, $N$, for $m=4$ and $5\leq n\leq 11$, and present an exponent matrix for each minimum distance. For girth 10, we provide a lower bound on the lifting degree which is tighter than the existing bound. More important, for an exponent matrix whose first row and first column are all-zero, we demonstrate that the non-existence of 8-cycles proves the non-existence of 6-cycles related to the first row of the exponent matrix too. All non-isomorphic QC-LDPC codes with girth 10 and $n=5,6$ whose numbers are more than those presented in the literature are provided. For $n=7,8$ we decrease the lifting degrees from 159 and 219 to 145 and 211, repectively. For girth 12, a lower bound on the lifting degree is achieved. For multiple-edge category, for the first time a lower bound on the lifting degree for both regular and irregular QC-LDPC codes with girth 6 is achieved. We also demonstrate that the achieved lower bounds on multiple-edge $(4,n)$-regular QC-LDPC codes with girth 6 are tight and the resultant codes have shorter length compared to their counterparts in single-edge codes. Additionally, difference matrices help to reduce the conditions of considering 6-cycles from seven states to five states. We obtain multiple-edge $(4,n)$-regular QC-LDPC codes with girth 8 and $n=4,6,8$ with the shortest length.

DOI
10.48550/arxiv.1709.00825

Related papers

Lower Bounds on the Lifting Degree of QC-LDPC Codes by Difference Matrices

Farzane Amirzade, Mohammad‐Reza Sadeghi

In this paper, we define two “difference matrices” which correspond to an exponent matrix. We present necessary and sufficient conditions for these difference matrices to have quasi-cyclic low-density parity-check codes (QC-LDPC) codes with a certain girth. We achieve all non-isomorphic QC-LDPC codes with the shortest length, girth 6, the column weight, m = 4, and the row weight, 5 ≤ n ≤ 11. Moreover, a method to obtain an exponent matrix with girth 10 is presented which reduces the complexity of the search algorithm. If the first row and the first column of the exponent matrix are all-zero, then by applying our method we do not need to test Fossorier's lemma to avoid 6-cycles and 8-cycles. For girth 10, we also provide a lower bound on the lifting degree which is tighter than the existing bound. For girth 12, a new lower bound on the lifting degree is achieved.

IEEE Access•Jan 1, 2018•28 citations

Analytical Lower Bound on the Lifting Degree of Multiple-Edge QC-LDPC Codes With Girth 6

Mohammad‐Reza Sadeghi, Farzane Amirzade

Multiple-edge protographs have some advantages over single-edge protographs, such as potentially having larger minimum Hamming distance. However, most of results in the literature are related to the construction of single-edge quasi-cyclic low-density parity-check codes (QC-LDPC) codes and little research has been done for the construction of multiple-edge QC-LDPC codes. In this letter, for the first time, necessary and sufficient conditions for the exponent matrices to have multiple-edge QC-LDPC codes with girth 6 are provided. As a consequence of this letter, a lower bound on the lifting degree of regular and irregular multiple-edge QC-LDPC codes with girth 6 is derived. We also present QC-LDPC codes whose lifting degrees meet our proposed lower bound. These codes have shorter lengths compared with single-edge QC-LDPC codes. Another contribution of this letter is presenting a technique to reduce the size of the search space to find these codes.

IEEE Communications Letters•May 29, 2018•24 citations

Quasi-Cyclic Protograph-Based Raptor-Like LDPC Codes With Girth 6 and Shortest Length

Farzane Amirzade, Mohammad‐Reza Sadeghi, Daniel Panario

We consider multiple-edge QC-LDPC codes with a base matrix of large size. We propose a new method, the degree reduction method, to obtain exponent matrices of these codes which considerably reduces the complexity of the search algorithm. We also provide a necessary and sufficient condition to avoid 4-cycles from occurrence in the Tanner graph of codes obtained using our method. Then, we apply our method to quasi-cyclic protograph-based Raptor-Like LDPC (QC-PBRL-LDPC) codes whose base matrices are multiple-edge. Numerical results show that as a consequence of this study we can obtain the minimum lifting degree of QC-PBRL-LDPC codes with girth at least 6. Thus, the lengths of the obtained codes are much smaller than those of their counterpart short-length codes in the literature.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•6 citations

Bounds on the Size of Parity-Check Matrices for Quasi-Cyclic Low-Density Parity-Check Codes

Kyung-Joong Kim, Jin-Ho Chung, Kyeongcheol Yang

In this paper, we investigate the cycle properties of quasi-cyclic low-density parity-check (QC-LDPC) codes. Using the sequence representation of a parity-check matrix for a QC-LDPC code, we analyze a necessary and sufficient condition for a cycle of a given length to exist. We then derive bounds which are necessary conditions for a QC-LDPC code to have a given girth in terms of its parameters. We also give a bound which is a sufficient condition for a QC-LDPC code of a given girth to be constructed by a greedy algorithm. The bounds derived here are applicable to any regular or irregular QC-LDPC codes as well as they improve the existing bounds in many classes of regular LDPC codes.

IEEE Transactions on Information Theory•Aug 28, 2013•15 citations

On the Girth of Quasi-Cyclic Protograph LDPC Codes

M. Karimi, Amir H. Banihashemi

In this paper, we study the relationships between the girth of the Tanner graph of a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code, the lifting degree, and the size and the structure of the base graph. As a result, for a given base graph, we derive a lower bound on the lifting degree as a necessary condition for the lifted graph to have a certain girth. This also provides an upper bound on the girth of the family of graphs lifted from a given base graph with a given lifting degree. The upper bounds derived here, which are applicable to both regular and irregular base graphs with no parallel edges, are in some cases more general and in some other cases tighter than the existing bounds. The results presented in this work can be used to design cyclic liftings with relatively small degree and relatively large girth. As an example, we present new QC protograph LDPC code constructions with girth 8 using fully connected base graphs. These constructions provide upper bounds on the lifting degree required for achieving girth 8 using fully connected base graphs.

IEEE Transactions on Information Theory•Mar 6, 2013•89 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.

IEEE Access•Jan 1, 2021•2 citations
In this paper, we define two matrices named as "difference matrices", denoted by DDD and DDDDDD which significantly contribute to achieve regular single-edge QC-LDPC codes with the shortest length and the certain girth as well as regular and irregular multiple-edge QC-LDPC codes. Making use of these matrices, we obtain necessary and sufficient conditions to have single-edge (m,n)(m,n)(m,n)-regular QC-LDPC codes with girth 6, 10 and 12. Additionally, for girth 6, we achieve all non-isomorphic codes with the minimum lifting degree, NNN, for m=4m=4m=4 and 5≤n≤115\leq n\leq 115≤n≤11, and present an exponent matrix for each minimum distance. For girth 10, we provide a lower bound on the lifting degree which is tighter than the existing bound. More important, for an exponent matrix whose first row and first column are all-zero, we demonstrate that the non-existence of 8-cycles proves the non-existence of 6-cycles related to the first row of the exponent matrix too. All non-isomorphic QC-LDPC codes with girth 10 and n=5,6n=5,6n=5,6 whose numbers are more than those presented in the literature are provided. For n=7,8n=7,8n=7,8 we decrease the lifting degrees from 159 and 219 to 145 and 211, repectively. For girth 12, a lower bound on the lifting degree is achieved. For multiple-edge category, for the first time a lower bound on the lifting degree for both regular and irregular QC-LDPC codes with girth 6 is achieved. We also demonstrate that the achieved lower bounds on multiple-edge (4,n)(4,n)(4,n)-regular QC-LDPC codes with girth 6 are tight and the resultant codes have shorter length compared to their counterparts in single-edge codes. Additionally, difference matrices help to reduce the conditions of considering 6-cycles from seven states to five states. We obtain multiple-edge (4,n)(4,n)(4,n)-regular QC-LDPC codes with girth 8 and n=4,6,8n=4,6,8n=4,6,8 with the shortest length.
In this paper, we define two “difference matrices” which correspond to an exponent matrix. We present necessary and sufficient conditions for these difference matrices to have quasi-cyclic low-density parity-check codes (QC-LDPC) codes with a certain girth. We achieve all non-isomorphic QC-LDPC codes with the shortest length, girth 6, the column weight, m = 4, and the row weight, 5 ≤ n ≤ 11. Moreover, a method to obtain an exponent matrix with girth 10 is presented which reduces the complexity of the search algorithm. If the first row and the first column of the exponent matrix are all-zero, then by applying our method we do not need to test Fossorier's lemma to avoid 6-cycles and 8-cycles. For girth 10, we also provide a lower bound on the lifting degree which is tighter than the existing bound. For girth 12, a new lower bound on the lifting degree is achieved.
Multiple-edge protographs have some advantages over single-edge protographs, such as potentially having larger minimum Hamming distance. However, most of results in the literature are related to the construction of single-edge quasi-cyclic low-density parity-check codes (QC-LDPC) codes and little research has been done for the construction of multiple-edge QC-LDPC codes. In this letter, for the first time, necessary and sufficient conditions for the exponent matrices to have multiple-edge QC-LDPC codes with girth 6 are provided. As a consequence of this letter, a lower bound on the lifting degree of regular and irregular multiple-edge QC-LDPC codes with girth 6 is derived. We also present QC-LDPC codes whose lifting degrees meet our proposed lower bound. These codes have shorter lengths compared with single-edge QC-LDPC codes. Another contribution of this letter is presenting a technique to reduce the size of the search space to find these codes.
We consider multiple-edge QC-LDPC codes with a base matrix of large size. We propose a new method, the degree reduction method, to obtain exponent matrices of these codes which considerably reduces the complexity of the search algorithm. We also provide a necessary and sufficient condition to avoid 4-cycles from occurrence in the Tanner graph of codes obtained using our method. Then, we apply our method to quasi-cyclic protograph-based Raptor-Like LDPC (QC-PBRL-LDPC) codes whose base matrices are multiple-edge. Numerical results show that as a consequence of this study we can obtain the minimum lifting degree of QC-PBRL-LDPC codes with girth at least 6. Thus, the lengths of the obtained codes are much smaller than those of their counterpart short-length codes in the literature.
In this paper, we investigate the cycle properties of quasi-cyclic low-density parity-check (QC-LDPC) codes. Using the sequence representation of a parity-check matrix for a QC-LDPC code, we analyze a necessary and sufficient condition for a cycle of a given length to exist. We then derive bounds which are necessary conditions for a QC-LDPC code to have a given girth in terms of its parameters. We also give a bound which is a sufficient condition for a QC-LDPC code of a given girth to be constructed by a greedy algorithm. The bounds derived here are applicable to any regular or irregular QC-LDPC codes as well as they improve the existing bounds in many classes of regular LDPC codes.
In this paper, we study the relationships between the girth of the Tanner graph of a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code, the lifting degree, and the size and the structure of the base graph. As a result, for a given base graph, we derive a lower bound on the lifting degree as a necessary condition for the lifted graph to have a certain girth. This also provides an upper bound on the girth of the family of graphs lifted from a given base graph with a given lifting degree. The upper bounds derived here, which are applicable to both regular and irregular base graphs with no parallel edges, are in some cases more general and in some other cases tighter than the existing bounds. The results presented in this work can be used to design cyclic liftings with relatively small degree and relatively large girth. As an example, we present new QC protograph LDPC code constructions with girth 8 using fully connected base graphs. These constructions provide upper bounds on the lifting degree required for achieving girth 8 using fully connected base graphs.
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 girthgmax⁡g_{\max }gmax​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 girthgmax⁡g_{\max }gmax​, some slope-matrices are constructed by a depth-first search algorithm for which the corresponding multitype QC-LDPC codes with even girthggg,g≤gmax⁡g\le g_{\max }g≤gmax​, 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.