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:0901.4129 · IEEE Transactions on Information Theory

Quasi-Cyclic LDPC Codes: Influence of Proto- and Tanner-Graph Structure on Minimum Hamming Distance Upper Bounds

Roxana Smarandache, Pascal O. Vontobel

Published Feb 1, 2012• 127 citations
arXivHTMLPDF

Abstract

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are an important instance of proto-graph-based LDPC codes. In this paper we present upper bounds on the minimum Hamming distance of QC LDPC codes and study how these upper bounds depend on graph structure parameters (like variable degrees, check node degrees, girth) of the Tanner graph and of the underlying proto-graph. Moreover, for several classes of proto-graphs we present explicit QC LDPC code constructions that achieve (or come close to) the respective minimum Hamming distance upper bounds. Because of the tight algebraic connection between QC codes and convolutional codes, we can state similar results for the free Hamming distance of convolutional codes. In fact, some QC code statements are established by first proving the corresponding convolutional code statements and then using a result by Tanner that says that the minimum Hamming distance of a QC code is upper bounded by the free Hamming distance of the convolutional code that is obtained by “unwrapping” the QC code.

DOI
10.1109/tit.2011.2173244

Related papers

Quasi-Cyclic LDPC Codes: Influence of Proto- and Tanner-Graph Structure on Minimum Hamming Distance Upper Bounds

Roxana Smarandache, Pascal O. Vontobel

Quasi-cyclic (QC) low-density parity-check (LDPC) codes are an important instance of proto-graph-based LDPC codes. In this paper we present upper bounds on the minimum Hamming distance of QC LDPC codes and study how these upper bounds depend on graph structure parameters (like variable degrees, check node degrees, girth) of the Tanner graph and of the underlying proto-graph. Moreover, for several classes of proto-graphs we present explicit QC LDPC code constructions that achieve (or come close) to the respective minimum Hamming distance upper bounds.

•Jan 1, 2009•102 citations

Design of Quasi-Cyclic Cycle LDPC Codes over GF(q)

HU Shu-kai, Chao Chen, Rong Xia Sun +1 more

Quasi-cyclic (QC) low-density parity-check (LDPC) codes have several appealing properties regarding decoding, storage requirements and encoding aspects. In this paper, we focus on the QC LDPC codes over GF(q) whose parity-check matrices have fixed column weight j=2. By investigating two subgraphs in the Tanner graphs of the corresponding base matrices, we derive two upper bounds on the minimum Hamming distance for this class of codes. In addition, a method is proposed to construct QC LDPC codes over GF(q), which have good Hamming distance distributions. Simulations show that our designed codes have good performance.

IEICE Transactions on Communications•Jan 1, 2012•0 citations

Partially Quasi-Cyclic Protograph-Based LDPC Codes

Roxana Smarandache, David G. M. Mitchell, Danniel J. Costello

A significant amount of the analysis of protograph-based low-density parity-check (LDPC) codes has been devoted to the subclass of quasi-cyclic (QC) LDPC codes. Despite their implementation advantages and algebraic properties that make them easy to analyze, protograph-based QC-LDPC codes have undesirable fixed upper limits on important code parameters. This implies that picking a QC code from an asymptotically good or capacity approaching ensemble is suboptimal, since long QC codes will not perform close to the ensemble asymptotic limits. Indeed, these limits can only be achieved by codes that are not QC. In this paper we present an overview together with some new results on partially-QC protograph-based LDPC codes, i.e., LDPC codes whose parity-check matrix is partially composed of circulant submatrices. We perform both a minimum Hamming distance and girth analysis of these codes. Moreover, we present explicit partially-QC LDPC code constructions with parameters that exceed the restricted QC upper bounds.

International Conference on Communications•Jun 1, 2011•10 citations

Quasi-cyclic LDPC codes based on pre-lifted protographs

David G. M. Mitchell, Roxana Smarandache, Daniel J. Costello

Quasi-cyclic Low-Density Parity-Check (QC-LDPC) codes based on protographs are of great interest to code designers because of their implementation advantages and algebraic properties that make them easy to analyze. However, the protograph structure imposes undesirable fixed upper limits on important code parameters. In this paper, we show that the upper bound on the minimum Hamming distance of protograph-based QC codes can be improved by the careful application of a two-step lifting procedure applied to the protograph. The promised improvement is validated by constructing codes with minimum distance exceeding the upper bound for QC codes based on a particular protograph.

