Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Generator matrix
Summary
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. A generator matrix for a linear -code has format , 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 .
The standard form for a generator matrix is,
where is the identity matrix and P is a 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, , then the parity check matrix for C is
where is the transpose of the matrix . This is a consequence of the fact that a parity check matrix of is a generator matrix of the dual code .
G is a matrix, while H is a matrix.
Codes C1 and C2 are equivalent (denoted C1 ~ C2) 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.