\documentclass[10pt]{article}
\usepackage{amsfonts}
\newtheorem{define}{Definition}

%\newcommand{\Z}{{\bf Z}}
\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

\lecture{16}{November 7, 2005}{Madhu Sudan}{Sergey Yekhanin}

\section{Today}

\begin{itemize}

\item Decoding of Reed-Solomon (RS) codes.

\item Decoding of Chinese Remainder (CR) codes.

\end{itemize}

\section{Error-correcting codes}

The theory of error-correcting codes studies the ways one should
add redundancy to data, in order to allow reliable transmission
over noisy channels. The theory was founded by Claude Shannon in
the 1940-s. Shannon proposed the following architecture:

\begin{center}
$m \in \Sigma^k$ $\rightarrow$ ENCODER $\rightarrow$ $E(m) \in
\Sigma^n$ $\rightarrow$ NOISY CHANNEL $\rightarrow$ $y\approx
E(m)$ $\rightarrow$ DECODER $\rightarrow$ $m^\prime = E(m).$
\end{center}

Here
\begin{itemize}
\item $m$ is the message one wants to transmit.

\item $E(m)$ is the encoding of $m$. I.e. $m$ plus some extra
redundant bits.

\item $y$ is the corrupted version of $E(m).$ I.e. $y$ agrees with
$E(m)$ in most of the locations except those that got flipped in
the channel during the transmission.

\item $m^\prime$ is the corrected version of of $E(m).$ For a good
and appropriately used error-correcting code $m^\prime$ should
(most of the time) be equal to $E(m).$

\end{itemize}

\section{Reed-Solomon code}

In this section we consider a classical error-correcting code
known as a Reed-Solomon code.

Assume we have a bijection between our message alphabet $\Sigma$
and some finite field $F_q.$ Fix some subset $M\subseteq F_q.$ Let
$M=\{\alpha_1,\ldots,\alpha_n\}.$

We represent messages $m=(m_0,\ldots,m_{k-1}) \in \Sigma^k$ by
univariate polynomials
$$m(x)=\sum\limits_{i=0}^{k-1}m_ix^i \in F_q[x].$$

We define the encoding of $m$ to be the evaluation of the
corresponding polynomial at every point of the set $M.$ I.e.
$$Enc(m)=\{m(\alpha_1),\ldots,m(\alpha_n)\}.$$

After some bits of $\{m(\alpha_1),\ldots,m(\alpha_n)\}$ are
flipped in the channel decoder gets the sequence
$\{y_1,\ldots,y_n\}$ as an input. Assuming that the number of
errors in the channel is upper bounded by $(n-t),$ the goal of the
decoder is to find a polynomial (or better - all polynomials) $m
\in F_q[x]$ such that $m(\alpha_i)=y_i$ for al least $t$ values of
$i\in [1,n].$

It is convenient to think of pairs $(\alpha_i,y_i)$ as points in
the plane $F_q^2.$ Our goal is to find all curves of the form
$y-m(x)=0,$ (where $m(x)$ is of degree $\leq k-1$) that pass
through at least $t$ points of the set $S=\{(\alpha_i,y_i)\}_{i\in
[1,n]}.$

Instead of trying to find the curves of the form $y-f(x)$
directly, we will first fit all the points of the set $S$ to some
low-degree curve (with no other restriction on the form of the
equation defining the curve). It is easy to see that there exists
a bivariate polynomial $Q(x,y)$ where $\deg_x Q\leq {\sqrt n}$ and
$\deg_x Q\leq {\sqrt n}$ such that $Q(\alpha_i,y_i)=0$ for all
$(\alpha_i,y_i)\in S.$ Moreover one can compute the polynomial
$Q(x,y)$ efficiently in time $O(n^3)$ by solving a system of $n$
homogeneous linear equations in the coefficients of $Q.$

Given the polynomial $Q(x,y)$ we want to claim that for every
polynomial $m(x)$ such that $y-m(x)$ contains sufficiently many
points from $S,$ $y-m(x) | Q(x,y).$ Formally,

\medskip

{\bf Claim 1:} Assume the following hold:
\begin{itemize}

\item $\deg_x Q\leq D,$ $\deg_y Q\leq D,$

\item $\deg m(x)\leq k-1,$

\item $Q(\alpha_i,y_i)=y_i-m(\alpha_i)=0$ for at least $t$ values
of $i\in [1,n],$

\item $t>2(D+1)k;$

\end{itemize}
then  $y-m(x) | Q(x,y).$

{\bf Proof:} It is clear that the polynomial $y-m(x)$ is irreducible.
Assume $y-m(x) \not | Q(x,y)$; then there exist polynomials
$A(x,y), B(x,y) \in F_q[x,y]$ such that
$$
R(x)=A(x,y)Q(x,y)+B(x,y)(y-m(x)).
$$
is non-zero. Namely, $R(x)$ is a resultant of $Q$ and $y-m(x)$
computed with respect to $y$. From the degree bound for the
resultant we conclude that $\deg R(x)\leq 2(D+1)k.$ However
$R(\alpha_i)=0$ for all $\alpha_i$ such that
$Q(\alpha_i,y_i)=y_i-m(\alpha_i)=0.$ Therefore $R(x)$ has at least
$2(D+1)k+1$ roots. Thus we arrive at a contradiction. Proof
complete.

