Generator matrix

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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

w = s G,

where w is a codeword of the linear code C, and s is any vector. A generator matrix for an (n, M = q^k, d)q-code has dimensions k×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,[1]

G = \begin{bmatrix} I_k | P \end{bmatrix},

where I_k is the k×k identity matrix and P is a k×r matrix. When the generator matrix is in standard form, the code C is systematic in its first k coordinate positions.[2]

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[3]

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}.

Equivalent Codes[edit]

Codes C1 and C2 are equivalent (denoted C1 ~ C2) if one code can be obtained from the other via the following two transformations:[4]

  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:[5]

  1. permute rows
  2. scale rows by a nonzero scalar
  3. add 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 a 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[edit]

Notes[edit]

  1. ^ Ling & Xing 2004, p. 52
  2. ^ Roman 1992, p. 198
  3. ^ Roman 1992, p. 200
  4. ^ Pless 1998, p. 8
  5. ^ Welsh 1988, pp. 54-55

References[edit]

  • 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 134, Springer-Verlag, ISBN 0-387-97812-7 
  • Welsh, Dominic (1988), Codes and Cryptography, Oxford University Press, ISBN 0-19-853287-3 

Further reading[edit]

External links[edit]