Stamp generating

A generating matrix is a concept of Théorie of the codes used in the case of the linear codes.

It corresponds to the matrix of the Linear application of E the vector Space of the messages to communicate in F , the vector space containing the transmitted codes.

The concept of generating matrix has at the same time a theoretical interest within the framework of the study of the correct codes, for example to define the systematic concept of code , and a practical interest for an effective implementation.

Context

Code correct

See also: correct Code

A correct code has for objective the detection or the correction of errors after the transmission of a Message. This correction is allowed thanks to the addition of redundant information. The message is plunged in a larger unit, the difference in size contains the redundancy, the image of the message by plunging is transmitted. In the event of deterioration of the message, the redundancy is conceived to detect or correct the errors. A simple example is that of the Code of repetition, the message, for example, is sent three times, decoding is done by vote. Here, the larger unit is of triple size to that of the initial message.

Let us point out the basic elements of formalization. There exists a unit E made up of continuations to values in an alphabet and length K , i.e. starting from the row K , all the values of the continuation are null. These elements are the space of the messages which one wishes to communicate. To provide the message with the desired redundancy, there exists a injective application φ of E to values in F , the space of the continuations from length to values in an alphabet N . The function φ is called encoding , φ ( E ) also noted C is called the code , an element of φ ( E ) word of the code , K the length of the code and N the dimension of the code. These notations are used in all the article.

Linear code

See also: linear Code

A linear code lays out algebraic of a structure richer than that of the general framework of the correct codes. The alphabets has and A' is identified and provided with a structure of Corps finished. The most frequent case consists in choosing the body F 2 or one of its finished extensions. This body corresponds to the binary alphabet whose tables of addition and multiplication are given below:

| |}

The units E and F are naturally provided with a structure of vector space of dimension respective K and N . If F d indicates the body finished (cf the article Corps finished) of cardinal D where D is a power of a Prime number p , then the vector space F is generally identified with F dn.

F is provided with a distance which derives from the Poids Hamming. The distance between two points of F corresponds to the numbers of nonnull coordinates of the difference between the two points, in the canonical Base. A code is described by three parameters, noted '' K '', δ, N is the dimension of the code, K the length of the code and δ the minimal distance between two words of the code. These notations are used in the remainder of the article.

Lastly, the application of encoding φ is selected linear, the code is thus a vectorial Sous-espace.

Definitions

A natural concept appears and gives place to the following definition:
* the generating matrix G of a linear code is the matrix of the linear application of encoding φ in the canonical bases.
The following equality is naturally checked according to the properties of the matrices:
\ forall X \ in \ mathbb {F} _q^k \ quad x.G = \ varphi (X) \ in C \ subset \ mathbb {F} _q^n
It is noticed that the dimension of the generating matrix is N X K because E is of dimension K and F of dimension N .
* Two generating matrices G and G' are known as equivalent if and only if there exists a square Matrice P of a Automorphisme of E such as: G' = G . P .
The codes length K and dimension N on the same finished body have the same properties exactly if their generating matrices are equivalent. In particular, they have the same minimal distance. Indeed, the image of φ, i.e. the code remains unchanged by any preliminary permutation on the unit E , in particular by an automorphism. It is not the same for F , an automorphism can associate with two vectors at a distance the Hamming one of δ, two vectors at a distance from one, which would destroy all the properties of the code.

Examples

Code repetition

See also: Code of repetition

A code of repetition is a code which with a message m length K , associates the message m… m . If its alphabet is selected as being equal to a finished body, then the code is linear of generating matrix G r equalizes with:

G_r= \ begin {pmatrix} I_k \ \ \ vdots \ \ I_k \ end {pmatrix} \ quad with \ quad I_k= \ begin {pmatrix} 1 & 0 & \ cdots & 0 \ \ 0 & \ ddots & \ ddots & \ vdots \ \ \ vdots & \ ddots & \ ddots & 0 \ \ 0 & \ cdots & 0 & 1 \ end {pmatrix}

Summon of control

See also: Checksum

The sum of control corresponds to a code of parameter + 1, '' K '', 2, with a message is associated the word with the code equal to the concaténé message with the sum (with value in the finished body) of all the letters of the message. If the code is binary, that amounts associating a if the sum of the letters is odd and zero if not. In the general case, it has as a generating matrix G s and, by using the preceding notations:

G_s= {I_k \ choose C} \ quad with \ quad C = (- 1, \ cdots, - 1)

Hamming code (7,4)

See also: Hamming code (7,4)

The Hamming code (7,4) is a binary code of parameter. The figure of right-hand side is a chart of this code. The message is the word D 1 D 2 D 3 D 4. The word of the code is consisted of the four letters of the word of the message, then of three checksums p 1 p 2 p 3. The value of p i is equal to zero if the sum of the three letters of the message included in its circle on the figure is even and a if not.

It thus has the generating matrix G h following:

G_h= \ begin {pmatrix} 1 & 0 & 0 & 0 \ \ 0 & 1 & 0 & 0 \ \ 0 & 0 & 1 & 0 \ \ 0 & 0 & 0 & 1 \ \ 1 & 1 & 0 & 1 \ \ 1 & 0 & 1 & 1 \ \ 0 & 1 & 1 & 1 \ end {pmatrix}

Properties

Systematic code

There exists the shape of the particularly simple matrix generating, which gives place to the following definition:
*Un linear code whose generating matrix has for K first columns a matrix identity is known as systematic code .
The matrix takes the following form then:
^tx. G= (x_1, \ cdots, x_k). \ begin {pmatrix} 1 & 0 & \ cdots & 0 & c_ {1 k+1} & \ cdots & c_ {1 N} \ \ 0 & \ ddots & \ ddots & \ vdots & \ vdots & \ ddots & \ vdots \ \ \ vdots & \ ddots & \ ddots & 0 & c_ {k-1 k+1} & \ cdots & c_ {k-1 N} \ \ 0 & \ cdots & 0 & 1 & c_ {K k+1} & \ cdots & c_ {K N} \ end {pmatrix}

(x_1, \ cdots, x_k, b_1, \ cdots, b_ {n-k})

This form is particularly interesting, the calculation of the word of code consists with the determination of N - K last coordinates, because the K first correspond to those of the message initial. Moreover, subject to absence of deterioration, decoding is him also fast, it consists in not considering solely N first coordinates of the word of the code. One notices in the passing that the number of lines of the generating matrix is equal to the order of the vector to code (noted K here), without what the matric product does not have a direction.

* N - K last columns ( C ij) of the generating matrix are called checks redundancy .

* N - K last coordinates ( B j) of a systematic code are known as bits of control or sometimes checksum .
These coordinates correspond exactly to the redundancy, their objective is the detection or the correction of possible errors. In the binary case, they correspond to the parity of sums of letters of the message of origin, one speaks then often about bits of parity.

The codes all linear can be put in this form:

* Any code linear is equivalent to a systematic code.
What means that, even if it means to modify the base of E , it is possible to express the generating matrix of the code thanks to a systematic matrix.

Random links:Gov' T Mule (album) | Part of the four riders | 7,92 × 33 mm | Daniel Baldwin | Lajas (Puerto Rico) | Vipère_d'USS