Cyclic encoding process. Cyclic codes Percentage of detected multiple errors

It is a subclass of linear codes that have the property that cyclic permutation of symbols in a coded block yields another possible coded block of the same code. Cyclic codes are based on the application of ideas from the algebraic theory of Galois fields1.

Many of the most important anti-jamming codes of communication systems, -

in particular cyclic, based on structures of finite arithmetic

Galois fields. By the field is called the set of elements that have a finite field

the names of the operations are enclosed in quotation marks because they are not always generally accepted arithmetic operations. The field always contains a zero element (0), or zero, and a one element (1), or one. If the number q the elements of the field are limited, then the field is called finite field, or finite Galois field, and denoted GF (q) y where q - field order. The smallest Galois field is the two-element iole GF ( 2), consisting of only two elements 1 and 0. In order to

1 Evariste Galois (1811 - 1832) - French mathematician, laid the foundations of modern algebra.

performing operations on elements GF ( 2) did not lead to going beyond this field, they are carried out modulo 2 (in general, this is determined by the order of the field for simple Galois fields).

The field has a number of specific mathematical properties. For field elements, addition and multiplication operations are defined, and the results of these operations must belong to the same set.

For addition and multiplication operations, the usual mathematical associativity rules are followed - a + (B + c) = (a + B)+ c, commutability - a + b = b + a and a b = b a and distribution - a (B+ s) = a b + a with.

