Generator matrix

For generator matrices in probability theory, see transition rate matrix.

In coding theory, a generator matrix is a basis for a linear code, generating all its possible codewords. If the matrix is G and the linear code is C,

w = cG

where w is a codeword of the linear code C, c is a row vector, and a bijection exists between w and c. A generator matrix for an ($n$, $M=q^{k}$, $d$)_$q$-code has dimensions k×n. Here n is the length of a codeword, k is the number of information bits, d is the minimum distance of the code, and q is the number of symbols in the alphabet (thus, q = 2 indicates a binary code, etc.). The number of redundant bits is denoted by r = n - k.

The systematic form for a generator matrix is

$G={\begin{bmatrix}I_{k}|P\end{bmatrix}}$

where $I_{k}$ is a k×k identity matrix and P is of dimension k×r.

A generator matrix can be used to construct the parity check matrix for a code (and vice-versa).

Equivalent Codes

Codes C₁ and C₂ are equivalent (denoted C₁ ~ C₂) if one code can be created from the other via the following two transformations:

1. permute components, and
2. scale components.

Equivalent codes have the same distance.

The generator matrices of equivalent codes can be obtained from one another via the following elementary operations:

1. permute rows
2. scale rows
3. add rows
4. permute columns, and
5. scale columns.

Thus we can perform Gaussian Elimination by rows. Indeed, this allows to assume assume the standard form. Explicitly, for any matrix G we can find a invertible matrix U such that $UG={\begin{bmatrix}I_{k}|P\end{bmatrix}}$, where both G and ${\begin{bmatrix}I_{k}|P\end{bmatrix}}$ generate the same code.

See also

• Hamming code (7,4)

External links

• MathWorld entry