# Folded Algebraic Geometric Codes From Galois Extensions - Computer Science > Information Theory

Folded Algebraic Geometric Codes From Galois Extensions - Computer Science > Information Theory - Download this document for free, or read online. Document in PDF available to download.

Abstract: We describe a new class of list decodable codes based on Galois extensions offunction fields and present a list decoding algorithm. These codes are obtainedas a result of folding the set of rational places of a function field usingcertain elements automorphisms from the Galois group of the extension. Thiswork is an extension of Folded Reed Solomon codes to the setting of AlgebraicGeometric codes. We describe two constructions based on this frameworkdepending on if the order of the automorphism used to fold the code is large orsmall compared to the block length. When the automorphism is of large order,the codes have polynomially bounded list size in the worst case. Thisconstruction gives codes of rate $R$ over an alphabet of size independent ofblock length that can correct a fraction of $1-R-\epsilon$ errors subject tothe existence of asymptotically good towers of function fields with largeautomorphisms. The second construction addresses the case when the order of theelement used to fold is small compared to the block length. In this case aheuristic analysis shows that for a random received word, the expected listsize and the running time of the decoding algorithm are bounded by a polynomialin the block length. When applied to the Garcia-Stichtenoth tower, this yieldscodes of rate $R$ over an alphabet of size$\frac{1}{\epsilon^2}^{O\frac{1}{\epsilon}}$, that can correct a fractionof $1-R-\epsilon$ errors.

Author: ** Ming-Deh Huang, Anand Kumar Narayanan**

Source: https://arxiv.org/