Motivation and notation for codes

Before the formal definition is given, let us go straight to an example.

Example 3.3.1   ``Hi Bob''.

``What?''

``Hi Bob'' (louder).

``What?''

``Hi Bob'' (even louder).

``Oh, hi.''

This illustrates a ``repetition code''. More precisely, the $q$-ary repetition code of length $n$ is the set of all $n$-tuples of the form $(x,x,...,x)$, for $x\in \mathbb{F}_q$. (We leave it as an exercise to verify that this is a vector space over $\mathbb{F}_q$.) We think of $x$ as representing information you want to send. It could be the ``greyness'' of a pixel in a picture or a letter (represented in ASCII code) in a word, for example. Since the channel might contain noise, we send $(x,x,...,x)$ instead, with the understanding that the receiver should perform a ``majority vote'' to decode the vector. (For example, if $(0,1,0,...,0)$ was received then 0 ``wins the vote'').

This wasn't a very efficient example. Let's try again.

Example 3.3.2   In this example, we will design a code which will send a number in $\{0, 1, 2, ..., 7\}$ to another person.

First, write the number in binary, 0 as $000$, $1$ as $001$, ..., $7$ as $111$. If $c_i\in \mathbb{F}_2$ for $1\leq i\leq 3$, then define

$$c_4=c_1+c_2,\ \ \ \ \ c_5=c_1+c_2+c_3,\ \ \ \ \ c_6=c_3.$$

For example, $4$ or $100$ is encoded as $(1,0,0,1,1,0)$. Let $C\subset \mathbb{F}_2^6$ denote the set of all vectors $c=(c_1,...,c_6)$ where $c_i\in \mathbb{F}_2$, for $1\leq i\leq 3$, and $c_4,c_5,c_6$ are defined as above. In other words, define

$$C=\{ v\in \mathbb{F}_2^6\ \vert\ Hv={\bf0}\},$$

where

$$H= \left( \begin{array}{cccccc} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 ... ...& 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{array}\right).$$

This is a $3$ dimensional vector space over $\mathbb{F}_2$. Why is this not a ``good'' code? Suppose for instance Alice wants to send the number $2$ to Bob. In binary, $2$ is $010$, so she encodes $(0,1,0)$ as $c=(0,1,0,1,1,0)$. Suppose Bob receives $v=(0,0,0,1,1,0)$. Bob knows that an error occurred in transmission since $Hv\not= {\bf0}$, so $v\notin C$. Suppose only one error occurred. (This is more likely than having two or more errors, and it is easier to detect exactly one error that two or more.) Where did the error occur? Bob doesn't know where since $v$ is just as close to $(1,0,0,1,1,0)$ as it is to $(0,1,0,1,1,0)$ in the sense that they differ by the same number of bits. He can't tell which is correct.

The problem with this example boils down to the fact that the first and second column of $H$ are the same. We shall explain this type of deficency more later.