Capacity-achieving sequences for the erasure channel

This paper starts a systematic study of capacity-achieving sequences of low-density parity-check codes for the erasure channel. We introduce a class A of analytic functions, show various useful properties of it, and develop a procedure to obtain degree distributions for the codes. We then study certain types of capacity-achieving sequences and introduce new measures for their optimality. For instance, it turns out that the right-regular sequence is capacity-achieving in a much stronger sense than, e.g., the Tornado sequence.

I. Introduction and Main Results

Low-density parity-check codes have attracted a lot of attention lately. Very simple and efficient decoding algorithms and the near capacity performance of the codes with respect to these algorithms have made them one of the most powerful classes of codes known to date. Despite recent advances in the asymptotic analysis of these codes [1], [2], [3], for all nontrivial channels except for the erasure channel it is still unknown whether there exist sequences of these codes that meet the Shannon capacity. The case of the erasure channel is the simplest to analyse, and a thorough understanding of this case seems to be a prerequisite for understanding the more general situation. For this reason, we will start in this paper a systematic study of capacity achieving sequences of low-density codes over the erasure channel.