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:0905.3733 · IEEE International Symposium on Information Theory (ISIT)

Trapping set enumerators for repeat multiple accumulate code ensembles

Christian Koller, Alexandre Graell i Amat, Jorg Kliewer, Daniel J. Costello

Published Jun 1, 2009• 6 citations
arXivHTMLPDF

Abstract

The serial concatenation of a repetition code with two or more accumulators has the advantage of a simple encoder structure. Furthermore, the resulting ensemble is asymptotically good and exhibits minimum distance growing linearly with block length. However, in practice these codes cannot be decoded by a maximum likelihood decoder, and iterative decoding schemes must be employed. For low-density parity-check codes, the notion of trapping sets has been introduced to estimate the performance of these codes under iterative message passing decoding. In this paper, we present a closed form finite length ensemble trapping set enumerator for repeat multiple accumulate codes by creating a trellis representation of trapping sets. We also obtain the asymptotic expressions when the block length tends to infinity and evaluate them numerically.

DOI
10.1109/isit.2009.5205355

Related papers

On trapping sets for repeat accumulate accumulate codes

Jörg Kliewer, Christian Koller, Alexandre Graell i Amat +1 more

The serial concatenation of a repetition code with two or more accumulators has the advantage of a simple encoder structure. Furthermore, the resulting ensemble is asymptotically good and exhibits minimum distance growing linearly with block length. For low-density parity-check codes, the notion of trapping sets has been introduced to estimate the performance of these codes under non-maximum likelihood decoding. We briefly address asymptotic expressions for the normalized minimum trapping distance for the Gallager-Zyablov-Pinsker bit flipping decoding algorithm. Then we consider belief propagation decoding and present a closed form finite length ensemble average trapping set enumerator for repeat accumulate accumulate codes by creating a trellis representation of trapping sets. For this case, we also obtain asymptotic expressions and evaluate them numerically.

Information Theory and Applications Workshop (ITA)•Feb 1, 2009•3 citations

Stopping set analysis of repeat multiple-accumulate codes

Alexandre Graell i Amat, Eirik Rosnes

In this work, we consider a stopping set analysis of repeat multiple-accumulate (RMA) code ensembles formed by the serial concatenation of a repetition code with multiple accumulators. The RMA codes are assumed to be iteratively decoded in a constituent code oriented fashion using maximum a posteriori erasure correction in the constituent codes. We give stopping set enumerators for RMA code ensembles and show that their stopping distance hmin, defined as the size of the smallest nonempty stopping set, asymptotically grows linearly with the block length. Thus, the RMA code ensembles are good for the binary erasure channel. Furthermore, it is shown that, contrary to the asymptotic minimum distance dmin, whose growth rate coefficient increases with the number of accumulate codes, the hmingrowth rate coefficient diminishes with the number of accumulators. We also consider random puncturing and show that for sufficiently high code rates, the asymptotic hmindoes not grow linearly with the block length, contrary to the asymptotic dmin, whose growth rate coefficient approaches the Gilbert-Varshamov bound as the rate increases. Finally, we give iterative decoding thresholds to show the convergence properties.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•0 citations

On the minimum trapping distance of repeat accumulate accumulate codes

Jörg Kliewer, Kamil Sh. Zigangirov, Daniel J. Costello

We consider the ensemble of codes formed by a serial concatenation of a repetition code with two accumulators through uniform random interleavers. For this ensemble, asymptotic expressions for the normalized minimum trapping distance are derived. We employ a variant of the Gallager-Zyablov-Pinsker bit flipping decoding algorithm on a binary symmetric channel, where the analysis is based on the factor graph of the code. In particular, we show that the minimum trapping distance can be determined by solving a non-linear optimization problem. As a result we find that the minimum trapping distance grows linearly with block length for code rates of 1/3 and smaller, albeit with very small growth rate coefficients.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2008•5 citations

On the Analysis of Weighted Nonbinary Repeat Multiple-Accumulate Codes

Eirik Rosnes, Alexandre Graell i Amat

In this paper, we consider weighted nonbinary repeat multiple-accumulate (WNRMA) code ensembles obtained from the serial concatenation of a nonbinary rate-1/n repeat code and the cascade of L>= 1 accumulators, where each encoder is followed by a nonbinary random weighter. The WNRMA codes are assumed to be iteratively decoded using the turbo principle with maximum a posteriori constituent decoders. We derive the exact weight enumerator of nonbinary accumulators and subsequently give the weight enumerators for WNRMA code ensembles. We formally prove that the symbol-wise minimum distance of WNRMA code ensembles asymptotically grows linearly with the block length when L >= 3 and n >= 2, and L=2 and n >= 3, for all powers of primes q >= 3 considered, where q is the field size. Thus, WNRMA code ensembles are asymptotically good for these parameters. We also give iterative decoding thresholds, computed by an extrinsic information transfer chart analysis, on the q-ary symmetric channel to show the convergence properties. Finally, we consider the binary image of WNRMA code ensembles and compare the asymptotic minimum distance growth rates with those of binary repeat multiple-accumulate code ensembles.