IEEE Information Theory Workshop (ITW)•Oct 1, 2011•9 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 girth of quasi cyclic protograph LDPC codes

Mehdi 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, on one hand, and the lifting degree and the size and the structure of the base graph, on the other hand. As a result, for a given base graph and a given lifting degree, we derive an upper bound on the girth of the resulting lifted graphs (codes). The upper bounds derived here are generally tighter than the existing bounds. The results presented in this work can be used to select an appropriate lifting degree for a given base graph, in order to have a desired girth, or to provide some insight in designing good base graphs, or to properly select the base graph's edge permutations.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•6 citations
Quasi-cyclic (QC) low-density parity-check (LDPC) codes are an important instance of proto-graph-based LDPC codes. In this paper we present upper bounds on the minimum Hamming distance of QC LDPC codes and study how these upper bounds depend on graph structure parameters (like variable degrees, check node degrees, girth) of the Tanner graph and of the underlying proto-graph. Moreover, for several classes of proto-graphs we present explicit QC LDPC code constructions that achieve (or come close to) the respective minimum Hamming distance upper bounds. Because of the tight algebraic connection between QC codes and convolutional codes, we can state similar results for the free Hamming distance of convolutional codes. In fact, some QC code statements are established by first proving the corresponding convolutional code statements and then using a result by Tanner that says that the minimum Hamming distance of a QC code is upper bounded by the free Hamming distance of the convolutional code that is obtained by “unwrapping” the QC code.
Quasi-cyclic (QC) low-density parity-check (LDPC) codes are an important instance of proto-graph-based LDPC codes. In this paper we present upper bounds on the minimum Hamming distance of QC LDPC codes and study how these upper bounds depend on graph structure parameters (like variable degrees, check node degrees, girth) of the Tanner graph and of the underlying proto-graph. Moreover, for several classes of proto-graphs we present explicit QC LDPC code constructions that achieve (or come close) to the respective minimum Hamming distance upper bounds.
Quasi-cyclic (QC) low-density parity-check (LDPC) codes have several appealing properties regarding decoding, storage requirements and encoding aspects. In this paper, we focus on the QC LDPC codes over GF(q) whose parity-check matrices have fixed column weight j=2. By investigating two subgraphs in the Tanner graphs of the corresponding base matrices, we derive two upper bounds on the minimum Hamming distance for this class of codes. In addition, a method is proposed to construct QC LDPC codes over GF(q), which have good Hamming distance distributions. Simulations show that our designed codes have good performance.
A significant amount of the analysis of protograph-based low-density parity-check (LDPC) codes has been devoted to the subclass of quasi-cyclic (QC) LDPC codes. Despite their implementation advantages and algebraic properties that make them easy to analyze, protograph-based QC-LDPC codes have undesirable fixed upper limits on important code parameters. This implies that picking a QC code from an asymptotically good or capacity approaching ensemble is suboptimal, since long QC codes will not perform close to the ensemble asymptotic limits. Indeed, these limits can only be achieved by codes that are not QC. In this paper we present an overview together with some new results on partially-QC protograph-based LDPC codes, i.e., LDPC codes whose parity-check matrix is partially composed of circulant submatrices. We perform both a minimum Hamming distance and girth analysis of these codes. Moreover, we present explicit partially-QC LDPC code constructions with parameters that exceed the restricted QC upper bounds.
Quasi-cyclic Low-Density Parity-Check (QC-LDPC) codes based on protographs are of great interest to code designers because of their implementation advantages and algebraic properties that make them easy to analyze. However, the protograph structure imposes undesirable fixed upper limits on important code parameters. In this paper, we show that the upper bound on the minimum Hamming distance of protograph-based QC codes can be improved by the careful application of a two-step lifting procedure applied to the protograph. The promised improvement is validated by constructing codes with minimum distance exceeding the upper bound for QC codes based on a particular protograph.
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.
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, on one hand, and the lifting degree and the size and the structure of the base graph, on the other hand. As a result, for a given base graph and a given lifting degree, we derive an upper bound on the girth of the resulting lifted graphs (codes). The upper bounds derived here are generally tighter than the existing bounds. The results presented in this work can be used to select an appropriate lifting degree for a given base graph, in order to have a desired girth, or to provide some insight in designing good base graphs, or to properly select the base graph's edge permutations.