%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% University/School Laboratory Report
% LaTeX Template
% Version 3.1 (25/3/14)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% Original author:
% Linux and Unix Users Group at Virginia Tech Wiki e
% (https://vtluug.org/wiki/Example_LaTeX_chem_lab_report)
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[11pt]{article}
\usepackage[version=3]{mhchem} % Package for chemical equation typesetting
\usepackage[separate-uncertainty=true]{siunitx} % Provides the \SI{}{} and \si{} command for typesetting SI units
%The first argument helps me keep the \pm symbol in a cool fashion
\usepackage{graphicx} % Required for the inclusion of images
\usepackage{natbib} % Required to change bibliography style to APA
\usepackage{amsmath} % Required for some math elements 
\usepackage[margin=2cm]{geometry} %This helps me not have ridiculous margins
\usepackage{verbatim}
\usepackage{gensymb} %This is so that I can use the degree symbol
\usepackage{appendix} %This helps me put appendices
\usepackage{tabularx}
\usepackage{float} %Makes figures and graphics appear in proper places
\usepackage{multirow} %Allows tables to merge columns vertically
\setlength\parindent{0pt} % Removes all indentation from paragraphs

\usepackage{scrextend} %For indented sections


\usepackage{mathtools}
\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}

%These let me write pseudocode in a cool way
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\makeatletter
\def\BState{\State\hskip-\ALG@thistlm}
\makeatother

\usepackage{mathtools} %Allows me to put symbols over arrows

\usepackage{enumitem}
\setlist{nolistsep}

\usepackage{amssymb} %Math symbols like Z, R, Q...

\renewcommand{\labelenumi}{\alph{enumi}.} % Make numbering in the enumerate environment by letter rather than number (e.g. section 6)

%\usepackage{times} % Uncomment to use the Times New Roman font

%%MUST PROCEED \begin{itemize} AND PRECEED \end{itemize}
\newcommand{\coolNote}[2]{
	\item \textbf{#1 - } #2
}



%%Copied this (and modified) from
%%http://tex.stackexchange.com/questions/128337/problem-solution-template
%%So that I could make this solution manual easier.

\newcounter{problem}
\newcounter{subproblem}
\newcounter{subsubproblem}
\newcounter{solution}
\newcounter{Lemma}

\newcommand\Problem{%
% \newpage %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%This line is only to separate out the hw by problems
  \stepcounter{problem}%
  \textbf{Exercise \theproblem:}~%
%   \textbf{Exercise }~%
  \setcounter{solution}{0}%
  \setcounter{subproblem}{0}
}

\newcommand\SubProblem{
	\stepcounter{subproblem}
    \textbf{(\alph{subproblem}.)}
    \setcounter{subsubproblem}{0}
    \setcounter{solution}{0}
}

\newcommand\SubSubProblem{
	\stepcounter{subsubproblem}
    \textbf{(\roman{subsubproblem}.)}
    \setcounter{solution}{0}
}


\newcommand\TheSolution{%
  \textbf{Solution:}\\%
}

\newcommand\ASolution{%
  \stepcounter{solution}%
  \textbf{Solution \thesolution:}\\%
}
\parindent 0in
\parskip 1em


%% Math commands
\newcommand\union{
    \cup
}

\newcommand\intersect{
    \cap
}

%%%Matlab typesetting:
\usepackage{listings}
\usepackage{color} %red, green, blue, yellow, cyan, magenta, black, white
\definecolor{mygreen}{RGB}{28,172,0} % color values Red, Green, Blue
\definecolor{mylilas}{RGB}{170,55,241}

%----------------------------------------------------------------------------------------
%	DOCUMENT INFORMATION
%----------------------------------------------------------------------------------------

\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage{setspace}
\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-2:\hspace{0.12cm}Advanced
          Algorithms (Spring'20)} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{26: Error-Correcting Codes}{April 30th,
  2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Daniel Beaglehole, David Rincon-Cruz}}



%----------------------------------------------------------------------------------------
%	SECTION 2
%----------------------------------------------------------------------------------------

% \TheSolution
% This is a solution to the subproblem

% \Problem This is the problem statement in multiple line. This is the
% problem statement in multiple line. This is the problem statement in
% multiple line.

% \TheSolution This is the solution of the problem. When there is only on
% solution, there is no need to numbering.

% \Problem This is another problem but two solution multiple line. This is
% another problem but two solution multiple line. This is another problem
% but two solution multiple line.


% \ASolution This is the first solution of the problem

% \ASolution This is the second solution.

%----------------------------------------------------------------------------------------
% 	Appendix
% ----------------------------------------------------------------------------------------

% \newpage
% \appendix
% \section{Appendix A: Gay-Lussac Experiment Data} \label{App:AppendixA}

% Please add the following required packages to your document preamble:
% \usepackage{multirow}

\section{Introduction}

\begin{figure}[H]
\centering
% \caption{Screenshot of html code}
\includegraphics[width=.50\textwidth]{diagram1.png}
\end{figure}