For each element of the field a inverse addition must exist (-a) and if a non-zero, inverse element of multiplication (th ').

The field must contain additive unit - element 0 such that a + 0 = a for any field element a.

The field must contain multiplicative unit - element 1 such that aL = a for any field element a.

For example, there are fields of real numbers, rational numbers, complex numbers. These fields contain an infinite number of items.

In fact, all sets formed by cyclic permutation of a codeword are also codewords. So, for example, cyclic permutations of combination 1000101 will also be code combinations 0001011, 0010110, 0101100, etc. This property makes it possible to greatly simplify the encoder and decoder, especially when detecting errors and correcting a single error. Attention to cyclic codes is due to the fact that their inherent high correcting properties are realized on the basis of relatively simple algebraic methods. At the same time, for decoding an arbitrary linear block code, tabular methods are often used, which require a large amount of decoder memory.

A cyclic code is called a linear block (n, k) - code that is cyclical, i.e. a left shift of any allowed codeword by one step also gives an allowed codeword belonging to the same code, and in which the set of codewords is represented by a set of polynomials of degree (NS- 1) or less divisible by the generating polynomial g (x) degree r = n-k y binomial NS n +

In a cyclic code, codewords are represented by polynomials (polynomials)

where NS - code length; A i - Galois field coefficients (code combination values).

For example, for the code combination 101101, the polynomial notation has the form

Examples of cyclic codes are even-check codes, repetition codes, Hamming codes, PC codes, and turbo codes.

Hamming Code... Error correction capabilities in Hamming code are associated with minimum coding distance d 0. All multiplicity errors are fixed q= cnt (d 0- l) / 2 (here cnt means "integer part") and multiplicity errors are detected d 0 - 1. So, when checking for oddness d Q = 2 and single errors are detected. In the Hamming code d 0 = 3. In addition to the information digits, a L = log 2 Q of redundant control bits, where Q - the number of information bits. Parameter L rounded to the nearest higher integer value. The L-bit control code is the inverted result of bitwise addition (addition modulo 2) of the numbers of those information bits, the values ​​of which are equal to one.

Example 7.7

Suppose we have the main code 100110, i.e. Q = 6. Let's define an additional code.

Solution

We find that L= 3 and complementary code is

where P is the symbol of the bitwise addition operation, and after inverting we have 000. Now the additional code will be transmitted with the main code. At the receiver, the additional code is calculated again and compared with the transmitted one. The comparison code is fixed, and if it is different from zero, then its value is the number of the erroneously received bit of the main code. So, if the code 100010 is received, then the calculated additional code is equal to the inversion from 010S10 = 100, i.e. 011, which means an error in the 3rd digit.

The generalization of Hamming codes are cyclic BCH codes, which allow correcting multiple errors in the received codeword.

Reed - Solomon codes are based on Galois fields, or trailing zeros. Arithmetic operations are addition, subtraction, multiplication, division, etc. over elements of a trailing zero give a result that is also an element of that zero. A Reed-Solomon encoder or decoder must perform these operations. All operations to implement the code require special hardware or specialized software.

Turbo codes. Redundant codes can be used both independently and in the form of some combination of several codes, when the sets of symbols of one redundant code are considered as elementary information symbols of another redundant code. Such a union began to be called cascading code. A huge advantage of concatenated codes is that their use makes it possible to simplify the encoder and especially the decoder in comparison with similar devices of non-concatenated codes of the same length and redundancy. Concatenated coding led to the creation of turbo codes. Turbocode is called a parallel signal structure consisting of two or more systematic codes. The basic principle of their construction is the use of several component coders working in parallel. As a component one can use both block and convolutional codes, Hamming codes, PC-code, BCH, etc. The use of perforation (puncturing) allows increasing the relative speed of the turbo code, adapting its correcting ability to the statistical characteristics of the communication channel. The principle of turbo code formation is as follows: input signal NS, consisting of TO bit, fed in parallel to N interleavers. Each of the latter is a device that permutes elements in a block of TO bits in pseudo-random order. The output signal from the interleavers - the reordered symbols - is fed to the corresponding elementary encoders. Binary sequences x p i= 1,2, ..., JV, at the output of the encoder are check symbols, which together with the information bits make up a single codeword. The use of the interleaver makes it possible to prevent the appearance of sequences of correlated errors when decoding turbo codes, which is important when using the recurrent decoding method, which is traditional in processing. Depending on the choice of the component code, the turbo codes are divided into convolutional turbo codes and block product codes.

6. Correction of errors using cyclic codes

In Section 3, it was shown that to decode a correctly received codeword, i.e., to find the corresponding information word, it is sufficient to divide the polynomial corresponding to the received codeword by the generating polynomial of the code. However, if errors occurred during the transmission, then during the decoding process, these errors must be corrected.

Since cyclic codes are linear, the error detection and correction process is associated with finding the received vector syndrome. Recall that the vector syndrome u is calculated as the product of a vector by the transposed code parity matrix, i.e. s u= uH T... In the case of a cyclic code, the syndrome is equal to the remainder of the division of the corresponding polynomial by the generating polynomial of the code if the parity-check matrix is ​​constructed in a certain way. In other words, if g(x) is the generating polynomial of the code, then the vector syndrome u equal to the remainder of the division u(x) on g(x). If there were no errors, then the remainder, and hence the syndrome of the accepted vector, is equal to 0.

In order to correct errors, we need to build a table in which one column contains all possible error vectors that this code can correct, and the second column contains the corresponding syndromes. The error correction common to all line codes will be as follows:

1. For the accepted word, we find the syndrome of the polynomial corresponding to the accepted word.

2. If the syndrome is not equal to 0, then by the resulting syndrome (the remainder of the division) we find in the table the corresponding error vector.

3. We correct the received word by adding modulo 2 with the calculated error vector.

The first step, which is performed by multiplying the received word by the transposed parity check matrix, is very simple for cyclic codes if the matrix H is the check matrix of the systematic code. In this case, j-th row of the transposed matrix HT corresponds to the remainder of the division of the polynomial x n -1- j by the generating polynomial of the code, and the syndrome is equal to the remainder of the division of the polynomial corresponding to the received word by the generating polynomial of the code.

Example: Consider the cyclic (7,1) -code generated by the polynomial g(x) = x 6 + x 5 + x 4 + x 3 + x 2 + x+1. The code consists of two words 0000000 and 1111111 and corrects all combinations of 3 or fewer errors. The generators are all Boolean vectors of length 7 and weights 0, 1, 2, and 3. The check matrix is ​​constructed from the quotient ( x+1) from division x 7 +1 on x 6 + x 5 + x 4 + x 3 + x 2 + x+1 and has the form

Let the word 11101101 be accepted, which corresponds to the polynomial x 6 + x 5 + x 4 + x 2 + 1. The remainder of this polynomial division by the generating polynomial of the code is x 3 + x... By direct verification, one can make sure that when multiplying the vector u= 1110101 to the transposed matrix HT, as well as when multiplying the vector 0001010 by HT the vector 0001010 is obtained, which corresponds to the polynomial x 3 + x... The vector corresponding to the polynomial x 3 + x, has weight 2, i.e., is a coset generator. Adding the received vector 11101101 with the generator 0001010, we get the code word 1111111, that is, the error will be corrected.

For linear codes, the number of different syndromes is 2 n - k, where n-k- the number of check symbols. Therefore, for codes with a large codeword length, i.e., with a sufficiently large number of check symbols, the syndrome table is very large, and it will take a lot of time to search for an error vector. To reduce the number of rows in this table for cyclic codes, you can use the strict mathematical structure of such codes. The main theorem is Megitt's theorem, which establishes a connection between cyclic shifts of a vector and their remainders after division by the generating polynomial of the code.

Theorem 6.1... (Meggit). Let be s- vector syndrome u length n... Cyclic vector shift syndrome u coincides with the syndrome of the vector corresponding to the polynomial xs(x).

Example: Consider the (7,4) Hamming code, which is a cyclic code generated by the polynomial g(x) = x 3 + x+ 1.binary vector 1011000 is a codeword since the corresponding polynomial x 6 + x 4 + x 3 is divided into g(x). Suppose that when transmitting this codeword, one error occurred in the bit corresponding to x 4, and the word is accepted u= 1001000. Syndrome s of the received vector is 110, which corresponds to the polynomial x 2 + x.

Consider the cyclical shift 0010001 of the vector u... It corresponds to the polynomial x 4 + 1. It can be verified directly that the remainder of the division of the polynomial x 4 + 1 per polynomial x 3 + x+ 1 equals x 2 + x+ 1, that is, the syndrome of the vector 0010001 is equal to 111. The remainder of the division of the polynomial xs(x) = x 3 + x 2 on x 3 + x+ 1 is also equal to x 2 + x + 1.

Using Megitta's theorem, only syndromes of error vectors corresponding to errors in the most significant bit can be stored in the syndrome table. The error correction procedure contains the following steps:

1. Find the syndrome of the accepted vector by dividing the corresponding polynomial by the generating polynomial of the code. If the remainder of the division contained in the register is 0, then there were no errors, and the quotient of the division is the required information word. Otherwise, compare the remainder of the division with all the syndromes contained in the table.

2. If the remainder coincides with one of the syndromes in the table, then we add the corresponding error vector to the received word, divide the resulting word by the generating polynomial of the code; the quotient of division is the required information word. If the remainder xs(x) does not match any of the table syndromes, we multiply s(x) on x and divide the polynomial xs(x) to the generating polynomial of the code.

3. We carry out Step 2 until after p the remainder of the steps will not coincide with one of the table syndromes. After that, we cyclically shift the corresponding error vector p once, we add the resulting vector to the received word, divide the resulting word by the generating polynomial of the code; the quotient of division is the required information word.

Example: Consider the cyclic (7,4) Hamming code generated by the polynomial g(x) = x 3 + x+ 1. The corresponding table for decoding with syndromes is as follows.

and suppose that one error has occurred in the transmitted codeword 0001011, i.e., for example, the word 0101011 is received, which corresponds to the polynomial x 5 + x 3 + x+ 1. Remainder of division of a polynomial x 5 + x 3 + x+ 1 per generator polynomial of the code g(x) = x 3 + x+ 1 equals x 2 + x+ 1, that is, the accepted vector syndrome is different from 0 and is equal to 111. There is no such syndrome in the table, and therefore, there are no errors in the most significant bit. We multiply the polynomial x 2 + x+ 1 corresponding to syndrome 111, on x and divide the resulting polynomial x 3 + x 2 + x on g(x). Remainder of a polynomial division x 3 + x 2 + x on x 3 + x+ 1 equals x 2 + 1, that is, the 101 syndrome corresponding to the remainder is the same as the syndrome in the abbreviated decoding table. Accordingly, the generatrix 100000 of the coset is shifted one bit to the left, and the resulting vector 0100000 is added to the received vector 0101011. As a result, word 0001011 is obtained, which is the transmitted codeword, that is, the error will be corrected.

You can simplify this decoder. In particular, when the received word is cyclically shifted, many of the correctable error patterns may appear multiple times. If you remove one of these syndromes, then with the corresponding cyclic shift, the error will still be found. Consequently, for each such pair, it is sufficient to memorize only one syndrome.

The simplest cyclic code with allows detecting single errors and errors of odd multiplicity. The generating polynomial of this code has the form Among the irreducible polynomials included in the expansion, this polynomial is the polynomial of the least degree. Thus, for any number of information bits, only one check bit is needed. The character value of this bit ensures the parity of the number of ones in any permitted code combination. The resulting cyclic parity-check code is capable of detecting not only single errors in individual bits, but also errors in any odd number of bits.

Example. Construct a cyclic code for Since the generating polynomial is a polynomial of the 1st degree, the number of check bits Therefore, To construct a cyclic code, we construct a generating matrix

To construct an additional matrix, we find the remainders of dividing the last row of the unit transpose matrix, padded with zeros, by the selected polynomial:

Thus, the additional matrix C, k has the form

Now we build the generating matrix

The lines of this matrix are the first three code combinations. The rest of the allowed combinations can be obtained by summing modulo two of all possible combinations of rows of the matrix.The resulting destroyed code combinations are given in Table. 39.

Table 39 (see scan)

It is of known interest to consider the following simplest code from the second-degree irreducible polynomial

The general view of the generating matrix of the cyclic code formed by the polynomial differs in the structure of the additional matrix having two columns.

It is easy to verify that, when divided by a given generator, the polynomials expressing the rows

the identity matrix (to find an additional matrix, three types of residuals are formed: 11, 01 and 10. Therefore, the weight of each combination of the obtained -code will be at least two. The minimum code distance between any two combinations is also two. But the simplest code with one parity check, formed by a binomial of the first degree However, the correcting ability of both codes is not the same.The considered code has a large redundancy and allows detecting not only any errors of odd multiplicity, but also any paired adjacent errors, as well as all errors separated by one undistorted element.

The class of linear codes, which are called cshaic codes... The name comes from the main property of these codes: if some code combination belongs to a cyclic code, then the combination obtained by cyclic permutation of the original combination (cyclic shift) also belongs to this code:

The second property of all allowed combinations of cyclic codes is their divisibility without a remainder by some chosen polynomial, called the generating one.

These properties are used in the construction of codes for encoding and decoding devices, as well as in the detection and correction of errors.

Cyclic codes are a whole family of error-correcting codes (one of the varieties of which are Hamming codes), which provides great flexibility in terms of the possibility of implementing codes with the necessary ability to detect and correct errors that occur when transmitting code combinations over a communication channel. Cyclic code refers to systematic block (l, &) - codes in which To the first digits are a combination of the primary code, and the subsequent (l - To) digits are checking.

The construction of cyclic codes is based on the operation of dividing the transmitted codeword by the generating irreducible polynomial of degree G. The remainder of the division is used to form check digits. In this case, the division operation is preceded by the multiplication operation, which performs a left shift of the ^ -bit information code combination by G discharges.

When decoding the received n-bit codeword, division is again performed by the generating (generating, generating) polynomial.

The error syndrome in these codes is the presence of the remainder of the division of the received codeword by the generating polynomial. If the syndrome is zero, then it is considered that there are no errors. Otherwise, using the resulting syndrome, you can determine the bit number of the received codeword, in which the error occurred, and correct it.

However, the possibility of multiple errors in the code combinations is not excluded, which can lead to false corrections and (or) non-detection of errors when transforming one allowed combination into another.

Let the total number of bits in the block be equal to i, of which useful information is carried T bits, then in case of an error it is possible to correct j bits. Dependency 5 on NS and T for codes can be determined from table. 2.6.

Table 2.6

Dependence of the total number of digits of combinations on the number of informational and corrected digits

Increasing the difference (n - t), you can not only increase the number of correctable bits s, but also detect multiple errors. The percentages of detected multiple errors are shown in Table. 2.7.

Table 2.7

Percentage of Multiple Errors Detected

It is convenient to describe cyclic codes and their construction using polynomials (or polynomials). The combination is written in the form of a polynomial in order to display in a formalized way the operation of the cyclic shift of the original codeword. So, the "-element code combination can be described by the polynomial (NS- 1) degrees:

wherea „_j =(0, 1), anda „_, =0 correspond to zero elements of the combination, q „_, = 1 - non-zero;i- number of the bit of the code combination.

Let's represent the polynomials for specific 4-element combinations:

Addition and subtraction operations are equivalent and associative and are performed modulo 2:

Examples of performing operations:

The division operation is the usual division of polynomials, but instead of subtraction, addition modulo 2 is used:

Cyclic shift of a code combination - moving its elements from right to left without disturbing their order, so that the leftmost element takes the place of the rightmost one.

The main properties and name of cyclic codes are related to the fact that all allowed combinations of bits in the transmitted message (codewords) can be obtained by the operation of cyclic shift of some source codeword.

Let's say the original code combination and the corresponding polynomial are given:

Multiply Oh) on NS:

Since the maximum degree NS in a codeword of length NS does not exceed (n - 1), then from the right side of the resulting expression to obtain the original polynomial, it is necessary to subtract Oh"- 1). Subtraction Oh"- 1) is called taking the remainder modulo (x n - 1).

