\documentclass[10pt]{article}

\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
%\newcommand{\Z}{{\bf Z}}
\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\parindent=0mm
\parskip=2mm

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

\lecture{10}{October 9, 2002}{Madhu Sudan}{Fu Liu}

%%%% body goes in here %%%%

\section{Overview}
\label{sec:overivew}

\begin{itemize}
\item Algorithmic issues
\item Algorithm for decoding Reed-Solomon codes
\end{itemize}

\section{Algorithmic tasks}
Broadly, it's relatively easier to give an encoding function and construction of a code than to find a decoding algorithm.

\subsection{Encoding}

If given a family of encoding functions $\{E_n | E_n : \{0, 1\}^k \rightarrow \{0, 1\}^n \}_n$, 
we would like to ask that how efficiently they can be computed.

It turns out that it is pretty hard when code is specified as part of the input. 
Fortunately, it works well for linear codes in polytime.
Also, if the encoding problem is given as "given an circuit $E,$ for the $i$th member of a family of a code, and a message $m,$ 
compute its encoding." The this problem is trivial to solve in linear time in the size of $E.$

\subsection{Construction of Code}

\begin{itemize}
\item Code $\cal C \subseteq$ $\{0, 1\}^n$
\item $|\cal C|$ $= 2^k$
\item Encoding circuit $E: \{0, 1\}^k \rightarrow \cal C.$
 
	Circuit for $E$ maybe specifictation of $\cal C.$
