Hamming code

A Hamming code is a correct Code linear. It allows the detection and the autocorrection of an error if it relates only to one letter of the message.

A Hamming code is perfect, which means that for length of code given, there does not exist other more compact code having the same capacity of correction. In this direction, its output is maximum.

There exists a family of Hamming code , most famous and simplest after the binary Code of repetition of size three and length a is undoubtedly the binary code of parameters [7,4,3]. For, each alphabet having for many letters a power of a Prime number and for each length L of code, there exists a Hamming code using this alphabet and length at least equal to L .

Several methods make it possible to build a Hamming code . An approach consists in seeking the cyclic codes of minimal distance equalizes to three, the code then seems a particular case of Code BCH. It is also possible to use only the tools of the Linear algebra and particularly the theory of the matrices.

History

Since 1946 Richard Hamming (1915 - 1998) works on a model of Calculateur to Perforated card of low reliability. If, during the week, of the engineers could correct the errors, the been unemployed periods as the end of the week see the machines stopping invariably on bugs. Frustration Hamming conduit to invent the first truly effective correct code.

This period corresponds to the birth of the Information theory. Claude Shannon (1916, 2001) formalizes this theory as a branch of mathematics. Hamming develops the premises of the theory of the codes and described its solution like an example.

In 1960, two mathematicians R.C. Bump, D.K. Ray-Chaudhuri show that ideals of the ring of the polynomials on the finished bodies of characteristic two are particularly adapted. The theory is generalized by mathematician A. Hocquenghem and gives rise to the family of codes BCH. The Hamming codes the binary ones seem codes BCH immediately.

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 Hamming code proceeds of this logic, the redundancy allows exactly the correction of a deterioration on a single letter of the 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 length N and values in an alphabet. 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 of a structure algebraic 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 ₂ or one of its finished extensions, one then speaks about binary alphabet .

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 _dⁿ.

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. Lastly, the application of encoding φ is selected linear, the code is thus a vectorial Sous-espace.

A Hamming code is a linear code, whose minimal distance δ is equal to three . These notations are used in the remainder of the article.

Perfect code

See also: perfect Code

Usually, it is considered that the word of emitted code is that more being close to the received word, which amounts supposing that the minimum of letters was modified. This process led to an error of decoding each time the error is higher than the corrective capacity of the code. The natural question is that of the value of T corresponding to the maximum number of corrigible errors.

A geometrical interpretation gives a brief reply. the closed balls ray T centered on the words of code must be disjoined. The capacity of correction of a code corresponds to the greatest entirety T checking this property, it is as the greatest entirety strictly smaller as δ/2, which in the case of gives a value equal to a a Hamming code. It makes it possible to define the first increase, called limits Hamming :

$1\; +\; N.\; (d-1)\; \backslash \; Leq\; d^\; \{n-k\}$

There exists an ideal configuration, corresponding if the closed balls of radius a and center the words of the code form a partition space F . If the transmission never produces more than one deterioration, then the error is corrigible. There does not exist any useless redundancy, the code is most compact possible to guarantee the unquestionable correction of an error. For such codes, the increase of the terminal the Hamming one is an equality. They are known as perfect . What gives place to the following definition:

* a Hamming code is a linear code perfect of minimal distance equalizes with three .

Parameters of the code

Determination

A code is perfect, if and only if the terminal the Hamming one is reached. This property allows the determination of the possible parameters for a Hamming code. Let us note m the value of N - K . One has the equalities then: $1\; +\; N.\; (d-1)\; =\; d^m\; \backslash \; quad\; thus\; \backslash \; quad\; N\; =\; \backslash \; frac\; \{d^m-1\}\; \{d-1\}$ The equality K = N - m and the fact that the minimal distance from a Hamming code is equal to three shows the following property:

* For any Hamming code on a finished body of cardinal D , there exists an entirety m equal to or higher than two, such as the parameters of the code are:

$\backslash \; left\; -\; m,\; 3\; \backslash \; right$ The property corresponds to a requirement. However, for any value of D and m , the continuation of the article shows that there exists a single Hamming code, except for an equivalence. The condition is thus also sufficient.

Polynomial enumerator of the weights

See also: Identity of Mac Williams

