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
![{\displaystyle w=sG}](//wikimedia.org/api/rest_v1/media/math/render/svg/f0d05009f825a0b37e15b6430507dde7ec8d07ce)
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.[1] 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,[2]
,
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.[3]
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[4]
,
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 C1 and C2 are equivalent (denoted C1 ~ C2) if one code can be obtained from the other via the following two transformations:[5]
- 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:[6]
- 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 an invertible matrix U such that
, where G and
generate equivalent codes.
MacKay, David, J.C. (2003). Information Theory, Inference, and Learning Algorithms (PDF). Cambridge University Press. p. 9. ISBN 9780521642989. Because the Hamming code is a linear code, it can be written compactly in terms of matrices as follows. The transmitted codeword
is obtained from the source sequence
by a linear operation,![{\displaystyle \mathbf {t} =\mathbf {G} ^{\intercal }\mathbf {s} }](//wikimedia.org/api/rest_v1/media/math/render/svg/f4311f0f9b20efb60ac7a874e5d98018d4ca9277)
where
is the generator matrix of the code... I have assumed that
and
are column vectors. If instead they are row vectors, then this equation is replaced by ![{\displaystyle \mathbf {t} =\mathbf {sG} }](//wikimedia.org/api/rest_v1/media/math/render/svg/78ff9e776d36c6d97eab7e5b90f13f2f62d9bdfc)
... I find it easier to relate to the right-multiplication (...) than the left-multiplication (...). Many coding theory texts use the left-multiplying conventions (...), however. ...The rows of the generator matrix can be viewed as defining the basis vectors.
{{cite book}}
: CS1 maint: multiple names: authors list (link)
- Ling, San; Xing, Chaoping (2004), Coding Theory / A First Course, Cambridge University Press, ISBN 0-521-52923-9
- Pless, Vera (1998), Introduction to the Theory of Error-Correcting Codes (3rd ed.), Wiley Interscience, ISBN 0-471-19047-0
- Roman, Steven (1992), Coding and Information Theory, GTM, vol. 134, Springer-Verlag, ISBN 0-387-97812-7
- Welsh, Dominic (1988), Codes and Cryptography, Oxford University Press, ISBN 0-19-853287-3