\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 3, 2004}{Madhu Sudan}{Reina Riemann}

\section{TOPICS}

\begin{itemize}
\item Tanner Products and Sipser-Spielman codes.
\item Linear time encodable \& decodable codes.
\item Decoding in linear time (Data structure exercise).
\end{itemize}

\section{Tanner product generalization}

Remember that for a $(\gamma,\delta)$ expander graph, $|S|\leq\delta\cdot n$
and the neighborhood of $S,$ $\Gamma(S)\geq\gamma|S|.$ This implies
that for a c-left regular graph with $\gamma>c/2$, the corresponding
code has minimum distance$\geq\delta\cdot n$.

We'll look at Tanner's construction in order to go past the $\frac{c}{2}$
barrier. Tanner's generalization uses a $d-right$ regular bipartite
graph, together with a small code $B=[d,l,\Delta]$. An assignment
to the left is a codeword of $C=C(G,B)$ if every right vertex sees
a codeword of $B$. This imposes $d-l$ new constrains, so the total
number of constrains is $n-m(d-l)$ where $n$ is the number of vertices
on the left of the bipartite graph and $m$ is the number of vertices
on the right. We also have that $c\cdot n=d\cdot m$. Therefore $n-m(d-l)=n(1-(c/d)(d-l))$. 

Consider the following partition of $\Gamma(S)=A\cup B$, where $A$
has$\leq(\Delta-1)$ neighbours and $B$ has $\geq\Delta$in $S$.
It follows that:

\begin{eqnarray*}
|A|+|B| & \geq & \gamma\cdot|S|\\
|A|+\Delta|B| & \leq & \#\, of\, edges\, of\, S\leq c\cdot|S|\\
(\Delta-1)|A| & \leq & (\bigtriangleup\gamma-c)|S|\end{eqnarray*}


Construction yields code $C(B,G)$ of minimum distance $\delta\cdot n$
provided $\gamma>\frac{c}{\Delta}.$ 

\begin{itemize}
\item First, pick $c,$$\gamma$, then we can build $\forall d\,\exists\delta>0,\forall n,$$(c,d)$
regular graphs that are $(\gamma,\delta)$ expanders.
\item Set $\Delta>\left\lceil \frac{c}{\gamma}\right\rceil $
\item Pick $(d,l)$ such that $d>c(d-l)$, $\exists[d,l,\Delta]_{2}$code
(so that $d>\Delta log(d)$) guaranteed.
\item $\exists\delta$ such that $\exists(c,d)$ regular $(\gamma,\delta)$
expander that we can construct.
\end{itemize}

\section{Parallel-flip algorithm}

In parallel, every right vertex acts as follows:

\begin{itemize}
\item If neighbors form codeword of $B$, then ok
\item If neighbors are at a distance $\leq\varepsilon\Delta,$ then send
a flip message to these neighbors.
\item If neighbors are at a distance $\geq\varepsilon\Delta,$ then do nothing
\end{itemize}
Note that at each iteration the number of bits in error reduces by
a constant fraction.


\section{Spielman codes}

With the Sipser-Spielman codes, the $n^{2}$ encoding time takes more
than the linear decoding. The Spielman codes have both linear time
encoding and decoding. The main idea is to use error-reduction codes.
Expanders are used in the spielman construction, but this time the
expander is associated with the generator matrix rather than the parity-check
matrix. These codes are systematic, i.e. the encoding contains the
message bits followed by the check bits. These codes are called {}``Cascade
codes'' because of their recursive structure. The encoding is determined
by a graph $G$ with $log(k)$layers, where $k$ is the number of
bits in the message, and each of the layers of $G$ is low density. 


\subsection*{Error-reduction codes}

\begin{itemize}
\item $R_{k}$: message$\rightarrow$$(message,check-bits)$
\item k message bits $\rightarrow$3$\cdot$k/2 codeword bits 
\item m'$\rightarrow$(m',c')
\end{itemize}
\emph{Property:} If the distance$\bigtriangleup(c',c)\leq t\leq$$\delta\cdot k$$\Rightarrow\Delta(m',m)\leq t/2$

Spielman Codes $C_{k}:m\rightarrow(m,\, x)$ where $|x|=3k$ that
is, $k$ message bits get encoded into $4k$ codeword bits


\subsection*{Encoding $C_{k}$}

\begin{itemize}
\item Apply $R_{k}(m)=(m,c)$, where $|c|=k/2$
\item Apply $C_{k/2}(c)=(c,y),$ where $|y|=3\cdot k/2$$ $
\item Apply $R_{2k}(c,y)=((c,y),\, z),$where $|z|=k$
\item All of the above imply that $C_{k}(m)=(m,(c,y,z)),$ where $|c,y,z|=3k$
\end{itemize}

\subsection*{Distance of $C_{k}$}

$\Delta(m,(c,y,z)),(m',(c',y',z')))<\delta k$

then$\Delta(z,z')<\delta k$

By $R_{2k},$ $\Delta((c',y'),(c,y))<\delta k/2$

By $C_{k/2},$ $(c',y')=(c,y)$

By $R_{k},$ $c'=c$

Next time we'll cover the error-reduction algorithm.
\end{document}