Optimal rate algebraic list decoding using narrow ray class fields

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:129

Article

Guruswami, Venkatesan¹  Xing, Chaoping² 

[1] Carnegie Mellon Univ, Dept Comp Sci, Pittsburgh, PA 15213 USA

[2] Nanyang Technol Univ, Sch Phys & Math Sci, Div Math Sci, Singapore 637371, Singapore

关键词: Folded codes;    Automorphism;    Class fields;    Chebotarev Density Theorem;    Encoding and decoding;   

DOI  :  10.1016/j.jcta.2014.09.003

来源: Elsevier

【 摘 要 】

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 l(2), these codes are within 2/(root l - 1) of the Singleton bound. The function 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 R is an element of (0,1) and constant epsilon > 0, we get codes over an alphabet size (1/epsilon)(O(1/epsilon 2)) that can be list decoded up to error fraction 1-R-epsilon confining close-by messages to a subspace with N-O(1/epsilon 2) elements. Previous results for list decoding up to error-fraction 1 - R - epsilon 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 themselves have the claimed list decoding property. (C) 2014 Elsevier Inc. All rights reserved.

【 授权许可】

Free