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

Advances in Mathematics of Communications

Codes based on dyadic matrices and their generalizations

Meraiah Martinez, Tefjol Pllaha, Christine A. Kelley

Published Dec 16, 2024• 3 citations
Publisher

Abstract

Codes based on algebraically structured parity check matrices are desirable in applications due to their compact representations, practical implementation advantages, and tractable decoder performance analysis. In this paper, we examine codes based on parity check matrices that are dyadic, $ n $-adic, or quasi-dyadic (QD), meaning the parity check matrix representation is block structured with dyadic matrices as blocks. Depending on the number of nonzero positions in the leading row of each matrix or block, these codes may be either low density or moderate density. We examine basic code properties of dyadic, $ n $-adic, and QD parity check codes, including reproducibility, bounds on the dimension and minimum distance, cycle structure of the corresponding Tanner graph, and their possible use in quantum code constructions.

DOI
10.3934/amc.2024054

Related papers

Combinatorial Analysis of Dyadic and Quasi-Dyadic Codes

Anthony Gómez-Fonseca, Gretchen L. Matthews, Kirsten D. Morris +1 more

Quantum low-density parity-check (QLDPC) codes offer a promising route to scalable fault-tolerant quantum computation, but their performance under iterative decoding is strongly influenced by short-cycle structure and other harmful subgraphs in the associated Tanner graphs. This paper develops an algebraic framework for constructing and analyzing (Q)LDPC codes from dyadic and quasi-dyadic matrices-translation-invariant $2^\ell \times 2^\ell$ binary matrices specified compactly by a signature row and forming a commutative ring with recursive block structure. Leveraging this structure, we relate cycles in lifted Tanner graphs to tailless backtrackless closed walks in the protograph and derive efficient, implementable methods to enumerate and control short cycles (notably $4$-, $6$-, and $8$-cycles). We introduce dyadic-aware PEG-style construction algorithms that use forbidden sets of shifts to maximize attainable girth when possible and otherwise minimize the multiplicity of the shortest cycles at the target girth. Motivated by error-floor phenomena, we further characterize and explicitly enumerate absorbing sets in key dyadic layout boundary cases, identifying configurations that induce abundant $(a,0)$-absorbing sets. Finally, we propose CSS-oriented dyadic constructions that satisfy commutation constraints by design and demonstrate via belief-propagation simulations that reducing short-cycle multiplicity can yield substantial decoding gains even when girth cannot be increased.

cs.ITCross-listedarXiv:2605.01942•May 5, 2026•0 citations

Quantum CSS LDPC Codes with Quasi-Dyadic Structure

Alessio Baldelli, Massimo Battaglioni, Paolo Santini

Quantum quasi-cyclic (QC) and quantum low-density parity-check (LDPC) codes have received significant attention due to their algebraic regularity and performance under low-complexity decoding. In this work, we explore a class of structured quantum codes based on reproducible matrices, which generalize known families such as cyclic, QC, and dyadic codes. Focusing on sparse quasi-dyadic (QD) structures, we investigate how their symmetries influence Tanner graph cycles. Moreover, we construct quantum LDPC codes within the Calderbank-Shor-Steane (CSS) framework, analyzing dual-containing configurations, and assess their error rates.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 18, 2025•2 citations

Quantum CSS LDPC Codes based on Dyadic Matrices for Belief Propagation-based Decoding

Alessio Baldelli, Massimo Battaglioni, Jonathan Mandelbaum +2 more

Quantum low-density parity-check (QLDPC) codes provide a practical balance between error-correction capability and implementation complexity in quantum error correction (QEC). In this paper, we propose an algebraic construction based on dyadic matrices for designing both classical and quantum LDPC codes. The method first generates classical binary quasi-dyadic LDPC codes whose Tanner graphs have girth 6. It is then extended to the Calderbank-Shor-Steane (CSS) framework, where the two component parity-check matrices are built to satisfy the compatibility condition required by the recently introduced CAMEL-ensemble quaternary belief propagation decoder. This compatibility condition ensures that all unavoidable cycles of length 4 are assembled in a single variable node, allowing the mitigation of their detrimental effects by decimating that variable node.

cs.ITCross-listedarXiv:2601.08636•IEEE International Symposium on Information Theory (ISIT)•Jan 14, 2026•0 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

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

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
Codes based on algebraically structured parity check matrices are desirable in applications due to their compact representations, practical implementation advantages, and tractable decoder performance analysis. In this paper, we examine codes based on parity check matrices that are dyadic, nnn-adic, or quasi-dyadic (QD), meaning the parity check matrix representation is block structured with dyadic matrices as blocks. Depending on the number of nonzero positions in the leading row of each matrix or block, these codes may be either low density or moderate density. We examine basic code properties of dyadic, nnn-adic, and QD parity check codes, including reproducibility, bounds on the dimension and minimum distance, cycle structure of the corresponding Tanner graph, and their possible use in quantum code constructions.
Quantum low-density parity-check (QLDPC) codes offer a promising route to scalable fault-tolerant quantum computation, but their performance under iterative decoding is strongly influenced by short-cycle structure and other harmful subgraphs in the associated Tanner graphs. This paper develops an algebraic framework for constructing and analyzing (Q)LDPC codes from dyadic and quasi-dyadic matrices-translation-invariant 2ℓ×2ℓ2^\ell \times 2^\ell2ℓ×2ℓ binary matrices specified compactly by a signature row and forming a commutative ring with recursive block structure. Leveraging this structure, we relate cycles in lifted Tanner graphs to tailless backtrackless closed walks in the protograph and derive efficient, implementable methods to enumerate and control short cycles (notably 444-, 666-, and 888-cycles). We introduce dyadic-aware PEG-style construction algorithms that use forbidden sets of shifts to maximize attainable girth when possible and otherwise minimize the multiplicity of the shortest cycles at the target girth. Motivated by error-floor phenomena, we further characterize and explicitly enumerate absorbing sets in key dyadic layout boundary cases, identifying configurations that induce abundant (a,0)(a,0)(a,0)-absorbing sets. Finally, we propose CSS-oriented dyadic constructions that satisfy commutation constraints by design and demonstrate via belief-propagation simulations that reducing short-cycle multiplicity can yield substantial decoding gains even when girth cannot be increased.
Quantum quasi-cyclic (QC) and quantum low-density parity-check (LDPC) codes have received significant attention due to their algebraic regularity and performance under low-complexity decoding. In this work, we explore a class of structured quantum codes based on reproducible matrices, which generalize known families such as cyclic, QC, and dyadic codes. Focusing on sparse quasi-dyadic (QD) structures, we investigate how their symmetries influence Tanner graph cycles. Moreover, we construct quantum LDPC codes within the Calderbank-Shor-Steane (CSS) framework, analyzing dual-containing configurations, and assess their error rates.
Quantum low-density parity-check (QLDPC) codes provide a practical balance between error-correction capability and implementation complexity in quantum error correction (QEC). In this paper, we propose an algebraic construction based on dyadic matrices for designing both classical and quantum LDPC codes. The method first generates classical binary quasi-dyadic LDPC codes whose Tanner graphs have girth 6. It is then extended to the Calderbank-Shor-Steane (CSS) framework, where the two component parity-check matrices are built to satisfy the compatibility condition required by the recently introduced CAMEL-ensemble quaternary belief propagation decoder. This compatibility condition ensures that all unavoidable cycles of length 4 are assembled in a single variable node, allowing the mitigation of their detrimental effects by decimating that variable node.
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.
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.
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.