\documentclass[10pt]{article}
\usepackage{amsfonts}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\bf Z}}
\usepackage{epsfig}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\begin{document}
\input{preamble.tex}
\lecture{8}{October 4, 2004}{Madhu Sudan}{Anindya C. Patthak}
%%%% body goes in here %%%%
\section{Overview}
In this lecture we will cover List Decoding of Reed-Solomon Codes.
\section{List Decoding of Reed-Solomon Codes: Combinatorial
Perspective} \label{sec:ListDecodingCombinatorial}
In the last lecture we have seen the combinatorial version of
list decoding. Recall that
we are given a code of distance $d$ and we would like to correct
more than $d/2$ errors. We argued that unique decoding is not
possible. Therefore we decided on outputting a small list of
codewords that has good agreement with the received word. We
established the following combinatorial version of list decoding
that ensured existence of a polynomial size list provided the
agreement is suitably large.
\begin{theorem}
\label{thm:JohnsonBound}(Combinatorial Version) Let $C$ be an
$(n,k,d)$ error\footnote{The bound on list size does not depend on
the dimension $k$.} correcting code over an alphabet $\Sigma$ of
size $q$. Then given any ball $B(x,r)$, where $x\in \Sigma^n$ and
$r=n-\sqrt{(n-d)n}$, the set $C\cap B(x,r)$ has size at most
$\poly(n)$, more specifically $n^2$.
\end{theorem}
\begin{definition}
\label{defn:elCorrectingCode} Given an $[n,k,d]_q$ code $C$ over
an alphabet $\Sigma$, we say that $C$ is $(e,\ell)$-list decodable
code, if for every $x\in \Sigma^n$, $B(x,e)\cap C$ has size at
most $\ell$.
\end{definition}
The following corollary is then immediate from Theorem
\ref{thm:JohnsonBound}.
\begin{corollary}
\label{cor:JohnsonBoundForRS} ({\bf List Decoding of Reed-Solomon
Codes}:Combinatorial Version) An $[n,k,n-k+1]_q$ $\rs$ code is
$(n-\sqrt{n(k-1)},n^2)$-list decodable.
\end{corollary}
\section{List Decoding of Reed-Solomon Codes: Algorithmic
Perspective} \label{sec:ListDecodingAlgorithmic} The algorithmic
challenge of list decoding is the following:
\begin{center}
{\em Given an $(e,\ell)$-list decodable code $C$ and any received
word $y=\langle y_1,\cdots,y_n\rangle$, output the set $B(y,e)\cap
C$.}
\\
\end{center}
For an easier exposition, we give the following definition.
\begin{definition}
\label{defn:agreement} Given $x,y \in \F_q^n$, we define the
agreement between $x$ and $y$ to be
\[ \mbox{agreement}(x,y)\stackrel{def}{=}|\{i|x_i = y_i\}|. \]
\end{definition}
With this definition, we reformulate our list-decoding task the
following way:
\begin{center}
{\em Given any $(e,\ell)$-list decodable code $C$ and a received
word $y=\langle y_1,\cdots,y_n\rangle$, output the set $\{x\in C\;
|\; \mbox{ agreement}(x,y)\geq t\}$, where we set $t=n-e$.}
\end{center}
We now describe an algorithm to list-decode $\rs$ codes from
$(k+1)\sqrt{n}+1$ agreements. With some parameter optimization,
the same algorithm can be used to list-decode $\rs$ codes from
agreements as low as $2\sqrt{kn}+1$. It is possible to improve our
result to correct more errors. There is an algorithm due to
Guruswami and Sudan that can list-decode $\rs$ codes from
agreement as small as $\sqrt{kn}+1$. However, that requires more
sophisticated arguments and therefore we skip.
\subsection{Problem Formulation}
\label{sec:Intuition}
We quickly recall the problem we are considering.
\begin{tabbing}
\= \hspace*{0.2in}\= \textsc{Problem}: {\bf List Decoding of Reed-Solomon codes}
\\
\> \> \textsc{Input}: $\F, n, k, t$;
$\alpha_1,\cdots,\alpha_n \in \F$, a received vector
$\langle{y_1,\cdots,y_n\rangle}\in \F^n$. \\
\> \> \textsc{Goal}: Find all polynomials $p$ of degree $ (k+1)\sqrt{n}$.
\par Recall that in Welch-Berlekamp Decoder we
carry out the following steps:
\vspace{0.2in} \\
\hspace{0.2in} \textsc{Welch-Berlekamp Decoder}
\begin{tabbing}
\= 1. \= Find polynomials $(N,E)$ s.t.\ $N(\alpha_i)/E(\alpha_i)=
y_i$ holds for all $i\in [n]$ provided $E(\alpha_i)\neq 0$ \\
\> 2. \> Output $N(x)/E(x)$
\end{tabbing}
%We have already seen that if the error is not too large then this
%works.
Alternatively we may think of finding a rational function
``to explain'' the data. We will make this idea precise soon.
Recall that univariate rational functions are functions that are
fraction of two univariate polynomials. They have a form
$f(x)/g(x)$, where $f(x)$ and $g(x)$ are univariate polynomials.
They also need to satisfy the requirement that whenever $g(x)=0$
implies $f(x)=0$. In another words the zero set of polynomial
$g(x)$ is a subset of the zero set of polynomial $f(x)$. Note if
$f(x)$ and $g(x)$ are given explicitly, then it is necessary that
$g(x)$ divides $f(x)$ and this does not give more power than
univariate polynomials. However, the power comes if we do not know
$f(x)$ and $g(x)$ explicitly, but given any $x$, we can compute
$f(x)$ and $g(x)$. Let $r(x)=f(x)/g(x)$ be a rational function.
Suppose $\alpha$ is in the zero set of $g(x)$. Then we know
$g(\alpha)=f(\alpha)=0$. How should we define $r(\alpha)$? A good
idea is to allow $r(\alpha)$ to take any possible value. This is
explained in the Figure~\ref{fig:rationalfunction}.
\fig{fig:rationalfunction}{2.9in}{Interpretation of data through
rational function}{rationalfnc.eps}
Therefore, given a set of $\{(\alpha_i,y_i)\}_{i\in [n]}$, we
relax the Welch-Berlekamp-type interpolation problem as follows:
\begin{itemize}
\item (\textsc{Welch-Berlekamp}-type Goal): Find a {\it
polynomial} $p(x)$ such that $p(\alpha_i)$ {\em equals} $y_i$
{\it for many $i$}
\item (Reformulation): Find a {\it rational function} $r(x)$ which {\em
explains} $y_i$ for all $\alpha_i$
\end{itemize}
Thus we replace the claim in Welch-Berlekamp by the following
claim.
\begin{claim}
\label{clm:Welch-Berlekampclm}(Welch-Berlekamp) If $\exists p$ of
degree $ \> \textsc{Input}: $\{(\alpha_i,y_i)\}_{i\in [n]},
t> (k+1)\sqrt{n}$ \\
\> \> \textsc{Output}: A list of univariate polynomials
$p_j$ of degree $\leq k$ such that $p_j(\alpha_i)=y_i$ for at least $t$ \\
\> \> \hspace*{0.4in} values of $i$
\end{tabbing}
\begin{tabbing}
\= 1. \= Find $Q(x,y)\neq 0$ where
$\mbox{deg}_x(Q),\mbox{deg}_y(Q) \leq \sqrt{n}$ such that
$Q(\alpha_i,y_i)=0$ for all $i$ \\
\> 2. \> Factor $Q(x,y)$ into irreducible polynomials i.e., let
$Q(x,y)=Q_1(x,y)\cdots Q_s(x,y)$ \\
\> 3. \> Output all polynomials $p_1,\cdots p_j$ of degree
$\leq k$ if $(y-p_j(x))\equiv Q_j(x,y)$ and \\
\> \> $p_j(\alpha_i)=y_i$ for at least $t$ values of $i$
\end{tabbing}
\begin{claim}
\label{clm:AnalysisOfListDecoder} Algorithm \textsc{List Decoding
of $\rs$ code} runs in poly time and outputs all polynomial $p(x)$
such that $p(\alpha_i)=y_i$ for at least $t$ values of $i$.
\end{claim}
\begin{proof-sketch}
Step 1 and 3 can clearly be done in polynomial time. Moreover there
are efficient algorithms to solve the multivariate polynomial factorization
problem over finite fields (in fact over almost all fields).
Deterministic versions of these algorithms takes
$poly(\log |\F|,n)$ steps over most fields and $poly(|\F|,n)$ steps
over few fields\footnote{For example, over a large prime field $\F_p$}.
However efficient randomized versions are known that runs in
$poly(\log |\F|,n)$ time for all fields. This ensures that the algorithm is
efficient i.e., runs in polynomial time.
\par By Claim~\ref{clm:bivariateInterpolation} we know step 1
always finds a non-trivial $Q$. Therefore all that remains to show
is the following: If $p$ has degree $\leq k$ and satisfies
$p(\alpha_i)=y_i$ for at least $t$ values of $i$ and if $Q(x,y)$
is an output of step 1, then $(y-p(x))| Q(x,y)$ provided $t>(k+1)\sqrt{n}+1$.
Assume $p(x)$ is such a polynomial.
\par How could one hope to prove such divisibility results? In
general this may be addressed using age-old Bezout's theorem.
\begin{theorem}
\label{thm:BezoutTheorem}(Bezout's Theorem in the plane) Let
$Q_1(x,y)$ and $Q_2(x,y)$ be bivariate polynomials of degree at most
$D_1$ and $D_2$, respectively over a field $F$. If $Q_1(x,y)$
and $Q_2(x,y)$ have more than $D_1\cdot D_2$ common zeros, then
they share a non-trivial factor.
\end{theorem}
Thus if one of the polynomials is irreducible, then this
gives a divisibility criteria. It turns out that we can argue
even simpler. We recall the following innocent lemma.
\begin{lemma}
\label{lem:RemainderTheorem}
(Remainder Theorem) Let $g(y)$ be an univariate polynomial over a field $F$. Then for
any $\gamma \in \F$, $(y-\gamma) | g(y)$ {\it if and only if}
$g(\gamma)=0$.
\end{lemma}
We mention that the above theorem holds over UFD (Unique
Factorization Domain). We also mention that $\F[x],\F[x_1,\cdots,x_n]$
i.e., the ring of univariate and multivariate polynomials over a
field, are in fact UFD. We will apply the above lemma over
$\F[x]$.
\par Recall we want to show that $(y-p(x))|Q(x,y)$.
By Lemma~\ref{lem:RemainderTheorem}, it is therefore enough to
show that $Q(x,p(x))$ is identically zero polynomial. Define
\[h(x)\stackrel{def}{=} Q(x,p(x)).\]
The following claim can easily be verified by replacing $y$ by
$h(x)$.
\begin{claim}
\label{clm:hsdegreebound} $\mbox{deg}(h(x)) \leq (1+k) \sqrt{n}$.
\end{claim}
By hypothesis we have that $p(\alpha_i)=y_i $ for at least $t$
values of $i$. Note whenever it holds that $p(\alpha_i)=y_i$,
we have $h(\alpha_i)=Q(\alpha_i,p(\alpha_i))=Q(\alpha_i,y_i)=0$.
This implies the following claim.
\begin{claim}
\label{clm:hhasmanyzeros} $h(x)$ has at least $t$ zeros.
\end{claim}
Since a univariate polynomial of degree $d$ can have at most $d$
zeros, from Claims~\ref{clm:hsdegreebound}
and~\ref{clm:hhasmanyzeros} and the fact that $t> (1+k)\sqrt{n}$ we conclude
that $h(x)$ must be identically zero polynomial. This concludes the
analysis.
\end{proof-sketch}
\begin{remark}
\label{rem:numberofsolution}
Note that the $\mbox{deg}_y(Q)\leq \sqrt{n}$ and therefore it
can have at most $\sqrt{n}$ factors of the form $(y-p(x))$.
However this does not improve upon the combinatorial version
of the list decoding. The agreement assumed here is much larger than
the one assumed in the combinatorial version.
\end{remark}
\par We now modify the interpolation lemma slightly. We now try
to find a bivariate poly $Q(x,y)$ with $\mbox{deg}_x(Q) \leq
\sqrt{kn} $ and $\mbox{deg}_y(Q) \leq \sqrt{n/k}$. With this
setting the same algorithm can be used to recover codewords from
agreement $t>2\sqrt{kn}$ (can be proved in an analogous fashion).
\begin{theorem}
\label{thm:ImprovedRSListDecoder} Interpolating with a bivariate
polynomial $Q(x,y)$ with $\mbox{deg}_x(Q)\leq \sqrt{nk}$ and
$\mbox{deg}_y(Q) \leq \sqrt{n/k}$, the algorithm \textsc{List
Decoding of RS code} solves the $\rs$ list decoding problem with
agreements $>2\sqrt{kn}$ in polynomial time.
\end{theorem}
({\bf Notes})
\begin{enumerate}
\item As mentioned previously the best
known list decoding algorithm can correct from agreements as low
as $\sqrt{kn}$. Moreover the algorithm does not necessarily
require that all $\alpha_i$'s are distinct. Though it assumes a
bound on the number that a distinct $\alpha_i$ can appear. We
leave the details.
\item Can we do better? A recent result of Guruswami and Rudra
suggest that in order to improve the algorithm we have to exploit
the fact that many $\alpha_i$'s are distinct.
\item At this moment all the combinatorial results involving
Reed-Solomon codes have their algorithmic counterparts.
We mention that Guruswami and Vardy have recently shown that
the Maximum-Likelihood Decoding of Reed-Solomon Code is ${\rm
NP}$-${\rm complete}$.
\end{enumerate}
\end{document}