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

Cambridge University Press eBooks

SP-Construction of Spatially Coupled QC-LDPC Codes

Juane Li, Shu Wen Lin, Khaled Abdel-Ghaffar, W.E. Ryan, Daniel J. Costello

Published Dec 1, 2016• 0 citations
Publisher

Abstract

In this chapter, we present an algebraic construction of a special type of LDPC code whose Tanner graph has a very specific structure. For an LDPC code of this type, its Tanner graph is locally connected . Every VN is only connected to the CNs that are confined to a (small) span of ρ col consecutive locations and every CN is only connected to VNs that are confined to a (small) span of ρ row consecutive locations . We call such constraints on the connections between VNs and CNs of a Tanner graph ( ρ col ,ρ row) -span-constraints . With this span-constraint, the Tanner graph of such an LDPC code is actually a chain of small Tanner graphs in which each graph is connected to its adjacent graphs on either side of it, except the first and the last ones. An LDPC code of this type is called a span-constrained LDPC code. The SC-LDPC code investigated in [59, 60, 22, 86] is a type of span-constrained LDPC code. An SC-LDPC code is an LDPC convolutional (LDPC-C) code viewed from a graphical point of view (or a spatial coupling point of view) [49, 104, 66, 67, 92]. An LDPC-C code [49, 104] is specified by a bi-infinite parity-check matrix whose nonzero entries are confined to a diagonal band of a certain width ρ row and a certain depth ρ col. The nonzero entries in every row are confined to a span of ρ row consecutive locations and the nonzero entries in every column are confined to a span of ρ col consecutive locations. With these constraints on the locations of the nonzero entries of the parity-check matrix of an LDPC-C code, every VN in its Tanner graph is only connected to the CNs that are confined to a span of ρ col consecutive locations and every CN is only connected to VNs that are confined to a span of ρ row consecutive locations. These constraints on the locations of the nonzero entries of the parity-check matrix of an LDPC-C code lead to the graphical ( ρ col ,ρ row)-span-constraint as mentioned above. Hence, an LDPC-C code is a span-constrained LDPC code, an SC-LDPC code.

DOI
10.1017/9781316780152.010

Related papers

Trapping sets of structured LDPC codes

Qin Huang, Qiuju Diao, Shu Lin +1 more

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. This paper analyzes trapping set structure of binary regular LDPC codes whose parity-check matrices satisfy the constraint that no two rows (or two columns) have more than one place where they both have non-zero components, which is called row-column (RC) constraint. For a (γ,ρ)-regular LDPC code whose parity-check matrix satisfies the RC-constraint, its Tanner graph contains no (κ, τ) trapping set with size κ ≤ γ and number τ of odd degree check nodes less than γ. For several classes of RC-constrained regular LDPC codes constructed algebraically, we show that their Tanner graphs contain no trapping sets of sizes smaller than their minimum weights.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•16 citations

Time-invariant spatially coupled low-density parity-check codes with small constraint length

Marco Baldi, Massimo Battaglioni, Franco Chiaraluce +1 more

We consider a special family of spatially coupled low-density parity-check (SC-LDPC) codes, that is, time-invariant low-density parity-check convolutional (LDPCC) codes, which are known in the literature for a long time. Codes of this kind are usually designed by starting from quasi-cyclic (QC) block codes, and applying suitable unwrapping procedures. We show that, by directly designing the LDPCC code syndrome former matrix without the constraints of the underlying QC block code, it is possible to achieve smaller constraint lengths with respect to the best solutions available in the literature. We also find theoretical lower bounds on the syndrome former constraint length for codes with a specified minimum length of the local cycles in their Tanner graphs. For this purpose, we exploit a new approach based on a numerical representation of the syndrome former matrix, which generalizes over a technique we already used to study a special subclass of the codes here considered.

arXiv:1605.05560•IEEE International Black Sea Conference on Communications and Networking•Jan 1, 2016•4 citations

Flexible Construction of High-Girth QC-LDPC Codes

Gabofetswe Malema

This article presents a highly flexible method for constructing high-girth quasi-cyclic low-density parity-check (QC-LDPC) codes. The proposed algorithm constructs a Tanner graph formed by connecting groups of rows (check nodes) and columns (variable nodes) of the constructed code. To obtain a sub-matrix structure, rows and columns are divided into groups of equal sizes. Rows and columns in a group are connected in their numerical (positional) order to obtain a cyclic structure. Connected rows and columns must satisfy the desired minimum cycle length. We present conditions that guarantee desired girths. The proposed algorithm is by far more flexible in constructing a wide range (rates and lengths) of regular and irregular QC-LDPC codes compared to existing methods. The algorithm, which has linear complexity with respect to the number of rows or columns, provides an easy and fast way to construct QC-LDPC codes. Constructed codes show good bit error rate performances.

International journal of computer science and applications•Aug 1, 2012•2 citations

Construction of Structured Nonbinary Low-Density Parity-Check Codes

