Capacity-Achieving Ensembles for the Binary Erasure Channel With Bounded Complexity

DOI10.1109/TIT.2005.850079MaRDI QIDQ3547478zbMATH OpenFDO

Authors Henry David Pfister, Igal Sason, Ruediger Urbanke

Publication date 21 December 2008

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0409026

Mathematics Subject Classification ID

Coding theorems (Shannon theory) (94A24) Decoding (94B35)

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.

Recommendations

• Accumulate–Repeat–Accumulate Codes: Capacity-Achieving Ensembles of Systematic Codes for the Erasure Channel With Bounded Complexity
• Capacity-achieving sequences for the erasure channel
• Bounds on the Number of Iterations for Turbo-Like Ensembles Over the Binary Erasure Channel
• New Sequences of Capacity Achieving LDPC Code Ensembles Over the Binary Erasure Channel
• Asymptotics of Input-Constrained Erasure Channel Capacity
• On Convergence Speed of Capacity-Achieving Sequences for Erasure Channel
• Complexity Versus Performance of Capacity-Achieving Irregular Repeat–Accumulate Codes on the Binary Erasure Channel
• scientific article; zbMATH DE number 4010386
• Lower bound for ensemble-average error probability for a discrete memoryless channel
• The Feedback Capacity of the Binary Erasure Channel With a No-Consecutive-Ones Input Constraint

Cited in

(6)

• SYMMETRIC INTERPOLATORY FRAMELETS AND THEIR ERASURE RECOVERY PROPERTIES
• Complexity Versus Performance of Capacity-Achieving Irregular Repeat–Accumulate Codes on the Binary Erasure Channel
• Accumulate–Repeat–Accumulate Codes: Capacity-Achieving Ensembles of Systematic Codes for the Erasure Channel With Bounded Complexity
• Capacity-achieving sequences for the erasure channel
• The Capacity of Online (Causal) q -Ary Error-Erasure Channels
• Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation

This page was built for publication: Capacity-Achieving Ensembles for the Binary Erasure Channel With Bounded Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3547478)