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

Spatially coupled quasi-cyclic quantum LDPC codes

Manabu Hagiwara, Kenta Kasai, Hideki Imai, Kohichi Sakaniwa

Published Jul 1, 2011• 59 citations
arXivHTMLPDF

Abstract

For designing low-density parity-check (LDPC) codes for quantum error-correction, we desire to satisfy the conflicting requirements below simultaneously. 1) The row weights of parity-check “should be large”: The minimum distances are bounded above by the minimum row weights of parity-check matrices of constituent classical codes. Small minimum distance tends to result in poor decoding performance at the error-floor region. 2) The row weights of parity-check matrices “should not be large”: The performance of the sum-product decoding algorithm at the water-fall region is degraded as the row weight increases. Recently, Kudekar et al. showed spatially-coupled (SC) LDPC codes exhibit capacity-achieving performance for classical channels. SC LDPC codes have both large row weight and capacity-achieving error-floor and water-fall performance. In this paper, we propose a new class of quantum LDPC codes based on spatially coupled quasi-cyclic LDPC codes. The performance outperforms that of quantum “non-coupled” quasi-cyclic LDPC codes.

DOI
10.1109/isit.2011.6034208

Related papers

Can cyclic codes be useful low-density parity-check codes?

Sarah J. Johnson, Steven R. Weller

Traditionally, low-density parity-check (LDPC) codes are constructed randomly and it is not clear whether algebraically constructed codes, such as cyclic codes, can compete with the error correction performances of the random codes. We consider in this paper new cyclic low-density parity-check codes decoded with the sum-product algorithm. The cyclic codes we present have sparse parity-check matrices, good minimum distance and girth 6. Using frnite-length analysis and simulation results we show that the most significant benefit of the new codes, in terms of error correction performance, is the linearly dependent rows in their parity-check matrices. Our results suggest that increasing column weight to improve the minimum distance and the minimum stopping set size of the code proves beneficial at low erasure probabilities but adversely affects performance in channels with high erasure probabilities.

•Jan 1, 2003•1 citation

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

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

Explicit Construction of Quantum Quasi-Cyclic Low-Density Parity-Check Codes with Column Weight 2 and Girth 12

Daiki Komoto, Kenta Kasai

This study proposes an explicit construction method for quantum quasi-cyclic low-density parity-check (QC-LDPC) codes with a girth of 12. The proposed method designs parity-check matrices that maximize the girth while maintaining an orthogonal structure suitable for quantum error correction. By utilizing algebraic techniques, short cycles are eliminated, which improves error correction performance. Additionally, this method is extended to non-binary LDPC codes and spatially-coupled LDPC codes, demonstrating that both the girth and orthogonality can be preserved. The results of this study enable the design of high-performance quantum error-correcting codes without the need for random search.

arXiv:2501.13444•Jan 23, 2025•0 citations

Construction of Quasi-Cyclic GF(q)-LDPC Codes Achieving the Upper Bound on the Minimum Hamming Distance

Xinmei Wang

In order to construct nonbinary low-density parity-check(LDPC) codes with good waterfall and error floor properties,a method to improve the minimum Hamming distance of a class of nonbinary quasi-cyclic(QC) LDPC codes is presented.Two upper bounds on the minimum Hamming distance are derived for the nonbinary QC LDPC codes whose parity-check matrices consist of weight-2 columns.A special base matrix design allowing linear encoding in a parallel manner is also proposed.In addition,the design principals are given,according to which,the parallel and efficiently encodable codes reaching the upper bound on the minimum Hamming distance can be developed.Simulation shows that the proposed codes have both good waterfall and error floor properties.

Beijing Youdian Xueyuan xuebao•Jan 1, 2012•0 citations

Error Floor Analysis of Quasi-Cyclic LDPC and Spatially Coupled-LDPC Codes and Construction of Codes with Low Error Floor

Sima Naseri

Forward error-correcting (FEC) codes play an important role in transmitting data with extremely high reliability through modern communication systems.Many applications such as optical communication channels require a very low error rate when transmitting data.In this thesis, we study the design and analysis of low-density parity-check (LDPC) codes in general and spatially coupled (SC) LDPC codes in particular.At first, we analyze the error floor performance of finite-length protographbased spatially coupled LDPC codes in terms of their design parameters.We conduct a comprehensive analysis to show that the parameter syndrome former memory (m) plays the main role in the average number of cycles and trapping sets in the Tanner graph of finite-length SC-LDPC codes.This, in fact, gives an insight into the error floor performance of protograph-based SC-LDPC codes, and demonstrates the superiority of these codes in the error floor region, compared to their block code counterparts.To complement the theoretical analysis conducted in the first stage of this research, we develop efficient design techniques for the construction of high-performance quasi-cyclic (QC)-LDPC and SC-LDPC codes, as the second part of the research.Our design approach is basically aimed at improving the performance of finite-length (SC) LDPC codes while maintaining the decoder complexity and latency small.The improvement in error floor is achieved by minimizing (elimination of) the most harmful trapping set (TS)s.In this regard, we present two design approaches: i) imposing simple conditions on the small cycles to result in the elimination of specific classes of trapping sets, ii) developing a search-based design technique such that specific trapping sets are targeted for minimization/elimination through the algorithm.Our constructed QC-LDPC and time-invariant SC-LDPC codes are superior to the stateof-the-art both in terms of their error floor performance and their low decoding latency and complexity.Finally, we look into the design of finite-length time-invariant QC SC-LDPC codes iii I would like to take this opportunity to express my sincere gratitude to my supervisor, Prof. Amir H. Banihashemi, for his invaluable guidance, continuous support and excellent mentorship during the course of my PhD studies.His immense knowledge and supervision always steered me to the right direction during this journey.Besides my supervisor, I would like to thank my committee members for their helpful comments and feedback on this thesis, and for their generosity in contributing their time to serve on my dissertation defense.I would like to mention the government of Ontario in acknowledgment of the Ontario Trillium Scholarship which pledged an ample

