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

IEEE Transactions on Communications

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

Massimo Battaglioni, Marco Baldi, Giovanni Cancellieri

Published Mar 29, 2018• 12 citations
Publisher

Abstract

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.

DOI
10.1109/tcomm.2018.2820702

Related papers

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

Design of Structured Regular LDPC Codes without Short Cycles using Gray Code Representations

Vibha Kulkarni, K. Jaya Sankar

Low Density Parity Check (LDPC) codes are specified by the parity check matrix H. Smaller girths in the Tanner graphs of LDPC codes prevent the sum-product algorithm from converging, i.e., short cycles in H-matrix degrade the performance of LDPC decoder. In this paper, we present an algorithm for constructing LDPC codes without short cycles. The H-matrix must be sufficiently sparse to increase the girth of a code. In this work, we present a simple method to increase the sparsity of matrix and provide lemmas to avoid short cycles of lengths 4 and 6. We design sub-matrices for column-weight two and column-weight three codes. This design makes use of a simple shifting function given by the proposed scheme. These are then combined into a final H-matrix using Gray code representations. The proposed method provides structured, regular codes with flexibility in code rates and code lengths. The regularity of these codes gives the advantages like simplicity of hardware implementation and fast encoding. Key words LDPC codes, Tanner Graph, Girth, Gray codes

•Jan 1, 2013•0 citations

Improving the minimum distance of QC-LDPC codes by removing cycles

Massimo Battaglioni, Marco Baldi, Giovanni Cancellieri

We focus on regular and irregular quasi-cyclic low-density parity-check codes and analyze their codewords. We show that any codeword can be decomposed into component codewords with smaller weight belonging to some component codes. Component codewords can be associated to cycles in the Tanner graph of the code. We transfer these theoretical results into the code design, finding that the removal of some specific classes of cycles yields benefits in terms of minimum distance and error rate performance.

AEIT International Annual Conference•Sep 23, 2020•3 citations

Girth analysis of polynomial-based time-invariant LDPC convolutional codes

Hua Ren Zhou, Norbert Goertz

Low-Density Parity-Check convolutional codes (LDPCccs) can be efficiently decoded by a pipelined sub-optimal Sum Product Algorithm. The latter may suffer, however, from convergence problems, due to cycles in the Tanner graph. To improve the decoding performance, we analyze the cycle properties, based on the connections between monomials in the polynomial syndrome former (transposed parity-check matrix in polynomial form) of time-invariant LDPCccs. Due to specific structures in the polynomial syndrome former, some cycles are unavoidable no matter what monomials are placed in the polynomial syndrome former. It is shown that large-weight entries in the polynomial syndrome former lead to small girth, while monomial or empty entries, which can break short unavoidable cycles, may result in large girth. A novel algorithm is proposed to generate “good” LDPCccs with respect to their cycle properties: destructive structures in the polynomial syndrome former leading to small girth are systematically avoided.

International Conference on Systems, Signals and Image Processing•Apr 11, 2012•8 citations

Edge-Coloring Technique to Analyze Elementary Trapping Sets of Spatially-Coupled LDPC Convolutional Codes

Mohammad‐Reza Sadeghi, Farzane Amirzade

In this letter, for the first time, an edge-coloring technique is proposed to characterize a certain elementary trapping set (ETS) and to obtain sufficient conditions to avoid small ETSs from occurrence in the Tanner graph of SC-LDPC convolutional codes. This technique is applicable to all protograph-based LDPC codes with different girths whose protographs are single-edge, that is, the entries of their base matrices are 0, 1. To further demonstrate the effectiveness of our proposed technique, we apply it to Time-Invariant SC-LDPC-CCs with girths 6 and 8 and column weights up to 5.

IEEE Communications Letters•Dec 27, 2019•15 citations

Decoding of LDPC convolutional codes with rational parity-check matrices from a new graphical perspective

Jian-Jia Weng, Chih-Chieh Lai, Chung-Hsuan Wang

