Optimal rate algebraic list decoding using narrow ray class fields

DOI10.1016/J.JCTA.2014.09.003zbMATH Open1361.94066arXiv1302.6660OpenAlexW2013369084MaRDI QIDQ472174FDOQ472174

Authors: Venkatesan Guruswami, Chaoping Xing 

Publication date: 19 November 2014

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

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.

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)

Cites Work

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

Cited In (6)

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

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)