TR05-132 Authors: Venkatesan Guruswami

Publication: 13th November 2005 19:39

Downloads: 3794

Keywords:

This paper is concerned with a new family of error-correcting codes

based on algebraic curves over finite fields, and list decoding

algorithms for them. The basic goal in the subject of list decoding is

to construct error-correcting codes $C$ over some alphabet $\Sigma$

which have good rate $R$, and at the same every Hamming ball of

(relative) radius $p$ has few codewords of $C$, and moreover these

codewords can be found in polynomial time.

The trade-off between the rate $R$ and the error-correction radius $p$

is a central one governing list decoding. Traditional ``unique

decoding'' algorithms can achieve $p = (1-R)/2$, and this was improved

in \cite{GS} to $p =1 - \sqrt{R}$ through a new list decoding

algorithm for Reed-Solomon (RS) codes. For several years, this

remained the best known trade-off between rate and list decoding

radius. In a recent breakthrough, Parvaresh and Vardy~\cite{PV} define

a variant of RS codes which can be list decoded beyond the

$1-\sqrt{R}$ radius for rates $R \le 1/16$.

We generalize the PV framework to algebraic-geometric

(AG) codes, of which RS codes are an important special case. This

shows that their framework applies to fairly general settings, and

also better elucidates the key algebraic concepts underlying the new

codes. Moreover, since AG codes of arbitrary block length exist over

{\em fixed} alphabets $\Sigma$, we are able to almost match the

trade-off between $p$ and $R$ obtained in \cite{PV} over alphabets of

{\em constant} size. In contrast, the PV codes have alphabet size that

is polynomially large in the block length.

Similar to list decoding algorithms for AG codes, our

encoding/decoding algorithms run in polynomial time assuming a natural

polynomial-size representation of the code. For codes based on a

specific ``optimal'' algebraic curve, we also present an expected

polynomial time algorithm to construct the requisite representation.