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
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 [ n , k , d ] q {\displaystyle [n,k,d]_{q}} -code has format k × 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 r = n − k {\displaystyle r=n-k} .
The standard form for a generator matrix is,[2]
where I k {\displaystyle I_{k}} is the k × k {\displaystyle k\times k} identity matrix and P is a k × ( 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, G = [ I k | P ] {\displaystyle G={\begin{bmatrix}I_{k}|P\end{bmatrix}}} , then the parity check matrix for C is[4]
where P ⊤ {\displaystyle P^{\top }} is the transpose of the matrix P {\displaystyle P} . This is a consequence of the fact that a parity check matrix of C {\displaystyle C} is a generator matrix of the dual code C ⊥ {\displaystyle C^{\perp }} .
G is a k × n {\displaystyle k\times n} matrix, while H is a ( n − k ) × n {\displaystyle (n-k)\times n} matrix.
Codes C1 and C2 are equivalent (denoted C1 ~ C2) if one code can be obtained from the other via the following two transformations:[5]
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]
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 U G = [ I k | P ] {\displaystyle UG={\begin{bmatrix}I_{k}|P\end{bmatrix}}} , where G and [ I k | P ] {\displaystyle {\begin{bmatrix}I_{k}|P\end{bmatrix}}} generate equivalent codes.
Because the Hamming code is a linear code, it can be written compactly in terms of matrices as follows. The transmitted codeword t {\displaystyle \mathbf {t} } is obtained from the source sequence s {\displaystyle \mathbf {s} } by a linear operation, t = G ⊺ s {\displaystyle \mathbf {t} =\mathbf {G} ^{\intercal }\mathbf {s} } where G {\displaystyle \mathbf {G} } is the generator matrix of the code... I have assumed that s {\displaystyle \mathbf {s} } and t {\displaystyle \mathbf {t} } are column vectors. If instead they are row vectors, then this equation is replaced by t = s G {\displaystyle \mathbf {t} =\mathbf {sG} } ... I find it easier to relate to the right-multiplication (...) than the left-multiplication (...). Many coding theory texts use the left-multiplying conventions (...), however. ...The rows of the generator matrix can be viewed as defining the basis vectors.
t = G ⊺ s {\displaystyle \mathbf {t} =\mathbf {G} ^{\intercal }\mathbf {s} }
t = s G {\displaystyle \mathbf {t} =\mathbf {sG} }
{{cite book}}