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 Information Theory

Distance Bounds for Periodically Time-Varying and Tail-Biting LDPC Convolutional Codes

Dmitri V. Truhachev, Kamil Sh. Zigangirov, Daniel J. Costello

Published Aug 19, 2010• 26 citations
Publisher

Abstract

Existence type lower bounds on the free distance of periodically time-varying LDPC convolutional codes and on the minimum distance of tail-biting LDPC convolutional codes are derived. It is demonstrated that the bound on free distance of periodically time-varying LDPC convolutional codes approaches the bound on free distance of general (nonperiodic) time-varying LDPC convolutional codes as the period increases. The proof of the bound is based on lower bounding the minimum distance of corresponding tail-biting LDPC convolutional codes, which is of interest in its own right.

DOI
10.1109/tit.2010.2053873

Related papers

Exact free distance and trapping set growth rates for LDPC convolutional codes

David G. M. Mitchell, Alí Emre Pusane, Michael Lentmaier +1 more

Ensembles of (J,K)-regular low-density parity-check convolutional (LDPCC) codes are known to be asymptotically good, in the sense that the minimum free distance grows linearly with the constraint length. In this paper, we use a protograph-based analysis of terminated LDPCC codes to obtain an upper bound on the free distance growth rate of ensembles of periodically time-varying LDPCC codes. This bound is compared to a lower bound and evaluated numerically. It is found that, for a sufficiently large period, the bounds coincide. This approach is then extended to obtain bounds on the trapping set numbers, which define the size of the smallest, non-empty trapping sets, for these asymptotically good, periodically time-varying LDPCC code ensembles.

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

Distance Bounds for an Ensemble of LDPC Convolutional Codes

Arvind Sridharan, Dmitri V. Truhachev, Michael Lentmaier +2 more

An ensemble of$(J,K)$-regular low-density parity- check (LDPC) convolutional codes is introduced and existence-type lower bounds on the minimum distance$d _ {\rm L}$of code segments of finite length$L$and on the free distance$d _{\rm free}$are derived. For sufficiently large constraint lengths$\nu$, the distances are shown to grow linearly with$\nu$and the ratio$d_ {\rm L}/\nu$approaches the ratio$d _{ {\rm free}}/\nu$for large$L$. Moreover, the ratio of free distance to constraint length is several times larger than the ratio of minimum distance to block length for Gallager's ensemble of (J,K)-regular LDPC block codes.

IEEE Transactions on Information Theory•Dec 1, 2007•49 citations

Bounds on the Free Distance of Periodically Time-Varying SC-LDPC Codes

Massimo Battaglioni, Marco Baldi, Franco Chiaraluce

Time-invariant spatially coupled low-density parity-check (TI-SC-LDPC) codes can be obtained by unwrapping quasi-cyclic (QC) LDPC block codes. This results in a free distance that is lower bounded by the minimum distance of the underlying QC-LDPC block codes. By introducing some variability in the syndrome former matrix, time-varying (TV) SC-LDPC codes are obtained, which trade an improved error correction performance for an increased decoding memory requirement and decoding complexity. A family of codes able to combine the advantages of TI-SC-LDPC codes with those of TV-SC-LDPC codes is that of periodically time-varying (PTV) SC-LDPC codes, based on a finite and periodic variation of the syndrome former matrix. In this paper we focus on such codes, and derive new upper bounds on the free distance of PTV-SC-LDPC code ensembles as well as on specific codes. By using these bounds, we show that PTV-SC-LDPC codes can achieve important improvements in the free distance over TI-SC-LDPC codes even using a very small period of variability, which corresponds to a minimal increase in memory and complexity. We also validate the new upper bounds through numerical experiments and assess the error correction performance of the corresponding codes through Monte Carlo simulations.

IEEE Transactions on Information Theory•Feb 5, 2024•4 citations

Free distance bounds for protograph-based regular LDPC convolutional codes

David G. M. Mitchell, Alí Emre Pusane, Norbert Goertz +1 more

In this paper, asymptotic methods are used to form lower bounds on the free distance to constraint length ratio of several ensembles of regular, asymptotically good, protograph-based LDPC convolutional codes. In particular, we show that the free distance to constraint length ratio of the regular LDPC convolutional codes exceeds that of the minimum distance to block length ratio of the corresponding LDPC block codes.

