🚨 🏪 🐾 Correction of multiple errors when encoding messages 🦅 👩🏾‍🚒 🎩

In information systems, the exchange of messages in communication or computing networks is accompanied by disturbing influences of the environment or an intruder, which leads to the appearance of signal distortions and to errors in symbols during digital transmission. The fight against this phenomenon is carried out using correction codes. Earlier I described the Hamming code, and showed how to fix a single error in a code word. Naturally, the question arose about situations with a large number of errors. Today we will consider the case of two errors in a codeword (multiple error). On the one hand, everything in theory is more or less simple and understandable, but on the other, it is not at all obvious. The presentation of the material is based on the works of E. Berlekamp.

Theoretical provisions

The idea of using organized redundancy in messages led R. Hamming to the construction of the correcting code described here . The linear correcting (n, k) -code is characterized by a check (m × n) matrix H. The requirements for the matrix are simple: the number of rows coincides with the number of check symbols, its columns must be different from zero, and all are different. Moreover, the column values describe the position numbers occupied in the codeword by word characters that are elements of the final field.

Often, the decoder uses a syndrome computation computed for that word to determine whether a transmitted word is in error. The syndrome is equal to the sum of the columns of this matrix multiplied by the components of the error vector. If H contains m lines and the code allows you to correct single errors, then the length of the block (codeword) does not exceed

n \leq 2^{m} - 1

$n≤2^m-1$ ... Also important is the feasibility of the required distance of the code words from each other.

Hamming codes reach this limit. Each position of the Hamming code word can be numbered with a binary vector that coincides with the corresponding column of the matrix H. In this case, the syndrome will coincide directly with the position number where the error occurred (if there is only one error) or with the binary sum of numbers (if there are several errors).

Vector numbering is a very fruitful idea. Further, we will assume

n \leq 2^{m} - 1

$n≤2^m-1$ and that the i-th position of the word is numbered i.

The binary numbering, (i.e. such representation) is called the position locator. Suppose you want to fix all double and single errors. Apparently, this will require a large code redundancy, i.e. matrix H must have more rows (twice the number). Therefore, we will form a matrix H with 2m rows and with

n \leq 2^{m} - 1

$n≤2^m-1$ columns, and it is wise to choose different columns. For the first m rows we will take the previous matrix of the Hamming code. These are the basis word vectors of the word space.

Example 1

Let m = 5 and n = 31. It would be desirable to obtain an (n, k) -code that corrects double errors, with a parity check matrix H in the form:

For the functions fj (ξ) indicated in the matrix, it is desirable to have a function that maps set of 5-dimensional vectors into itself. The last 5 rows of the matrix will define the Hamming code if and only if the function f is a bijection (permutation).

If the first 5 lines and the last 5 lines separately allow you to correct single errors, then perhaps together they will allow you to correct two errors.

We must learn to add, subtract, multiply and divide binary 5-dimensional vectors, represent them by polynomials of degree at most 4, in order to find the required function fj (ξ).

Example 2

00000 ← → 0

00010 ← → 1

00011 ← → x

...

11011 \leftarrow\to х^{4} + х^{3} + х + 1

$11011 ←→ ^4 +^3++1$

The sum and difference of such polynomials corresponds to the sum and difference of vectors:

0 ± 0 = 0, 0 ± 1 = 1, 1 ± 0 = 1, 1 ± 1 = 0, the signs of ± have the same meaning in the binary case. Not so with multiplication, the exponent of the multiplication result can exceed 4.

Example 3

(х^{3} + х + 1) х^{4} + х^{3} + х + 1) = х^{7} + х^{6} + х^{5} + 3 х^{4} + 2 х^{3} + х^{2} + 2 х + 1 =

$(^3++1)^4+^3++1)=^7+^6+^5+3^4+2^3+^2+2+1=$

= х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1

$=^7+^6+^5+^4+^2+1$ ...

A method of lowering degrees greater than 4

is needed. It is called (reduction) the construction of residues modulo an irreducible polynomial M (x) of degree 5; the method consists in the transition from the polynomials of the products to their remainders after division by

M (x) = x^{5} + x^{2} + 1

$M(x)=x^5+x^2 + 1$

So that

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 = (х^{2} + х + 1) (х^{5} + х^{2} + 1) + х^{3} + х^{2} + х

$^7+^6+^5+^4+^2+1 =(^2+ + 1)(^5 +^2 +1) +^3 +^2 +$ or

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 \equiv (х^{3} + х^{2} + x) m o d (х^{5} + х^{2} + 1) .

$^7+^6+^5+^4+^2+1 ≡(^3+^2 + x)mod(^5 +^2 +1).$

The ≡ symbol reads "comparable to".

In general form A (x) ≡a (x) mod M (x)

If and only if there exists a polynomial C (x) such that

A (x) = M (x) C (x) + a (x) the coefficients of the polynomials are reduced modulo two:

A (x) ≡ a (x) mod (2, M (x)).

Important properties of comparisons

If a (x) ≡A (x) mod M (x) and b (x) ≡ B (x) mod M (x), then

a (x) ± b (x) ≡ A (x) ± B (x ) mod M (x) and

(x) b (x) ≡ (x) B (x) mod M (x).

Moreover, if the degrees of the polynomials a (x) and A (x) are less than the degree of M (x), then

it follows from the formula a (x) ≡ A (x) mod (2, M (x)) that a (x) = A (x).

There are 2 different residue classes in degree degM (x) - that is, as many as there are different polynomials of degree less than m, i.e. how many different division residues can be. Division is even more difficult.

Division algorithm

For numbers.

