Cyclic codes.

Cyclic codes.

CC is a kind of linearly group code rel. to systematic code. It is convenient to set the cyclic binary code vector in the form of a polynomial (and not a combination of 0.1). F (x) = an-1xn-1 (+) an-2an-2 (+) ... (+) a1x (+) a0 (*)

x - the base of the number system in which the code is built. ai, where i = 0, (n-1) are the digits of this number system. For example: x = 3, ai = 0,1,2. We will consider. X = 2, ai = 0.1.

EXAMPLE: to represent a numerical sequence in the form of a polynomial F (x) = 1x3 (+) 0x2 (+) 0x (+) 1, F (x) = x3 (+) 1. The representation of binary vectors in the form of a polynomial allows you to move from actions on vectors to action on polynomials. In this case, the addition of vectors involves the addition of polynomials, which is carried out as a sum modulo x of coefficients of the same name. The multiplication of vectors corresponds to the multiplication by the multiplication rule of polynomials, the division of vectors is the division of polynomials, and the operation “-“ is transformed into the operation “+” modulo. F1 (x) = x3 + x2 + 1, F2 (x) = x + 1.

1) F1 (x) + F2 (x) = x3 + x2 + x (in the binary system 1 + 1 = 0), 2) F1 (x) * F2 (x) = (x3 + x2 + 1) (x + 1) = x3 + x3 + x3 + x2 + x + 1 = x4 + x2 + x + 1,

3) F1 (x) / F2 (x) = x2.

The main property of the cyclic code

is: if some vector belongs

cyclic code then any other vector

derived from given by an arbitrary number of cyclic shifts also belongs

cyclic code. The idea of ​​building a cyclic code is based on the concept of an irreducible polynomial, which is divided only into itself and into a unit, i.e. cannot be decomposed into simpler polynomials. The irreducible polynomial itself is a divisor of the polynomial xn (+) 1 without remainder. Irreducible polynomials in the theory of cyclic codes play the role of generators of polynomials or polynomials. These polynomials are tabulated. P (x) = x + 1; P (x2) = x2 + x + 1; P (x3) = x3 + x + 1; P (x4) = x3 + x2 + 1. The vector of the cyclic code for a given information word is constructed as follows:

Let the information word Q (x) and the polynomial P (xr) be given. Then, when the word F (x) = Q (x) * xr + Res [Q (x) xr / P (xr)], Q (x) is an information word that needs to be encoded. P (x) is the generator polynomial.

Example (CODING IN CYCLIC CODE): the number to be encoded is 0111. P (x3) = x3 + x2 + 1, Q (x) = x2 + x + 1, r = 3, Q (x) * xr = x5 + x4 + x3, P (x) = x5 + x4 + x3 + R, divide by the column Q (x) * xr / P (xr) = x2 + 1, the remainder is R = 1.

ANSWER: F (x) = x5 + x4 + x3 + 1 => 0111 001.

A cyclic code, like any systematic code, a code can be specified in the form of a generator matrix. The structure of this matrix is:

G (n, k) = || ITk xk, Pk x (nk) ||, P is the check digit matrix.

EXAMPLE: BUILD A MATRIX G (7,4) CC

Q1 (x) = 1, Q2 (x) = x, Q3 (x) = x2, Q4 (x) = x3.

P (x3) = x3 + x2 + 1. To find the values, which then enter in the right side of the matrix, it is necessary to divide the column and find the residues, which then, in accordance with the present powers x, convert to binary form and write to the right side. Res [Q (x) x3 / P (x3)] -? It should be divided 4 times. Divide by P, respectively x3, then x4, x5, x6.

Detection and correction of errors in the CC.

