$[n,k,d]$-codes and error correction

How does the minimum distance related to the number of errors which can be corrected? This section addresses this and similar questions.

Definition 3.4.1   Let $F$ be a finite field. A code $C\subset F^n$ is called an $(n,M,d)$-code if it is length $n$, cardinality $\vert C\vert=M$, and minimum distance $d$. A linear code $C\subset F^n$ is called an $[n,k,d]$-code if it is length $n$, dimension $k$, and minimum distance $d$. If $d$ is unknown then we call a linear code $C\subset F^n$ of dimension $k$ a $[n,k]$-code.

For example, the ISBN code is a $[10,9,2]$-code over the field $\mathbb{F}_{11}$.

Proposition 3.4.2   Let $C\subset F^n$ be a code which is defined by

$$C=\{v\in F^n\ \vert\ Hv=0\},$$

where $H$ is some $r\times n$ matrix with entries in $F$. The $C$ is $1$-error correcting if and only if all the columns of $H$ are distinct.

The matrix $H$ in the above proposition is called a parity check matrix of $C$. We have yet to show that a given linear code $C$ has a parity check matrix (see Proposition 3.6.3).

proof: (sketch) Generalizing suitably example 3.3.2 shows that if all the columns of $H$ are not distinct then $C$ is not $1$-error correcting.

Conversely, suppose that $v$ contains exactly one error and that all the columns of $H$ are distinct. Then $v=c+e_i$, for some $c$ and some $i$, where $c\in C$ and where

$$e_1=(1,0,...,0), \ \ e_2=(0,1,0,...,0), ..., e_n=(0,0,...,0,1).$$

To correct $v$, we need to determine $i$. Note $Hv=Hc+He_i=0+He_i=h_i$, where $h_i$ denotes the $i^{th}$ column of $H$. Since all the columns are $H$ are distinct, $h_i$ uniquely determines $i$. $\Box$

Proposition 3.4.3   Let $C\subset F^n$ be a code which is of minimum distance $d$. Then $C$ is $[(d-1)/2]$-error-correcting.

proof: Suppose that a code word ${\bf c}\in C$ is sent and a vector ${\bf v}\in F^n$ is received with $e$ errors, where $e\leq [(d-1)/2]$. We must show that the receiver, who does not know ${\bf c}$ (though he does know $C$), can recover ${\bf c}$ from ${\bf v}$.

We claim that the code word closest to ${\bf v}$ is ${\bf c}$. Suppose not, say ${\bf c'}\in C$, ${\bf c}\not= {\bf c'}$, is closer to ${\bf v}$ than ${\bf c}$. Then

$$d({\bf v},{\bf c'})\leq d({\bf v},{\bf c})\leq e,$$

so, by the triangle inequality, $d\leq d({\bf c},{\bf c'})\leq d({\bf c},{\bf v})+d({\bf v},{\bf c'}) \leq e+e=2e\leq d-1$. This is a contradiction, which proves the claim is true.

To recover ${\bf c}$ from ${\bf v}$, the receiver can apply the nearest neighbor algorithm. $\Box$