__
TR13-046 | 27th March 2013 16:16
__

#### Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets

**Abstract:**
We construct a new list-decodable family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. The function fields underlying these codes are constructed using class field theory, specifically Drinfeld modules of rank $1$, and designed to have an automorphism of large order that is used to ``fold" the AG code. This generalizes earlier work by the first author on folded AG codes based on cyclotomic function fields. The recent linear-algebraic approach to list decoding can be applied to our new codes, and crucially, we use the Chebotarev density theorem to establish a polynomial upper bound on the list-size for list decoding 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 \in (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 chosen subcode of algebraic-geometric codes. In contrast, our result shows that these folded algebraic-geometric codes {\em themselves} have the claimed list decoding property. Further, our methods to get function fields with the properties needed for constructing and decoding the code might be of independent algebraic interest.