## The generator matrix

Since a code is a finite dimensional vector space over a finite field, it only has finitely many elements. To represent a code in a computer one may of course store all the elements. But there must be a simpler way of representing a code than by listing all of its elements, right? Yes, there is and this motivates the following definition.

Definition 3.4.4   If is a basis for an -code , where

then the matrix

is called a generator matrix for .

A code is often represented by simply giving a generator matrix. To compute a generator matrix of a given code of length , first determine a basis for the code as a vector space over , then put these basis vectors into a matrix, where .

Example 3.4.5   For the ISBN code,

is a generator matrix.

Definition 3.4.6   If is any matrix with entries in a field then replacing any row of by

(a) its sum with another row, or

(b) its scalar multiple with any non-zero element of ,

is called an elementary row operation.

If is any matrix with entries in a field then

(a) swapping any two columns, or

(b) replacing any column of by its scalar multiple with any non-zero element of ,

is called a simple column operation.

Lemma 3.4.7   If is a generator matrix for a linear code then so is , where is any matrix obtained from by an elementary row operation.

proof: The rows of still form a basis for the vector space over .

Definition 3.4.8   If is a generator matrix for a linear code and is the linear code with generator matrix , where is any matrix obtained from by elementary row operations or simple column operations, then we say that the codes and are equivalent.

Example 3.4.9   We know a generator matrix for the ISBN code by Example 3.4.5. By the above lemma, another generator matrix is given by

where we replaced the second row of by its sum with the first row.

However, if we swap the first two columns of , to get

then generates a code which is different from . However, the codes and are equivalent.

Example 3.4.10   Let be a subset of distinct points. Let

denote the vector space of all polynomials of degree less than or equal to . The dimension of is since the polynomials , , ..., form a basis. Assume . Define the evaluation map by

This is 1-1 if since no polynomial of degree can have more than zeros. Its image is denoted . This is a linear -code over .

These are called generalized (or shortened or extended) Reed-Solomon codes. (As we shall see later, in the context of cyclic codes, Reed-Solomon codes have .) Note the parameters satisfy the Singleton bound, so these are MDS codes.

The generator matrix for is of the form .

The encoding matrix of a linear code of dinension is an matrix whose image is . To compute the encoding matrix from the generator matrix is easy.

The proof of this is left as an exercise.

Example 3.4.12   Consider the binary code with generator matrix

Then

and the vector gets encoded as .

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

Theorem 3.4.13   Let be a linear -code with parity check matrix . Then any subset of columns of are linearly independent but there are columns of which are linearly dependent.

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

David Joyner 2007-09-03