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 $ {\bf f}_1,{\bf f}_2,...,{\bf f}_k$ is a basis for an $ [n,k]$-code $ C$, where

$\displaystyle {\bf f}_1=(f_{11},f_{12},...,f_{1n}), $

$\displaystyle {\bf f}_2=(f_{21},f_{22},...,f_{2n}), $

$\displaystyle \vdots $

$\displaystyle {\bf f}_k=(f_{k1},f_{k2},...,f_{kn}), $

then the matrix

\begin{displaymath} \begin{array}{c} G= \left( \begin{array}{c} {\bf f}_1\ {\b... ...ots \ f_{k1}&f_{k2}&...&f_{kn} \end{array}\right) \end{array}\end{displaymath}

is called a generator matrix for $ C$.

A code is often represented by simply giving a generator matrix. To compute a generator matrix of a given code $ C$ of length $ n$, first determine a basis for the code as a vector space over $ \mathbb{F}_q$, then put these basis vectors into a $ k\times n$ matrix, where $ k={\rm dim}_{\mathbb{F}_q}(C)$.

Example 3.4.5   For the ISBN code,

\begin{displaymath} G=\left( \begin{array}{cccccccccc} 1&0&0&0&0&0&0&0&0&1\ 0&... ... 1&0&0&1&0&1&0&0&0&0\ 1&1&1&0&1&0&0&0&0&0 \end{array}\right) \end{displaymath}

is a generator matrix.

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

(a) its sum with another row, or

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

is called an elementary row operation.

If $ G$ is any matrix with entries in a field $ F$ then

(a) swapping any two columns, or

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

is called a simple column operation.

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

proof: The rows of $ G'$ still form a basis for the vector space $ C$ over $ F$. $ \Box$

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

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

\begin{displaymath} G'=\left( \begin{array}{cccccccccc} 1&0&0&0&0&0&0&0&0&1\ 1... ...1&0&0&1&0&1&0&0&0&0\ 1&1&1&0&1&0&0&0&0&0 \end{array}\right), \end{displaymath}

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

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

\begin{displaymath} G''=\left( \begin{array}{cccccccccc} 0&1&0&0&0&0&0&0&0&1\ ... ... 0&1&0&1&0&1&0&0&0&0\ 1&1&1&0&1&0&0&0&0&0 \end{array}\right) \end{displaymath}

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

Example 3.4.10   Let $ {\cal P}=\{P_1,...,P_n\}\subset \mathbb{F}_q$ be a subset of $ n$ distinct points. Let

$\displaystyle L(a)=\{ f\in \mathbb{F}_q[x]\ \vert\ {\rm deg}(f)\leq a\} $

denote the vector space of all polynomials of degree less than or equal to $ a$. The dimension of $ L(a)$ is $ a+1$ since the polynomials $ 1$, $ x$, ..., $ x^a$ form a basis. Assume $ n>a$. Define the evaluation map by

$\displaystyle E_{\cal P}:L(a) \rightarrow \mathbb{F}_q^n $

$\displaystyle f\longmapsto (f(P_1),...,f(P_n)). $

This is 1-1 if $ n>a$ since no polynomial of degree $ a$ can have more than $ a$ zeros. Its image is denoted $ C$. This is a linear $ [n,a+1,n-a]$-code over $ \mathbb{F}_q$.

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 $ n=q-1$.) Note the parameters satisfy the Singleton bound, so these are MDS codes.

The generator matrix for $ C$ is of the form $ G=(P_i^j)_{0\leq j\leq a,1\leq i\leq n}$.

The encoding matrix of a linear code $ C\subset F^n$ of dinension $ k$ is an $ n\times k$ matrix $ E:F^k\rightarrow F^n$ whose image is $ C$. To compute the encoding matrix from the generator matrix is easy.

Proposition 3.4.11   $ E=G^t$.

The proof of this is left as an exercise.

Example 3.4.12   Consider the binary code with generator matrix

\begin{displaymath} G= \left( \begin{array}{ccccccc} 1&0&0&0&1&1\ 0&1&0&0&0&1\ 0&0&1&0&1&0 \end{array}\right). \end{displaymath}

Then

\begin{displaymath} E= \left( \begin{array}{ccc} 1 & 0 & 0\ 0 & 1 & 0\ 0 & 0 & 1\ 0 & 0 & 0\ 1 & 0 & 1\ 1 & 1 & 0 \end{array}\right) \end{displaymath}

and the vector $ v=(1,1,1)$ gets encoded as $ Ev=(1,1,1,0,0,0)$.

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 $ C$ be a linear $ [n,k,d]$-code with parity check matrix $ H$. Then any subset of $ d-1$ columns of $ H$ are linearly independent but there are $ d$ columns of $ H$ which are linearly dependent.

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


David Joyner 2007-09-03