Generator matrix

From Wikipedia, the free encyclopedia

In coding theory, a generator matrix is a basis for a linear code, generating all its possible codewords. If the matrix is G and the linear code is C,

w=cG

where w is a unique codeword of the linear code C, c is a unique row vector, and a bijection exists between w and c. A generator matrix for a (n, M = qk, d)q-code is of dimension k * n. Here n is the length of a codeword, k is the number of information bits, d is the minimum distance of the code, and q is the number of symbols in the alphabet (thus, q = 2 indicates a binary code, etc.). Note that the number of redundant bits is denoted r = n − k.

The standard form for a generator matrix is

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

where Ik is a k * k identity matrix and P is of dimension k * r.

A generator matrix can be used to construct the parity check matrix for a code (and vice-versa).

[edit] Equivalent Codes

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

  1. permute components, and
  2. scale components.

Equivalent codes have the same distance.

The generator matrices of equivalent codes can be obtained from one another via the following transformations:

  1. permute rows
  2. scale rows
  3. add rows
  4. permute columns, and
  5. scale columns.

[edit] External links

Languages