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

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

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

$$\vdots$$

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

then the matrix

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

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,

$$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)$$

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

$$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),$$

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

$$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)$$

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

$$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

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

$$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

$$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).$$

Then

$$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)$$

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$