\medskip

Given the claim above we are ready to formulate the (list)
decoding algorithm for Reed-Solomon codes:

\medskip

{\bf Algorithm 1:}
\begin{enumerate}

\item Input: $k,n,\{(\alpha_i,y_i)\}_{i\in [1,n]}.$

\item Find $Q(x,y)$ such that $\deg_x Q\leq {\sqrt n},$
      $\deg_y Q\leq {\sqrt n},$ $Q(\alpha_i, y_i)=0,$ and
      $Q(x,y)\ne 0.$

\item Find all factors of $Q(x,y)$ of the form $y-m(x).$

\item Output: A list of polynomials $m(x)$ such that $y-m(x) |
Q(x,y)$ and $y-m(x)$ passes through at least $t$ points
$(\alpha_i,y_i).$

\end{enumerate}

\medskip

Claim 1 implies that our algorithm successfully decodes RS code
from up to $2{\sqrt n}k$ agreement.

{\bf Exercise 1:} Improve the decoding algorithm to decode
successfully from $t>\min\{(n-k)/2, 2{\sqrt {kn}}\}$ agreement.

\medskip

We conclude our discussion of decoding algorithm for RS codes with
a historical overview:

\begin{itemize}

\item The first decoding algorithm for RS codes was developed by
Peterson in the sixties. The algorithm runs in time $O(n^3).$
Petersen claimed his algorithm to be {\it efficient} as it avoided
the brute-force search. Note that this work precedes the work of
Edmonds!

\item Later the running time was brought down to $O(n^2)$ by
Berlekamp.
      Berlekamp's algorithm relies on efficient randomized factorization
      of univariate polynomials. (Which is also due to Berlekamp.)

\item The algorithm that we have just seen was developed by Sudan in 1996.
      It allows to correct a larger number of errors than previously known
      algorithms. The algorithm relies on efficient factorization of
      multivariate polynomials.

\end{itemize}


\section{Chinese Remainder code}

We use $p_i$ to denote the $i$-th prime. Let
$K=\prod\limits_{i=1}^{k}p_i.$ Assume our message $m$ is a
sequence of $\log K$ bits. We can think of it as an integer $0
\leq m \leq K-1.$ Let $n$ be an integer such that $k\leq n.$ the
Chinese Remainder encoding of $m$ is:
$$
Enc(m) = \{(m \mbox{ mod } p_1),\ldots,(m\mbox{ mod } p_n)\}.
$$

Clearly, any $k$ coordinates of the $Enc(m)$ suffice to reconstruct the
message $m.$ This follows from the standard CRT "interpolation".

The decoding problem for the CR code is the following. Given
integers $\{r_1,\ldots,r_n\}$ find some integer $m\in [0,K-1]$ (or
better - all such integers), such that $m\mbox{ mod } p_i = r_i$
for at least $t$ values of $i.$ In what follows we will sketch the
solution of this problem assuming $t\geq 2k{\sqrt n}\log p_n/\log
p_1.$

Our approach is to extend the technique we have for decoding of RS
codes. We start by building some informal dictionary between $Z$ and
$F_q[x].$

$$
\begin{array}{ccc}

Z                         &                 & F_q[x]                        \\
\mbox{small integer}      & \leftrightarrow & \mbox{low degree polynomial}  \\
Z[y]                      & \leftrightarrow & F_q[x,y]                      \\
Q(r_i)=0 \mbox{ mod } p_i & \leftrightarrow & Q(\alpha_i,y_i)=0.            \\
\end{array}
$$

Using the dictionary above we "translate" the algorithm for decoding of RS codes
into an algorithm for decoding of CR codes.

\medskip

{\bf Algorithm 2:}
\begin{enumerate}

\item Input: $k,n,\{(p_i,r_i)\}_{i\in [1,n]}.$

\item Find $Q(y)\in Z[y]$ such that $\deg Q\leq {\sqrt n},$
      $Q(r_i)=0 \mbox{ mod } p_i,$ $Q(y)\ne 0,$ and all
      coefficients of $Q(y)$ are small.
      (The particular meaning of small that we need here is $\leq p_n^{\sqrt n}/2$
      in the absolute value.)

\item Find all linear factors of $Q(y).$ They are of the form $y-m.$

\item Output: A list of integers $m$ such that $y-m |
Q(y)$ and $m = r_i \mbox{ mod } p_i$ for at least $t$ values of $i.$

\end{enumerate}

\medskip

There is a simple counting argument that allows one to conclude that a
polynomial $Q(y)$ that we want to find in step~1 really exists. One needs to
look at the number of polynomails of degree $\leq {\sqrt n}$ with coefficients
in the range $[-p_n^{\sqrt n}/2,p_n^{\sqrt n}/2],$ and compare this number
to $\prod\limits_{i=1}^{n} p_i.$ However, finding such a $Q(y)$ is no longer
a linear algebra problem. Luckily it can be reduced to finding short vector in
the lattice and thus be (approximately) resolved using the LLL algorithm.

\medskip

{\bf Exercise 2:} Prove the correctness of step 2 of the decoding
                  algorithm for CR codes.


\end{document}