Incoding theory, agenerator matrix is amatrix whose rows form abasis for alinear code. The codewords are all of thelinear combinations of the rows of this matrix, that is, the linear code is therow space of its generator matrix.

IfG is a matrix, it generates thecodewords of a linear codeC by

${\displaystyle w=sG}$

wherew is a codeword of the linear codeC, ands is any input vector. Bothw ands are assumed to be row vectors.^[1] A generator matrix for a linear${\displaystyle [n,k,d{]}_q}$-code has format${\displaystyle k\times n}$, wheren is the length of a codeword,k is the number of information bits (the dimension ofC as a vector subspace),d is the minimum distance of the code, andq is size of thefinite field, that is, the number of symbols in the alphabet (thus,q = 2 indicates abinary code, etc.). The number ofredundant bits is denoted by${\displaystyle r=n-k}$.

Thestandard form for a generator matrix is,^[2]

${\displaystyle G=\left[\begin{array}{c}{I}_k|P\end{array}\right]}$,

where${\displaystyle I_k}$ is the${\displaystyle k\times k}$identity matrix and P is a${\displaystyle k\times (n-k)}$ matrix. When the generator matrix is in standard form, the codeC issystematic in its firstk coordinate positions.^[3]

A generator matrix can be used to construct theparity check matrix for a code (and vice versa). If the generator matrixG is in standard form,${\displaystyle G=\left[\begin{array}{c}{I}_k|P\end{array}\right]}$, then the parity check matrix forC is^[4]

${\displaystyle H=\left[\begin{array}{c}-P^{\mathrm{\top }}|I_{n-k}\end{array}\right]}$,

where${\displaystyle P^{\mathrm{\top }}}$ is thetranspose of the matrix${\displaystyle P}$. This is a consequence of the fact that a parity check matrix of${\displaystyle C}$ is a generator matrix of thedual code${\displaystyle C^{\perp }}$.

G is a${\displaystyle k\times n}$ matrix, while H is a${\displaystyle (n-k)\times n}$ matrix.

CodesC₁ andC₂ areequivalent (denotedC₁ ~C₂) if one code can be obtained from the other via the following two transformations:^[5]

1. arbitrarily permute the components, and
2. 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 followingelementary operations:^[6]

1. permute rows
2. scale rows by a nonzero scalar
3. add rows to other rows
4. permute columns, and
5. scale columns by a nonzero scalar.

Thus, we can performGaussian elimination onG. Indeed, this allows us to assume that the generator matrix is in the standard form. More precisely, for any matrixG we can find aninvertible matrixU such that${\displaystyle UG=\left[\begin{array}{c}{I}_k|P\end{array}\right]}$, whereG and${\displaystyle \left[\begin{array}{c}{I}_k|P\end{array}\right]}$ generate equivalent codes.

• Hamming code (7,4)

• 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

• MacWilliams, F.J.;Sloane, N.J.A. (1977),The Theory of Error-Correcting Codes, North-Holland,ISBN 0-444-85193-3

• Generator Matrix at MathWorld

• Coding theory

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description matches Wikidata