The shift of the original combination by / measures can be represented as follows: a (x)? Y - Oh"- 1), i.e. multiplication Oh) nah "and taking the remainder modulo (x" - 1). Taking the remainder is necessary when obtaining a polynomial of degree greater than or equal to NS.

The idea of ​​constructing cyclic codes is based on the use of irreducible polynomials. An irreducible polynomial is a polynomial that cannot be represented as a product of polynomials of lower degrees, i.e. divisible only by itself or by one and not divisible by any other polynomial. The binomials (x "+ 1) are divisible by such a polynomial without a remainder. Irreducible polynomials in the theory of cyclic codes play the role of generating polynomials.

Returning to the definition of the cyclic code and taking into account the record of the cyclic shift operations of the code combinations, we can write the generating matrix of the cyclic code in the following form:

whereP (x)- the original code combination, on the basis of which all the others were obtained(T- 1) basic combinations;

С, = 0 orCj =1 ("O" if the resulting degree of the polynomialP (x) -x ‘does not exceed (l - 1), or "1" - if it does).

Combination P (x) is called a generating (generator) combination. To construct a cyclic code, it is enough to choose correctly P (x). Then all other code combinations are the same as in the group code.

The generator polynomial must satisfy the following requirements:

• P (x) must be non-zero;
• the weight P (x) must not be less than the minimum code distance: V (P (x))> d mm;
• P (x) must have the maximum degree k (k - the number of redundant elements in the code);
• P (x) must be a divisor of the polynomial (x "- 1).

The fulfillment of the last condition leads to the fact that all working code combinations of the cyclic code acquire the property of divisibility by P (x) without a remainder. Taking this into account, we can give another definition of a cyclic code: a cyclic code is a code, all working combinations of which are divisible by the generator polynomial without a remainder.

To determine the degree of the generating polynomial, one can use the expression r> log 2 (and + 1), where NS- the size of the transmitted packet at a time, i.e. the length of the constructed cyclic code.

Examples of generating polynomials are given in table. 2.8.

Table 2.8

Examples of generator polynomials

The algorithm for obtaining a permitted code combination of a cyclic code from a combination of a simple code is as follows.

Let the polynomial P (x) = a z _ (x z + a z _ 2 x r ~ 1 + ... + 1, which determines the correcting ability of the code, and the number of check bits To, as well as the original combination of a simple from-element code and information bits in the form of a polynomial A m (x).

It is required to determine the permitted code combination of the cyclic code (and, To).

• 1. We represent the original code combination in the form of a polynomial A m (x). We multiply the polynomial of the original codeword by x g: A t (x) x d. Degree of Generating Polynomial G is equal to the value of the most significant bit of the original codeword.
• 2. Determine the check digits that supplement the original information combination to the permitted one, as the remainder of dividing the product obtained in the previous paragraph by the generator

polynomial:

The remainder of the division is denoted as R (x).

3. The finally resolved cyclic pattern

code is defined as = And m (x)? x r + R (x).

To determine the errors in the received codeword, it is sufficient to divide it by the generating polynomial. If the accepted combination is legal, then the remainder of the division will be zero. A nonzero remainder indicates that the accepted combination contains errors. By the type of the remainder (syndrome), in some cases, it is also possible to draw a conclusion about the nature of the error and its location and correct the error.

The algorithm for determining the error is as follows.

Let there be given "-element combinations ( n = k + m).

• 1. We identify the fact of the presence of an error. We get the remainder of the division of the accepted combination A n - (x) to the generating polynomial P (x): A(NS)
• --- = Rq (x). The presence of the remainder R 0 (x) for (A 0 (x) f 0) indicates P (x)

about the error.

2. Divide the resulting polynomial # (x) = Л „_,(NS) 0 Rq (x) per generator R g (x): W-1 = R (x), where R (x)- current balance.

3. Compare LDx) and R (x). If they are equal, then the error occurred in the most significant bit. If not, then we increase the degree of the adopted polynomial by x and divide again:

4. Compare the resulting balance with Rq (x). If they are equal, then the error occurred in the second bit. If they are not equal, then we multiply Shx) x 2 and repeat these operations until we get

R (x) = hell.

The error will be in the digit corresponding to the number by which the degree is increased Shx), plus 1. For example, in the case of equality R (x) and LDx)