Previous studies on low-density parity-check convolutional codes (LDPC-CC) reveal that LDPC-CC with rational parity-check matrices (RPCM) suffer from the unaffordable decoding latency/complexity due to the infinite memory order and the poor bit-error-rate performance due to the existence of length-4 cycles in the Tanner graph. However, in this paper, we show that every LDPC-CC with RPCM can be associated with an equivalent Tanner graph which can avoid the infinite memory order and undesired short length cycles but still implements the same constraints specified by the RPCM. Together with the iterative decoding based on belief propagation with proper scheduling, simulation results indicate that LDPC-CC with RPCM can also provide satisfactory decoding performance.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•4 citations
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.
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.
Low Density Parity Check (LDPC) codes are specified by the parity check matrix H. Smaller girths in the Tanner graphs of LDPC codes prevent the sum-product algorithm from converging, i.e., short cycles in H-matrix degrade the performance of LDPC decoder. In this paper, we present an algorithm for constructing LDPC codes without short cycles. The H-matrix must be sufficiently sparse to increase the girth of a code. In this work, we present a simple method to increase the sparsity of matrix and provide lemmas to avoid short cycles of lengths 4 and 6. We design sub-matrices for column-weight two and column-weight three codes. This design makes use of a simple shifting function given by the proposed scheme. These are then combined into a final H-matrix using Gray code representations. The proposed method provides structured, regular codes with flexibility in code rates and code lengths. The regularity of these codes gives the advantages like simplicity of hardware implementation and fast encoding. Key words LDPC codes, Tanner Graph, Girth, Gray codes
We focus on regular and irregular quasi-cyclic low-density parity-check codes and analyze their codewords. We show that any codeword can be decomposed into component codewords with smaller weight belonging to some component codes. Component codewords can be associated to cycles in the Tanner graph of the code. We transfer these theoretical results into the code design, finding that the removal of some specific classes of cycles yields benefits in terms of minimum distance and error rate performance.
Low-Density Parity-Check convolutional codes (LDPCccs) can be efficiently decoded by a pipelined sub-optimal Sum Product Algorithm. The latter may suffer, however, from convergence problems, due to cycles in the Tanner graph. To improve the decoding performance, we analyze the cycle properties, based on the connections between monomials in the polynomial syndrome former (transposed parity-check matrix in polynomial form) of time-invariant LDPCccs. Due to specific structures in the polynomial syndrome former, some cycles are unavoidable no matter what monomials are placed in the polynomial syndrome former. It is shown that large-weight entries in the polynomial syndrome former lead to small girth, while monomial or empty entries, which can break short unavoidable cycles, may result in large girth. A novel algorithm is proposed to generate “good” LDPCccs with respect to their cycle properties: destructive structures in the polynomial syndrome former leading to small girth are systematically avoided.
In this letter, for the first time, an edge-coloring technique is proposed to characterize a certain elementary trapping set (ETS) and to obtain sufficient conditions to avoid small ETSs from occurrence in the Tanner graph of SC-LDPC convolutional codes. This technique is applicable to all protograph-based LDPC codes with different girths whose protographs are single-edge, that is, the entries of their base matrices are 0, 1. To further demonstrate the effectiveness of our proposed technique, we apply it to Time-Invariant SC-LDPC-CCs with girths 6 and 8 and column weights up to 5.
Previous studies on low-density parity-check convolutional codes (LDPC-CC) reveal that LDPC-CC with rational parity-check matrices (RPCM) suffer from the unaffordable decoding latency/complexity due to the infinite memory order and the poor bit-error-rate performance due to the existence of length-4 cycles in the Tanner graph. However, in this paper, we show that every LDPC-CC with RPCM can be associated with an equivalent Tanner graph which can avoid the infinite memory order and undesired short length cycles but still implements the same constraints specified by the RPCM. Together with the iterative decoding based on belief propagation with proper scheduling, simulation results indicate that LDPC-CC with RPCM can also provide satisfactory decoding performance.