Wojciech Sułek

Low Density Parity Check (LDPC) codes over nonbinary Galois Fields GF(q) are a generalization of the industrial standard binary LDPC codes for forward error correction in communication and information systems.The nonbinary codes can achieve significantly better performance for short and moderate block lengths.A lot of works concerning "good" LDPC codes parity check matrix construction has been published so far.However, it is well known that efficient partially parallel hardware decoder architectures are allowed only for codes with blockwise partitioned structure of the parity check matrix, called structured codes.In this paper we present a versatile algorithm for construction of codes that are both nonbinary and structured.The proposed algorithm aims at optimizing the code graph (Tanner graph) by reducing the existence of small cycles with low external connectivity, while at the same time selecting appropriate nonzero coefficients from the Galois Field under interest.The algorithm can be used for code construction of any field order, block length and code rate.

International Journal of e-Education e-Business e-Management and e-Learning•Jan 1, 2013•0 citations

Connections Between Low-Weight Codewords and Cycles in Spatially Coupled LDPC Convolutional Codes

Massimo Battaglioni, Marco Baldi, Giovanni Cancellieri

In this paper, time-invariant spatially coupled low-density parity-check convolutional codes (SC-LDPC-CCs) are considered, and the connections existing between their low-weight codewords and cycles in their Tanner graphs are studied. Using the polynomial representation of these codes, we show that parity-check matrices having columns with weight ≥2 can be analyzed considering a certain number of parity-check sub-matrices having regular columns with weight 2. These sub-matrices are associated to cycles in the code Tanner graph and define as many codes we denote as component codes. Based on this observation, we find that codewords of the main code can be expressed as combinations of codewords of the component codes. The design of codes free of codewords up to a certain weight is also addressed. We show that low-weight codewords in the main code can be avoided by removing some types of cycles in its Tanner graph. Our design approach is applied to some well-known ensembles of SC-LDPC-CCs to prove its effectiveness.

IEEE Transactions on Communications•Mar 29, 2018•11 citations

Spatially-Coupled QLDPC Codes

Siyi Yang, Robert Calderbank

Spatially-coupled (SC) codes is a class of convolutional LDPC codes that has been well investigated in classical coding theory thanks to their high performance and compatibility with low-latency decoders. We describe toric codes as quantum counterparts of classical two-dimensional spatially-coupled (2D-SC) codes, and introduce spatially-coupled quantum LDPC (SC-QLDPC) codes as a generalization. We use the convolutional structure to represent the parity check matrix of a 2D-SC code as a polynomial in two indeterminates, and derive an algebraic condition that is both necessary and sufficient for a 2D-SC code to be a stabilizer code. This algebraic framework facilitates the construction of new code families. While not the focus of this paper, we note that small memory facilitates physical connectivity of qubits, and it enables local encoding and low-latency windowed decoding. In this paper, we use the algebraic framework to optimize short cycles in the Tanner graph of 2D-SC hypergraph product (HGP) codes that arise from short cycles in either component code. While prior work focuses on QLDPC codes with rate less than 1/10, we construct 2D-SC HGP codes with small memories, higher rates (about 1/3), and superior thresholds.