Cyclic codes are a kind of linear group codes and are classified as systematic codes. They were originally created to simplify decoding procedures. However, the high efficiency in detecting errors of such codes ensured their wide application in practice. It is convenient to consider a binary vector of a cyclic code not as a combination of zeros and ones, but as a polynomial of some degree

where x is the base of the number system, the coefficients belonging to the set in the case of the binary number system.

Example. A binary vector can be represented as a polynomial as follows:

Representation of binary vectors in the form of polynomials allows you to reduce the action on vectors to actions on polynomials. Wherein:

the addition of polynomials is reduced to the sum modulo 2 of the coefficients for equal powers of the variable

multiplication is performed according to the usual rule of multiplication of power functions, however, the obtained coefficients for a given degree are added modulo 2;

division is carried out according to the rules for dividing power functions, while the subtraction operation is replaced by summation modulo 2.

Example. Find the sum of polynomials

Find the product of polynomials

Divide polynomials

The main property of cyclic codes is the following: if a vector belongs to a cyclic code, then any vector obtained from the considered one by means of cyclic shifts also belongs to the cyclic code.

The idea of ​​constructing cyclic codes is based on the concept of an irreducible polynomial. A polynomial is said to be irreducible if it is divisible only by itself and by one, and is not divisible by any other polynomial. In other words, an irreducible polynomial cannot be represented as a product of polynomials of lower degrees. A polynomial is divisible by an irreducible polynomial without a remainder. In the theory of cyclic codes, irreducible polynomials play the role of generators of polynomials. The types of irreducible polynomials of various degrees are given in