arXiv:0804.4466•International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2008•12 citations

Graph-based convolutional and block LDPC codes

Irina E. Bocharova, Boris D. Kudryashov, Roman V. Satyukov

We consider regular block and convolutional LDPC codes determined by paritycheck matrices with rows of a fixed weight and columns of weight 2. Such codes can be described by graphs, and the minimum distance of a code coincides with the girth of the corresponding graph. We consider a description of such codes in the form of tail-biting convolutional codes. Long codes are constructed from short ones using the “voltage graph” method. On this way we construct new codes, find a compact description for many known optimal codes, and thus simplify the coding for such codes. We obtain an asymptotic lower bound on the girth of the corresponding graphs. We also present tables of codes.

Problems of Information Transmission•Dec 1, 2009•12 citations

Design and Analysis of LDPC Convolutional Codes

Arvind Sridharan

Low-density parity-check (LDPC) block codes invented by Gallager in 1962 achieve exceptional error performance on a wide variety of communication channels. LDPC convolutional codes are the convolutional counterparts of LDPC block codes. This dissertation describes techniques for the design of LDPC convolutional codes, and analyzes their distance properties and iterative decoding convergence thresholds. The construction of time invariant LDPC convolutional codes by unwrapping the Tanner graph of algebraically constructed quasi-cyclic LDPC codes is described. The convolutional codes outperform the quasi-cyclic codes from which they are derived. The design of parity-check matrices for time invariant LDPC convolutional codes by the polynomial extension of a base matrix is proposed. An upper bound on free distance, proving that time invariant LDPC codes are not asymptotically good, is obtained. The Tanner graph is used to describe a pipelined message passing based iterative decoder for LDPC convolutional codes that outputs decoding results continuously. The performance of LDPC block and convolutional codes are compared for fixed decoding parameters like computational complexity, processor complexity, and decoding delay. In each case, the LDPC convolutional code performance is at least as good as that of LDPC block codes. An analog circuit to implement pipelined decoding of LDPC convolutional codes is proposed. The distance properties of a permutation matrix based (time varying) ensemble of (J,K) regular LDPC convolutional codes is investigated. It is proved that these codes (for J > 2) have free distance increasing linearly with constraint length, i.e., they are asymptotically good. Further, the asymptotic free distance to constraint length ratio for the convolutional codes is several times larger than the minimum distance to block length ratio for corresponding LDPC block codes. Iterative decoding of terminated LDPC convolutional codes, based on the ensemble mentioned above, is analyzed, assuming transmission over a binary erasure channel. The structured irregularity of the codes leads to significantly better convergence thresholds compared to corresponding LDPC block codes. At the calculated thresholds, both the bit and block error probability can be made arbitrarily small. The results obtained suggest that the thresholds approach capacity with increasing J.