The polynomial enumerator of the weights P is the polynomial whose coefficient p _i of the students' rag procession X ⁱ is equal to the number of words of the code of the Hamming weight equal one to I . The identity of Mac Williams allows his calculation (cf detailed article) . It is equal to:

$P=\; \backslash \; frac\; 1\; \{d^m\}\; \backslash \; Bigg\; (\backslash \; Big\; (1\; +\; (d-1)\; X\; \backslash \; Big)\; ^n\; +\; (d^m-1)\; \backslash \; Big\; (1\; +\; (d-1)\; X\; \backslash \; Big)\; ^\; \{n-d^\; \{M-1\}\}\; (1\; -\; X)\; ^\; \{d^\; \{M-1\}\}\; \backslash \; Bigg)\; \backslash ;$

Example: code repetition

See also: Code of repetition

The simplest case is without question that where D is equal to two , i.e. that where the code is binary and m is also equal to two. A code of parameter is obtained.

The messages consist of a letter, for example 0 , the codes of triple repetition of the letter is 000 in the example. As the alphabet contains only two letters, at least two out of three of the letters of an element of F are similar, in conclusion any word of F is remote of a of a word of the code. Moreover, one word of F is not at a distance from with the more a but of one single word of the code, which shows that this code is perfect .

This property falls if the code contains more than two letters, indeed it exists elements of F consisted of three letters different and thus remotely from two of three words different from the code and remote of a of any word of the code. It is also noticed that the formula of the parameters, if D is different from two is not checked more.

Example: the binary case length four

See also: Hamming code (7,4)

The correct codes really used in industry are more complex than the precedents. Simplest is that of parameters.

It is a code of dimension seven , i.e. the receiver receives seven Bit S, length four i.e. once decoded, the message contains four letters and the minimal distance between each word of code is three .

The figure of right-hand side is a chart of this code. The message is the word D ₁ D ₂ D ₃ D ₄. The word of the code consists of three checksums p ₁ p ₂ p ₃, then of the four letters of the word of the message. 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 is noticed that the sum of the elements of each circle is even if and only if the element is a word of the code. Moreover, each element of F is at a distance from a of a word of the code. Consequently, this code is perfect and has a maximum capacity of correction of a error.

This example, simplest presenting a nonobvious solution , presents a capable approach to show the existence and the unicity of a solution for all the values of m in the case of a binary code.

Linear approach

Stamp parity

See also: Matrix of control

There exists a surjective linear application of F in a space of dimension N - K having for core exactly the code:

* a matrix of control of a code φ ( E ) is a matrix H of dimension N X N - K such as:

$x\; \backslash \; in\; \backslash \; varphi\; (E)\; \backslash \; Leftrightarrow\; H.^tx\; =\; 0$

This application is essential at the same time in the field of the implementation, because it allows a detection and a simple correction (cf Décodage by syndrome) and on that of the construction of a code.

There exists a direct relationship between the matrix of control and the minimal distance from the code:

* the minimal distance δ of a linear code is equal to the dimension of the smallest vectorial subspace S of F generated by elements of the canonical base and such as the restriction of the matrix of control on S is not Injective.

The minimal distance is thus higher or equal to three if, and only if, two vectors unspecified columns are free. This property makes it possible to solve the binary case for all the values of m .

Note: For the remainder of the article H indicates the matrix of parity.

Example: binary case of parameters

Stamp of control

In the binary case with for value of m four , the matrix of control is of dimension 15x4, i.e. it contains fifteen columns and four lines. To obtain a minimal distance at least equal to three, each column must be different. Indeed, a column corresponds to the syndrome of a vector of the canonical Base of F , i.e. with a message of weight a . If two columns are similar, then the message m , of weight two whose coordinates are worth zero everywhere safe for the two equal columns where coordinates are worth a , checks H ^t m = 0. Indeed, in a binary body 1 + 1 is equal to 0. There would then exist a word of the code of weights two , consequently the minimal distance cannot be equal to three . In the same way, no vector column can be null, if not, a vector of the canonical base of weight a would be element of the code.

However, there exists only fifteen vectors in the whole of arrival of the matrix of control. Except for the order, there thus exists only one single matrix of possible control for this case, corresponding following the numbers of a to fifteen into binary. If H is selected in such manner to represent a systematic code then one obtains:

