Capacity-achieving ensembles for the binary erasure channel with bounded complexity

We present two sequences of ensembles of nonsystematic irregular repeat-accumulate (IRA) 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 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 (MBIOS) channel and is refined for the binary erasure channel.

• Publication year

  2004

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2004-09-13

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2005.850079arXiv cs/0409026
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Raptor codes

  2011cited by this paper
• Accumulate-Repeat-Accumulate Codes: Systematic Codes Achieving the Binary Erasure Channel Capacity with Bounded Complexity

  2005cited by this paper
• Multi-Edge Type LDPC Codes

  2004cited by this paper
• Complexity versus performance of capacity-achieving irregular repeat-accumulate codes on the binary erasure channel

  2004influential reference
• Graph-based codes and iterative decoding

  2003cited by this paper
• Parity-check density versus performance of binary linear block codes over memoryless symmetric channels

  2003influential reference
• On the capacity of finite state channels and the analysis of convolutional accumulate-m codes

  2003cited by this paper
• Design of repeat-accumulate codes for iterative detection and decoding

  2003cited by this paper
• Upper bounds on the rate of LDPC codes

  2002influential reference
• Progressive edge-growth Tanner graphs

  2001cited by this paper
• Efficient erasure correcting codes

  2001cited by this paper
• Capacity-achieving sequences for the erasure channel

  2001cited by this paper
• On the complexity of reliable communication on the erasure channel

  2001cited by this paper
• The capacity of low-density parity-check codes under message-passing decoding

  2001cited by this paper
• Irregular repeat accumulate codes

  2000cited by this paper
• Practical loss-resilient codes

  1997cited by this paper
• Singularity Analysis of Generating Functions

  1990influential reference
• Asymptotic methods in analysis

  1958influential reference
• Methods analysis.

  1953cited by this paper

• High Performance and Resource Efficient Low Density Parity Check Decoder Design

  2025cites this paper
• Trends in Channel Coding for 6G

  2024cites this paper
• On the Performance of Low-complexity Decoders of LDPC and Polar Codes

  2024cites this paper
• Erasure Decoding for Quantum LDPC Codes via Belief Propagation with Guided Decimation

  2024cites this paper
• BEP evaluation of 5G LDPC codes in a pre-amplified optical PPM receiver

  2023cites this paper
• Performance Evaluation of the 5G LDPC and RS Codes in a Pre-Amplified PPM Receiver

  2022cites this paper
• Device-Independent Quantum Key Distribution

  2021cites this paper
• Latency and Reliability Trade-Off With Computational Complexity Constraints: OS Decoders and Generalizations

  2021cites this paper
• Experimental quantum key distribution certified by Bell's theorem

  2021cites this paper
• Performance Analysis of Channel Coding Techniques for 5G Networks

  2021cites this paper
• Low‐Density Parity‐Check ( LDPC ) Codes for 5G Communications

  2021cites this paper
• Log-Logarithmic Time Pruned Polar Coding

  2019cites this paper
• The Performance of Multithreshold Decoders in Concatenated Schemes Over Erasure Channels

  2019cites this paper
• An overview of channel coding for 5G NR cellular communications

  2019influential citation
• Log-logarithmic Time Pruned Polar Coding on Binary Erasure Channels

  2018cites this paper
• Hardware Implementation and Performance Analysis of Resource Efficient Probabilistic Hard Decision LDPC Decoders

  2018cites this paper
• Multiedge-type low-density parity-check codes for continuous-variable quantum key distribution

  2018cites this paper
• Some New Constructions and Bounds for Locally Generated Quantum Codes

  2018cites this paper
• Design of Low-Density Parity Check Codes for 5G New Radio

  2018cites this paper
• Efficient Error-Correcting Codes in the Short Blocklength Regime

  2018cites this paper
• Reconciliation of Weakly Correlated Information Sources Utilizing Generalized EXIT Chart

  2018cites this paper
• Improving performance of multithreshold decoder over binary erasure channel

  2017cites this paper
