In coding theory

Coding theory

Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

, a generator matrix is a basis

Basis (linear algebra)

In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...

 for a linear code

Linear code

In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although Turbo codes can be seen as a hybrid of these two types. Linear codes allow for...

, generating all its possible codewords.
If the matrix is G and the linear code is C,

w = cG

where w is a codeword of the linear code C, c is a row vector, and a bijection

Bijection

A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...

 exists between w and c. A generator matrix for an (, , )-code has dimensions 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

Binary code

A binary code is a way of representing text or computer processor instructions by the use of the binary number system's two-binary digits 0 and 1. This is accomplished by assigning a bit string to each particular symbol or instruction...

, etc.). The number of redundant bits

Redundancy (information theory)

Redundancy in information theory is the number of bits used to transmit a message minus the number of bits of actual information in the message. Informally, it is the amount of wasted "space" used to transmit certain data...

 is denoted by r = n - k.

The systematic

Systematic code

In coding theory, a systematic code is any error-correcting code in which the input data is embedded in the encoded output. Conversely, in a non-systematic code the output does not contain the input symbols....

 form for a generator matrix is

where is a k×k identity matrix

Identity matrix

In linear algebra, the identity matrix or unit matrix of size n is the n×n square matrix with ones on the main diagonal and zeros elsewhere. It is denoted by In, or simply by I if the size is immaterial or can be trivially determined by the context...

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

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