Capacity Achieving Codes From Randomness Condensers

Details Capacity Achieving Codes From Randomness Condensers Capacity Achieving Codes From Randomness Condensers

2009-01-13

arxiv.org/abs/0901.1866v2

Computer Science

Information Theory

Full version. A preliminary summary of this work appears (under the title "Capacity Achieving Codes From Randomness~Conductors

Scientific paper

We establish a general framework for construction of small ensembles of capacity achieving linear codes for a wide range of (not necessarily memoryless) discrete symmetric channels, and in particular, the binary erasure and symmetric channels. The main tool used in our constructions is the notion of randomness extractors and lossless condensers that are regarded as central tools in theoretical computer science. Same as random codes, the resulting ensembles preserve their capacity achieving properties under any change of basis. Using known explicit constructions of condensers, we obtain specific ensembles whose size is as small as polynomial in the block length. By applying our construction to Justesen's concatenation scheme (Justesen, 1972) we obtain explicit capacity achieving codes for BEC (resp., BSC) with almost linear time encoding and almost linear time (resp., quadratic time) decoding and exponentially small error probability.

Affiliated with

Also associated with

No associations

Rating

Capacity Achieving Codes From Randomness Condensers 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 Codes From Randomness Condensers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Capacity Achieving Codes From Randomness Condensers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-72540