Generator matrix

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 (<math>n</math>, <math>M = q^k</math>, <math>d</math>)_{<math>q</math>} code is of dimension <math>k*n</math>. Note that <math>n</math> is the length of a codeword, <math>k</math> is the number of information bits, and <math>d</math> is the minimum distance of the code. Note that the number of redundant bits is denoted <math>r = n - k</math>. The standard form for a generator matrix is

<math>G = \begin{bmatrix} I_k | P \end{bmatrix}</math>

where <math>I_k</math> is a <math>k*k</math> identity matrix and P is of dimension <math>k*r</math>.

Check Matrix

The check matrix is derived from a generator matrix defined in standard form as above

<math>H = \begin{bmatrix} -P^T | I_r \end{bmatrix}</math>

and negation is performed in the finite field mod <math>q</math>. For any valid codeword <math>x</math>, <math>Hx = 0</math>. For any invalid codeword <math>\tilde{x}</math>, the syndrome <math>S</math> satisfies <math>H\tilde{x} = S</math>.

Equivalent Codes

Codes C₁ and C₂ are equivalent (denoted C₁ ~ C₂) 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.

External links

• MathWorld entry