The preceding analysis shows that it is necessary that a matrix of control of a code of minimal distance equalizes to three has this form. Reciprocally this form is sufficient to guarantee that the minimal distance is indeed equal to three. Indeed, no message of weight a is element of the code (a message of weight a is an element of the canonical base) because their images by H is a vector not no one. And no message of weights two (a message of weights two is the sum of two elements of the canonical base) is element of the code. Indeed, they would have even image by H because two vectors are colinéaires if and only if it are equal in the case of a binary body, but the vectors all columns are different.

Stamp generating

See also: generating Matrix

The matrix of control defines the geometry of the code completely, it is thus enough, to finish the implementation to find a matrix generating G of E in F . The associated linear application must check two conditions: it is injective, and its image is the core of H . It is thus enough to find a matrix of row 11 such as H . G = the 0 construction of the matrix G is simplified in the case or H represents a systematic code, if Id _q the matrix identity of order Q :

$G=\; \{Id\_k\; \backslash \; choose\; C\}\; \backslash \; quad\; \backslash \; quad\; H=\; (-\; C\; \backslash ;\; Id\_\; \{n-k\})\; \backslash \; Rightarrow\; H.G=\; (-\; C\; \backslash ;\; Id\_\; \{n-k\})\; \backslash ,\; \{Id\_k\; \backslash \; choose\; C\}\; =0\_\; \{n-kk\}$ By noticing that in a binary body the operations + and - are the same ones, one obtains: The code is thus composed of the message and four checksums making it possible to correct an error exactly.

Binary case

Theorem of existence

The preceding method spreads for all the Hamming codes the binary ones. The required parameters of the code are now - 1,2^m - '' m '' - 1,3. One can quote like example of use of code of this nature, that of the Minitel which chose the value seven for m . Thus, for a message length a hundred and twenties, seven checksums make it possible to correct any error on a single bit.

The matrix of control is of dimension m x2^m - 1. A requirement and sufficient so that the associated minimal distance is equal to three is that all the vectors is free two to two. It is the case if they are nonnull and all different. A binary vector space of dimension m contains 2^m exactly - 1 different nonnull vectors. Except for the order, there thus exists only one single matrix of control associated with a minimal distance equalizes to three.

It is always possible to reorder the matrix of control to give him the form of a systematic code. This form simply makes it possible to calculate the associated systematic generating matrix.

* If m is an entirety equal to or higher than two, there exists only one binary code, of parameters - 1,2^m - '' m '' - 1,3, except for an equivalence. These codes form the whole of the binary codes the Hamming one, they are perfect.

Generalized Hamming code

Two reasons push to generalize the code. A dimension equal to 2^m - 1 is not ideal, in industrial term. It is indeed more convenient to use a dimension of the form 2^m. Moreover one such code an error corrects, but if two errors occur, not only the code does not detect it, but in more he adds a third of it.

These two reasons in general bring to add a last sum of control validating the parity of the 2^m - the first 1 letters of the code. A second error is then detected, even if it cannot be corrected without new transmission. 010 & 001 &

* the Hamming code generalized , of parameter 2^m - '' m '', 3 corresponds to a Hamming code to which was added a bit of parity relating to the 2^m -1 letters of the word of the code.

Unspecified finished body

Finished body

See also: Body finished

The use of other bodies that binary is not an only theoretical concern. They are used to correct obliterations which can be important. They are used for example for the reading of the compact disks being able to correct up to 4096 consecutive obliterations.

All the finished bodies have a cardinal of the form p ^q where p is a prime number. Industry often uses the value p equalizes to two. The code is still transmitted in the form of bits, the table of addition remains unchanged, on the other hand the multiplication is not any more the same one. One obtains, for example for the body F ₈ with eight elements the following table:

| |} If linear logic remains the same one, on the other hand, the modification of the multiplication table generates an additional complexity with the encoding and decoding. The precise term is not any more nap of control but of cyclic Check redundancy or CRC.

Example: the case of parameters 7,3

