src/index.tex (view raw)
1\maketitle
2
3\
4These short notes (under construction) are meant for the students of the {\em Optimization} course, with no background in Linear Algebra. Students can check out, for instance, the Linear Algebra textbook of the Schaum series for further examples and exercises. They should, however be familiar with matrix multiplication and able to solve linear systems. The Gauss elimination method is also described at the beginning of these notes.
5
6
7\section{Introduction}
8Suppose we're trying to build a remote for a DVD player.
9
10% TODO: fill intro
11
12\begin{definition}[Hamming distance]
13Given two code words $\textbf{w}, \textbf{w}' \in \{0,1\}^n$, the \emph{Hamming distance} between $\textbf{w}$ and $\textbf{w}'$ is the number of bits in which $\textbf{w}$ differs from $\textbf{w}'$:
14
15\begin{equation}
16 d_H(\textbf{w}, \textbf{w}') := |\{j \in \{1, 2, \ldots, n\} : w_j \neq w_j'\}|.
17\end{equation}
18\end{definition}
19In other words, the Hamming distance is the number of errors (bit flips) that need to occur for \textbf{w} to become \textbf{w'}.
20
21\begin{example}
22If $n = 3$, we can form $2^3=8$ unique code words, with the following distances from each other:
23
24\begin{table}[!ht]
25 \centering
26 \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
27 \hline
28 \textbf{$d_H$} & \textbf{101} & \textbf{111} & \textbf{011} & \textbf{001} & \textbf{000} & \textbf{010} & \textbf{110} & \textbf{100} \\ \hline
29 \textbf{101} & 0 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\ \hline
30 \textbf{111} & 1 & 0 & 1 & 2 & 3 & 2 & 1 & 2 \\ \hline
31 \textbf{011} & 2 & 1 & 0 & 1 & 2 & 1 & 2 & 3 \\ \hline
32 \textbf{001} & 1 & 2 & 1 & 0 & 1 & 2 & 3 & 2 \\ \hline
33 \textbf{000} & 2 & 3 & 2 & 1 & 0 & 1 & 2 & 1 \\ \hline
34 \textbf{010} & 3 & 2 & 1 & 2 & 1 & 0 & 1 & 2 \\ \hline
35 \textbf{110} & 2 & 1 & 2 & 3 & 2 & 1 & 0 & 1 \\ \hline
36 \textbf{100} & 1 & 2 & 3 & 2 & 1 & 2 & 1 & 0 \\ \hline
37 \end{tabular}
38 \caption{Hamming distances for all possible code words with $n=3$}
39\end{table}
40
41Another way to visualize the Hamming distance is by putting each possible code word in the vertices of a (hyper)cube. Of course, for $n=2$ the cube becomes a square. If every word is placed such that it has only one bit of difference with respect to each of its neighbors, then the Hamming distance between two words will be the number of edges we need to traverse in order to get from one word to the other.
42
43\begin{figure}
44 \centering
45 \includegraphics[width=0.25\textwidth]{hamming-cube.png}
46\caption{Hamming cube for $n=3$}
47\end{figure}
48
49\end{example}
50
51\begin{definition}[weight of a code-word]
52Suppose $\textbf{w}$ is a code-word such that $\textbf{w} \in \{0,1\}^n$. The \emph{weight} of $\textbf{w}$ is the number of 1's in $\textbf{w}$:
53
54\begin{equation}
55 |\textbf{w}| := |\{j \in \{1, 2, \ldots, n\} : w_j = 1\}|.
56\end{equation}
57
58\end{definition}
59\begin{example}
60Suppose $n=5$.
61\begin{equation}
62 |(1, 0, 0, 1, 1)| = 3 \quad\quad |(1, 0, 0, 0, 0)| = 1 \quad\quad |(0, 0, 1, 1, 1)| = 4
63\end{equation}
64\end{example}
65
66\begin{definition}[bit-wise xor]
67Given two words $\textbf{w}, \textbf{w}' \in \{0,1\}^n$, we can define the following operation:
68\begin{equation}
69 \textbf{w} \oplus \textbf{w}' = ((w_1 + w_1')\text{mod}2, (w_2 + w_2')\text{mod}2, \ldots, (w_n + w_n')\text{mod}2) \in \{0,1\}^n
70\end{equation}
71\end{definition}
72The \emph{sum modulo 2} operation returns a vector of size $n$ where each component $z_j$ has value:
73\begin{itemize}
74 \item 0 if $w_j = w_j'$;
75 \item 1 if $w_j \neq w_j'$
76\end{itemize}
77
78\begin{example}
79Suppose $n=6, \textbf{w} = (1, 1, 0, 0, 1, 0), \textbf{w}' = (0, 1, 1, 0, 0, 1)$.
80\begin{equation}
81\begin{array}{l}
82(1, 1, 0, 0, 1, 0) \,+ \\
83(0, 1, 1, 0, 0, 1) = \\ \hline
84(1, 2, 1, 0, 1, 1)
85\end{array}
86\quad\rightarrow\quad
87\begin{array}{l}
88(1, 2, 1, 0, 1, 1)\text{mod} 2 = \\ \hline
89(1, 0, 1, 0, 1, 1) = \textbf{w} \oplus \textbf{w}'
90\end{array}.
91\end{equation}
92\end{example}
93
94At this point, it's clear how this identity holds true:
95\begin{equation}
96 d_H(\textbf{w}, \textbf{w}') = |\textbf{w} \oplus \textbf{w}'|
97\end{equation}
98Which means: the weight of the result obtained from the bit-wise xor operation is the Hamming distance between the two code-words.
99
100\begin{definition}[distance of a code]
101In coding theory, any subset $\mathcal{C} \subseteq \{0,1\}^n$ is called a \emph{code}.
102
103A code $\mathcal{C}$ has \emph{distance} $d$ if:
104
105\begin{equation}
106 d_H(\textbf{w}, \textbf{w}') \geq d \;\; \forall \;\textbf{w}, \textbf{w}' \in \mathcal{C}.
107\end{equation}
108
109Lastly, for $n, d \geq 0$, let $A(n,d)$ denote the maximum cardinality of a code $\mathcal{C} \subseteq \{0,1\}^n$ with distance $d$.
110\end{definition}
111
112\begin{example}
113For $n=7$, a valid code of distance $d=3$ could be the set:
114
115\begin{equation}
116\mathcal{C} =
117\left.
118\begin{cases}
119& 0000000, 0001011, 0010101, 0011110, \;\;\;\\
120& 0100110, 0101101, 0110011, 0111000, \\
121& 1000111, 1001100, 1010010, 1011001, \\
122& 1100001, 1101010, 1110100, 1111111
123\end{cases}\right\}.
124\end{equation}
125
126Notice how, in this code, every two distinct words have an Hamming distance of at least $3$.
127\end{example}
128
129\begin{proposition}
130A code $\mathcal{C}$ can correct at most $r$ errors if and only if it has distance $d \geq 2r+1$.
131\end{proposition}
132\begin{example}
133 Suppose $\mathcal{C}$ contains two distinct words $\textbf{w}', \textbf{w}''$ that differ in at most $2r$ bits. For example, with $n=7$ and $r=1$, suppose we receive $\hat{\textbf{w}}$, obtained by flipping $r=1$ bits in one of them:
134\begin{equation}
135\textbf{w}' = 0000011 \quad \textbf{w}'' =0000101 \quad \hat{\textbf{w}} = 0000001
136\end{equation}
137At this point, it's impossible to know whether the originally transmitted word was $\textbf{w}'$ or $\textbf{w}''$. This test can be repeated by choosing any code with distance $d=2r$ and flipping $r$ of them.
138
139On the other hand, if $\mathcal{C}$ had a distance of $2r+1$, we would be sure it could correct up to $r$ errors:
140
141\begin{equation}
142\textbf{w}' = 0000011 \quad \textbf{w}'' =0010101 \quad \hat{\textbf{w}} = 0000001
143\end{equation}
144
145In this case, we can be sure that $\textbf{w}''$ was transmitted.
146\end{example}
147
148In most cases, the number $n$ of bits we can transmit and the amount of errors $r$ to be corrected are given; one of the main problems of coding theory (and the main topic of this document) is finding $A(n,d)$, the maximum possible size of a code $\mathcal{C} \subseteq \{0,1\}^n$ with distance $d$.
149
150\subsection{Simple cases}
151For all $n$, we always have $A(n,1) = 2^n$, because any code has distance 1 by definition; of course, this does not allow us to correct any error.
152%TODO: finish this part
153%\begin{array}{l}
154
155%\end{array};
156
157\subsection{The sphere-packing bound}
158For any $n$ and $d$, we can use a \emph{volume argument} to obtain a simple upper bound on $A(n, d)$.
159
160Imagina a spherical box filled with prize balls. If you wanted to guess how many balls can fit inside it, you could conclude that the number of balls is bounded above by the volume of the spherical box divided by the volume of a single box.
161
162Let's assume that $d = 2r+1$ is odd and fix any code $\mathcal{C}$ of distance $d$. Now, the set $\{0,1\}^n$ represents the spherical box, containing $|\mathcal{C}|$ Hamming balls:
163\begin{equation}
164 B(\mathbf{w}, r) := \{\mathbf{w}' \in \{0,1\}^n : d_H(\mathbf{w}, \mathbf{w}') \leq r\}, \mathbf{w} \in \mathcal{C}.
165\end{equation}
166
167\section{The Delsarte Bound}
168test