Examples of irreducible polynomials:

Cyclic code vectors are constructed according to the following rules. Let be any binary vector of some natural code; is a monomial of degree, an irreducible polynomial of degree.Then any vector of a cyclic code is formed using the relation

where is the remainder of the division

Thus, any vector of a cyclic code can be formed by multiplying some vector of a natural binary code by a monomial of a degree with the addition of the remainder of the division to the resulting product. and the rest of the digits are checking.

Example. The vector of a natural binary code has the form Generate a cyclic code vector from a negro, provided that the generating polynomial has the form

We represent the vector as a polynomial

As a result of dividing the polynomial by the polynomial, we get the remainder. That's why

A cyclic code, like any systematic code, can be conveniently given in matrix form using a generating matrix of the form

where is the transposed identity matrix of the format - the matrix of check digits formed by the remainder of the division

Let us set the generating matrix of the cyclic code with the length of information bits and the generating polynomial.

Obviously, the blank for the generating matrix has the form

To find the rows of the check bits of the matrix, we calculate and write in the form of a polynomial each vector of the identity matrix

The length of the cyclic code vector is therefore

(see scan)

As a result, we get the generating matrix C:

Any vector of a cyclic code is obtained as the mod sum of the vectors of its generating matrix. Since the cyclic code is a group code, the zero vector is always assigned to the cyclic code as the unit element of the group "

