Folded Algebraic Geometric Codes From Galois Extensions

zbMATH Open1220.94054arXiv0901.1162MaRDI QIDQ3062279FDOQ3062279

Authors:

Publication date: 3 January 2011

Abstract: 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 $(frac1epsilo{n}^2{)}^{O(frac1epsilon)}$, that can correct a fraction of $1-R-epsilon$ errors.

Full work available at URL: https://arxiv.org/abs/0901.1162

Recommendations

• Artin automorphisms, cyclotomic function fields, and folded list-decodable codes
• Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate
• List decoding of algebraic-geometric codes
• Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets (extended abstract)
• Optimal rate algebraic list decoding using narrow ray class fields
• scientific article; zbMATH DE number 2154145
• On representations of algebraic-geometry codes
• On the decoding of algebraic-geometric codes over F/sub q/ for q<or=16
• scientific article; zbMATH DE number 1670663

zbMATH Keywords

algebraic function fieldserror-correcting codeslist-decoding algorithm

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Arithmetic theory of algebraic function fields (11R58) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Cited In (1)

• Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate

This page was built for publication: Folded Algebraic Geometric Codes From Galois Extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3062279)