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:
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:
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 , .
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