Cyclic codes are characterized by the fact that when all the symbols of a code combination of a given code are cyclically rearranged, another code combination of the same code is formed.
Cyclic code combination;
Also a combination of cyclic code.
When considering cyclic codes, binary numbers are represented as a polynomial whose degree ( P - 1), P- length of the code combination.
For example, the combination 1001111 ( n= 7) will be represented by a polynomial
With this representation, actions on code combinations are reduced to actions on polynomials. These operations are carried out in accordance with ordinary algebra, except that the reduction of similar terms is carried out modulo 2.
Error detection using a cyclic code is ensured by the fact that the permitted combinations are those that are divisible without a remainder by some pre-selected polynomial G(x). If the received combination contains garbled symbols, then division by the polynomial G(x) is carried out with the remainder. This generates a signal indicating an error. Polynomial G(x)called generator.
Constructing cyclic code combinations is possible by multiplying the original combination A(X) to a generating polynomial G(x)with the reduction of similar terms modulo 2:
- if the highest power of the product does not exceed ( P - 1), then the resulting polynomial will represent the code combination of the cyclic code;
- if the highest power of the product is greater than or equal to P, then the product polynomial is divided by a pre-selected polynomial of degree P and the result of multiplication is the resulting remainder from division.
Thus, all polynomials representing combinations of the cyclic code will have a degree lower than P.
Often the polynomial by which division is carried out is taken as a polynomial G(x)= +1. With this formation of code combinations, the positions of information and control symbols cannot be determined in advance.
The great advantage of cyclic codes is the ease of construction of encoding and decoding devices, which in their structure represent shift registers with feedback.
The number of register bits is chosen equal to the degree of the generating polynomial.
Feedback is carried out from the register output to some bits through adders, the number of which is chosen to be one less than the number of non-zero terms of the generating polynomial. Adders are installed at the inputs of those register bits that correspond to non-zero terms of the generating polynomial.
Figure 17 shows a diagram of a coding register for converting a four-bit combination into a seven-bit one.
Figure 17 - Coding register diagram
In table Figure 4 shows how, by shifting the original combination 0101, the cyclic code combination 1010011 is obtained. n= 7,k=4. Combination 0101, key in position 1. During the first four clock cycles, the register will be filled, then the key is moved to position 2. The feedback is closed. Under the influence of seven shift clocks, a seven-bit cyclic code is formed.
Table 4
Properties of cyclic code:
1) the cyclic code detects all single errors if the generating polynomial contains more than one term. If G(x)=x+ 1, then the code detects single errors and all odd ones;
2) cyclic code with G(x)= (x+ 1)G(x) detects all single, double and triple errors;
3) cyclic code with a generating polynomial G(x) degrees r = n - k detects all group errors lasting for r characters.
Control questions
Cyclic codes are so named because in them some or all of the code combinations can be obtained by cyclically shifting one or more code combinations. The cyclic shift is carried out from right to left, with the leftmost symbol being moved to the end of the combination each time. Almost all cyclic codes belong to systematic codes; in them, control and information bits are located in strictly defined places. In addition, the codes are classified as block codes. Each block (one letter is a special case of a block) is encoded independently.
The idea of constructing cyclic codes is based on the use of polynomials that are irreducible in the field of binary numbers. Irreducible are called polynomials that cannot be represented as a product of polynomials of lower degrees with coefficients from the same field, just as prime numbers cannot be represented as a product of other numbers. In other words, irreducible polynomials are divisible without remainder only by themselves or by one.
Irreducible polynomials in the theory of cyclic codes play the role of generating polynomials. If a given code combination is multiplied by a selected irreducible polynomial, we obtain a cyclic code whose correcting capabilities are determined by the irreducible polynomial.
Suppose you need to encode one of the four-digit binary code combinations. Let us also assume that this combination G(x) = x 3 + x 2 + 1 ® 1011. Without justifying our choice yet, we take from the table of irreducible polynomials as a generating polynomial P(x) = x 3 + x + 1 ® 1011. Then multiply G(x) by a monomial of the same degree as the generating polynomial. From multiplying a polynomial by a monomial of degree n the degree of each term of the polynomial will increase by n, which is equivalent to assigning n zeros on the low-order side of the polynomial. Since the degree of the selected irreducible polynomial is three, the original information combination is multiplied by a monomial of three degrees
G(x) x n =(x 3 + x 2 + 1) x 3 =x 6 + x 5 + x 3 = 1101000.
This is done so that later correction digits can be written in the place of these zeros.
The value of the corrective digits is found from the results of division G(x)xn on P(x):
x 6 +x 5 +0+x 3 +0+0+0 ½x 3 +x+1
x 6 +0+x 4 +x 3
x 5 +x 4 +0+0 x 3 +x 2 +x+1+ x 5 +0+x 3 +x 2
x 4 + x 3 +x 2 +0
x 4 + 0 +x 2 +x
x 3 +0+x+0
x 3 +0+x+1
Thus,
or in general view
Where Q(x)¾ quotient, and R(x)¾ remainder of division G(x)×xn on P(x).
Since in binary arithmetic 1 Å 1 = 0, which means -1 = 1, then when adding binary numbers you can transfer the terms from one part to another without changing the sign (if convenient), so the equality is of the form a Å b = 0 can also be written as a = b, And How a - b = 0. All three equalities in this case mean that either a And b are equal to 0, or a And b are equal to 1, i.e. have the same parity.
Thus, expression (5.1) can be written as
F(x)=Q(x) P(x)= G(x) x n +R(x),
which in the case of our example will give
F(x)=(x 3 + x 2 + x + 1) (x 3 + x + 1)= (x 3 + x 2 + 1)x 3 + 1,
F(x)= 1111 1011 = 1101000 + 001 = 1101001.
The polynomial 1101001 is the desired combination, where 1101 is the information part, and 001 is the control characters. Note that we would obtain the desired combination both as a result of multiplying one of the combinations of the complete four-digit binary code (in this case 1111) by a generating polynomial, and by multiplying the given combination by a monomial having the same degree as the selected generating polynomial (in In our case, the combination 1101000 was obtained in this way, followed by adding to the resulting product the remainder from dividing this product by the generating polynomial (in our example, the remainder has the form 001).
And here the properties of the generating polynomial play a decisive role P(x). The technique for constructing a cyclic code is such that the generator polynomial takes part in the formation of each code combination, therefore any polynomial of the cyclic code is divided into the generator without a remainder. But only those polynomials that belong to this code, i.e. the generating polynomial allows you to select allowed combinations from all possible ones. If, when dividing a cyclic code by a generating polynomial, a remainder is obtained, then either an error occurred in the code, or it is a combination of some other code (forbidden combination). The remainder reveals the presence of a prohibited combination, i.e., an error is detected. Residues from division of polynomials are error detectors of cyclic codes.
On the other hand, the remainders from dividing one with zeros by a generating polynomial are used to construct cyclic codes.
When dividing a unit with zeros by a generating polynomial, you should remember that the length of the remainder must be no less than the number of check digits, therefore, if there are not enough digits in the remainder, the required number of zeros is added to the right of the remainder.
01100 11111+
starting from the eighth, the remainders will be repeated.
Division remainders are used to construct generating matrices, which, due to their clarity and ease of obtaining derivative combinations, are widely used for constructing cyclic codes. The construction of a generating matrix comes down to compiling a unit transposed and complementary matrix, the elements of which are the remainders from the division of one with zeros by the generating polynomial P(x). Recall that the identity transposed matrix is square matrix, all elements of which are zero, except for the elements located diagonally from right to left from top to bottom (in a non-transposed matrix, the diagonal with unit elements is located from left to right from top to bottom). The elements of the complementary matrix are assigned to the right of the identity transposed matrix. Only those residues whose weight W ³ d 0- 1, where d 0- minimum code distance. The length of the remainders must be no less than the number of control bits, and the number of remainders must be equal to the number of information bits.
The rows of the generating matrix represent the first combinations source code. The remaining code combinations are obtained by summing modulo 2 all possible combinations of rows of the generating matrix.
Example.
Construct a complete generating matrix of a cyclic code that detects all single and double errors when transmitting 10-bit binary combinations.
Solution.
According to table 5.12, select the closest value k ³ 10.
Table 5.12 – Relationships between information and check characters for codes up to 16 bits long
| n | k | ρ | n | k | ρ |
According to the table, this value will be k = 11, while r = 4, A
n= 15. We also choose a generating polynomial x 4 + x 3 +1.
We construct the complete generating matrix from a unit transposed matrix in canonical form and an additional matrix corresponding to the check bits.
Transposed matrix for k = 11 looks like:
An additional matrix can be constructed from the remainders of division of the combination in the form of one with zeros (the last row of the unit transposed matrix) by the selected generating polynomial.
The complete generating matrix will look like:
The method described above for constructing generating matrices is not the only one. The generating matrix can be constructed by directly multiplying the elements of the identity matrix by the generating polynomial. This is often more convenient than finding remainders from division. The resulting codes are no different from codes constructed using generating matrices, in which the additional matrix consists of the remainders from dividing one with zeros by the generating polynomial.
The generating matrix can also be constructed by cyclically shifting the combination obtained by multiplying the row of the identity matrix of rank k to a generating polynomial.
Errors in cyclic codes are detected using remainders from dividing the resulting combination by a generating polynomial. Division remainders are error identifiers, but do not directly indicate the location of the error in the cyclic code.
The idea of error correction is based on the fact that the erroneous combination, after a certain number of cyclic shifts, is “adjusted” to the remainder in such a way that, together with the remainder, it gives a corrected code combination. The remainder is nothing more than the difference between the distorted and with the correct characters, the units in the remainder stand exactly in the places of the distorted digits in the combination adjusted by cyclic shifts. The distorted combination is adjusted until the number of units in the remainder is equal to the number of errors in the code. In this case, naturally, the number of units can be either equal to the number of errors s, corrected by this code (the code corrects 3 errors and 3 errors in a distorted combination), or less s(the code corrects 3 errors, and in the accepted combination there is 1 error).
The location of the error in the code combination does not matter. If k³(n/2), then after a certain number of shifts all errors will be in the zone of “one-time” action of the generating polynomial, i.e. it is enough to obtain one remainder whose weight W £ s, and this will already be enough to correct the distorted combination.
The error correction process is discussed in detail below using examples of constructing specific codes.
Cyclic code
Cyclic codes are among the block systematic codes in which each combination is encoded independently (in the form of a block) in such a way that the information k and control symbols are always the same
dress in certain places. The ability to detect and correct almost any errors with relatively low redundancy compared to other codes, as well as the simplicity of the circuit implementation of encoding and decoding equipment, made these codes widespread. The theory of cyclic codes is based on group theory and the algebra of polynomials over the Galois field.
A cyclic code is a code in which the order of distribution of code combinations is carried out in such a way that when moving from any combination to the neighboring one, each time the Hamming code distance remains constant.
Cyclic codes are a whole family of error-resistant codes, including Hamming codes as one of their varieties, but in general providing greater flexibility in terms of the ability to implement codes with the necessary ability to detect and correct errors that arise when transmitting code combinations over a communication channel. A cyclic code refers to systematic block (n, k) codes, in which the first k digits represent a combination of the primary code, and the subsequent (n ? k) digits are check ones.
The construction of cyclic codes is based on the operation of dividing the transmitted code combination by a generating irreducible polynomial of degree r. The remainder of the division is used to form check digits. In this case, the division operation is preceded by a multiplication operation, which shifts the k-bit information code combination to the left by r bits.
A polynomial (polynomial) that can be represented as a product of polynomials of lower degrees is called reducible (in a given field), otherwise irreducible. Irreducible polynomials play a role similar to prime numbers in number theory. Irreducible polynomials P(X) can be written as decimal or binary numbers or as an algebraic polynomial.
Cyclic coding process
Cyclic coding is based on the use of an irreducible polynomial P(X), which in relation to cyclic codes is called a generator, generator or generating polynomial (polynomial).
Combinations of binary code for all combinations are taken as information symbols k for constructing cyclic codes. In the general case, if a given code combination Q(x) is multiplied by a generating polynomial P(x), the result is a cyclic code that has certain corrective properties depending on the choice of P(x). However, in this code, the control symbols m will be located in a wide variety of places in the code combination. Such code is not systematic, which makes its circuit implementation difficult. The situation can be significantly simplified if control symbols are added at the end, that is, after information symbols. For this purpose, it is advisable to use the following method:
We multiply the code combination G(x) that needs to be encoded by a monomial X m having the same degree as the generating polynomial P(x);
We divide the product G(x)Х m by the generating polynomial Р(х m):
where Q(x) is the quotient of division; R(x) - remainder.
Multiplying expression (2.1) by P(x) and transferring R(x) to the other part of the equality without reversing the sign, we obtain:
Thus, according to equality (2.2), a cyclic code, that is, an encoded message F(x), can be formed in two ways:
Multiplication of one code combination of a binary code by all combinations by a generating polynomial P(x);
By multiplying a given code combination G(x) by a single polynomial X m having the same degree as the generating polynomial P(x), adding the remainder R(x) obtained after dividing the product G(x)X m by the generating polynomial P( X).
Message encoding
It is required to encode the code combination 1100, which corresponds to G(x)=x 3 +x 2 using P(x)=x 3 +x+1.
We multiply G(x) by X m, which has the third power, we get:
Dividing the product G(x)Х m by the generating polynomial Р(х m), according to (2.1) we obtain:
or in binary equivalent:
Thus, as a result, we obtain the quotient Q(x) of the same degree as G(x):
Q(x)=x 3 +x 2 +x>1110
and the remainder:
As a result, the binary code combination encoded with a cyclic code, according to (2.2), will take the form:
F(x)=1110 1011=1100010
Since each allowed cyclic code combination represents all possible sums of the generating polynomial G(x), they must be divisible by P(x) without a remainder. Therefore, checking the correctness of the accepted code combination comes down to identifying the remainder when dividing it by the generating polynomial.
Receiving a balance indicates the presence of an error. The remainder of the division in cyclic codes plays the role of a syndrome.
For example, the transmitted code combination F(x)=1100010, constructed using the generating polynomial P(x)=1011. Under the influence of interference, the code combination was transformed into the combination F"(x)=1000010
We divide the accepted combination by a generating polynomial
The presence of the remainder R(x)=001 indicates an error. However, it does not directly indicate the location of the error in the combination. To determine the error, there are several methods based on syndrome analysis.
Let's determine the location of the error; to do this, divide one with an arbitrary number of zeros by P(x) = 1011.
An error occurred in element number:
Number of residues -2>4-2=2
That is, the error is in the second element.
BELARUSIAN STATE UNIVERSITY OF INFORMATICS AND RADIO ELECTRONICS
Department of RES
abstract on the topic:
"Cyclic codes. BCH Codes"
MINSK, 2009
Cyclic codes
A cyclic code is a linear block (n,k) code, which is characterized by the property of cyclicity, i.e. a left shift by one step of any allowed codeword also gives an allowed codeword belonging to the same code and for which the set of codewords is represented by a set of polynomials of degree (n-1) or less, divisible by some polynomial g(x) of degree r = n-k , which is a factor of the binomial x n +1.
The polynomial g(x) is called generating.
As follows from the definition, in a cyclic code, codewords are represented as polynomials
where n is the code length; - coefficients from the field GF(q).
If the code is built over the GF(2) field, then the coefficients take the values 0 or 1 and the code is called binary.
Example. If the code word of the cyclic code
For example, if the code is built over the field GF(q)=GF(2 3), which is an extension of GF(2) modulo the irreducible polynomial f(z)=z 3 +z+1, and the elements of this field have the form presented in table 1,
then the coefficients
take the values of the elements of this field and therefore they themselves are displayed in the form of polynomials of the following formwhere m is the degree of the polynomial by which the field extension GF(2) was obtained; a i - coefficients taking the value of the elements of GF(2), i.e. 0 and 1. Such a code is called q-th.
The length of a cyclic code is called primitive and the code itself is called primitive if its length is n=q m -1 on GF(q).
If the length of the code is less than the length of the primitive code, then the code is called shortened or non-primitive.
As follows from the definition, the general property of codewords of a cyclic code is their divisibility without remainder by some polynomial g(x), called the generator.
The result of dividing the binomial x n +1 by the polynomial g(x) is the test polynomial h(x).
When decoding cyclic codes, the error polynomial e(x) and the syndrome polynomial S(x) are used.
The error polynomial of degree no more than (n-1) is determined from the expression
where are polynomials representing the received (with error) and transmitted codewords, respectively.Non-zero coefficients in e(x) occupy positions that correspond to errors.
Example.
The syndromic polynomial used when decoding a cyclic code is defined as the remainder of dividing the received codeword by the generating polynomial, i.e.
or
Consequently, the syndrome polynomial depends directly on the error polynomial e(x). This provision is used in constructing the syndrome table used in the decoding process. This table contains a list of error polynomials and a list of corresponding syndromes determined from the expression
(see table 2).During the decoding process, the syndrome is calculated from the received codeword, then the corresponding polynomial e(x) is found in the table, the summation of which with the received codeword gives the corrected codeword, i.e.
The listed polynomials can be added, multiplied and divided using the known rules of algebra, but with the result given mod 2, and then mod x n +1 if the degree of the result exceeds the degree (n-1).Let's assume that the code length is n=7, then we present the result mod x 7 +1.
When constructing and decoding cyclic codes as a result of dividing polynomials, it is usually necessary to have not the quotient, but the remainder of the division.
Therefore, a simpler method of division is recommended, using not polynomials, but only its coefficients (option 2 in the example).
Example.
Matrix code assignment
A cyclic code can be specified by a generator and a check matrix. To construct them, it is enough to know the generating g(x) and testing polynomials h(x). For a non-systematic cyclic code, matrices are constructed by cyclically shifting the generating and checking polynomials, i.e. by multiplying them by x
AndWhen constructing the matrix H (n,k), the leading coefficient of the polynomial h(x) is located on the right.
Example. For a cyclic (7.4) code with a generating polynomial g(x)=x 3 +x+1, the matrices G (n,k) and H (n,k) have the form:
WhereFor a systematic cyclic code, the matrix G (n,k) is determined from the expression
where I k is the identity matrix; R k,r is a rectangular matrix. The rows of the matrix R k,r are determined from the expressions or where a i (x) is the value of the i-th row of the matrix I k ; i is the row number of the matrix R k,r.Example. The matrix G (n,k) for the (7.4) code based on the generating polynomial g(x)=x 3 +x+1 is constructed in the following sequence
or
R 4.3 is determined using
becauseDetermined in a similar way
Loading...