arXiv:1101.5966•Jan 31, 2011•3 citations

Finite-length analysis of a capacity-achieving ensemble for the binary erasure channel

Henry D. Pfister

In this paper, we consider the finite-length performance of a capacity-achieving sequence of irregular repeat-accumulate (IRA) code ensembles. We focus on a sequence of bit-regular ensembles with degree 3 which was shown to achieve capacity with bounded complexity [Pfister, 2005]. To characterize how fast the block length of the code must grow with respect to the truncation point of the degree distribution (i.e., maximum check degree), we compute an upper bound on the average weight enumerator. Based on this analysis, we present a particular truncation sequence that could achieve a minimum distance which grows like n/sup 1/3/ even as the gap to capacity goes to zero. We also consider the performance of these codes in the waterfall region by extending the finite-length scaling law [Amraoui] from low-density parity-check codes to IRA codes. This shows that the performance near the iterative decoding threshold is well characterized by a suitably scaled Q-function for large enough block length. Numerical results are given for the scaling parameters of this ensemble sequence and for a few other IRA codes. Unfortunately, the simulation results for the capacity-achieving sequence start to match the scaling law only for very large block lengths.

IEEE Information Theory Workshop (ITW)•Jan 1, 2005•3 citations

Constructing LDPC codes from simple loop-free encoding modules

D. Divsalar, Samuel J. Dolinar, Jeremy Thorpe +1 more

Inspired by recently proposed accumulate-repeat-accumulate (ARA) codes, in this paper we propose a construction method for LDPC codes using simple loop-free encoding modules. Such codes can be viewed as serial/parallel concatenations of simple modules such as accumulators, repetition codes, differentiators, and punctured single parity check codes. Examples are accumulate-repeat-accumulate (ARA) codes, accumulate-repeat-accumulate-accumulate (ARAA) codes and accumulate-repeat-check-accumulate codes, and other variations. These codes constitute a subclass of LDPC codes with very fast encoder structure. They also have a projected graph or protograph representation that allows for high-speed decoder implementation. Based on density evolution, we show through some examples that low iterative decoding thresholds close to the channel capacity limits can be achieved with low maximum variable node degrees, as the block size goes to infinity. The decoding threshold in many examples outperforms that of the best known unstructured irregular LDPC codes constrained to have the same maximum node degree. Furthermore, by puncturing the accumulator modules, any desired higher rate codes can be obtained with thresholds that stay close to their respective channel capacity thresholds uniformly.

