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.
- 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,
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
The rows of the generator matrix can be viewed as defining the basis vectors.
- Ling & Xing 2004, p. 52
- Roman 1992, p. 198
- Roman 1992, p. 200
- Pless 1998, p. 8
- Welsh 1988, pp. 54-55
- 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