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 International Symposium on Information Theory (ISIT)

Low-density arrays of circulant matrices: Rank and row-redundancy, and QC-LDPC codes

Qin Huang, Keke Liu, Zulin Wang

Published Jul 1, 2012• 12 citations
Publisher

Abstract

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, tight bounds on rank and row-redundancy are derived, which make it possible to consider row-redundancy in constructions of QC-LDPC codes to achieve better performance. Moreover, a new construction of QC-LDPC codes from random partitions of finite fields, which has flexible code dimensions and is abundant in row-redundancy, is presented and analyzed.

DOI
10.1109/isit.2012.6284127

Related papers

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

Quasi-cyclic LDPC codes: Construction and rank analysis of their parity-check matrices

Keke Liu, Qin Huang, Shu Lin +1 more

A construction of binary and non-binary quasi-cyclic (QC)-LDPC codes based on partitions of finite fields of characteristic 2 is proposed. The construction is carried out in the Fourier transform domain. The parity-check matrices of these QC-LDPC codes are arrays of circulant permutation matrices. The ranks of these arrays are analyzed and combinatorial expressions are derived. Example codes are given and simulations show that they perform well over the AWGN channel decoded with message-passing decoding algorithms.

Information Theory and Applications Workshop (ITA)•Feb 1, 2012•15 citations

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

Circulant arrays: Rank analysis and construction of quasi-cyclic LDPC codes

Li Guo Zhang, Shu Lin, Khaled Abdel-Ghaffar +1 more

This paper consists of three parts. The first part presents a large class of new binary quasi-cyclic (QC)-LDPC codes with girth of at least 6 whose parity-check matrices are constructed based on cyclic subgroups of finite fields. Experimental results show that the codes constructed perform well over the binary-input AWGN channel with iterative decoding using the sum-product algorithm (SPA) and they outperform the corresponding pseudo-random QC-LDPC codes constructed with the PEG-algorithm. The second part analyzes the ranks of the parity-check matrices of codes constructed based on finite fields with characteristic of 2 and gives combinatorial expressions for these ranks. The third part identifies a subclass of constructed QC-LDPC codes that have large minimum distances. Decoding of codes in this subclass with the SPA converges very fast.

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

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

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

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

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.

IEEE Transactions on Information Theory•Sep 17, 2025•1 citation
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, tight bounds on rank and row-redundancy are derived, which make it possible to consider row-redundancy in constructions of QC-LDPC codes to achieve better performance. Moreover, a new construction of QC-LDPC codes from random partitions of finite fields, which has flexible code dimensions and is abundant in row-redundancy, is presented and analyzed.
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.
A construction of binary and non-binary quasi-cyclic (QC)-LDPC codes based on partitions of finite fields of characteristic 2 is proposed. The construction is carried out in the Fourier transform domain. The parity-check matrices of these QC-LDPC codes are arrays of circulant permutation matrices. The ranks of these arrays are analyzed and combinatorial expressions are derived. Example codes are given and simulations show that they perform well over the AWGN channel decoded with message-passing decoding algorithms.
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.
This paper consists of three parts. The first part presents a large class of new binary quasi-cyclic (QC)-LDPC codes with girth of at least 6 whose parity-check matrices are constructed based on cyclic subgroups of finite fields. Experimental results show that the codes constructed perform well over the binary-input AWGN channel with iterative decoding using the sum-product algorithm (SPA) and they outperform the corresponding pseudo-random QC-LDPC codes constructed with the PEG-algorithm. The second part analyzes the ranks of the parity-check matrices of codes constructed based on finite fields with characteristic of 2 and gives combinatorial expressions for these ranks. The third part identifies a subclass of constructed QC-LDPC codes that have large minimum distances. Decoding of codes in this subclass with the SPA converges very fast.
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.
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.