Optimal rate algebraic list decoding using narrow ray class fields

DOI10.1016/J.JCTA.2014.09.003MaRDI QIDQ472174zbMATH OpenOpenAlexFDO

Authors Venkatesan Guruswami, Chaoping Xing

Publication date 19 November 2014

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

automorphismChebotarev density theoremclass fieldsencoding and decodingfolded codes

Mathematics Subject Classification ID

Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27) Decoding (94B35)

Abstract: We use class field theory, specifically Drinfeld modules of rank 1, to construct a family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. Over a field of size $el{l}^2$, these codes are within $2/(sqrtell-1)$ of the Singleton bound. The functions fields underlying these codes are subfields with a cyclic Galois group of the narrow ray class field of certain function fields. The resulting codes are "folded" using a generator of the Galois group. This generalizes earlier work by the first author on folded AG codes based on cyclotomic function fields. Using the Chebotarev density theorem, we argue the abundance of inert places of large degree in our cyclic extension, and use this to devise a linear-algebraic algorithm to list decode these folded codes up to an error fraction approaching $1-R$ where $R$ is the rate. The list decoding can be performed in polynomial time given polynomial amount of pre-processed information about the function field. Our construction yields algebraic codes over constant-sized alphabets that can be list decoded up to the Singleton bound --- specifically, for any desired rate $Rin(0,1)$ and constant $eps>0$, we get codes over an alphabet size $(1/eps{)}^{O(1/ep{s}^2)}$ that can be list decoded up to error fraction $1-R-eps$ confining close-by messages to a subspace with $N^{O(1/ep{s}^2)}$ elements. Previous results for list decoding up to error-fraction $1-R-eps$ over constant-sized alphabets were either based on concatenation or involved taking a carefully sampled subcode of algebraic-geometric codes. In contrast, our result shows that these folded algebraic-geometric codes {em themselves} have the claimed list decoding property.

Cites work

• scientific article; zbMATH DE number 125898 (Why is no real title available?)
• scientific article; zbMATH DE number 702026 (Why is no real title available?)
• scientific article; zbMATH DE number 1532366 (Why is no real title available?)
• A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound
• Algebraic function fields and codes
• Computing Riemann-Roch spaces in algebraic function fields and related topics.
• Computing equations of curves with many points
• Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate
• Encoding and error-correction procedures for the Bose-Chaudhuri codes
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
• Field Arithmetic
• Folded codes from function field towers and improved optimal rate list decoding
• Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
• List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound
• On the asymptotic behaviour of some towers of function fields over finite fields

Cited in

(6)

• The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally repairable codes
• Folded Algebraic Geometric Codes From Galois Extensions
• Subspace designs based on algebraic function fields
• Optimal Rate List Decoding via Derivative Codes
• Folded codes from function field towers and improved optimal rate list decoding
• The asymptotic behavior of automorphism groups of function fields over finite fields

This page was built for publication: Optimal rate algebraic list decoding using narrow ray class fields

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