Explicit Capacity-achieving Codes for Worst-Case Additive Errors

Details Explicit Capacity-achieving Codes for Worst-Case Additive Errors Explicit Capacity-achieving Codes for Worst-Case Additive Errors

2009-12-05

arxiv.org/abs/0912.0965v2

Computer Science

Information Theory

This preprint has been withdrawn since it is superseded by arXiv:1004.4017 [cs.IT] (same authors), which contains significantl

Scientific paper

For every p in (0,1/2), we give an explicit construction of binary codes of rate approaching "capacity" 1-H(p) that enable reliable communication in the presence of worst-case additive errors}, caused by a channel oblivious to the codeword (but not necessarily the message). Formally, we give an efficient "stochastic" encoding E(\cdot,\cdot) of messages combined with a small number of auxiliary random bits, such that for every message m and every error vector e (that could depend on m) that contains at most a fraction p of ones, w.h.p over the random bits r chosen by the encoder, m can be efficiently recovered from the corrupted codeword E(m,r) + e by a decoder without knowledge of the encoder's randomness r. Our construction for additive errors also yields explicit deterministic codes of rate approaching 1-H(p) for the "average error" criterion: for every error vector e of at most p fraction 1's, most messages m can be efficiently (uniquely) decoded from the corrupted codeword C(m)+e. Note that such codes cannot be linear, as the bad error patterns for all messages are the same in a linear code. We also give a new proof of the existence of such codes based on list decoding and certain algebraic manipulation detection codes. Our proof is simpler than the previous proofs from the literature on arbitrarily varying channels.

Affiliated with

Also associated with

No associations

Rating

Explicit Capacity-achieving Codes for Worst-Case Additive Errors 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 Explicit Capacity-achieving Codes for Worst-Case Additive Errors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Explicit Capacity-achieving Codes for Worst-Case Additive Errors will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-706376