\item \[
	Decide(x) = \left\{
	\begin{array}{ll}
	1, &\quad \mbox{if $x \in \cal C$}\\
	0, &\quad \mbox{otherwise}
	\end{array}
	\right.
	\]
	
	Circuit for $Decide$ is specification of $\cal C.$ 
\end{itemize}

\subsection{Decoding}

Now we come to the hard part. The problem can be stated informally as "if message $c$ is sent, how can we compute $c$ from the received message $r$? Also, we we consider the specification of the encoding function $E,$ when/how is it specified" and "how much time it takes to design the decoding algorithm"... Unfortunately, these problems are so hard that we do not know any efficient algorithm. So we will have to focus on some specific codes.

\subsubsection{Popular definitions in decoding}

\begin{enumerate}
\item{Maximum Likelihood Decoding (MLD)}

If we are given the channel, the code $\cal C,$ and a received vector $r \in \Gamma^n,$ find a codeword $c \in \cal C,$ which
$$\mbox{maximizes Pr}_{\mbox{channel}} \mbox{ [$r$ seen $|$ $c$ sent].}$$

\item{Nearest Codeword Problem (NCP)}

Given channel and the code $\cal C,$ and received vector $r \in \Sigma^n,$ find a codeword $c \in \cal C,$ which 
$$\mbox{minimizes } \Delta (c, r).$$

If we look back the MLD problem and give the channel as a $q$-ary symmetric channel, i.e. if $\Sigma = \{x_1, x_2, \dots, x_q\},$ for $\forall i: 1 \le i \le q,$ the probability of $x_i$ seen when $x_i$ sent is $1-p,$ and the probablity of $x_j (j \neq i)$ seen when $x_i$ sent is $p \over {1-q},$ 
where $1 - p > { 1 \over q}$ and $|\Sigma| = q.$ Then this problem is just a NCP. 
This is a connection between MLD and NCP.

\item{Soft-decision Decoding Problem}

Given the channel, the code $\cal C$ and a $\Sigma$ by $n$ matrix $M,$ whose entries are nonnegative reals, find a $c \in \cal C,$ that
$$\mbox{minimizes} \Sigma_{i=1}^n M_{c_i,i}$$

If $M$ is given as a $0/1$ matrix with one $1$ in each column. Then it is the NCP problem.

If Assume the given channel is i.i.d.. Then
\begin{eqnarray}
& &\mbox{Pr[$r$ seen $|$ $c$ sent]} \nonumber \\
&=&\Pi_{i=1}^n \mbox{Pr[$r_i$ seen $|$ $c_i$ sent]} \nonumber \\
&=&\mbox{EXP} (\Pi_{i=1}^n \underbrace{- log \mbox{ Pr}[r_i \mbox{ seen} | c_i \mbox{ sent} ]}_{M_{c_i, i}}) \nonumber 
\end{eqnarray}

By the equation above, soft-decision decoding solves MLD for i.i.d. channel.
\end{enumerate}

\subsubsection{Reasonable decoding problems}

For a decoding problem, we should consider both the number of errors we're trying to correct and number of errors the code designed to handle.
Let's look at the following three questions:

\begin{enumerate}

\item{Unambiguous/unique decoding}
Given a code $\cal C$ with minimum distance $d,$ and $r \in \Sigma^n,$ find codeword $c$ such that $\Delta(r, c) < {d \over 2}$ if it exists.
Sometimes it is also called Bounded Distance Decoding.

\item{Relatively Near Codeword (RNC)}
This is a parameterize problem with parameter $\gamma > 0.$ Given a code $\cal C$ with minimum distance $d,$ and $r \in \Sigma^n, e < \gamma d,$ find $c \in \cal C,$ such that $\Delta(r, c) \le e.$

Note when pick $\gamma = {1 \over 2},$ RNC is Unambiguous Decoding Problem.

When pick $\gamma = \infty,$ RNC becomes NCP.

And the problem is reasonable up to when $\gamma < 1.$

\item{List-decoding problem}
The definition of this problem is similar to RNC except that here we want a list of all codewords $c$ such that $\Delta(r, c) < \gamma d.$

Therefore, Unambiguous decoding is List-decoding also, for $\gamma = {1 \over 2}.$

For each $\gamma,$ RNC reduces to List-decoding Problem. And the List-decoding can be very hard if the list size is (potentialy) super polynomial. Hence, we should only attempt to solve this up to the list-decoding radius of a code, which is the radius of a ball with guarantee that the number of codewords in the ball is polynomial.

\end{enumerate}

\subsubsection{Easy problems for linear codes}

For a linear code, because a generator matrix is given, the following three problem is "easy". Here "easy" means that it takes poly time.

\begin{itemize}

\item{Encoding}
Clearly, code can be easily generated by the generator matrix.

\item{Error-detection}
We can get the parity matrix from the given generator matrix, and use it to detect whether errors occur.

\item{Erasure correction}

\begin{itemize}

\item Erasure-decoding problem: Given an $k$ by $n$ generator matrix $G$, the code $\cal C$ generated by $G$ and vector $r \subseteq (\Sigma \cup \{ ?\})^n ,$ find $c \in \cal C,$ such that $c_i = r_i,$ for $i: 1 \le i \le n$ with $ri \neq ?.$

\item Decoding Algorithm: If there're $s$ symbols of $r$ are $?'s,$ i.e. erased, let $r'$ be a vector obtained by removing the $s ?'s$ from $r.$ And let $G'$ obtained by removing the corresponding columns. Then solving the linear system $mG' = r'$ will give the solution $c = mG.$

If $mG' = r'$ has no solution, they our problem does not have solution; if it has one solution, our problem have one solution; if it has more than one solution, they our problem has a solution space in the form of $Ax + b.$

\item Another fact about the erasure-decoding problem is that when the number of erasures, $s$, is smaller than $d$, the minimum distance of the code, then the solution is unique.

\end{itemize}

\end{itemize}

\subsubsection{Syndrome Decoding}

\begin{itemize}
\item Definition: Given a linear code $\cal C$ with parity check matrix $H$ and $e \in F_q^n,$ $e\cdot H$ is the \textit{syndrome} of $e.$

\item Note that if given a vector $r = c + e,$ where $c \in \cal C$ and $e$ is the error, the $r \cdot H = e \cdot H$ depends only on the error $e$ but not on the codeword $c.$

\item Syndrome decoding can be interpreted in two ways:
\begin{itemize}
\item Given $e \cdot H,$ compute $e.$
\item Build up a table of map $e \cdot H \rightarrow e,$ and look up the table by index $e \cdot H$ to compute $e.$ This is a brute-force algorithm.
\end{itemize}
\end{itemize}

\section{Unambiguous Decoding of Reed-Solomon Codes}
\subsection{Problem statement}
If given $n$ distinct elements $\alpha_1, \alpha_2, \dots, \alpha_n \in F_q, r_1, r_2, \dots, r_n \in F_q$ and a parameter $k,$ 
find a polynomial $p \in F_q[x]$ of degree no more than $k,$ such that $p(\alpha_i) = r_i$ for $\underbrace{\mbox{many values}}_{> {{n+k} \over 2}}$ of $i.$

\subsection{Convoluted history}
At first glance, this problem is not trivial. Let's look at the history of this problem first.

\begin{itemize}
\item In 1958, BC + H discovered binary BCH>
\item Peterson 60' gave polytime decoding algorithm for binary BCH in 1960.
\item Reed-Solomon found RS code, but did not notice the connection between it and BCH.
\item In 1963, Gorenstein-Zierler discovered $q$-ary BCH codes and noticed that RS codes are special cases of $q$-ary BCH codes and that Peterson's algorithm generalizes to $q$-ary BCH codes.

\end{itemize}

\end{document}