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

arXiv:cs/0508030 · IEEE International Symposium on Information Theory (ISIT)

Terminated LDPC convolutional codes with thresholds close to capacity

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

Published Jan 1, 2005• 77 citations
arXivHTMLPDF

Abstract

An ensemble of LDPC convolutional codes with parity-check matrices composed of permutation matrices is considered. The convergence of the iterative belief propagation based decoder for terminated convolutional codes in the ensemble is analyzed for binary-input output-symmetric memoryless channels using density evolution techniques. We observe that the structured irregularity in the Tanner graph of the codes leads to significantly better thresholds when compared to corresponding LDPC block codes

DOI
10.1109/isit.2005.1523567

Related papers

Convergence analysis for a class of LDPC convolutional codes on the erasure channel

Arvind Sridharan, Michael Lentmaier, Daniel J. Costello +1 more

An ensemble of LDPC convolutional codes with parity-check matrices composed of permutation matrices is introduced.The convergence of the iterative belief propagation based decoder for terminated convolutional codes in the ensemble when operating on the erasure channel is analyzed.The structured irregularity in the Tanner graph of the codes leads to significantly better thresholds when compared to the corresponding LDPC block codes.

•Jan 1, 2004•52 citations

Iterative Decoding Threshold Analysis for LDPC Convolutional Codes

Michael Lentmaier, Arvind Sridharan, Daniel J. Costello +1 more

An iterative decoding threshold analysis for terminated regular LDPC convolutional (LDPCC) codes is presented. Using density evolution techniques, the convergence behavior of an iterative belief propagation decoder is analyzed for the binary erasure channel and the AWGN channel with binary inputs. It is shown that for a terminated LDPCC code ensemble, the thresholds are better than for corresponding regular and irregular LDPC block codes.

IEEE Transactions on Information Theory•Sep 15, 2010•407 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

AWGN channel analysis of terminated LDPC convolutional codes

David G. M. Mitchell, Michael Lentmaier, Daniel J. Costello

It has previously been shown that ensembles of terminated protograph-based low-density parity-check (LDPC) convolutional codes have a typical minimum distance that grows linearly with block length and that they are capable of achieving capacity approaching iterative decoding thresholds on the binary erasure channel (BEC). In this paper, we review a recent result that the dramatic threshold improvement obtained by terminating LDPC convolutional codes extends to the additive white Gaussian noise (AWGN) channel. Also, using a (3,6)-regular protograph-based LDPC convolutional code ensemble as an example, we perform an asymptotic trapping set analysis of terminated LDPC convolutional code ensembles. In addition to capacity approaching iterative decoding thresholds and linearly growing minimum distance, we find that the smallest non-empty trapping set of a terminated ensemble grows linearly with block length.

arXiv:1102.3936•Information Theory and Applications Workshop (ITA)•Feb 1, 2011•21 citations

On the universality of LDPC code ensembles under belief propagation and ML decoding

Boaz Shuval, Igal Sason

A universal design of low-density parity-check (LDPC) code ensembles which enables to operate reliably over various channels is of great interest. This paper considers the universality of LDPC code ensembles over sets of memoryless binary-input output-symmetric (MBIOS) channels, addressing their universality under belief-propagation (BP) and maximum-likelihood (ML) decoding. Based on the density evolution approach, closed-form, easy-to-calculate, analytical results related to the universality of LDPC code ensembles under BP decoding are derived. LP Bounds on the achievable rate of LDPC code ensembles over a set of equi-capacity channels are also derived. This paper considers the universality under ML decoding of properly selected regular LDPC code ensembles for the set of equi-capacity MBIOS channels. The full paper version related to this work [13] provides further results, full proofs, and additional discussions on the theorems.

IEEE Convention of Electrical and Electronics Engineers in Israel•Nov 1, 2010•10 citations

On the thresholds of generalized LDPC convolutional codes based on protographs

Michael Lentmaier, Gerhard Paul Fettweis

A threshold analysis of terminated generalized LDPC convolutional codes (GLDPC CCs) is presented for the binary erasure channel. Different ensembles of protograph-based GLDPC CCs are considered, including braided block codes (BBCs). It is shown that the terminated PG-GLDPC CCs have better thresholds than their block code counterparts. Surprisingly, our numerical analysis suggests that for large termination factors the belief propagation decoding thresholds of PG-GLDPC CCs coincide with the ML decoding thresholds of the corresponding PG-GLDPC block codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•75 citations
An ensemble of LDPC convolutional codes with parity-check matrices composed of permutation matrices is considered. The convergence of the iterative belief propagation based decoder for terminated convolutional codes in the ensemble is analyzed for binary-input output-symmetric memoryless channels using density evolution techniques. We observe that the structured irregularity in the Tanner graph of the codes leads to significantly better thresholds when compared to 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.
It has previously been shown that ensembles of terminated protograph-based low-density parity-check (LDPC) convolutional codes have a typical minimum distance that grows linearly with block length and that they are capable of achieving capacity approaching iterative decoding thresholds on the binary erasure channel (BEC). In this paper, we review a recent result that the dramatic threshold improvement obtained by terminating LDPC convolutional codes extends to the additive white Gaussian noise (AWGN) channel. Also, using a (3,6)-regular protograph-based LDPC convolutional code ensemble as an example, we perform an asymptotic trapping set analysis of terminated LDPC convolutional code ensembles. In addition to capacity approaching iterative decoding thresholds and linearly growing minimum distance, we find that the smallest non-empty trapping set of a terminated ensemble grows linearly with block length.
A universal design of low-density parity-check (LDPC) code ensembles which enables to operate reliably over various channels is of great interest. This paper considers the universality of LDPC code ensembles over sets of memoryless binary-input output-symmetric (MBIOS) channels, addressing their universality under belief-propagation (BP) and maximum-likelihood (ML) decoding. Based on the density evolution approach, closed-form, easy-to-calculate, analytical results related to the universality of LDPC code ensembles under BP decoding are derived. LP Bounds on the achievable rate of LDPC code ensembles over a set of equi-capacity channels are also derived. This paper considers the universality under ML decoding of properly selected regular LDPC code ensembles for the set of equi-capacity MBIOS channels. The full paper version related to this work [13] provides further results, full proofs, and additional discussions on the theorems.
A threshold analysis of terminated generalized LDPC convolutional codes (GLDPC CCs) is presented for the binary erasure channel. Different ensembles of protograph-based GLDPC CCs are considered, including braided block codes (BBCs). It is shown that the terminated PG-GLDPC CCs have better thresholds than their block code counterparts. Surprisingly, our numerical analysis suggests that for large termination factors the belief propagation decoding thresholds of PG-GLDPC CCs coincide with the ML decoding thresholds of the corresponding PG-GLDPC block codes.