Introduction

Error-correcting codes are used primarily to transmit data across a noisy channel. They do this by encoding the data (adding some redundancy) to the transmission so that the original message can be recovered even if a few errors have occured. Codewords are the encoded data; they are what is transmitted. A code is a set of codewords, and a linear code is a subspace of the vector space $({\mathbb{F}}_q)^n$, where $\mathbb{F}=GF(q)$ is the finite field with $q$ elements. A generator matrix of a linear code can be any basis for the subspace. Let $C$ be a linear code of length $n$ over ${\mathbb{F}}$ with generator matrix $G$, where $q$ is a power of a prime $p$. If $p=2$, then the code is called binary. We assume that ${\mathbb{F}}^{n}$ has been given the standard basis $\mathbf{e}_{1}=(1,0,...,0)\in {\mathbb{F}}^{n}$, $\mathbf{e}_{2}=(0,1,0,...,0)\in {\mathbb{F}}^{n}$, ..., $\mathbf{e}_{n}=(0,0,...,0,1)\in {\mathbb{F}}^{n}$. The dimension of $C$ is denoted $k$, so the number of elements of $C$ is equal to $q^{k}$. The quantity $R=k/n$ is called the rate of the code and measures the amount of information that the code can transmit.

Example 1   Consider the code $C_1$ over $GF(2)$ with generator matrix $G_1$ given by

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

and consider the code $C_2$ over $GF(2)$ with generator matrix $G_2$ given by

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

Notice that these two codes are identical except that the 4th and 5th columns have been swapped. Therefore they are equivalent to each other in the sense defined below.

Two codes are equivalent to each other if one can be obtained from the other by a combination of permutations of positions of the code and multiplication of the symbols appearing in a fixed position by a non-zero scalar. More precisely, two codes are equivalent if the generator matrix of one can be derived from the other using operations of the following types:

1. Permutation of the rows.
2. Multiplication of a row by a non-zero scalar.
3. Addition of a scalar multiple of one row to another.
4. Permutation of the columns.

5. Multiplication of any column by a non-zero scalar.

Two codes are permutation equivalent if one generator matrix can be obtained from the other by using operations of only type 4.

Lemma 1   ¹Every linear code $C$ of length $n$ and dimension $k$ is permutation equivalent to a code $C'$ with a generator matrix of the form $(I_{k} \, \vert \, A)$, where $A$ is a $k \times (n-k)$ matrix.

A code with generator matrix in the form above is said to be in standard form.

Another important parameter associated to the code is the number of errors which it can, in principle, correct. For this notion, let us introduce the concept of distance between codewords. For any two $\mathbf{x},\mathbf{y}\in {\mathbb{F}}^n$, let $d(\mathbf{x},\mathbf{y})$ denote the number of coordinates where these two vectors differ:

$$d(\mathbf{x},\mathbf{y})=\vert\{0\leq i\leq n\ \vert\ x_{i}\not=y_{i}\}\vert.$$ (1)

This defines the Hamming metric on the space ${\mathbb{F}}^n$. Define the weight $w$ of $\mathbf{v}$ to be the number of non-zero entries of $\mathbf{v}$. Note, $d(\mathbf{x},\mathbf{y})=w(\mathbf{x}-\mathbf{y})$ because the vector $\mathbf{x}-\mathbf{y}$ has non-zero entries only at locations where $\mathbf{x}$ and $\mathbf{y}$ differ.

If $d(C)$ is the smallest distance between codewords in a linear code $C$, then there exist $\mathbf{x}$ and $\mathbf{y}$ such that $d(C)=d(\mathbf{x},\mathbf{y})$. Then $% d(C)=w(\mathbf{x}-\mathbf{y}) \geq w(C)$, where $w(C)$ is the minimum weight of a codeword in $C$. Also, for some other codeword $\mathbf{z}$, $w(C)=w(\mathbf{z})=d(\mathbf{0},\mathbf{z})\geq d(C)$.

Therefore, $w(C)=d(C)$.

If $M$ is any matrix with coefficents in ${\mathbb{F}}$, then let $d(M)$ denote the minimum distance of the linear code spanned by the rows of $M$.

Now, define the minimum distance of $C$ to be

$$d=d(C)=\min_{\mathbf{c}\in C,\, \mathbf{c}\not= \mathbf{0}}d(\mathbf{0},\mathbf{c}).$$ (2)

Note, if $C$ is equivalent to $C'$, then $d(C)=d(C')$. In general, this parameter is known to be very difficult to efficiently determine [CHA]. In fact, computing it in general is known to be NP-complete [BMT], [VAR].