Capacity-achieving ensembles for the binary erasure channel with bounded complexity
arXiv:cs/0409026 · doi:10.1109/TIT.2005.850079
Abstract
We present two sequences of ensembles of non-systematic irregular repeat-accumulate codes which asymptotically (as their block length tends to infinity) achieve capacity on the binary erasure channel (BEC) with bounded complexity per information bit. This is in contrast to all previous constructions of capacity-achieving sequences of ensembles whose complexity grows at least like the log of the inverse of the gap (in rate) to capacity. The new bounded complexity result is achieved by puncturing bits, and allowing in this way a sufficient number of state nodes in the Tanner graph representing the codes. We also derive an information-theoretic lower bound on the decoding complexity of randomly punctured codes on graphs. The bound holds for every memoryless binary-input output-symmetric channel and is refined for the BEC.
47 pages, 9 figures. Submitted to IEEE Transactions on Information Theory
References in corpus (1)
Cited by in corpus (35)
- Code Design for Short Blocks: A Survey
- Capacity-Achieving Ensembles of Accumulate-Repeat-Accumulate Codes for the Erasure Channel with Bounded Complexity
- On Universal Properties of Capacity-Approaching LDPC Ensembles
- The price of certainty: "waterslide curves" and the gap to capacity
- Experimental quantum key distribution certified by Bell's theorem
- Low-density graph codes that are optimal for source/channel coding and binning
- Accumulate-Repeat-Accumulate Codes: Systematic Codes Achieving the Binary Erasure Channel Capacity with Bounded Complexity
- Improved Bounds on the Parity-Check Density and Achievable Rates of Binary Linear Block Codes with Applications to LDPC Codes
- Low-Complexity LDPC Codes with Near-Optimum Performance over the BEC
- Iterative Decoding of Low-Density Parity Check Codes (A Survey)
- Log-logarithmic Time Pruned Polar Coding
- On the Design of Fast Convergent LDPC Codes: An Optimization Approach
- Fingerprinting with Minimum Distance Decoding
- Optimal Rate for Irregular LDPC Codes in Binary Erasure Channel
- On Achievable Rates and Complexity of LDPC Codes for Parallel Channels with Application to Puncturing
- Bounds on the decoding complexity of punctured codes on graphs
- Performance versus Complexity Per Iteration for Low-Density Parity-Check Codes: An Information-Theoretic Approach
- On the Growth Rate of the Weight Distribution of Irregular Doubly-Generalized LDPC Codes
- Efficient Error-Correcting Codes in the Short Blocklength Regime
- An Improved Sphere-Packing Bound for Finite-Length Codes on Symmetric Memoryless Channels
- Error Bounds for Repeat-Accumulate Codes Decoded via Linear Programming
- Coding for Parallel Channels: Gallager Bounds for Binary Linear Codes with Applications to Repeat-Accumulate Codes and Variations
- Iterative Decoding Performance Bounds for LDPC Codes on Noisy Channels
- Bounds on the Number of Iterations for Turbo-Like Ensembles over the Binary Erasure Channe
- Decoding of Expander Codes at Rates Close to Capacity
- The Extraction and Complexity Limits of Graphical Models for Linear Codes
- On the Parity-Check Density and Achievable Rates of LDPC Codes
- On Achievable Rates and Complexity of LDPC Codes for Parallel Channels: Information-Theoretic Bounds and Applications
- Tradeoff between decoding complexity and rate for codes on graphs
- Minimum-Delay Decoding of Turbo-Codes for Upper-Layer FEC
- Optimal Rate and Maximum Erasure Probability LDPC Codes in Binary Erasure Channel
- Decoding Complexity of Irregular LDGM-LDPC Codes Over the BISOM Channels
- Irregular turbo code design for the binary erasure channel
- Latency and Reliability Trade-off with Computational Complexity Constraints: OS Decoders and Generalizations
- Performance of LDPC Codes Under Faulty Iterative Decoding