Error-correcting codes arise in the context of sending messages from a source to a destination. In particular, suppose we would like to communicate a message $m \in \Sigma^k$ from a source to a destination, where $\Sigma$ is what is called the alphabet (could be bits or even up to the word level). The idea is that we send a longer message than the original to protect the original message from possible corruption.

Consider then two functions - the encoder $E : \Sigma^k \rightarrow \Sigma^n$ and a decoder $D : \Sigma^n \rightarrow \Sigma^k$, presumably with $n > k$. We then would like that our encoder/decoder has the property that for any message $(f_0, ..., f_{k-1}) = f$:
\begin{align*}
    D(E(f) + "corruption") = f
\end{align*}

Some standard corruption models are the following. 1.) erasure: replace e characters with question marks (e.g. $0 \rightarrow ?$) 2.) error (substitution): e characters got changed, and you don’t know which (e.g. $0 \rightarrow 1$) 3.) deletion/insertion - a message in $\Sigma^n$ got transformed into $\Sigma^{n+1}$ (e.g. $000 \rightarrow 0100$ or $00$). 

Our study is motivated, for example, by two applications: communication and memory storage. E.g. How can effectively communicate messages in the face of possible noise? Or, how can we store data such that it will remain in tact despite corruption? 

Imagine storing information on k files on k hard drives - if one fails that's a major problem - you lose the file. One naïve way to make fault tolerant is by repetition: repeat each file on $\alpha > 1$ hard drives. In this case, the number of hard-drives would then be $n = \alpha * k$. With $\alpha$ copies of each file, if $(\alpha - 1)$ hard-drives fail, we will still be okay, as there is a remaining hard-drive! Can we do better? Yes: we will attempt to encode our message (files) such that for constant $\alpha$, $n = \alpha * k$ hard-drives are resilient to far more errors. 

\section{Codes}

\underline{Definition}: a code is a set $\mathcal{C} \subset \Sigma^n$ where $\mathcal{C} = \{ E(f) : f \in \Sigma^k\}$.

\begin{figure}[H]
\centering
% \caption{Screenshot of html code}
\includegraphics[width=.3\textwidth]{diagram2.png}
\end{figure}


A natural decoding would then be: to map $m \in \Sigma^n$ into closest code in $\mathcal{C}$ and then decode $f$. Using this scheme, when can we decode our corrupted message? (How many coordinates can be affected?)

1.) \textbf{Erasure}. Suppose there is an adversary that deletes the minimum number of letters such that the code can no longer be decoded. The number of erasure errors our system can tolerate by this adversary is $\leq d - 1$, where $d$ is defined below.

\underline{Definition}. $d := \min \{dist (x,y) : x,y \in C, x \neq y \}$. 

If there are at least $d$ erasures, then delete the position where x and y differ, and then you can’t tell whether the encoded message is x or y. 

2.) \textbf{Errors (substitution)}. Decoding: map the corrupted message $m \in \Sigma^n$ into closest codeword in $\mathcal{C}$. The decoding is correct iff $e \leq (d-1)/2$, where $e$ is defined to be the number of errors in the encoded message. 

\begin{figure}[H]
\centering
% \caption{Screenshot of html code}
\includegraphics[width=.3\textwidth]{diagram3.png}
\end{figure}

\underline{Definition}: a code $\mathcal{C}$ has parameters $(k, n, d)$, where $k$ - length of the original message, $n$ - length of codeword, $d$ - length of minimum distance between two distinct codewords.

E.g. the repetition code has the parameters $(k, n = \alpha * k, \alpha - 1)$. 


\textbf{\newtheorem{theorem2}{Theorem (Shannon ’48)}}. There exists a code $\mathcal{C}$ with $n = \alpha * k$, $d = \beta * k$, for $\alpha = O(1)$, $\beta = \Omega(1)$. 

In other words, we can design a code that is tolerant to a constant fraction of failures - much better than a constant number (e.g. $\alpha - 1$ as in repetition). 

\textbf{Proof}: take $\mathcal{C}$ = set of $2^k$ random vectors in ${0,1}^n$ (for $\Sigma = \{0,1\}$). Let the encoder $E$ be any map of $\{0,1\}^k \rightarrow e$ that is bijective. Our decoder $D$ will then decode to the closest codeword. 

How can we compute $E,D$ (particularly $D$)? Naïvely, we can find closest codeword in time ~$2^k$ by brute-force checking all the possible messages and their codewords. However, we'd like $D$ to run in time $poly(k)$. This leads to the following definition for Reed-Solomon Codes. 

\underline{Definition}: Reed-Solomon (RS) code: $\mathcal{C} := \{ f(\alpha_1), \ldots, f(\alpha_n) : f(x) = \sum_{i=0}^{k-1} f_i x^i$, where $f_0, \ldots, f_{k-1} \in \mathbb{F}_p \}$ for some finite field $\mathbb{F}_p$, and where $\alpha_1, \ldots, \alpha_n$ are distinct in $\mathbb{F}_p$. 

