List decoding subspace codes from insertions and deletions

Details List decoding subspace codes from insertions and deletions List decoding subspace codes from insertions and deletions

2012-02-02

arxiv.org/abs/1202.0535v1

Computer Science

Information Theory

13 pages. A conference version appeared at ITCS 2012

Scientific paper

We present a construction of subspace codes along with an efficient algorithm for list decoding from both insertions and deletions, handling an information-theoretically maximum fraction of these with polynomially small rate. Our construction is based on a variant of the folded Reed-Solomon codes in the world of linearized polynomials, and the algorithm is inspired by the recent linear-algebraic approach to list decoding. Ours is the first list decoding algorithm for subspace codes that can handle deletions; even one deletion can totally distort the structure of the basis of a subspace and is thus challenging to handle. When there are only insertions, we also present results for list decoding subspace codes that are the linearized analog of Reed-Solomon codes (proposed previously, and closely related to the Gabidulin codes for rank-metric), obtaining some improvements over similar results in previous work.

Affiliated with

Also associated with

No associations

Rating

List decoding subspace codes from insertions and deletions 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 List decoding subspace codes from insertions and deletions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and List decoding subspace codes from insertions and deletions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-3498