Hamming codes.

Hamming codes.

The most common among the linear group codes using errors received HAMMING CODE. It has the following structure of the generating matrix: (n, k). The Hamming code has the structure: (2in - 1, 2m-1-m), m = 3,4 ... If m = 3, then (7,4).

If we construct the matrix H for this code, then it will look like this:

H = || 1101,100; 1011 010; 0111 001 ||. Number of lines = m. Each digit forms an m-bit binary number. H = || 6537421 ||. Hamming code is so popular that standard chips are released, so when a computer network is organized, each computer is equipped with an encoder and a decoder. The user works with informational words, but before leaving the network communication channel, the word passes through the encoder chip and enters the decoder in the received computer.

SYSTEMIC AND NON-SYSTEMATIC.

The user works with informational words, but before leaving the network communication channel, the word passes through the encoder chip and enters the decoder in the received computer.

There are systematic and non-systematic linear group codes, including the Hamming code. In systematic codes, the information word occupies the first k bits, and the test nk. In non-systematic codes, the check bits are embedded in certain positions of the code word. In the systematic Hamming code, the type of syndrome with the number of erroneous discharge are connected through a table. In a non-systematic Hamming code, the type of syndrome is represented by a binary number, which is the number of the erroneous discharge.

Consider an example of constructing a non-systematic code - build a Hamming code for n = 17 .

1) The number of check digits is determined, in this code r ≥] log ₂ (n + 1) [is the nearest integer from above. r = 5 for our case.

Check equations: a ₁₆ + a ₁₇ = 0 (we write a, those where there is one in the table), a ₈ + ... + a ₁₅ = 0 ..., etc. (5 total). It is necessary that each digit entered. a ₁ , a ₂ , a ₄ , a ₈ , a ₁₆ - there is a unit in the columns once in a while.

Suppose a ₁₂ refused! We look at the column (01100). To find the error, you need to look at the value of the sum of the rows.

Encoding and decoding in the communication channel.

The information word before entering the communication channel is converted to a code word in the encoder, which must automatically assign check bits to this word. This can be done in 2 ways:

by type G is determined by the sum of which lines is the information part of the future word. For example, I = 0110, it is clear that for the matrix this word is the sum of the 2nd and 3rd lines.

To obtain the code word C (I), it suffices to add the 2nd and 3rd row of the matrix G from the last example. 2) An multiplication operation can be performed at the encoder. Any codeword C = I * G, C = || 0110 || * || G || = || 0110110 ||.

When building a decoder, we can use 2m methods: 1) the received word is analyzed using syndromes. However, if the length of the code is very large, then the number of equations becomes large. 2) is to use the so-called test matrix. It is denoted by H = || Dn-1, k In-k ||, I is the identity matrix, D is the matrix for which each row is a check column of the matrix G. Example: G = || 100 110; 010 011; 001 101 ||, the row becomes a column, H = || 101 100; 110 010; 011 001 ||. If the word is coded, then C * H ^T = 0. Assuming that the matrix I is composed of code words, the product of each of them by HT is 0, we can write G * H ^T = 0 - is an expression that can uniquely be used to construct H and vice versa.