Table 13.5

Example. Construct all vectors of the cyclic code given by the generating matrix

The code is presented in table. 13.5.

It should be noted that each cyclic code specified by a certain generating matrix can be represented in several versions, differing from each other in the length and number of information bits (with the same detecting abilities). These variants of the so-called shortened cyclic codes are obtained by deleting the last rows and the same number of columns on the left in the generating matrix of the cyclic code. In this case, the number of check bits remains unchanged, while the length of the code and the number of its information bits are reduced, respectively, by an amount equal to the number of crossed out rows and columns of the generating matrix.

Example, Cyclic code is given by its generator matrix

Cross out the last six rows and the first six columns from the left. We get the generating matrix

The characteristics (in the sense of error detection) of the received code are the same as those of the cyclic code represented by the generating matrix

The construction of cyclic codes with given parameters is associated with the choice of a generating irreducible polynomial. The generating polynomial is selected based on the following condition: the degree of the polynomial must be equal to the number of check bits of the cyclic code.

In practice, the problem often arises of constructing a cyclic code of a given power and a given detecting and correcting capabilities.

1. Since the power of the cyclic code is given, the number of its information bits is determined in accordance with the formula

2. The optimal number of check bits of the cyclic code is determined according to special tables.

3. Reference books find all irreducible polynomials of degree