• Energy Consumption of Error Control Coding Circuits

  2017cites this paper
• A family of LDPC codes for Binary Symmetric Channel with optimized rate

  2017cites this paper
• Analysis and implementation of resource efficient probabilistic Gallager B LDPC decoder

  2017cites this paper
• Optimizing low density parity check code for two parallel erasure links

  2016cites this paper
• Code Design for Short Blocks: A Survey

  2016cites this paper
• LDA Lattices Without Dithering Achieve Capacity on the Gaussian Channel

  2016cites this paper
• Model-code separation architectures for compression based on message-passing

  2015cites this paper
• LDPC code ensembles that universally achieve capacity under BP decoding: A simple derivation

  2015cites this paper
• A fast convergence density evolution algorithm for optimal rate LDPC codes in BEC

  2014cites this paper
• Design of Irregular Repeat Accumulate Codes for Finite Decoder Iterations

  2014cites this paper
• On the Design of Fast Convergent LDPC Codes for the BEC: An Optimization Approach

  2014influential citation
• Bounds on the Error Probability of Block Codes over the q-Ary Erasure Channel

  2013cites this paper
• Spatially-coupled multi-edge type LDPC codes with bounded degrees that achieve capacity on the BEC under BP decoding

  2013cites this paper
• Performance analysis of faulty Gallager-B decoding of QC-LDPC codes

  2013cites this paper
• Optimal rate irregular low-density parity-check codes in binary erasure channel

  2012cites this paper
• On the design of network coding for downlink of single-relay multi-users two-way network

  2012cites this paper
• Iteration-constrained design of IRA codes

  2012cites this paper
• Rate - Reliability - Complexity limits in ML and Lattice based decoding for MIMO, multiuser and cooperative communications. (Le compromis Débit-Fiabilité-Complexité dans les systèmes MMO multi-utilisateurs et coopératifs avec décodeurs ML et Lattice)

  2012cites this paper
• Irregular repeat accumulate codes with few iterations for the binary adder channel

  2012cites this paper
• Performance Analysis and Improvements for the Future Aeronautical Mobile Airport Communications System (AeroMACS)

  2012cites this paper
• Capacity-Achieving Schemes for Finite-State Channels.

  2011cites this paper
• Optimal rate and maximum erasure probability LDPC codes in binary erasure channel

  2011cites this paper
• Outage Performance Analysis and Code Design for Three-Stage MMSE Turbo Equalization in Frequency-Selective Rayleigh Fading Channels

  2011cites this paper
• Raptor codes

  2011cites this paper
• ON UNIVERSAL LDPC CODES OVER MEMORYLESS SYMMETRIC CHANNELS

  2011cites this paper
• Degree Distribution Design for LDPC Codes: A Derivative Matching Approach

  2011cites this paper
• Successive Maximization for Systematic Design of Universally Capacity Approaching Rate-Compatible Sequences of LDPC Code Ensembles over Binary-Input Output-Symmetric Memoryless Channels

  2011cites this paper
• Optimal rate for irregular LDPC codes in binary erasure channel

  2011cites this paper
• Reliability Options for Data Communications in the Future Deep-Space Missions

  2011cites this paper
• Simple capacity-achieving ensembles of rateless erasure-correcting codes

  2010cites this paper
• Coding versus feedback: Hybrid ARQ protocols for the packet erasure channel

  2010cites this paper
• Capacity-Achieving Codes With Bounded Graphical Complexity and Maximum Likelihood Decoding

  2010influential citation
• Design of irregular LDPC codes with optimized performance-complexity tradeoff

  2010cites this paper
• Capacity-Approaching Irregular Turbo Codes for the Binary Erasure Channel

  2010cites this paper
• Achieving a near‐optimum erasure correction performance with low‐complexity LDPC codes

  2010cites this paper
• Unreliable and resource-constrained decoding

  2010cites this paper
• Codes AL-FEC hautes performances pour les canaux à effacements : variations autour des codes LDPC. (High performances AL-FEC codes for the erasure channel : variation around LDPC codes)

  2010cites this paper