Let us study on F ₈ the case where m is equal to two . It corresponds to parameters 7,3. The matrix of control is of dimension 2x9. The theorem on the relation between the minimal distance and the matrix of control shows that to build this code, it is enough to find nine vectors in a space of size two , free two to two. Preceding logic does not apply any more, two distinct vectors can be colinéaires, for example: $(001,\; 011)\; =\; 011.\; (010,\; 001)\; \backslash ;$ A matrix of dimension 2x9 is associated with a minimal distance equal to three if and only if each vector column is selected in a class of the projective Espace of F ₈² different. Each class of equivalence of projective space contains seven elements (the cardinal of the body less a ), and projective space is a partition of the space of the syndromes without the null vector, i.e. a whole of cardinal sixty three. There exist exactly nine elements in projective space, exactly the number of columns in the matrix of control. The matrix of control is thus still single, with the order close and with a Homothétie near for each vector column. One can choose for example: Same logic that previously allows to determine the generating matrix: The code is thus composed of the message and two checks redundancy cyclic making it possible to correct an error exactly.

If one counts in term of bit, three bits are necessary to code a letter. The code is thus dune length 27 bits with 6 bits of CRC. If one compares it with the Hamming code binary length 26 with 5 bits of parity, the profit is not clear. In practice, the use of vaster bodies is especially the offering object of codes of the redundancies much more important like those of Reed-Solomon.

Existence and unicity in the general case

The general case is close to the preceding example. The existence and the unicity of a Hamming code on a body of cardinal D and for the value m depends on the cardinal of the projective space of a vector space on the body F _d. The vector space S of the syndromes is of dimension m . It contains D ^m - 1 nonnull vectors, the body contains D - 1 nonnull elements, the projective space of S is thus of cardinal D ^m - 1 D - 1. It is exactly the dimension of F , the space of the codes. With an order close and with a homothety near on each vector of the canonical base of F , there thus exists only one single matrix of control. In conclusion:

* If D is a power of a prime number and m an entirety higher than two , except for an equivalence, there exists one and only one Hamming code of parameters:

$\backslash \; left\; -\; m,\; 3\; \backslash \; right$ Its construction is similar to that used for the preceding example.

Cyclic code

See also: cyclic Code

It is possible to enrich the algebraic structure of F by a structure of ring. This enrichment aims to build codes having good properties of optimality. The codes BCH as those of Reed-Solomon are the principal examples. In the binary case, a Hamming code seems a cyclic code of type BCH.

To include/understand this structure of ring, a first remark is necessary. The extension of F ₂ of cardinal 2^m has like groups multiplicative a cyclic Groupe of order 2^m - 1, one finds here dimension N of a binary code the Hamming one. Any element of the extension is thus root of the Polynôme P = X ⁿ - 1. A polynomial with coefficients in F ₂, K defines a function on the extension of cardinal 2^m. There exists one and only one polynomial R of degree strictly lower than N and having same the values on this extension as K . Indeed, Euclidean division gives the following equality if D R indicates the degree of the polynomial R :

The selected structure of ring is then that of the quotient F _d/ P . The associated codes are the ideal of this ring.

* Is m a strictly positive entirety and N an entirety defined by N = 2^m - 1. A linear code on F _d is known as cyclic if the vector space is provided with the structure of ring F _d/ P , with P = X ⁿ - 1 and that the code is an ideal of F .

To say that the code is an ideal amounts saying that it is cyclic, i.e. it checks the following property:

$\backslash \; forall\; (x\_\; \{n-1\},\; x\_\; \{N2\},\; \backslash \; cdots,\; x\_1,\; x\_0)\; \backslash \; in\; C\; \backslash \; quad\; (x\_\; \{N2\},\; x\_\; \{n-3\},\; \backslash \; cdots,\; x\_0,\; x\_\; \{n-1\})\; \backslash \; in\; C$

That is to say Φ_n a cyclotomic polynomial of order N dimension of the code, and with coefficient in F ₂. It is a polynomial of degree m (cf the cyclotomic article Polynôme), moreover:

* the ideal C generated by Φ_n is a cyclic code length K = N - m .

It has the good minimal distance:

* the ideal C generated by Φ_n has a minimal distance equalizes with three .

This cyclic code is thus a binary code the Hamming one and any binary code the Hamming one admits a cyclic representation.

The demonstrations are in the associated article.

Random links:

Claude de Mesme | Constantina Phipps, 1r marqués de Normanby | Aboul Féda | Mirko Filipović | William T. Cosgrave | Pawel Maciwoda | Devera

© 2007-2008 speedlook.com; article text available under the terms of GFDL, from fr.wikipedia.org