4. For one of the non-conductive polynomials (one should choose a polynomial with the maximum number of terms) of the degree, a generating matrix of the cyclic code is constructed. Each code vector is calculated by the formula

where is the polynomial of the information vector of the generating matrix; - monomial of degree - remainder of division

5. The constructed generating matrix is ​​checked for the following conditions:

a) the weight in the Hamming sense of any vector of the generating matrix must satisfy the relation where is the minimum distance in the Hamming sense of the cyclic code under consideration;

b) the weight in the sense of Hamming of the check vector, which is the sum modulo 2 of any two check vectors of the generating matrix, must satisfy the relation

6. If the generating matrix of the cyclic code satisfies all the above conditions, then all the vectors of the cyclic code are written out and determined in accordance with the well-known rules for linear group codes. If the code does not meet the requirements, then another generator polynomial of the same degree is selected and the procedure for generating a cyclic code is repeated for a new polynomial.

Let us construct a cyclic code with a power of 16 and a correcting code

For, we determine the value by

3 »Using the reference books, we find all irreducible polynomials of degree There are two such polynomials:

4. We choose the polynomial as the generator. The blank of the generating matrix of the cyclic code has the form

Each information vector from the matrix is ​​represented by a polynomial

Determine completely all vectors of the generating matrix using the formula

Since the length of the cyclic code vector (see the format of the generating matrix then

Similarly, we find all the other vectors of the generating matrix

Table 13.6

The result is a generating matrix C? cyclic code

5. The resulting generating matrix satisfies all the necessary conditions. Therefore, we construct the cyclic code completely (Table 13.6). As follows from the table, the code has, that is, it satisfies the requirements of the problem.

Remarks. When using an irreducible polynomial as a generator, we obtain a code that also satisfies the requirements of the problem. Its generating matrix has the form

Error detection using cyclic codes is performed as follows. Any vector of the cyclic code is divisible by the generating polynomial without a remainder. Therefore, the criterion for the presence of an error in the cyclic code vector is the appearance of a nonzero remainder after dividing the cyclic code vector by the generating polynomial. A nonzero remainder identifies an error in the cyclic code vector, but its appearance does not indicate the location of the error in the code vector. Error correction is based on the following algorithm:

1. Divide the received code vector by the generating polynomial.

If the number of units does not exceed the correcting ability of the code, then add the received vector modulo 2 with the resulting remainder. The result of the summation will give the corrected code vector. If the number of units of the remainder is greater than the correcting ability of the code, then perform a cyclic shift of the distorted vector to the left by one bit, and then divide by the generating polynomial. If the resulting remainder contains units not more than the correcting ability of the cyclic code, then add the cyclically shifted vector with the remainder. Shift the summation result cyclically one bit to the right. The resulting vector does not already contain errors and is a cyclic code vector.

3. If after the first cyclic shift and subsequent division the remainder contains more ones than the correcting ability of the code, then repeat the algorithm procedure until a remainder is obtained with the number of ones not exceeding the correcting ability of the code. In this case, the result of the last cyclic shift is added to the remainder, and the resulting vector is cyclically shifted by as many bits to the right as the original received vector with an error was shifted to the left. The result is a corrected code vector.

Let the cyclic code be given by its generating matrix C and generating polynomial, where

The code has a value of 3, that is, it corrects the multiplicity errors. Let the vector 0011101 be adopted instead of the vector 0001101. To correct the error, perform the following actions. The accepted vector is written as a polynomial: then we divide by

The remainder obtained as a result of division contains three ones, which is more than the correcting ability of the code. Therefore, we make a cyclic left shift by one bit of the received code vector. As a result, we have

We carry out division into

The resulting remainder contains two units, which is more than the correcting ability of the code. Therefore, we make another cyclic left shift by one bit of the received code vector. As a result, we have

We carry out division into

The resulting remainder again contains two ones, so we make another cyclic shift to the left by one digit and we get Divide by