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

IEEE Transactions on Information Theory

Rank Analysis and Its Applications for Quasi-Cyclic Low-Density Parity-Check Codes

Po‐Chun Yang, Chung-Hsuan Wang, Chi-chao Chao

Published Sep 17, 2025• 1 citation
Publisher

Abstract

In this paper, we develop a new approach for rank analysis of parity-check matrices for quasi-cyclic low-density parity-check codes based on the associated polynomials of circulant matrices, applicable to general finite fields and arbitrary circulant sizes. Some formulas on the rank for parity-check matrices with one, two, and three row-blocks are first derived. For the general case with arbitrary numbers of row-blocks, lower and upper bounds on the rank are presented, and these bounds can be combined to give the exact rank result under certain conditions. We also investigate the effect on the rank by changing the circulant size. Furthermore, we study the relations between the rank of the masked matrix and that of the masking matrix, which can be used to predict the rank of the parity-check matrix after masking. The obtained rank analysis results are then applied to several classes of existing algebraically constructed parity-check matrices, along with their masked matrices. Finally, we demonstrate how rank analysis can be used in the code design procedure.

DOI
10.1109/tit.2025.3611129

Related papers

Rank Analysis of Parity-Check Matrices for Quasi-Cyclic LDPC Codes

Po‐Chun Yang, Chung-Hsuan Wang, Chi-Chao Chao

Quasi-cyclic low-density parity-check (QC-LDPC) codes are an important class of LDPC codes which can be encoded and decoded with low complexity and suitable for many applications. As the code dimension, which describes the number of protected information bits, is equal to the code length minus the rank of the parity-check matrix and the parity-check matrix for QC-LDPC codes is usually not full-rank, determining the rank of the parity-check matrix is of essential importance. In this paper, we study the rank of the parity-check matrix for QC-LDPC codes based on the associated polynomials for circulant matrices. A formula for the rank of the parity-check matrix with only one row-block is first derived. We then extend the result to matrices with two, three, or more row-blocks. Some bounds are also presented for matrices with arbitrary numbers of row-blocks. Furthermore, the exact rank is determined for a class of algebraically constructed parity-check matrices.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•5 citations

A matrix-theoretic approach for analyzing quasi-cyclic low-density parity-check codes

Qiuju Diao, Qin Huang, Shu Lin +1 more

A matrix-theoretic approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is developed. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is amicable to the analysis and construction of quasi-cyclic low-density parity-check codes since it takes into account the specific parity-check matrix used for decoding with iterative message-passing algorithms. Based on this approach, the dimension of the codes and parity-check matrices for the dual codes can be determined. Several algebraic and geometric constructions of quasi-cyclic codes are presented as applications along with simulation results showing their performance over additive white Gaussian noise channels decoded with iterative message-passing algorithms.

IEEE Transactions on Information Theory•Jan 18, 2012•83 citations

Structural Analysis of Generalized Quasi-Cyclic LDPC Codes: Rank, Design, and Generator Matrices

Roxana Smarandache, David G. M. Mitchell, Anthony Gómez-Fonseca

Generalized low-density parity-check (GLDPC) codes, where single parity-check constraints on the code bits are replaced with generalized constraints (an arbitrary linear code), are a promising class of codes for low-latency communication. The block error rate performance of the GLDPC codes, combined with a complementary outer code, has been shown to outperform a variety of state-of-the-art code and decoder designs with suitable lengths and rates for the 5G ultra-reliable low-latency communication (URLLC) regime. A major drawback of these codes is that it is not known how to construct appropriate polynomial matrices to encode them efficiently. In this paper, we analyze practical constructions of quasi-cyclic GLDPC (QC-GLDPC) codes and show how to construct polynomial generator matrices in various forms using minors of the polynomial matrix. The approach can be applied to fully generalized matrices or partially generalized (with mixed constraint node types) to find better performance/rate trade-offs. The resulting encoding matrices are presented in useful forms that facilitate efficient implementation. The rich substructure displayed also provides us with new methods of determining low weight codewords, providing lower and upper bounds on the minimum distance and often giving those of weight equal to the minimum distance. Based on the minors of the polynomial parity-check matrix, we also give a formula for the rank of any parity-check matrix representing a QC-LDPC or QC-GLDPC code, and hence, the dimension of the code. Finally, we show that by applying double graph-liftings, the code parameters can be improved without affecting the ability to obtain a polynomial generator matrix.

IEEE Transactions on Information Theory•Oct 27, 2025•3 citations

Cyclic and Quasi-Cyclic LDPC Codes on Constrained Parity-Check Matrices and Their Trapping Sets

Qin Huang, Qiuju Diao, Shu Lin +1 more

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances.

IEEE Transactions on Information Theory•Jan 31, 2012•108 citations

Low-Density Arrays of Circulant Matrices: Rank and Row-Redundancy Analysis, and Quasi-Cyclic LDPC Codes

Qin Huang, Keke Liu, Zulin Wang

