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,
- w = s G,
where w is a codeword of the linear code C, and s is any vector. 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 r = n - k.
The standard form for a generator matrix is,
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.
- 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 , where G and generate equivalent codes.
- 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 134, Springer-Verlag, ISBN 0-387-97812-7
- Welsh, Dominic (1988), Codes and Cryptography, Oxford University Press, ISBN 0-19-853287-3
- MacWilliams, F.J.; Sloane, N.J.A. (1977), The Theory of Error-Correcting Codes, North-Holland, ISBN 0-444-85193-3