Capacity-Achieving Ensembles of Accumulate-Repeat-Accumulate Codes for the Erasure Channel with Bounded Complexity

Abstract

The paper introduces ensembles of accumulate-repeat-accumulate (ARA) codes which asymptotically achieve capacity on the binary erasure channel (BEC) with {\em bounded complexity}, per information bit, of encoding and decoding. It also introduces symmetry properties which play a central role in the construction of capacity-achieving ensembles for the BEC with bounded complexity. The results here improve on the tradeoff between performance and complexity provided by previous constructions of capacity-achieving ensembles of codes defined on graphs. The superiority of ARA codes with moderate to large block length is exemplified by computer simulations which compare their performance with those of previously reported capacity-achieving ensembles of LDPC and IRA codes. The ARA codes also have the advantage of being systematic.

Submitted to IEEE Trans. on Information Theory, December 1st, 2005. Includes 50 pages and 13 figures

References in corpus (4)

• Sparse Graph Codes for Quantum Error-Correction
• Capacity-achieving ensembles for the binary erasure channel with bounded complexity
• Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy Channels
• Channel Coding: The Road to Channel Capacity

Cited by in corpus (15)

• Code Design for Short Blocks: A Survey
• On Universal Properties of Capacity-Approaching LDPC Ensembles
• On a Family of Circulant Matrices for Quasi-Cyclic Low-Density Generator Matrix Codes
• Spatially-Coupled MacKay-Neal Codes and Hsu-Anastasopoulos Codes
• The price of certainty: "waterslide curves" and the gap to capacity
• Tree-Structure Expectation Propagation for LDPC Decoding over the BEC
• Spatially-Coupled Codes and Threshold Saturation on Intersymbol-Interference Channels
• Log-logarithmic Time Pruned Polar Coding
• Fingerprinting with Minimum Distance Decoding
• On the Growth Rate of the Weight Distribution of Irregular Doubly-Generalized LDPC Codes
• A Semiclassical Proof of Duality Between the Classical BSC and the Quantum PSC
• Efficient Error-Correcting Codes in the Short Blocklength Regime
• Beyond Powers of Two: Hexagonal Modulation and Non-Binary Coding for Wireless Communication Systems
• Bounds on the Number of Iterations for Turbo-Like Ensembles over the Binary Erasure Channe
• Decoding Complexity of Irregular LDGM-LDPC Codes Over the BISOM Channels