$[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.

Proposition 3.4.11   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.4.31). 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.12   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$

Definition 3.4.13   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. If ${\bf f}_1,{\bf f}_2,...,{\bf f}_k$ is a basis for an $[n,k]$-code $C$, where

$${\bf f}_1=(f_{11},f_{12},...,f_{1n}),$$

$${\bf f}_2=(f_{21},f_{22},...,f_{2n}),$$

$$\vdots$$

$${\bf f}_k=(f_{k1},f_{k2},...,f_{kn}),$$

then the matrix

$$\begin{array}{c} G= \left( \begin{array}{c} {\bf f}_1\\... ... f_{k1}&f_{k2}&...&f_{kn} \end{array} \right) \end{array}$$

is called a generating matrix for $C$.

To compute a generating matrix of a code $C$, first determine a basis for the code then put these basis vectors into a $k\times n$ matrix. The encoding matrix of a linear code $C\subset F^n$ of dinension $k$ is an $n\times k$ matrix $E:F^k\rightarrow F^n$ whose image is $C$. To compute the encoding matrix from the generator matrix is easy.

Proposition 3.4.14   $E=G^t$.

The proof of this is left as an exercise.

Example 3.4.15   Consider the binary code with generating matrix

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

Then

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

and the vector $v=(1,1,1)$ gets encoded as $Ev=(1,1,1,0,0,0)$.

Many general properties about a linear code may be reduced to a corresponding property of its generating matrix. Can one determine the minimum distance of a code from its generating matrix? The following result answers this.

Theorem 3.4.16   Let $C$ be a linear $[n,k,d]$-code with parity check matrix $H$. Then any subset of $d-1$ columns of $H$ are linearly independent but there are $d$ columns of $H$ which are linearly dependent.

proof: By definition of $d$, there is a code word in $C$ having exactly $d$ non-zero entries. Thus by definition of $H$, there are $d$ columns of $H$ which are linearly dependent. If there were $d-1$ columns of $H$ which are linearly independent then there would be (by definition of $H$) a code word in $C$ having exactly $d-1$ non-zero entries. This would contradict the definition of $d$. $\Box$