For the RS codes, an input message is encoded into a polynomial with coefficients equal to the message. I.e. the message $(f_0, f_1, \ldots, f_{k-1})$ is encoded by $E$ to $(f(\alpha_1), \ldots, f(\alpha_n))$. 

What are the parameters of the RS code, as we have defined them? Suppose here that $n = \Theta(k)$. Then, we have the following lemma.

\newtheorem{lemma2}[Lemma]{ The minimum distance in an RS code is $d = n - k + 1$} E.g. $n = 2k \implies d = k + 1$, which implies that the message can tolerate $k$ erasures or $k/2$ substitutions (constant fraction of the transmitted message). 

\textbf{Proof}: Take 2 distinct RS codewords. I.e. $A(x) = \sum f_i x^i$, $B(x) = \sum g_i x^i$, with $\{f_i\} \neq \{g_i\}$. Then the distance between $E(f)$ and $E(g)$ can be found by considering the number of $\alpha_i$’s such that $A(\alpha_i) = B(\alpha_i)$. 

Both $E(f)$ and $E(g)$ are polynomials of degree $\leq k - 1$. Therefore, 
at most $(k - 1)$ of the $alpha_i$’s can be equal (by the fundamental theorem of algebra). In particular, $C(x) = A(x) - B(x)$ can have at most $k - 1$ roots, and a root of $C(x)$ occurs iff $A(x) = B(x)$. This completes the proof of the lemma, which also completes the proof of Shannon's Theorem. $\square$


\section{Algorithms for Encoding/Decoding}

For encoding, we can directly compute the encoded message using our choice of coding scheme. However, for decoding algorithms we consider the different possible corruption schemes.

\textbf{Erasure errors}:
We want a decoding algorithm to decode correctly provided that the number of errors $e \leq n - k = d - 1$. In the case of RS codes, this poses the following computational problem. 

\textbf{Computational Problem}: 
Suppose we get a vector $(y_1, y_2, \ldots, y_n)$ where for $i\in S$, $|S| <= e$, $y_i = ?$ (as in the case of erasure). Otherwise, $y_i = f(alpha_i)$. How can we recover $f(x) = \sum_{i=0}^{k-1} f_i x^i$? Suppose the original message is $(f_0, \ldots, f_{k-1})$, which is the same as the description of the entire polynomial $f$.

\underline{Algorithm}: Polynomial Interpolation.
Given evaluation of $f(x)$ in $n - e \geq k$ values. Let's set these evaluations up as a linear system of equations:
$\sum_{i=0}^{k-1} f_i \alpha_j^i = y_j, j \notin S$.

Here we have $K$ unknowns $(f_i)$ - our original message, and $\geq k$ equations $(n - |s| \geq k)$. This linear system of equations can be represented by $Af = y$ where $A$ is the Vandermonde matrix:

\begin{align*}
    A = 
\begin{pmatrix}
\alpha_1^0 & \alpha_1^1 & \cdots & \alpha_1^{k-1} \\
\alpha_2^0 & \alpha_2^1 & \cdots & \alpha_2^{k-1} \\
\vdots  & \vdots  & \ddots & \vdots  \\
\alpha_n^0 & \alpha_n^1 & \cdots & \alpha_n^{k-1}
\end{pmatrix}
\end{align*}

What about the case of substitution errors? The challenge here is we don’t know $S$ (position of errors). Trying all possible sets $S$ too costly, as
$n \choose |S|$ is approximately $n \choose n/2$, which is approx. $2^{\Theta(n)}$. 

\begin{figure}[H]
\centering
% \caption{Screenshot of html code}
\includegraphics[width=.1\textwidth]{diagram4.png}
\end{figure}

\textbf{Berlekamp-Welch Algorithm (Decoding)}:
Let the Error polynomial be $E(x) := \Pi (x - \alpha_i)$, where the product is over $y_i \neq f(\alpha_i)$. We don’t know $E(x)$ otherwise we could recover the set of errors and we could do erasure decoding, but we’ll try to learn it.

\textbf{Property (*)}: $E(\alpha_i)* (f(x) - y_i) = 0, \forall i \in [n]$ 

Let $N(x) := E(x) * f(x)$. Then we claim:

\textbf{Claim}: There exist polynomials $N(\alpha_i) = y_i E(\alpha_i)$, where $N(x)$ has degree $e + k - 1$, and $E(x)$ has degree $e$.

The proof of this claim follows from property (*). 

\underline{Algorithm}:
Learn/compute polynomial $N(x)$ of degree $e + k -1$, $E(x)$ of degree $e$
Such that $N(\alpha_i) = y_i E(\alpha_i)$

\textbf{Proof}: Setting up a system of linear equations 
Number of unknowns is $(e + k -1) + 1 + e + 1$. The number of equations is $n$. We can set up this system as long as $(e + k -1) + 1 + e + 1 \leq n$, i.e. $e \leq (n - k - 1)/2 = d/2 - 1$. 

Therefore, RS is the best possible code for large $\Sigma$. 

\end{document}