List-decoding of Subspace Codes and Rank-Metric Codes up to Singleton Bound

Computer Science – Information Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

Subspace codes and rank-metric codes can be used to correct errors and erasures in network, with linear network coding. Subspace codes were introduced by Koetter and Kschischang to correct errors and erasures in networks where topology is unknown (the noncoherent case). In a previous work, we have developed a family of subspace codes, based upon the Koetter-Kschichang construction, which are efficiently list decodable. Using these codes, we achieved a better decoding radius than Koetter-Kschischiang codes at low rates. Herein, we introduce a new family of subspace codes based upon a different approach which leads to a linear-algebraic list-decoding algorithm. The resulting error correction radius can be expressed as follows: for any integer $s$, our list-decoder using $s+1$-interpolation polynomials guarantees successful recovery of the message subspace provided the normalized dimension of errors is at most $s(1-sR)$. The same list-decoding algorithm can be used to correct erasures as well as errors. The size of output list is at most $Q^{s-1}$, where $Q$ is the size of the field that message symbols are chosen from. Rank-metric codes are suitable for error correction in the case where the network topology and the underlying network code are known (the coherent case). Gabidulin codes are a well-known class of algebraic rank-metric codes that meet the Singleton bound on the minimum rank metric of a code. In this paper, we introduce a folded version of Gabidulin codes analogous to the folded Reed-Solomon codes of Guruswami and Rudra along with a list-decoding algorithm for such codes. Our list-decoding algorithm makes it possible to recover the message provided that the normalized rank of error is at most $1-R-\epsilon$, for any $\epsilon > 0$. Notably this achieves the information theoretic bound on the decoding radius of a rank-metric code.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

List-decoding of Subspace Codes and Rank-Metric Codes up to Singleton Bound 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 of Subspace Codes and Rank-Metric Codes up to Singleton Bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and List-decoding of Subspace Codes and Rank-Metric Codes up to Singleton Bound will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-329972

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.