\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{6}{September 27, 2004}{Madhu Sudan}{Kyomin Jung}
\noindent
Remark: We defer the proof of the next statement to some later lecture.(it occurred in the proof of Plotkin bound in the last lecture):\\
if $x_1,\ldots ,x_m\in \mathbb{R}^n$ satisfy $\forall$ $i\ne j$, $\le
0$ then, $m\le 2n$.
\\
\section{Overview}
In this lecture we will examine some topics of decoding codes.
Especially we will study Welch-Berlekamp algorithm, an error
detecting decoding algorithm for Reed Solomon Codes(RS Codes).
\section{Decoding linear codes}
When we encode or decode linear codes, the some problems of
finding efficient algorithm arise.
\begin{itemize}
\item Encoding codes: by multiplying the generator matrix,
complexity of encoding any linear code is $O(n^2)$.\footnote{Some
codes have lower encoding complexity. For example there exists an
$O(n(log n)^{O(1)})$ algorithm for encoding RS codes. There even
exist some linear-time encoding codes}
\item Detecting errors : For any linear codes, if the number of
errors is less than $d$, we can detect errors in $O(n^2)$ since it
only involves multiplication by $H$, the error check matrix.
\item Decoding from erasures
\item Decoding from erroneous codes: This is one of the main
topics in codes decoding and in this lecture we will cover one
algorithm for RS codes decoding.
\end{itemize}
\section{Decoding from erasure}
Given a generator matrix $G$, and a codeword $y\in (\sum \cup \{ ?
\})^n$ where $`?'$ represents an erasure,\\
Goal: find $x$ such that $xG$ is consistent with $y$.\\
Note that if $y_i\ne ?$, $(xG)_i=x(G_i)=y_i$ because $xG$ is
consistent with $y$. ( Here, $G_i$ refers
to the $i$th column of $G$ )\\
Now construct $G'$ consisting of such $i$th columns of $G$, and
$y'$ consisting of non $?$ elements of $y$. If the number of
erasure is less than $d$, than because $d\le n-k+1$, we can obtain
unique $x$ such that $xG'=y'$. Then this is the required $x$.
\section{Welch-Berlekamp algorithm for RS codes decoding('86)}
\subsection{Brief history for RS codes decoding}
\begin{itemize}
\item 1958,1959 - BCH codes were discovered.
\item 1960 - Peterson gave a polynomial time algorithm for
decoding BCH codes.
\item 1963 - Gorenstein Zierler saw that BCH codes and RS codes
have a common generalization. And the decoding algorithm extends
to more general situation.
\item 1968 - Berlekamp, Massey gave more efficient algorithm to
decode BCH, RS codes.
\end{itemize}
\subsection{Error-locator polynomial}
Let's recall the RS decoding problem. In this problem inputs are
pairwise distinct $\alpha_i$'s ($i=1\ldots n$) and a codeword
$y=(y_1,\ldots,y_n)\in\mathbb{F}^n$. Now our goal is to find a
polynomial $P$ over $\mathbb{F}$ such that $P$ has degree less
than $k$ and (the number of $i$'s s.t. $P(\alpha_i)\ne y_i$) $\le
\frac{d-1}{2}=\frac{n-k}{2}$. Note that the coefficients of $P$
are the encoded information.
To solve this problem, we may think of an indicator for the $i$'s
where error occurred. To this end, we will define a Error-locator
polynomial $E(x)$. $E(x)$ will be a polynomial over $\mathbb{F}$
such that $E(\alpha_i)=0$ if $y_i\ne P(\alpha_i)$ and the degree
of $E$ is less than or equal to $\frac{n-k}{2}$.
\begin{claim}
Error locator polynomial exists.
\end{claim}
\textbf{Proof}\\
Let $S=\{\alpha_i|P(\alpha_i)\ne y_i\}$\\
Then let $E(x)=\prod_{\alpha_i \in S}(x-\alpha_i)$.$\spadesuit$\\
Now, define $N(x)$ a polynomial over $\mathbb{F}$ by
$N(x)=E(x)P(x)$. Then $E(x)$ and $N(x)$ have following properties.
\begin{itemize}
\item $deg (E) \le \frac{n-k}{2}$
\item $E\ne 0$
\item $deg (N)\le \frac{n-k}{2}+(k-1)=\frac{n+k}{2}-1$
\item $\forall i$ $N(\alpha_i)=E(\alpha_i)y_i$
\item $\frac{N}{E}=P$
\end{itemize}
The proofs for the above properties are straightforward. Now we
introduce \textbf{Welch-Berlekamp Algorithm}. it uses above
properties of $E$ and $N$.\\
\subsection{Welch-Berlekamp Algorithm}
\textbf{Welch-Berlekamp Algorithm}\\
Find two polynomials $E_0(x)$, $N_0(x)$ such that
\begin{enumerate}
\item $deg E_0 = frac{n-k}{2}$, the highest coefficient of $E_0$
is 1.
\item $deg N_0\le \frac{n-k}{2}+(k-1)=\frac{n+k}{2}-1$
\item $\forall i$ $N_0(\alpha_i)=E_0(\alpha_i)y_i$
\end{enumerate}
We can find these $E_0$ and $N_0$ using $n$ linear equations of 3)
over $\frac{n-k}{2}+\frac{n+k}{2}=n$ unknown coefficients of $E_0$
and $N_0$. It can be performed in $O(n^3)$ time.
Let the output of this algorithm be $\frac{N_0}{E_0}$.
\begin{lemma} If $(N_1,E_1)$ and $(N_2,E_2)$ are two solutions
satisfying above 1), 2), 3), then
\begin{equation}
\frac{N_1}{E_1}=\frac{N_2}{E_2}
\end{equation}
\end{lemma}
\textbf{Proof}
For all $i$, $N_j(\alpha_i)=E_j(\alpha_i)y_i$.\\
If $y_i\ne 0$, we obtain
\begin{equation}
N_1(\alpha_i)E_2(\alpha_i)=N_2(\alpha_i)E_1(\alpha_i)
\end{equation}
by multiplying $N_1(\alpha_i)=E_1(\alpha_i)y_i$ and
$E_2(\alpha_i)y_i=N_2(\alpha_i)$ side by side.\\
If $y_i=0$, $N_1(\alpha_i)=N_2(\alpha_i)=0$. So (2) still holds.\\
Therefore (2) holds for all $i$.\\
Then because $N_1E_2$ and $N_2E_1$ have degrees less than $n$,
they must be identical.$\spadesuit$\\
Now, it can be easily checked that for some polynomial $R(x)$ with
degree $\frac{n-k}{2}-deg(E)$ , $(E(x)R(x),N(x)R(x))$ is one
solution for 1), 2), 3). And by definition of $N(x)$, it also can
be easily checked that $\frac{N\cdot R}{E\cdot R}=P$. So for any
solution $(N_0,E_0)$ of 1), 2), 3), $\frac{N_0}{E_0}=P$ as
expected.
\section{Abstracting the algorithm}
In this section, we will try to generalize the condition given for
the Welch-Berlekamp algorithm. When we consider $E$,$N$,$P$ of
Welch-Berlekamp algorithm, $E$ is an element of set $A$ of all the
polynomials with degree $\frac{n-k}{2}$ or less. Similarly $N$ is
an element of set $B$ of all the polynomials with degree
$\frac{n+k}{2}-1$ or less, and $P$ is an element of set $C$ of all
the polynomials with degree $k-1$ or less.\\
Then the problem we need to solve is,\\
Given $(A,B,C)$ and $y=(y_1,y_2,\ldots,y_n)$ such that $y$ is (in
some sense) close to some element of $C$,\\
Find $E\in A$ , $N\in B$ such that $E\ne 0$ and $\forall i$
$E_iy_i=N_i$.\\
More precise description and analysis of this generalization will
be given in the next lecture.
\end{document}