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

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

2004-09-13

arxiv.org/abs/cs/0409026v1

IEEE Transactions on Information Theory, Vol. 51 (7), pp. 2352-2379, July 2005

Computer Science

Information Theory

47 pages, 9 figures. Submitted to IEEE Transactions on Information Theory

Scientific paper

10.1109/TIT.2005.850079

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.

Affiliated with

Also associated with

No associations

Rating

Capacity-achieving ensembles for the binary erasure channel with bounded complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Capacity-achieving ensembles for the binary erasure channel with bounded complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Capacity-achieving ensembles for the binary erasure channel with bounded complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-530659