•Jan 1, 2021•2 citations
For designing low-density parity-check (LDPC) codes for quantum error-correction, we desire to satisfy the conflicting requirements below simultaneously. 1) The row weights of parity-check “should be large”: The minimum distances are bounded above by the minimum row weights of parity-check matrices of constituent classical codes. Small minimum distance tends to result in poor decoding performance at the error-floor region. 2) The row weights of parity-check matrices “should not be large”: The performance of the sum-product decoding algorithm at the water-fall region is degraded as the row weight increases. Recently, Kudekar et al. showed spatially-coupled (SC) LDPC codes exhibit capacity-achieving performance for classical channels. SC LDPC codes have both large row weight and capacity-achieving error-floor and water-fall performance. In this paper, we propose a new class of quantum LDPC codes based on spatially coupled quasi-cyclic LDPC codes. The performance outperforms that of quantum “non-coupled” quasi-cyclic LDPC codes.
Traditionally, low-density parity-check (LDPC) codes are constructed randomly and it is not clear whether algebraically constructed codes, such as cyclic codes, can compete with the error correction performances of the random codes. We consider in this paper new cyclic low-density parity-check codes decoded with the sum-product algorithm. The cyclic codes we present have sparse parity-check matrices, good minimum distance and girth 6. Using frnite-length analysis and simulation results we show that the most significant benefit of the new codes, in terms of error correction performance, is the linearly dependent rows in their parity-check matrices. Our results suggest that increasing column weight to improve the minimum distance and the minimum stopping set size of the code proves beneficial at low erasure probabilities but adversely affects performance in channels with high erasure probabilities.
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.
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 study proposes an explicit construction method for quantum quasi-cyclic low-density parity-check (QC-LDPC) codes with a girth of 12. The proposed method designs parity-check matrices that maximize the girth while maintaining an orthogonal structure suitable for quantum error correction. By utilizing algebraic techniques, short cycles are eliminated, which improves error correction performance. Additionally, this method is extended to non-binary LDPC codes and spatially-coupled LDPC codes, demonstrating that both the girth and orthogonality can be preserved. The results of this study enable the design of high-performance quantum error-correcting codes without the need for random search.
In order to construct nonbinary low-density parity-check(LDPC) codes with good waterfall and error floor properties,a method to improve the minimum Hamming distance of a class of nonbinary quasi-cyclic(QC) LDPC codes is presented.Two upper bounds on the minimum Hamming distance are derived for the nonbinary QC LDPC codes whose parity-check matrices consist of weight-2 columns.A special base matrix design allowing linear encoding in a parallel manner is also proposed.In addition,the design principals are given,according to which,the parallel and efficiently encodable codes reaching the upper bound on the minimum Hamming distance can be developed.Simulation shows that the proposed codes have both good waterfall and error floor properties.
Forward error-correcting (FEC) codes play an important role in transmitting data with extremely high reliability through modern communication systems.Many applications such as optical communication channels require a very low error rate when transmitting data.In this thesis, we study the design and analysis of low-density parity-check (LDPC) codes in general and spatially coupled (SC) LDPC codes in particular.At first, we analyze the error floor performance of finite-length protographbased spatially coupled LDPC codes in terms of their design parameters.We conduct a comprehensive analysis to show that the parameter syndrome former memory (m) plays the main role in the average number of cycles and trapping sets in the Tanner graph of finite-length SC-LDPC codes.This, in fact, gives an insight into the error floor performance of protograph-based SC-LDPC codes, and demonstrates the superiority of these codes in the error floor region, compared to their block code counterparts.To complement the theoretical analysis conducted in the first stage of this research, we develop efficient design techniques for the construction of high-performance quasi-cyclic (QC)-LDPC and SC-LDPC codes, as the second part of the research.Our design approach is basically aimed at improving the performance of finite-length (SC) LDPC codes while maintaining the decoder complexity and latency small.The improvement in error floor is achieved by minimizing (elimination of) the most harmful trapping set (TS)s.In this regard, we present two design approaches: i) imposing simple conditions on the small cycles to result in the elimination of specific classes of trapping sets, ii) developing a search-based design technique such that specific trapping sets are targeted for minimization/elimination through the algorithm.Our constructed QC-LDPC and time-invariant SC-LDPC codes are superior to the stateof-the-art both in terms of their error floor performance and their low decoding latency and complexity.Finally, we look into the design of finite-length time-invariant QC SC-LDPC codes iii I would like to take this opportunity to express my sincere gratitude to my supervisor, Prof. Amir H. Banihashemi, for his invaluable guidance, continuous support and excellent mentorship during the course of my PhD studies.His immense knowledge and supervision always steered me to the right direction during this journey.Besides my supervisor, I would like to thank my committee members for their helpful comments and feedback on this thesis, and for their generosity in contributing their time to serve on my dissertation defense.I would like to mention the government of Ontario in acknowledgment of the Ontario Trillium Scholarship which pledged an ample