Any code word of a CC is divided into an irreducible polynomial without a remainder; therefore, a sign of the presence of an error in a received word is a nonzero remainder from dividing the received word into an irreducible polynomial. However, the presence of a nonzero remainder only indicates the existence of an error, i.e. errors are detected, but it is impossible to judge the location of the error by the type of the residue. For correction of t and less errors, the following algorithm is used: 1) the received word is divided into an irreducible polynomial. 2) the weight of the residue is calculated. 3) If the weight does not exceed the correcting ability of the code (t), then the remainder is added to the dividend, and the resulting amount is the correct word. If the weight of the residue is greater than t, then the received word is cyclically shifted to the left by one digit, divided by P (x ^r ), and the weight of the residue is analyzed. If the weight of the remainder is not greater than t, then the remainder is added to the dividend. The resulting amount is cyclically shifted to the right by one digit. The result of this operation is the corrected word. If the weight of the remainder is greater than t, then the dividend shifts left again. EXAMPLE: CK is defined by the generator matrix G =

P (x ³ ) = x ³ + x ² +1, t = 1 , d _min = 3

Code word: A = 0001101,

misspelled word: A '= 0011101 = x ⁴ + x ³ + x ² +1,

divide by column A '/ P = x,

the remainder Res = x ² + x + 1, ω (Res) = 3> t (no need to correct). Now we shift

A ' ^{1 y} (above arrow) = 0111010, and again also we divide Res = x + 1 (ω = 2)> t, again it means not that - we shift again to the left and so on until Res = 1 (ω = 1 = t). We fix the last character A ' ^{3 y} (ß) on the reverse and move, aa 3. This will be A = 0001101.

Undetectable cyclic error code.

We represent the vector of single errors in the form of a unit matrix with a side sl. diag. To such a matrix we add to the right a matrix obtained by dividing each vector of errors by the generating polynomial. The matrix to be added is called the remainder matrix and has r columns, where r is the degree of the generating polynomial. As a result, we obtain the matrix M ^' , which we will analyze. Single error matrix:

M '= || I _{n * n ^T} * (I ^T _{r * r} / R) ||

It is not necessary to know the code word, it is enough to know the error string (the error word).

V = C + E.

To study the properties of the codes, we represent the received word as the sum of the code word C and the error word E. It is known that when C is divided by the generating polynomial, the remainder is always 0. So it is. to study the properties of the code, it suffices to study the remainder of dividing the vector E by the generating polynomial. It is on this basis that the matrix M 'is constructed. As can be seen from the residual matrix in M ​​', all residues are nonzero and are different, that single errors are corrected 100%. In addition, 2-fold errors are detected, which can be found out by constructing the matrix M ", where in the k-th line there will be 2 errors each. In this case, the submatrix of residuals will not contain 0th rows, but among them there will be repeated lines. Similarly for any cyclic code. It should be said that the actual discovery. code capacity is greater than guaranteed. So, for the considered code, guaranteed detecting ability = 2, out of a total of 35 3-fold errors, only 7 are detected, out of 4-fold errors - also 7, a single 7-fold error is not detected. In total, only 15 erroneous combinations are not detected.

The implementation of coding and decoding in the Central Committee.

Consider the basic structures of encoders and decoders of cyclic codes. Circuits based on shift registers are called digital filters. The basis is a cyclic shift. Most often this is a D-trigger. The n-bit shift register is used to cycle the polynomial x ⁿ -1. Each time after the shift x * V (x) is calculated (mod (x ⁿ -1)),

V (x) is some initial vector that is placed in this register. The structure defines an expression modulo ^xn -1, where n is the number of registers. x - multiplication, in logic - shift. Multiplication by x corresponds to a single cyclic shift of V (x) to the right, with the most significant digits of the word to the right.

Generalized scheme of the dividing device:

This scheme divides the input polynomial into the generator polynomial g (x). In the initial

condition all triggers are reset and first

r shifts at the output of the last trigger 0, i.e.

feedback is open. Polynomial

d (x) is pushed into the circuit starting with

higher coefficients. After n shifts,

where n is the degree of the polynomial d (x) at the output of the circuit will be the quotient, and in the register itself the remainder of d (x) divided by g (x) will be written.

g (x) = g _r x ^r +… + g1x + g0.

Example: build a division scheme into a polynomial g (x) = x ⁶ + x ⁵ + x ⁴ + x ³ +1

d (x) = 11000001, d (x) (a) = 10000011.

Divide d (x) = x ⁷ + x ⁶ +1

The result is the remainder 110011 (R = x ⁵ + x ⁴ + x + 1).