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.
Contents
Terminology
If G is a matrix, it generates the codewords of a linear code C by,
w = s G,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
The standard form for a generator matrix is,
where
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,
where
Equivalent Codes
Codes C1 and C2 are equivalent (denoted C1 ~ C2) if one code can be obtained from the other via the following two transformations:
- arbitrarily permute the components, and
- independently scale by a non-zero element any components.
Equivalent codes have the same minimum distance.
The generator matrices of equivalent codes can be obtained from one another via the following elementary operations:
- permute rows
- scale rows by a nonzero scalar
- add rows to other rows
- permute columns, and
- scale columns by a nonzero scalar.
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 a invertible matrix U such that