Properties of the minimum distance

Let $C\subset F^n$ be a code. The number

$$d=\min_{{\bf v}\not= {\bf w}} d({\bf v}, {\bf w}),$$

where the minimum runs over all distinct code words in $C$, is called the minimum distance of $C$. This (as we will see) measures the ability for the code to correct errors which might be introduced in transmission.

Theorem 3.3.10   If $C$ is a linear code and if $d$ denotes the minimum distance of $C$ then

$$d=\min_{{\bf v}\not= {\bf0}} d({\bf v}, {\bf0}),$$

where the minimum runs over all non-zero code words in $C$.

In other words, the minimum distance of a linear code is the length of its shortest non-zero vector.

proof: Clearly, $d\leq \min_{{\bf v}\not= {\bf0}} d({\bf v}, {\bf0})$. Conversely, suppose ${\bf v},{\bf w}$ are code words such that $d=d({\bf v},{\bf w})$. By (3.1), $d=d({\bf v}-{\bf w},{\bf0})$, so $\min_{{\bf v}\not= {\bf0}} d({\bf v}, {\bf0})\leq d$. $\Box$

The above theorem helps us find the minimum distance of the ISBN code $C$ in Example 3.3.6. This is a subspace of $\mathbb{F}_{11}^{10}$. There is no codeword of weight $1$. This is due to the fact that $(x_1,x_2,...,x_{10})\in \mathbb{F}_{11}^{10}$ is a codeword if and only if $x_1+2x_2+3x_3+...+9x_9+10x_{10}\equiv 0\ ({\rm mod}\ 11)$. But if only one coordinate is non-zero then $11$ divides $ix_i$, for some $1\leq i\leq 10$. This forces $11\vert x_i$ but in $\mathbb{F}_{11}$ that says $x_i=0$. However, there is a codeword of weight $2$, for example, $(1,0,...,0,1)$ ( $x_1=x_{10}=1$, all other $x_i=0$). By the above theorem, the minimum distance $d$ of $C$ is therefore $d=2$.

Definition 3.3.11   We say that $C$ is $e$-error correcting if the following property always holds: given any ${\bf w}\in F^n$ whose Hamming distance from some ${\bf c}\in C$ is $\leq e$ then any ${\bf c'}\in C$, ${\bf c}\not= {\bf c'}$, must satisfy $d({\bf w},{\bf c'})>e$ (in other words, a codeword at most distance $e$ from ${\bf w}$ is unique if ${\bf w}$ has at most $e$ errors).

In the next section we shall show that if $d$ denotes the minimum distance of $C$ then the smallest $e$ for which $G$ is $e$-error correcting is the integer part of $\frac{d-1}{2}$. For now, we explore some of this definitions more basic consequences.

This definition means that if you have sent off a code word ${\bf c}\in C$ and know the receiver received a vector ${\bf v}\in F^n$ which has $e$ errors or less (i.e., $d({\bf c},{\bf v})\leq e$) then the code word closest to ${\bf v}$ (in the sense of the Hamming distance) is ${\bf c}$. In this case, to decode the received vector ${\bf v}$, all the receiver has to do to determine $c$ is search $C$ (which is a finite set) and find a code word ${\bf c'}$ which is as close as possible to ${\bf v}$. This strategy is called the nearest neighbor algorithm. If $C$ is $e$-error correcting and ${\bf v}$ has no more than $e$ errors then ${\bf c'}={\bf c}$. If $C$ is ``too large'' (where the definition of ``large'' is a function of the speed of your computer and your level of patience) then this algorithm is too slow for practical purposes.

The following theorem of Shannon is fundamental to the theory of error correcting codes.

Theorem 3.3.12 (fundamental theorem of information theory)   Consider a binary symmetric channel with $p>1/2$. Let $\epsilon>0$ and $\delta>0$ be given. For all sufficiently large $n$, there is a code $C\subset \mathbb{F}_2^n$ with information rate $R$ satisfying $cap(p)-\epsilon <R<cap(p)$, such that the nearest neighbor algorithm decoding has average probability of incorrect decoding less that $\delta$.

Shannon's theorem guarantees us that ``very good'' codes (in the sense that they are close to being best possible) exist. They may not be linear and even if they are, the theorem does not suggest that they are practical (i.e., ``fast'' encoding and decoding algorithms exist). However, we shall very briefly discuss in a later chapter ``low density parity check codes'', which can be both ``very good'' and practical. The proof of Shanon's theorem is not easy and goes beyond the scope of this book. For a proof and further discussion, see Ash [Ash], §3.5.

Figure 3.1 graphs the capacity for a binary code.

Figure 3.1: The capacity function for binary codes.