Title: Attaining Capacity with Algebraic Geometry Codes through the $(U|U+V)$ Construction and Koetter-Vardy Soft Decoding,
Abstract: In this paper we show how to attain the capacity of discrete symmetric
channels with polynomial time decoding complexity by considering iterated
$(U|U+V)$ constructions with Reed-Solomon code or algebraic geometry code
components. These codes are decoded with a recursive computation of the {\em a
posteriori} probabilities of the code symbols together with the Koetter-Vardy
soft decoder used for decoding the code components in polynomial time. We show
that when the number of levels of the iterated $(U|U+V)$ construction tends to
infinity, we attain the capacity of any discrete symmetric channel in this way.
This result follows from the polarization theorem together with a simple lemma
explaining how the Koetter-Vardy decoder behaves for Reed-Solomon codes of rate
close to $1$. However, even if this way of attaining the capacity of a
symmetric channel is essentially the Ar{\i}kan polarization theorem, there are
some differences with standard polar codes.
Indeed, with this strategy we can operate succesfully close to channel
capacity even with a small number of levels of the iterated $(U|U+V)$
construction and the probability of error decays quasi-exponentially with the
codelength in such a case (i.e. exponentially if we forget about the
logarithmic terms in the exponent). We can even improve on this result by
considering the algebraic geometry codes constructed in \cite{TVZ82}. In such a
case, the probability of error decays exponentially in the codelength for any
rate below the capacity of the channel. Moreover, when comparing this strategy
to Reed-Solomon codes (or more generally algebraic geometry codes) decoded with
the Koetter-Vardy decoding algorithm, it does not only improve the noise level
that the code can tolerate, it also results in a significant complexity gain.