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.
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.
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.
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 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.
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.
It is well recognized that low-density parity-check (LDPC) codes can suffer from an error floor when decoded iteratively. This performance degradation is often attributed to the class of objects known as trapping sets. Past work has focused on characterizing the distribution of trapping sets for a variety of code ensembles, including regular, irregular and structured LDPC codes. As a subset of the trapping set collection, there exists a class of graphical structures called the absorbing sets. An absorbing set is a combinatorially-defined object; in particular a fully absorbing set is stable under bit-flipping decoding. By construction, there can exist trapping sets that are not stable under such a decoder. As a result, for finite-precision, iterative decoding algorithms used over additive channels, absorbing sets can describe decoding errors more accurately than the broader class of trapping sets. In this paper, we compute the normalized logarithmic asymptotic distributions of absorbing sets and fully absorbing sets, including elementary (fully) absorbing sets. The calculations are based on the trapping set enumeration method proposed by Milenkovic, Soljanin, and Whiting in [1]. We compare distributions of absorbing and trapping sets for representative code parameters of interest, and quantify the (lack of) discrepancies between the two. Good absorbing set properties are implied for known structured LDPC codes, including repeat accumulate codes and protograph-based constructions. Establishing the distribution of fully absorbing sets (especially when the discrepancy with the trapping set distribution is significant) allows one to further refine the estimates of the error rates under bit-flipping and related decoders.
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.