Generator matrix

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}${\displaystyle w=sG}

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 ${\displaystyle [n,k,d]_{q}}${\displaystyle [n,k,d]_{q}}-code has format ${\displaystyle k\times n}${\displaystyle k\times n}, 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 ${\displaystyle r=n-k}${\displaystyle r=n-k}.

The standard form for a generator matrix is,^[2]

${\displaystyle G={\begin{bmatrix}I_{k}|P\end{bmatrix}}}${\displaystyle G={\begin{bmatrix}I_{k}|P\end{bmatrix}}},

where ${\displaystyle I_{k}}${\displaystyle I_{k}} is the ${\displaystyle k\times k}${\displaystyle k\times k} identity matrix and P is a ${\displaystyle k\times (n-k)}${\displaystyle k\times (n-k)} 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, ${\displaystyle G={\begin{bmatrix}I_{k}|P\end{bmatrix}}}${\displaystyle G={\begin{bmatrix}I_{k}|P\end{bmatrix}}}, then the parity check matrix for C is^[4]

${\displaystyle H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}}${\displaystyle H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}},

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

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

Codes C₁ and C₂ are equivalent (denoted C₁ ~ 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 following elementary 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 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 ${\displaystyle UG={\begin{bmatrix}I_{k}|P\end{bmatrix}}}${\displaystyle UG={\begin{bmatrix}I_{k}|P\end{bmatrix}}}, where G and ${\displaystyle {\begin{bmatrix}I_{k}|P\end{bmatrix}}}${\displaystyle {\begin{bmatrix}I_{k}|P\end{bmatrix}}} 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