Generator matrix

Terminology

If G is a matrix, it generates the codewords of a linear code C by

${\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. A generator matrix for a linear ${\displaystyle [n,k,d{]}_q}$-code has format ${\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}$.

The standard form for a generator matrix is,

${\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 code C is systematic in its first k coordinate positions.

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=\left[\begin{array}{c}{I}_k|P\end{array}\right]}$, then the parity check matrix for C is

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

where ${\displaystyle P^{\mathrm{\top }}}$ is the transpose 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 the dual code ${\displaystyle C^{\perp }}$.

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