For given a and M, there are uniquely defined numbers q and A, such that a = qM + A, 0 ≤ A ≤ M,

For polynomials with coefficients from a given field.

For given a (x) and M (x), there are uniquely defined polynomials q (x) and A (x) such that a (x) = q (x) M (x) + A (x), degA (x ) <deg M (x).

The possibility of dividing polynomials is provided by the Euclidean algorithm.

For numbers, an example of an extended GCD is described here .

For a given a and b, there are numbers A and B such that aA + bB = (a, b), where (a, b) is the GCD of the numbers a and b.

For polynomials with coefficients from a given field.

For given a (x) and b (x), there exist polynomials A (x) and B (x) such that

a (x) A (x) + b (x) B (x) = (a (x), b (x)),

where (a (x), b (x)) is the normalized common divisor of a (x) and b (x) of greatest degree.

If a (x) and M (x) have a common divisor d (x) ≠ 1, then division by a (x) mod M (x) is not always possible.

It is obvious that division by a (x) is equivalent to multiplication by A (x).

Since if (a (x), b (x)) = 1 = GCD, then according to Euclid's algorithm, there are A (x) and B (x) such that a (x) A (x) + b (x) B (x) = 1, so that a (x) A (x) ≡ 1mod b (x). Checking that a binary polynomial is irreducible over the field GF (

2^{5}

$2^5$ ), is performed by direct division by all possible divisors with degrees less than deg M (x).

Example 4 .

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ divided by x and by (x + 1)

by linear divisors. The division result is not zero. Divide by square divisors

х^{2}, х^{2} + х = х (х + 1), х^{2} + 1, х^{2} + 2 х + 1 = (х + 1)^{2}, х^{2} + х + 1.

$^2 , ^2 +=( +1),^2 +1, ^2 +2 +1= ( +1)^2, ^2 + + 1.$ ... They give out non-zero balances. Divisors of degree ≥ 3 do not exist, since their product gives degree ≥ 6.

Thus, polynomials can be added, subtracted, multiplied, and divided modulo

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ ...

We turn to the search for a function for the parity check matrix H defining a double error correction code with a block length of 31 and a rate of 21/31; 31-21 = 10 = 2t - check symbols = 10. Such a function must have as its roots the numbers of erroneous positions in the code word, i.e. when position numbers are substituted into this function, it turns it to zero.

Search function

Suppose that β1 and β2 are the numbers of the distorted characters (positions) of the word. Using the binary notation of the numbers β1 and β2 , these numbers can be represented as residue classes modulo M (x) i.e. establish the correspondence βi → β ⁽ⁱ⁾ (x) - binary polynomials of degree <5.

The first 5 test conditions determine β1 + β2 ; the second set of test equations must determine f (β1) + f (β2) .

The decoder must determine β1 and β2 according to the given system:

What should be the function f (x) ?

The simplest function is multiplication by a constant f (β) ≡ αβ () modM (x) .

But then ξ2 = αξ1 , i.e. the equations of the system are dependent. The new five test conditions will not give the decoder anything new.

Similarly, the function f (β) = β + α does not change the situation, since ξ2 = ξ1 .

Trying power functions: first take

f (β) = β^{2}

$f(β) = β^2$ ... Moreover,

these equations are also dependent, since

ξ 1^{2} = (β 1 + β 2)^{2} = β 1^{2} + 2 β 1 β 2 + β 2^{2} = β 1^{2} + β 2^{2} = ξ 2

$ξ1^2 =(β1 + β2)^2=β1^2 + 2β1β2 + β2^2 = β1^2 + β2^2 =ξ2$

So the second equation is the square of the first.

Trying

f (β) = β^{3}

$f(β) = β^3$ ... Change decoder equation form:

Location

ξ 2 = β 1^{3} + β 2^{3} = (β 1 + β 2) (β 1^{2} - β 1 β 2 + β 2^{2}) = ξ 1 (β 1 β 2 - ξ 1^{2}) .

$ξ2 =β1^3 + β2^3=(β1 + β2)(β1^2 -β1β2+ β2^2)=ξ1(β1β2-ξ1^2).$

So for ξ1 ≠ 0 we have

So, β1 and β2 satisfy the equation

Thus, if exactly two errors occurred, then their locators satisfy this equation.

Since this equation has exactly 2 roots in the field of binary polynomials modulo M (x) , the decoder can always find the two required locators.

If only one error occurs, then β1 = ξ1 and $β1^2 = ξ2$ ... Therefore, in this case, the only error satisfies the equation β + ξ1 = 0 or 1+ ξ1β ^-1 = 0 .

Finally, the decoder always performs decoding, if no errors occurred, in this case ξ1 + ξ2 = 0 .

It is more convenient (in practice) to operate not directly with a polynomial whose roots are error locators, but with a polynomial whose roots are mutual to the locators; those. are multiplicative reciprocals to them.

It is clear that with no more than two errors, the decoder can determine the error numbers. If three or more symbols are distorted, then a decoding error or decoding failure will occur.

So the function

f (x) = x^{3}

$f(x) = x^3$ suitable for constructing the lower five rows of the check matrix H of a binary code with a codeword length of 31 and 10 check symbols, correcting all double errors.

The first five checks specify the sum of error numbers (S1); the second five checks are the sum of the error number cubes (S3).

The decoding procedure consists of three main steps:

each received codeword is checked and S1 and S3 are calculated;
find the error locator polynomial in σ (z);
the mutual values for the roots σ (z) are calculated and the symbols in the corresponding positions of the resulting word are changed.

Correction of multiple errors when encoding messages

Theoretical provisions

Important properties of comparisons

Division algorithm

Search function

More articles: