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 an Ensemble of LDPC Convolutional Codes

Arvind Sridharan, Dmitri V. Truhachev, Michael Lentmaier, Daniel J. Costello, Kamil Sh. Zigangirov

Published Dec 1, 2007• 49 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2007.909113

Related papers

Minimum Distance and Trapping Set Analysis of Protograph-Based LDPC Convolutional Codes

David G. M. Mitchell, Alí Emre Pusane, Daniel J. Costello

Low-density parity-check (LDPC) convolutional codes have been shown to be capable of achieving capacity-approaching performance with iterative message-passing decoding. In the first part of this paper, using asymptotic methods to obtain lower bounds on the free distance to constraint length ratio, we show that several ensembles of regular and irregular LDPC convolutional codes derived from protograph-based LDPC block codes have the property that the free distance grows linearly with respect to the constraint length, i.e., the ensembles are asymptotically good. In particular, we show that the free distance to constraint length ratio of the LDPC convolutional code ensembles exceeds the minimum distance to block length ratio of the corresponding LDPC block code ensembles. A large free distance growth rate indicates that codes drawn from the ensemble should perform well at high signal-to-noise ratios under maximum-likelihood decoding. When suboptimal decoding methods are employed, there are many factors that affect the performance of a code. Recently, it has been shown that so-called trapping sets are a significant factor affecting decoding failures of LDPC codes over the additive white Gaussian noise channel with iterative message-passing decoding. In the second part of this paper, we study the trapping sets of the asymptotically good protograph-based LDPC convolutional codes considered earlier. By extending the theory presented in part one and using similar bounding techniques, we show that the size of the smallest non-empty trapping set grows linearly with the constraint length for these ensembles.

IEEE Transactions on Information Theory•Aug 7, 2012•61 citations

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

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

Asymptotically good LDPC convolutional codes based on protographs

David G. M. Mitchell, Alí Emre Pusane, Kamil Sh. Zigangirov +1 more

LDPC convolutional codes have been shown to be capable of achieving the same capacity-approaching performance as LDPC block codes with iterative message-passing decoding. In this paper, asymptotic methods are used to calculate a lower bound on the free distance for several ensembles of asymptotically good protograph-based LDPC convolutional codes. Further, we show that the free distance to constraint length ratio of the LDPC convolutional codes exceeds the minimum distance to block length ratio of corresponding LDPC block codes.

arXiv:0805.0241•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2008•29 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

Asymptotically regular LDPC codes with linear distance growth and thresholds close to capacity

Michael Lentmaier, David G. M. Mitchell, Gerhard Paul Fettweis +1 more

Families of asymptotically regular LDPC block code ensembles can be formed by terminating (J, K)-regular protograph-based LDPC convolutional codes. By varying the termination length, we obtain a large selection of LDPC block code ensembles with varying code rates and substantially better iterative decoding thresholds than those of (J, K)-regular LDPC block code ensembles, despite the fact that the terminated ensembles are almost regular. Also, by means of an asymptotic weight enumerator analysis, we show that minimum distance grows linearly with block length for all of the ensembles in these families, i.e., the ensembles are asymptotically good. We find that, as the termination length increases, families of ¿asymptotically regular¿ codes with capacity approaching iterative decoding thresholds and declining minimum distance growth rates are obtained, allowing a code designer to trade-off between distance growth rate and threshold. Further, we show that the thresholds and the distance growth rates can be improved by carefully choosing the component protographs used in the code construction.

arXiv:1005.1062•Information Theory and Applications Workshop (ITA)•Jan 1, 2010•40 citations
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.
Low-density parity-check (LDPC) convolutional codes have been shown to be capable of achieving capacity-approaching performance with iterative message-passing decoding. In the first part of this paper, using asymptotic methods to obtain lower bounds on the free distance to constraint length ratio, we show that several ensembles of regular and irregular LDPC convolutional codes derived from protograph-based LDPC block codes have the property that the free distance grows linearly with respect to the constraint length, i.e., the ensembles are asymptotically good. In particular, we show that the free distance to constraint length ratio of the LDPC convolutional code ensembles exceeds the minimum distance to block length ratio of the corresponding LDPC block code ensembles. A large free distance growth rate indicates that codes drawn from the ensemble should perform well at high signal-to-noise ratios under maximum-likelihood decoding. When suboptimal decoding methods are employed, there are many factors that affect the performance of a code. Recently, it has been shown that so-called trapping sets are a significant factor affecting decoding failures of LDPC codes over the additive white Gaussian noise channel with iterative message-passing decoding. In the second part of this paper, we study the trapping sets of the asymptotically good protograph-based LDPC convolutional codes considered earlier. By extending the theory presented in part one and using similar bounding techniques, we show that the size of the smallest non-empty trapping set grows linearly with the constraint length for these ensembles.
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.
LDPC convolutional codes have been shown to be capable of achieving the same capacity-approaching performance as LDPC block codes with iterative message-passing decoding. In this paper, asymptotic methods are used to calculate a lower bound on the free distance for several ensembles of asymptotically good protograph-based LDPC convolutional codes. Further, we show that the free distance to constraint length ratio of the LDPC convolutional codes exceeds the minimum distance to block length ratio of corresponding LDPC block 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.
Families of asymptotically regular LDPC block code ensembles can be formed by terminating (J, K)-regular protograph-based LDPC convolutional codes. By varying the termination length, we obtain a large selection of LDPC block code ensembles with varying code rates and substantially better iterative decoding thresholds than those of (J, K)-regular LDPC block code ensembles, despite the fact that the terminated ensembles are almost regular. Also, by means of an asymptotic weight enumerator analysis, we show that minimum distance grows linearly with block length for all of the ensembles in these families, i.e., the ensembles are asymptotically good. We find that, as the termination length increases, families of ¿asymptotically regular¿ codes with capacity approaching iterative decoding thresholds and declining minimum distance growth rates are obtained, allowing a code designer to trade-off between distance growth rate and threshold. Further, we show that the thresholds and the distance growth rates can be improved by carefully choosing the component protographs used in the code construction.