This paper is concerned with general analysis on the rank and row-redundancy of an array of circulants whose null space defines a QC-LDPC code. Based on the Fourier transform and the properties of conjugacy classes and Hadamard products of matrices, we derive tight upper bounds on rank and row-redundancy for general array of circulants, which make it possible to consider row-redundancy in constructions of QC-LDPC codes to achieve better performance. We further investigate the rank of two types of construction of QC-LDPC codes: constructions based on Vandermonde Matrices and Latin Squares and give combinatorial expression of the exact rank in some specific cases, which demonstrates the tightness of the bound we derive. Moreover, several types of new construction of QC-LDPC codes with large row-redundancy are presented and analyzed.

arXiv:1202.0702•Feb 3, 2012•1 citation

A transform approach for analyzing and constructing quasi-cyclic low-density parity-check codes

Qiuju Diao, Qin Huang, Shu Hwa Lin +1 more

An approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is presented. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is used to characterize certain structural properties of low-density parity-check (LDPC) codes such as the girths of their Tanner graphs. Many constructions of quasi-cyclic LDPC codes can be unified under the proposed approach.

Information Theory and Applications Workshop (ITA)•Feb 1, 2011•14 citations
In this paper, we develop a new approach for rank analysis of parity-check matrices for quasi-cyclic low-density parity-check codes based on the associated polynomials of circulant matrices, applicable to general finite fields and arbitrary circulant sizes. Some formulas on the rank for parity-check matrices with one, two, and three row-blocks are first derived. For the general case with arbitrary numbers of row-blocks, lower and upper bounds on the rank are presented, and these bounds can be combined to give the exact rank result under certain conditions. We also investigate the effect on the rank by changing the circulant size. Furthermore, we study the relations between the rank of the masked matrix and that of the masking matrix, which can be used to predict the rank of the parity-check matrix after masking. The obtained rank analysis results are then applied to several classes of existing algebraically constructed parity-check matrices, along with their masked matrices. Finally, we demonstrate how rank analysis can be used in the code design procedure.
Quasi-cyclic low-density parity-check (QC-LDPC) codes are an important class of LDPC codes which can be encoded and decoded with low complexity and suitable for many applications. As the code dimension, which describes the number of protected information bits, is equal to the code length minus the rank of the parity-check matrix and the parity-check matrix for QC-LDPC codes is usually not full-rank, determining the rank of the parity-check matrix is of essential importance. In this paper, we study the rank of the parity-check matrix for QC-LDPC codes based on the associated polynomials for circulant matrices. A formula for the rank of the parity-check matrix with only one row-block is first derived. We then extend the result to matrices with two, three, or more row-blocks. Some bounds are also presented for matrices with arbitrary numbers of row-blocks. Furthermore, the exact rank is determined for a class of algebraically constructed parity-check matrices.
A matrix-theoretic approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is developed. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is amicable to the analysis and construction of quasi-cyclic low-density parity-check codes since it takes into account the specific parity-check matrix used for decoding with iterative message-passing algorithms. Based on this approach, the dimension of the codes and parity-check matrices for the dual codes can be determined. Several algebraic and geometric constructions of quasi-cyclic codes are presented as applications along with simulation results showing their performance over additive white Gaussian noise channels decoded with iterative message-passing algorithms.
Generalized low-density parity-check (GLDPC) codes, where single parity-check constraints on the code bits are replaced with generalized constraints (an arbitrary linear code), are a promising class of codes for low-latency communication. The block error rate performance of the GLDPC codes, combined with a complementary outer code, has been shown to outperform a variety of state-of-the-art code and decoder designs with suitable lengths and rates for the 5G ultra-reliable low-latency communication (URLLC) regime. A major drawback of these codes is that it is not known how to construct appropriate polynomial matrices to encode them efficiently. In this paper, we analyze practical constructions of quasi-cyclic GLDPC (QC-GLDPC) codes and show how to construct polynomial generator matrices in various forms using minors of the polynomial matrix. The approach can be applied to fully generalized matrices or partially generalized (with mixed constraint node types) to find better performance/rate trade-offs. The resulting encoding matrices are presented in useful forms that facilitate efficient implementation. The rich substructure displayed also provides us with new methods of determining low weight codewords, providing lower and upper bounds on the minimum distance and often giving those of weight equal to the minimum distance. Based on the minors of the polynomial parity-check matrix, we also give a formula for the rank of any parity-check matrix representing a QC-LDPC or QC-GLDPC code, and hence, the dimension of the code. Finally, we show that by applying double graph-liftings, the code parameters can be improved without affecting the ability to obtain a polynomial generator matrix.
This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances.
This paper is concerned with general analysis on the rank and row-redundancy of an array of circulants whose null space defines a QC-LDPC code. Based on the Fourier transform and the properties of conjugacy classes and Hadamard products of matrices, we derive tight upper bounds on rank and row-redundancy for general array of circulants, which make it possible to consider row-redundancy in constructions of QC-LDPC codes to achieve better performance. We further investigate the rank of two types of construction of QC-LDPC codes: constructions based on Vandermonde Matrices and Latin Squares and give combinatorial expression of the exact rank in some specific cases, which demonstrates the tightness of the bound we derive. Moreover, several types of new construction of QC-LDPC codes with large row-redundancy are presented and analyzed.
An approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is presented. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is used to characterize certain structural properties of low-density parity-check (LDPC) codes such as the girths of their Tanner graphs. Many constructions of quasi-cyclic LDPC codes can be unified under the proposed approach.