•Sep 15, 2022•30 citations
Existence type lower bounds on the free distance of periodically time-varying LDPC convolutional codes and on the minimum distance of tail-biting LDPC convolutional codes are derived. It is demonstrated that the bound on free distance of periodically time-varying LDPC convolutional codes approaches the bound on free distance of general (nonperiodic) time-varying LDPC convolutional codes as the period increases. The proof of the bound is based on lower bounding the minimum distance of corresponding tail-biting LDPC convolutional codes, which is of interest in its own right.
Ensembles of (J,K)-regular low-density parity-check convolutional (LDPCC) codes are known to be asymptotically good, in the sense that the minimum free distance grows linearly with the constraint length. In this paper, we use a protograph-based analysis of terminated LDPCC codes to obtain an upper bound on the free distance growth rate of ensembles of periodically time-varying LDPCC codes. This bound is compared to a lower bound and evaluated numerically. It is found that, for a sufficiently large period, the bounds coincide. This approach is then extended to obtain bounds on the trapping set numbers, which define the size of the smallest, non-empty trapping sets, for these asymptotically good, periodically time-varying LDPCC code ensembles.
An ensemble of(J,K)(J,K)(J,K)-regular low-density parity- check (LDPC) convolutional codes is introduced and existence-type lower bounds on the minimum distancedLd _ {\rm L}dL​of code segments of finite lengthLLLand on the free distancedfreed _{\rm free}dfree​are derived. For sufficiently large constraint lengthsν\nuν, the distances are shown to grow linearly withν\nuνand the ratiodL/νd_ {\rm L}/\nudL​/νapproaches the ratiodfree/νd _{ {\rm free}}/\nudfree​/νfor largeLLL. Moreover, the ratio of free distance to constraint length is several times larger than the ratio of minimum distance to block length for Gallager's ensemble of (J,K)-regular LDPC block codes.
Time-invariant spatially coupled low-density parity-check (TI-SC-LDPC) codes can be obtained by unwrapping quasi-cyclic (QC) LDPC block codes. This results in a free distance that is lower bounded by the minimum distance of the underlying QC-LDPC block codes. By introducing some variability in the syndrome former matrix, time-varying (TV) SC-LDPC codes are obtained, which trade an improved error correction performance for an increased decoding memory requirement and decoding complexity. A family of codes able to combine the advantages of TI-SC-LDPC codes with those of TV-SC-LDPC codes is that of periodically time-varying (PTV) SC-LDPC codes, based on a finite and periodic variation of the syndrome former matrix. In this paper we focus on such codes, and derive new upper bounds on the free distance of PTV-SC-LDPC code ensembles as well as on specific codes. By using these bounds, we show that PTV-SC-LDPC codes can achieve important improvements in the free distance over TI-SC-LDPC codes even using a very small period of variability, which corresponds to a minimal increase in memory and complexity. We also validate the new upper bounds through numerical experiments and assess the error correction performance of the corresponding codes through Monte Carlo simulations.
We consider regular block and convolutional LDPC codes determined by paritycheck matrices with rows of a fixed weight and columns of weight 2. Such codes can be described by graphs, and the minimum distance of a code coincides with the girth of the corresponding graph. We consider a description of such codes in the form of tail-biting convolutional codes. Long codes are constructed from short ones using the “voltage graph” method. On this way we construct new codes, find a compact description for many known optimal codes, and thus simplify the coding for such codes. We obtain an asymptotic lower bound on the girth of the corresponding graphs. We also present tables of codes.
Low-density parity-check (LDPC) block codes invented by Gallager in 1962 achieve exceptional error performance on a wide variety of communication channels. LDPC convolutional codes are the convolutional counterparts of LDPC block codes. This dissertation describes techniques for the design of LDPC convolutional codes, and analyzes their distance properties and iterative decoding convergence thresholds. The construction of time invariant LDPC convolutional codes by unwrapping the Tanner graph of algebraically constructed quasi-cyclic LDPC codes is described. The convolutional codes outperform the quasi-cyclic codes from which they are derived. The design of parity-check matrices for time invariant LDPC convolutional codes by the polynomial extension of a base matrix is proposed. An upper bound on free distance, proving that time invariant LDPC codes are not asymptotically good, is obtained. The Tanner graph is used to describe a pipelined message passing based iterative decoder for LDPC convolutional codes that outputs decoding results continuously. The performance of LDPC block and convolutional codes are compared for fixed decoding parameters like computational complexity, processor complexity, and decoding delay. In each case, the LDPC convolutional code performance is at least as good as that of LDPC block codes. An analog circuit to implement pipelined decoding of LDPC convolutional codes is proposed. The distance properties of a permutation matrix based (time varying) ensemble of (J,K) regular LDPC convolutional codes is investigated. It is proved that these codes (for J > 2) have free distance increasing linearly with constraint length, i.e., they are asymptotically good. Further, the asymptotic free distance to constraint length ratio for the convolutional codes is several times larger than the minimum distance to block length ratio for corresponding LDPC block codes. Iterative decoding of terminated LDPC convolutional codes, based on the ensemble mentioned above, is analyzed, assuming transmission over a binary erasure channel. The structured irregularity of the codes leads to significantly better convergence thresholds compared to corresponding LDPC block codes. At the calculated thresholds, both the bit and block error probability can be made arbitrarily small. The results obtained suggest that the thresholds approach capacity with increasing J.