\documentclass[10pt]{article}
\usepackage{amsfonts}
\usepackage{fullpage}
%\usepackage{epsfig}
\begin{document}
\input{preamble.tex}
\setlength\parindent{0pt}
\lecture{15}{April 3 2013}{Madhu Sudan}{Zonghao Chen}
\section{Introduction}
Graph-based codes were introduced in the previous lecture. Definitions as well as important properties of those codes were presented with explicit decoding algorithms left over to this lecture.As mentioned previously, one of the main topics in the near future would be linear time algorithms. A linear time decoding algorithm of the Expander Codes will be discussed in the following part.\newline
As the encoding process may take quadratic time for these graph-based codes, we will continue to explore codes that are linear time encodable and decodable. Spielman's family of codes will be presented in the second half of this scribe notes.
\section{Linear Time Decoding Algorithm}
\subsection{Review}
In the previous lecture, we discussed the expander codes. Before presenting the decoding algorithm, we may first review some of the definitions and lemmas.
\begin{definition}
Given a subset of vertices $S \subseteq L$, its {\bf neighborhood} $\Gamma(S)$ is the set of vertices in $R$ which are adjacent to at least one vertex in $S$; that is,
\[\Gamma(S) = \{v \in R | \exists u \in S\ s.t.\ (u,v) \in E\}.\]
\end{definition}
\begin{definition}
A graph is a {\bf $(\gamma,\delta)$-expander} if for all $S \subseteq L$ such that $|S| < \delta n$, we have
\[|\Gamma(S)| \ge \gamma|S|.\]
\end{definition}
\begin{definition}
A graph is a {\bf $(\gamma,\delta)$-unique-expander} if for all $S \subseteq L$ such that $|S| < \delta n$, we have
\[|\Gamma^{unique}(S)| \ge \gamma|S|.\]
\end{definition}
\begin{lemma}
If $G$ is a $(c,d)$-regular $(\gamma, \delta)$-expander, then $G$ is a $(2\gamma-c,\delta)$-unique expander.
\end{lemma}
Now we are ready to present the decoding algorithms of this code. Recall that when $r$ is the received vector and $H$ is the parity check matrix, the error can be determined from $r \cdot H$. In particular, if the $j$th bit of $r \cdot H$ is non-zero, an error must have occured at an index $i$ such that $H_{ij} \neq 0$. Then we can consider performing decoding by flipping $r_{i} $. A vertex in $R$ is called satisfied if it has an even number of non-zero neighbors.
\subsection{ Decoding Algorithm}
If there exists a vertex $r_{i}$ in $L$ with more unsatisfied neighbors than satisfied neighbors, flip $r_{i}$.
To prove that this flipping algorothm leads to the desired result, we need to show the following:
\begin{enumerate}
\item This algorithm does terminate.
\item When the algorithm stops, we end in a codeword.
\item When the algorithm stops and we get a codeword $\widetilde{c}$, then $\widetilde{c} = c$.
\end{enumerate}
Thus we need to show that the above three rules can be satisfied as long as the number of errors is small enough.Given a received vector $x$ ($with \exists c \in C\ s.t. \delta (x, c) \leq \tau n < \frac{\delta}{c + 1} n$)\newline
\begin{lemma}
The number of iteration of this decoding algorithm $\le \tau cn$
\end{lemma}
\begin{corollary}
$\delta (c,\widetilde{c})\le \tau (c+1)n < \delta n$
\end{corollary}
\begin{proof}
Each bit error that occured can lead to at most $c$ unsatisfied vertices on the right. Then the total number of unsatisfied vertices on the right should be $\le \tau n$. Since each iteration can reduce the number of unsatisfied vertices by at least one, the algorithm terminates in at most $\tau cn$ iterations.
\end{proof}
\begin{theorem}
If graph $G$ is (c, d)regular and (r, s) expander with $\gamma > \frac{3}{4} c$, then the associated code has distance at least $\delta$ and can correct at least $\frac{\delta}{c + 1}$fraction of errors.
\end{theorem}
\begin{proof}
We have shown that the algorithm does terminates and since $\delta (c, \widetilde{c}) < \delta n$, we will get the correct codeword if we do end with a codeword. All that remains to be proved is that the result must be a codeword. \newline
To argue that $\widetilde{c}$ must equals $c$, let $\widetilde{c} + c = y$ and note that $y$ is a vector of weight less than$\delta n$. Furthermore, since $c$ is a codeword and hence every node on the right is satisfied, assigning $\widetilde{c}$ to the vertices on the left will induce the same assignments on the right as assigning $y$ to the left.
Therefore, in order to argue that the Flip Algorithm would not terminate with the vertices on the left assigned to $\widetilde{c} \neq c$, we argue that many of
the vertices on the right would be non-zero. Since $\widetilde{c}$ induces the same
assignment to the right as $y$ does, we will argue this in terms of $y$.
Let $S$ be the set of non-zero left side vertices under an assignment of
$y$, then$|S| < \delta n$. Therefore, since $G$ is $(\gamma, \delta)$-expander, $|\Gamma^{unique}(S) | > (2\gamma -c)|S| > 0$. Thus there must exist a vertex in $S$ that is unsatisfied which contradicts the assumption that the Flip Algorithm has terminated.
\end{proof}
\section{Spielman's code}
Though linear time decoding is possible for the expander codes as proved in the previous section, the encoding process may take quadratic time. Similar to the idea adopted above, the encoding can be faster if the generator matrix is sparse.Spielman's family of codes can be encoded and decoded in linear time, and will be presented in the following notes.
\subsection{Encoding}
Denote $E_{k}$ the Spielman's code for message of length $k$. Code $E_{k}$ will be described in terms of Spielman's codes for shorter message. Given a message $x \in \{0,1\}^k$, the corresponding codeword should be of length $4k$ the first $k$ bits of which is the original message while the rest $3k$ are parity check bits. Define $G_{k}: \{0,1\}^k \rightarrow \{0,1\}^{k/2}$ a family of error reduction codes.
Given a message $x$ of length $k$, the first $3k/2$ bits of encoding are the original message and the result of applying $G_{k}$ to $x$ (denoted $u$). Then the substring $u$ is encoded with $E_{k/2}$ to generate the next $3k/2$ check bits (denoted v). The last $k$ bits (denoted w) are generated by applying $G_{2k}$ to $(u,v)$.
Now we claim that this encoding procedure can be implemented in linear time. Assume the generator of $G_{l}$ has $\le cl\ 1's\ \forall\ l$, then \[T_{E}(k) \le ck + c(2k) + T_{E}(k/2)\]
This implies that $T_{E}(k) \le 6ck\ = O(k)$
\subsection{Decoding}
Assume the original word is $(x,u,v,w)$ and $(\widetilde{x},\widetilde{u},\widetilde{v},\widetilde{w})$ is received. If the number of errors is small enough, we can decode with linear time algorithms.
The decoding of this code will be implemented in several steps:\newline
\begin{enumerate}
\item Error Reduction. Run the Flip Algorithm on $(\widetilde{u},\widetilde{v},\widetilde{w})$ until it teminates. Denote the result $(u',v')$.
\item Decoding of $E_{k/2}$. Decode $(u',v')$ with $E_{k/2}$ recursively to obtain a new vector $u''$.
\item Error Reduction. Run the Flip Algorithm on $(\widetilde{x},u'')$ and obtain the recovered message $x'$.
\end{enumerate}
Assume that the number of errors is at most $\tau k$. Then $\delta ((u,v),(\widetilde{u},\widetilde{v}) \le\ \tau k$\ and $\delta (w,\widetilde{w}) \le\ \tau k$.After the error reduction in step 1, we have $\delta ((u,v),(u',v')) \le\ \frac{\tau k}{2}$. By induction, we may conclude that the step 2 can correct all errors in $u$, which means $u = u''$. Thus the error reduction in step 3 can recover $x$ without error. \newline
As for the running time of the decoding algorithm. From the fact that error reduction can be done in $O(k)$, we have
\[T_{D}(k) \le O(k) + T_{D}(\frac{k}{2}) + O(k)\]
Which implies that $T_{D}(k) = O(k)$
\end{document}