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 occurred.
**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
,
where
is the finite field with elements.
A **generator matrix** of a linear code can be any basis
for the subspace.
Let be a linear code of length over
with
generator matrix , where is a power of a prime .
If , then the code is called **binary**. We
assume that
has been given the standard basis
,
, ...,
.
The **dimension** of is denoted , so the number of
elements of is equal to . The quantity is called
the **rate** of
the code and measures the amount of information that the code can transmit.

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:

- Permutation of the rows.
- Multiplication of a row by a non-zero scalar.
- Addition of a scalar multiple of one row to another.
- Permutation of the columns.
- Multiplication of any column by a non-zero scalar.

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 , let denote the number of coordinates where these two vectors differ:

(1) |

This defines the

If is the smallest distance between codewords in a linear code , then there exist and such that . Then , where is the minimum weight of a codeword in . Also, for some other codeword , .

Therefore, .

If is any matrix with coefficients in , then let denote the minimum distance of the linear code spanned by the rows of .

Now, define the **minimum distance of ** to be

(2) |

Note, if is equivalent to , then . 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].