• Properties of LDGM-LDPC codes with applications to secrecy coding

  2010cites this paper
• Sparse graph codes for compression, sensing, and secrecy

  2010influential citation
• A general lower bound on the decoding complexity of message passing decoding

  2010influential citation
• New Sequences of Capacity Achieving LDPC Code Ensembles Over the Binary Erasure Channel

  2010cites this paper
• Erasure Codes with a Banded Structure for Hybrid Iterative-ML Decoding

  2009cites this paper
• Capacity-achieving codes for channels with memory with maximum-likelihood decoding

  2009cites this paper
• Low-Density Graph Codes That Are Optimal for Binning and Coding With Side Information

  2009influential citation
• Quasi-systematic doped LT codes

  2009cites this paper
• Code design for erasure channels with limited or noisy feedback

  2009cites this paper
• On systematic design of universally capacity approaching rate-compatible sequences of LDPC code ensembles over binary-input output-symmetric memoryless channels

  2009cites this paper
• Lower bounds on the graphical complexity of finite-length LDPC codes

  2009influential citation
• Quasi-systematic doped LT codes

  2009cites this paper
• Statistical physics methods for sparse graph codes

  2009cites this paper
• On LDPC codes over symmetric channels

  2009cites this paper
• Error bounds for repeat-accumulate codes decoded via linear programming

  2009cites this paper
• Algorithm-Based Fault Tolerance Applied to P2P Computing Networks

  2009cites this paper
• Capacity-achieving codes for finite-state channels with maximum-likelihood decoding

  2009cites this paper
• Capacity-approaching protograph codes

  2009cites this paper
• On the growth rate of the weight distribution of irregular doubly-generalized LDPC codes

  2008cites this paper
• Low-Complexity LDPC Codes with Near-Optimum Performance over the BEC

  2008cites this paper
• On the Growth Rate of the Weight Distribution of Irregular Doubly Generalized LDPC Codes

  2008cites this paper
• Generalized serial turbo coding ensembles: analysis and design

  2008cites this paper
• A construction of channel code, joint source-channel code, and universal code for arbitrary stationary memoryless channels using sparse matrices

  2008cites this paper
• Bounds on the convergence speed of iterative message-passing decoders over the binary erasure channel

  2008cites this paper
• Bandwidth-Efficient Modulation Codes Based on Nonbinary Irregular Repeat Accumulate Codes

  2008cites this paper
• Generalized IRA Erasure Correcting Codes for Hybrid Iterative/Maximum Likelihood Decoding

  2008cites this paper
• The price of certainty: "waterslide curves" and the gap to capacity

  2008cites this paper
• Bandwidth-Efficient Modulation Codes Based on Nonbinary Irregular Repeat–Accumulate Codes

  2008cites this paper
• The price of certainty: iterative decoding from a total power perspective

  2008cites this paper
• Joint iterative decoding of LDPC codes for channels with memory and erasure noise

  2008cites this paper
• Irregular turbo code design for the binary erasure channel

  2008cites this paper
• Performance of LDPC Codes Under Faulty Iterative Decoding

  2008cites this paper
• An Improved Sphere-Packing Bound for Finite-Length Codes Over Symmetric Memoryless Channels

  2008cites this paper
• Pseudo-binomial degree distributions from derivative matching

  2008cites this paper
• New sequences of capacity achieving LDPC code ensembles over the binary erasure channel

  2008cites this paper
• Finite-length scaling of parallel turbo codes on the BEC

  2008cites this paper
• Minimum-delay decoding of turbo codes for upper-layer FEC

  2008cites this paper
• Raptor Codes

  2007cites this paper
• Constrained Information Combining: Theory and Applications for LDPC Coded Systems

  2007cites this paper
• Bounds on the Tradeoff Between Decoding Complexity and Rate for Sparse-Graph Codes

  2007cites this paper
• Doped Accumulate LT Codes

  2007cites this paper