Generator matrix

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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.

Terminology

If G is a matrix, it generates the codewords of a linear code C by 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 [n, k, d]_q -code has format 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 . The standard form for a generator matrix is, G = \begin{bmatrix} I_k | P \end{bmatrix} , where I_k is the k \times k identity matrix and P is a 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, G = \begin{bmatrix} I_k | P \end{bmatrix} , then the parity check matrix for C is H = \begin{bmatrix} -P^{\top} | I_{n-k} \end{bmatrix} , where P^{\top} is the transpose of the matrix P . This is a consequence of the fact that a parity check matrix of C is a generator matrix of the dual code C^{\perp} . G is a k \times n matrix, while H is a (n-k) \times n matrix.

Equivalent codes

Codes C 1 and C 2 are equivalent (denoted C 1 ~ C 2 ) 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. The generator matrices of equivalent codes can be obtained from one another via the following elementary operations: 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 an invertible matrix U such that UG = \begin{bmatrix} I_k | P \end{bmatrix} , where G and \begin{bmatrix} I_k | P \end{bmatrix} generate equivalent codes.

See also

Hamming code (7,4)

Notes

References

Further reading

External links

Generator Matrix at MathWorld

Text derived from https://en.wikipedia.org/w/index.php?oldid=1362628443 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001362628443 · captured 1783226263.0 · version history

Cite this page as: encyclopegia.org, “Generator matrix”, snapshot enwiki-001362628443. https://encyclopegia.org/a/generator-matrix

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.