# 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 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.

Example 1   Consider the code over with generator matrix given by

and consider the code over with generator matrix given by

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   1Every linear code of length and dimension is permutation equivalent to a code with a generator matrix of the form , where is a 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 , let denote the number of coordinates where these two vectors differ:

 (1)

This defines the Hamming metric on the space . Define the weight of to be the number of non-zero entries of . Note, because the vector has non-zero entries only at locations where and differ.

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].

Next: Algorithms Up: foster_final_report Previous: Contents   Contents
David Joyner 2004-04-27