arXiv:2305.00137•Quantum•Apr 7, 2025•21 citations
In this chapter, we present an algebraic construction of a special type of LDPC code whose Tanner graph has a very specific structure. For an LDPC code of this type, its Tanner graph is locally connected . Every VN is only connected to the CNs that are confined to a (small) span of ρ col consecutive locations and every CN is only connected to VNs that are confined to a (small) span of ρ row consecutive locations . We call such constraints on the connections between VNs and CNs of a Tanner graph ( ρ col ,ρ row) -span-constraints . With this span-constraint, the Tanner graph of such an LDPC code is actually a chain of small Tanner graphs in which each graph is connected to its adjacent graphs on either side of it, except the first and the last ones. An LDPC code of this type is called a span-constrained LDPC code. The SC-LDPC code investigated in [59, 60, 22, 86] is a type of span-constrained LDPC code. An SC-LDPC code is an LDPC convolutional (LDPC-C) code viewed from a graphical point of view (or a spatial coupling point of view) [49, 104, 66, 67, 92]. An LDPC-C code [49, 104] is specified by a bi-infinite parity-check matrix whose nonzero entries are confined to a diagonal band of a certain width ρ row and a certain depth ρ col. The nonzero entries in every row are confined to a span of ρ row consecutive locations and the nonzero entries in every column are confined to a span of ρ col consecutive locations. With these constraints on the locations of the nonzero entries of the parity-check matrix of an LDPC-C code, every VN in its Tanner graph is only connected to the CNs that are confined to a span of ρ col consecutive locations and every CN is only connected to VNs that are confined to a span of ρ row consecutive locations. These constraints on the locations of the nonzero entries of the parity-check matrix of an LDPC-C code lead to the graphical ( ρ col ,ρ row)-span-constraint as mentioned above. Hence, an LDPC-C code is a span-constrained LDPC code, an SC-LDPC code.
THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. This paper analyzes trapping set structure of binary regular LDPC codes whose parity-check matrices satisfy the constraint that no two rows (or two columns) have more than one place where they both have non-zero components, which is called row-column (RC) constraint. For a (γ,ρ)-regular LDPC code whose parity-check matrix satisfies the RC-constraint, its Tanner graph contains no (κ, τ) trapping set with size κ ≤ γ and number τ of odd degree check nodes less than γ. For several classes of RC-constrained regular LDPC codes constructed algebraically, we show that their Tanner graphs contain no trapping sets of sizes smaller than their minimum weights.
We consider a special family of spatially coupled low-density parity-check (SC-LDPC) codes, that is, time-invariant low-density parity-check convolutional (LDPCC) codes, which are known in the literature for a long time. Codes of this kind are usually designed by starting from quasi-cyclic (QC) block codes, and applying suitable unwrapping procedures. We show that, by directly designing the LDPCC code syndrome former matrix without the constraints of the underlying QC block code, it is possible to achieve smaller constraint lengths with respect to the best solutions available in the literature. We also find theoretical lower bounds on the syndrome former constraint length for codes with a specified minimum length of the local cycles in their Tanner graphs. For this purpose, we exploit a new approach based on a numerical representation of the syndrome former matrix, which generalizes over a technique we already used to study a special subclass of the codes here considered.
This article presents a highly flexible method for constructing high-girth quasi-cyclic low-density parity-check (QC-LDPC) codes. The proposed algorithm constructs a Tanner graph formed by connecting groups of rows (check nodes) and columns (variable nodes) of the constructed code. To obtain a sub-matrix structure, rows and columns are divided into groups of equal sizes. Rows and columns in a group are connected in their numerical (positional) order to obtain a cyclic structure. Connected rows and columns must satisfy the desired minimum cycle length. We present conditions that guarantee desired girths. The proposed algorithm is by far more flexible in constructing a wide range (rates and lengths) of regular and irregular QC-LDPC codes compared to existing methods. The algorithm, which has linear complexity with respect to the number of rows or columns, provides an easy and fast way to construct QC-LDPC codes. Constructed codes show good bit error rate performances.
Low Density Parity Check (LDPC) codes over nonbinary Galois Fields GF(q) are a generalization of the industrial standard binary LDPC codes for forward error correction in communication and information systems.The nonbinary codes can achieve significantly better performance for short and moderate block lengths.A lot of works concerning "good" LDPC codes parity check matrix construction has been published so far.However, it is well known that efficient partially parallel hardware decoder architectures are allowed only for codes with blockwise partitioned structure of the parity check matrix, called structured codes.In this paper we present a versatile algorithm for construction of codes that are both nonbinary and structured.The proposed algorithm aims at optimizing the code graph (Tanner graph) by reducing the existence of small cycles with low external connectivity, while at the same time selecting appropriate nonzero coefficients from the Galois Field under interest.The algorithm can be used for code construction of any field order, block length and code rate.
In this paper, time-invariant spatially coupled low-density parity-check convolutional codes (SC-LDPC-CCs) are considered, and the connections existing between their low-weight codewords and cycles in their Tanner graphs are studied. Using the polynomial representation of these codes, we show that parity-check matrices having columns with weight ≥2 can be analyzed considering a certain number of parity-check sub-matrices having regular columns with weight 2. These sub-matrices are associated to cycles in the code Tanner graph and define as many codes we denote as component codes. Based on this observation, we find that codewords of the main code can be expressed as combinations of codewords of the component codes. The design of codes free of codewords up to a certain weight is also addressed. We show that low-weight codewords in the main code can be avoided by removing some types of cycles in its Tanner graph. Our design approach is applied to some well-known ensembles of SC-LDPC-CCs to prove its effectiveness.
Spatially-coupled (SC) codes is a class of convolutional LDPC codes that has been well investigated in classical coding theory thanks to their high performance and compatibility with low-latency decoders. We describe toric codes as quantum counterparts of classical two-dimensional spatially-coupled (2D-SC) codes, and introduce spatially-coupled quantum LDPC (SC-QLDPC) codes as a generalization. We use the convolutional structure to represent the parity check matrix of a 2D-SC code as a polynomial in two indeterminates, and derive an algebraic condition that is both necessary and sufficient for a 2D-SC code to be a stabilizer code. This algebraic framework facilitates the construction of new code families. While not the focus of this paper, we note that small memory facilitates physical connectivity of qubits, and it enables local encoding and low-latency windowed decoding. In this paper, we use the algebraic framework to optimize short cycles in the Tanner graph of 2D-SC hypergraph product (HGP) codes that arise from short cycles in either component code. While prior work focuses on QLDPC codes with rate less than 1/10, we construct 2D-SC HGP codes with small memories, higher rates (about 1/3), and superior thresholds.