Folded Algebraic Geometric Codes From Galois Extensions

Details Folded Algebraic Geometric Codes From Galois Extensions Folded Algebraic Geometric Codes From Galois Extensions

2009-01-09

arxiv.org/abs/0901.1162v1

Computer Science

Information Theory

Scientific paper

We describe a new class of list decodable codes based on Galois extensions of function fields and present a list decoding algorithm. These codes are obtained as a result of folding the set of rational places of a function field using certain elements (automorphisms) from the Galois group of the extension. This work is an extension of Folded Reed Solomon codes to the setting of Algebraic Geometric codes. We describe two constructions based on this framework depending on if the order of the automorphism used to fold the code is large or small compared to the block length. When the automorphism is of large order, the codes have polynomially bounded list size in the worst case. This construction gives codes of rate $R$ over an alphabet of size independent of block length that can correct a fraction of $1-R-\epsilon$ errors subject to the existence of asymptotically good towers of function fields with large automorphisms. The second construction addresses the case when the order of the element used to fold is small compared to the block length. In this case a heuristic analysis shows that for a random received word, the expected list size and the running time of the decoding algorithm are bounded by a polynomial in the block length. When applied to the Garcia-Stichtenoth tower, this yields codes of rate $R$ over an alphabet of size $(\frac{1}{\epsilon^2})^{O(\frac{1}{\epsilon})}$, that can correct a fraction of $1-R-\epsilon$ errors.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-544062