International Conference on Communications•Aug 16, 2005•31 citations
The serial concatenation of a repetition code with two or more accumulators has the advantage of a simple encoder structure. Furthermore, the resulting ensemble is asymptotically good and exhibits minimum distance growing linearly with block length. However, in practice these codes cannot be decoded by a maximum likelihood decoder, and iterative decoding schemes must be employed. For low-density parity-check codes, the notion of trapping sets has been introduced to estimate the performance of these codes under iterative message passing decoding. In this paper, we present a closed form finite length ensemble trapping set enumerator for repeat multiple accumulate codes by creating a trellis representation of trapping sets. We also obtain the asymptotic expressions when the block length tends to infinity and evaluate them numerically.
The serial concatenation of a repetition code with two or more accumulators has the advantage of a simple encoder structure. Furthermore, the resulting ensemble is asymptotically good and exhibits minimum distance growing linearly with block length. For low-density parity-check codes, the notion of trapping sets has been introduced to estimate the performance of these codes under non-maximum likelihood decoding. We briefly address asymptotic expressions for the normalized minimum trapping distance for the Gallager-Zyablov-Pinsker bit flipping decoding algorithm. Then we consider belief propagation decoding and present a closed form finite length ensemble average trapping set enumerator for repeat accumulate accumulate codes by creating a trellis representation of trapping sets. For this case, we also obtain asymptotic expressions and evaluate them numerically.
In this work, we consider a stopping set analysis of repeat multiple-accumulate (RMA) code ensembles formed by the serial concatenation of a repetition code with multiple accumulators. The RMA codes are assumed to be iteratively decoded in a constituent code oriented fashion using maximum a posteriori erasure correction in the constituent codes. We give stopping set enumerators for RMA code ensembles and show that their stopping distance hmin, defined as the size of the smallest nonempty stopping set, asymptotically grows linearly with the block length. Thus, the RMA code ensembles are good for the binary erasure channel. Furthermore, it is shown that, contrary to the asymptotic minimum distance dmin, whose growth rate coefficient increases with the number of accumulate codes, the hmingrowth rate coefficient diminishes with the number of accumulators. We also consider random puncturing and show that for sufficiently high code rates, the asymptotic hmindoes not grow linearly with the block length, contrary to the asymptotic dmin, whose growth rate coefficient approaches the Gilbert-Varshamov bound as the rate increases. Finally, we give iterative decoding thresholds to show the convergence properties.
We consider the ensemble of codes formed by a serial concatenation of a repetition code with two accumulators through uniform random interleavers. For this ensemble, asymptotic expressions for the normalized minimum trapping distance are derived. We employ a variant of the Gallager-Zyablov-Pinsker bit flipping decoding algorithm on a binary symmetric channel, where the analysis is based on the factor graph of the code. In particular, we show that the minimum trapping distance can be determined by solving a non-linear optimization problem. As a result we find that the minimum trapping distance grows linearly with block length for code rates of 1/3 and smaller, albeit with very small growth rate coefficients.
In this paper, we consider weighted nonbinary repeat multiple-accumulate (WNRMA) code ensembles obtained from the serial concatenation of a nonbinary rate-1/n repeat code and the cascade of L>= 1 accumulators, where each encoder is followed by a nonbinary random weighter. The WNRMA codes are assumed to be iteratively decoded using the turbo principle with maximum a posteriori constituent decoders. We derive the exact weight enumerator of nonbinary accumulators and subsequently give the weight enumerators for WNRMA code ensembles. We formally prove that the symbol-wise minimum distance of WNRMA code ensembles asymptotically grows linearly with the block length when L >= 3 and n >= 2, and L=2 and n >= 3, for all powers of primes q >= 3 considered, where q is the field size. Thus, WNRMA code ensembles are asymptotically good for these parameters. We also give iterative decoding thresholds, computed by an extrinsic information transfer chart analysis, on the q-ary symmetric channel to show the convergence properties. Finally, we consider the binary image of WNRMA code ensembles and compare the asymptotic minimum distance growth rates with those of binary repeat multiple-accumulate code ensembles.
In this paper, we consider the finite-length performance of a capacity-achieving sequence of irregular repeat-accumulate (IRA) code ensembles. We focus on a sequence of bit-regular ensembles with degree 3 which was shown to achieve capacity with bounded complexity [Pfister, 2005]. To characterize how fast the block length of the code must grow with respect to the truncation point of the degree distribution (i.e., maximum check degree), we compute an upper bound on the average weight enumerator. Based on this analysis, we present a particular truncation sequence that could achieve a minimum distance which grows like n/sup 1/3/ even as the gap to capacity goes to zero. We also consider the performance of these codes in the waterfall region by extending the finite-length scaling law [Amraoui] from low-density parity-check codes to IRA codes. This shows that the performance near the iterative decoding threshold is well characterized by a suitably scaled Q-function for large enough block length. Numerical results are given for the scaling parameters of this ensemble sequence and for a few other IRA codes. Unfortunately, the simulation results for the capacity-achieving sequence start to match the scaling law only for very large block lengths.
Inspired by recently proposed accumulate-repeat-accumulate (ARA) codes, in this paper we propose a construction method for LDPC codes using simple loop-free encoding modules. Such codes can be viewed as serial/parallel concatenations of simple modules such as accumulators, repetition codes, differentiators, and punctured single parity check codes. Examples are accumulate-repeat-accumulate (ARA) codes, accumulate-repeat-accumulate-accumulate (ARAA) codes and accumulate-repeat-check-accumulate codes, and other variations. These codes constitute a subclass of LDPC codes with very fast encoder structure. They also have a projected graph or protograph representation that allows for high-speed decoder implementation. Based on density evolution, we show through some examples that low iterative decoding thresholds close to the channel capacity limits can be achieved with low maximum variable node degrees, as the block size goes to infinity. The decoding threshold in many examples outperforms that of the best known unstructured irregular LDPC codes constrained to have the same maximum node degree. Furthermore, by puncturing the accumulator modules, any desired higher rate codes can be obtained with thresholds that stay close to their respective channel capacity thresholds uniformly.