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•15 citations

Low-density parity-check codes: properties and constructions

Sarah J. Johnson

Introduction The construction of binary low-density parity-check (LDPC) codes simply involves replacing a small number of the values in an all-zeros matrix by 1s in such a way that the rows and columns have the required degree distribution. In many cases, randomly allocating the entries in H will produce a reasonable LDPC code. However, the construction of H can affect the performance of the sum–product decoder, significantly so for some codes, and also the implementation complexity of the code. While there is no one recipe for a “good” LDPC code, there are a number of principles that inform the code designer. The first obvious decisions are which degree distribution to choose and how to construct the matrix with the chosen degrees, i.e. pseudo-randomly or with some sort of structure. Whichever construction is chosen, the features to consider include the girth of the Tanner graph and the minimum distance of the code. In this chapter we will discuss those properties of an LDPC code that affect its iterative decoding performance and then present the common construction methods used to produce codes with the preferred properties. Following common practice in the field we will call the selection of the degree distributions for an LDPC code code design and the methods to assign the locations in the parity-check matrix for the 1 entries code construction .

Cambridge University Press eBooks•Nov 19, 2009•0 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

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•9 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

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
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.
Introduction The construction of binary low-density parity-check (LDPC) codes simply involves replacing a small number of the values in an all-zeros matrix by 1s in such a way that the rows and columns have the required degree distribution. In many cases, randomly allocating the entries in H will produce a reasonable LDPC code. However, the construction of H can affect the performance of the sum–product decoder, significantly so for some codes, and also the implementation complexity of the code. While there is no one recipe for a “good” LDPC code, there are a number of principles that inform the code designer. The first obvious decisions are which degree distribution to choose and how to construct the matrix with the chosen degrees, i.e. pseudo-randomly or with some sort of structure. Whichever construction is chosen, the features to consider include the girth of the Tanner graph and the minimum distance of the code. In this chapter we will discuss those properties of an LDPC code that affect its iterative decoding performance and then present the common construction methods used to produce codes with the preferred properties. Following common practice in the field we will call the selection of the degree distributions for an LDPC code code design and the methods to assign the locations in the parity-check matrix for the 1 entries code construction .
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.
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.
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.
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.