In coding theory, a generator matrix is a matrix whose rows form a basis for a linear code. The codewords are all of the linear combinations of the rows of this matrix, that is, the linear code is the row space of its generator matrix.
If G is a matrix, it generates the codewords of a linear code C by
where w is a codeword of the linear code C, and s is any input vector. Both w and s are assumed to be row vectors. A generator matrix for a linear -code has format , where n is the length of a codeword, k is the number of information bits (the dimension of C as a vector subspace), d is the minimum distance of the code, and q is size of the finite field, that is, the number of symbols in the alphabet (thus, q = 2 indicates a binary code, etc.). The number of redundant bits is denoted by .
The standard form for a generator matrix is,
where is the identity matrix and P is a matrix. When the generator matrix is in standard form, the code C is systematic in its first k coordinate positions.
A generator matrix can be used to construct the parity check matrix for a code (and vice versa). If the generator matrix G is in standard form, , then the parity check matrix for C is
where is the transpose of the matrix . This is a consequence of the fact that a parity check matrix of is a generator matrix of the dual code .
G is a matrix, while H is a matrix.
Codes C<sub>1</sub> and C<sub>2</sub> are equivalent (denoted C<sub>1</sub> ~ C<sub>2</sub>) if one code can be obtained from the other via the following two transformations:
Equivalent codes have the same minimum distance.
The generator matrices of equivalent codes can be obtained from one another via the following elementary operations:
Thus, we can perform Gaussian elimination on G. Indeed, this allows us to assume that the generator matrix is in the standard form. More precisely, for any matrix G we can find an invertible matrix U such that , where G and generate equivalent codes.