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:2609.16836

CPM-LDPC Codes Attaining the Minimum-Distance Bound

Kenta Kasai

Published Sep 15, 2026• 0 citations
arXivHTMLPDF

Abstract

We study binary quasi-cyclic LDPC codes whose parity-check matrices are full arrays of single circulant permutation matrices (CPMs), referred to here as CPM-LDPC codes. Their minimum distance is at most $(J+1)!$, where $J$ is the column weight. For every fixed pair of column and row weights $2\le J

DOI
10.48550/arxiv.2609.16836

Related papers

Upper Bounds on the Minimum Distance of Structured LDPC Codes

François Arnault, Philippe Gaborit, Wouter Rozendaal +2 more

We investigate the minimum distance of structured binary Low-Density Parity-Check (LDPC) codes whose parity-check matrices are of the form $[\mathbf{C} \vert \mathbf{M}]$ where $\mathbf{C}$ is circulant and of column weight $2$, and $\mathbf{M}$ has fixed column weight $r \geq 3$ and row weight at least $1$. These codes are of interest because they are LDPC codes which come with a natural linear-time encoding algorithm. We show that the minimum distance of these codes is in $O(n^{\frac{r-2}{r-1} + ε})$, where $n$ is the code length and $ε> 0$ is arbitrarily small. This improves the previously known upper bound in $O(n^{\frac{r-1}{r}})$ on the minimum distance of such codes.

arXiv:2501.19125•Jan 31, 2025•0 citations

(7,K) GIRTH-8 QC-LDPC CODES WITH AN EXPLICIT CONSTRUCTION

M. Majdzadeh, Mohammad Gholami, Gh. Raeisi

Recently, for each row weight $K$ and column-weight $J$, $3le J< K$, several classes of $(J,K)$ quasi-cyclic (QC) low-density parity-check (LDPC) codes with girth 8 have been constructed explicitly such that their corresponding lower-bounds on the size of circulant permutation matrices (CPMs) have been considered small as possible. In this paper, for $J=7$, a class of $(7,K)$ QC-LDPC codes with girth 8 is generated by an explicit method such that the lower-bounds of the constructed codes remarkably are better than the state-of-the-art bound $(K-1)(K^2+K)+1$.

Journal of Algebraic Systems•Jan 1, 2022•2 citations

On regular quasi-cyclic LDPC codes from binomials

Roxana Smarandache, Pascal O. Vontobel

In the past, several authors have considered quasicyclic LDPC codes whose circulant matrices in the parity-check matrix are cyclically shifted identity matrices. By composing a parity-check matrix not only with such matrices but also with sums of two cyclically shifted identity matrices and with zero matrices, one can increase the minimum distance while keeping the same regularity. Specifically, whereas for (3, 4)-regular codes in the first class the best minimum distance is 24, the best minimum distance in the second class is 32. We give examples of codes that achieve these bounds.

IEEE International Symposium on Information Theory (ISIT)•Dec 23, 2004•43 citations

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

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.

•Jan 1, 2003•0 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
We study binary quasi-cyclic LDPC codes whose parity-check matrices are full arrays of single circulant permutation matrices (CPMs), referred to here as CPM-LDPC codes. Their minimum distance is at most (J+1)!(J+1)!(J+1)!, where JJJ is the column weight. For every fixed pair of column and row weights $2\le J
We investigate the minimum distance of structured binary Low-Density Parity-Check (LDPC) codes whose parity-check matrices are of the form [C∣M][\mathbf{C} \vert \mathbf{M}][C∣M] where C\mathbf{C}C is circulant and of column weight 222, and M\mathbf{M}M has fixed column weight r≥3r \geq 3r≥3 and row weight at least 111. These codes are of interest because they are LDPC codes which come with a natural linear-time encoding algorithm. We show that the minimum distance of these codes is in O(nr−2r−1+ε)O(n^{\frac{r-2}{r-1} + ε})O(nr−1r−2​+ε), where nnn is the code length and ε>0ε> 0ε>0 is arbitrarily small. This improves the previously known upper bound in O(nr−1r)O(n^{\frac{r-1}{r}})O(nrr−1​) on the minimum distance of such codes.
Recently, for each row weight KKK and column-weight JJJ, 3leJ<K3le J< K3leJ<K, several classes of (J,K)(J,K)(J,K) quasi-cyclic (QC) low-density parity-check (LDPC) codes with girth 8 have been constructed explicitly such that their corresponding lower-bounds on the size of circulant permutation matrices (CPMs) have been considered small as possible. In this paper, for J=7J=7J=7, a class of (7,K)(7,K)(7,K) QC-LDPC codes with girth 8 is generated by an explicit method such that the lower-bounds of the constructed codes remarkably are better than the state-of-the-art bound (K−1)(K2+K)+1(K-1)(K^2+K)+1(K−1)(K2+K)+1.
In the past, several authors have considered quasicyclic LDPC codes whose circulant matrices in the parity-check matrix are cyclically shifted identity matrices. By composing a parity-check matrix not only with such matrices but also with sums of two cyclically shifted identity matrices and with zero matrices, one can increase the minimum distance while keeping the same regularity. Specifically, whereas for (3, 4)-regular codes in the first class the best minimum distance is 24, the best minimum distance in the second class is 32. We give examples of codes that achieve these bounds.
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.
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.
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.