home > Internet > Cyclic codes. Cyclic coding process Cyclic code 7 with code distance 3

Cyclic codes. Cyclic coding process Cyclic code 7 with code distance 3

The main properties and the very name of cyclic codes are related to the fact that all allowed combinations of binary symbols in the transmitted message can be obtained by a cyclic shift operation of some source word: Usually, code combinations of a cyclic code are considered not as a sequence of zeros and ones, but as a polynomial of some degree . Any number in any positional number system can be represented in general view as: where x is the base of the number system; a - digits of this number system; p-1, p-2, ... - an indicator of the degree to which the base is raised, and at the same time the ordinal numbers that occupy the digits. For the binary system, x=2, and a is either "0" or "1". For example, the binary combination 01001 can be written as a polynomial in the argument x: When writing a code combination as a polynomial, the unit in the 1st digit is written as a member x", and zero is not written at all. Representing code combinations in the form of polynomials allows you to establish a one-to-one correspondence between them and reduce actions on combinations to action on polynomials.Thus, the addition of binary polynomials is reduced to the addition modulo 2 of the coefficients with equal powers of the variable.For example, Multiplication is performed according to the usual rule of multiplication of power functions, however, the resulting coefficients at a given degree are added modulo 2.For example , The division is also carried out as a normal division of polynomials; in this case, the subtraction operation is replaced by the operation of addition modulo 2: As noted above, the codes are called cyclic because the cyclic shift a n ^ a l L,..., a 2 ,a 1 ,a d1 a n1 of the allowed combination a n (, a n _ 2 ,...,a 1 , and 0 is also an allowed combination. Such a cyclic permutation when using representations in the form of polynomials is formed as a result of multiplying this polynomial by x. ( x + a 0 , then Y (x) x \u003d a n] x n + a n 2 x n " 1 + ... + a x x 2 + a ^ x. In order for the degree of the polynomial not to exceed n-1, the term x" is replaced by one, therefore: For example, we have the code combination 1101110-> x in + x 5 + x 3 +. x g -1-x. Let's shift it by one digit. We get: Which is the same as multiplying the original polynomial on x: The theory of constructing cyclic codes is based on sections of higher algebra that studies the properties of binary polynomials.A special role in this theory is played by the so-called irreducible polynomials, i.e. polynomials that cannot be represented as a product of polynomials of lower degrees. the th-term is divisible only by itself and by one. It is known from higher algebra that the binomial x "+1 is divisible by an irreducible polynomial without remainder. In coding theory, irreducible polynomials are called generating polynomials, since they "form" allowed code combinations (irreducible polynomials are tabulated, see Table 8.4) (9). The idea of constructing a cyclic code boils down to the fact that the polynomial representing the informational part of the code combination must be converted into a polynomial of degree no more than n-1, which is divided without a remainder by the generating polynomial P(x).It is essential that the degree of the latter corresponds to the number of bits In cyclic codes, all allowed combinations represented as polynomials have one feature: divisibility without remainder by the generating polynomial P(x). polynomial O(x) 2. Multiply O(x) by the monomial Y and obtain 0(x)x r, i.e., the derivative im a shift of the ¿-bit codeword by r bits. 3. Divide the polynomial O(x)x" by the generating polynomial P(x), the degree of which is equal to r. As a result of multiplying O(x) by x r, the degree of each monomial included in O(x) increases by r. When dividing the product of x r O[x) and the generatrix of a polynomial of degree r yields a quotient C(x) of the same degree as 0(x).The results of these operations can be represented as: (8.28) where Wx) is the remainder of dividing 0(x)x r by P(x). Since C(x) has the same degree as 0(x), then C(x) is a code combination of the same ¿-digit code. The degree of the remainder obviously cannot be greater than the degree of the generating polynomial, i.e., its highest degree is equal to r-1. Consequently, the largest number of digits of the remainder does not exceed r. Multiplying both parts of (8.28) by P(x), crawling: (8.29) (the sign of subtraction is replaced by the sign of addition modulo 2). Obviously, F(x) is divisible by P(x) without a remainder. The polynomial F(x) is the allowed code combination of the cyclic code. From (8.29) it follows that the allowed code combination of a cyclic code can be obtained in two ways: by multiplying the code combination simple code C(x) by the generating polynomial P(x) or by multiplying the code combination 0(x) of the simple code by the monomial x r and adding to this product the remainder P(x) obtained by dividing the product by the generating polynomial P(x). With the first encoding method, the information and check bits are not separated from each other (the code is inseparable). This complicates the practical implementation of the decoding process. In the second method, a separable code is obtained: information digits occupy senior positions, the rest p-k ranks are verification. This coding method is widely used in practice. Example 3. Code combination 0111 is given. Let's construct a cyclic code with d o = 3. Solution. At the first stage, based on the required d o = 3, we determine the code length l and the number of check elements k. To do this, we use Table 8.6.1. For a given four-bit codeword N-16. Then for d \u003d 3 from relation 16 (Table 8.3) we find n - 7, respectively, k \u003d n - m - \u003d 7 - 4 \u003d 3. Therefore, code (7.4) is needed. According to the table of generators of polynomials (Table 8.4), for k = 3, we determine P (x) = x 3 + x 2 + 1. Further: 1) for message 0111 we have O (x) = x 2 + x + 1; 2) multiply 0 (x) by x 3 (since r \u003d 3): O (x) x 3 \u003d (x 2 -I- x + 1) x 3 \u003d x 5 + x 4 + x 3; 3) divide (E (x) x 3 by P (x): 4) we get: ^ (x) \u003d O (x) x 3 0 I (x) \u003d x 5 + x 4 + x 3 + 1. This polynomial corresponds to the code combination: All of these operations can also be performed on binary numbers: Table 8.4
4) F(0,1) = O(0,l)x 3 (0,l)©R(0 1 l) = 011100000001= 0111 001. Now let's construct an allowed codeword in the first way: F(x)=C( x)P(x). Let's do the multiplication, representing the polynomials as binary numbers: It can be seen that information and check bits cannot be distinguished in the resulting code combination. Error detection in cyclic coding comes down to dividing the received codeword by the same generating polynomial that was used in coding (its form must be known at the reception). If there are no errors in the received code combination (or they are such that the given transmitted code combination is converted into another allowed one), then the division by the generating polynomial will be performed without a remainder. If the division produces a remainder, then this indicates an error. Example 4. As an allowed code combination, we take the code combination obtained in the previous example: P (x) \u003d x 5 + x 4 + x 3 + 1, and P (x) \u003d x 3 + x 2 + 1, or in binary the form E(0.1) = 0111001; P(0.1) = 1101. Let's assume that an error occurred in the most significant (7th) digit in the information part (digits are counted from right to left). The received code combination looks like 1111001. Let's perform the error detection operation: The presence of a remainder of 110 indicates an error. Cyclic codes are widely used in information transmission systems. For example, in the widely used modem protocol \7.42, to encode code groups, a generating polynomial q (X) = X 16 + X "-2 + X 5 + 1 is used, which is equivalent to the code 1 0001 0000 0010 0001, as well as a higher-order generating polynomial d(X) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 1 + X 5 + X 4 + X 2 + 1. 8.6.

Cyclic codes are characterized by the fact that during the cyclic permutation of all symbols of the code combination of a given code, another code combination of the same code is formed.

Cyclic code combination;

Also a cyclic code combination.

When considering cyclic codes, binary numbers are represented as a polynomial, the degree of which ( P - 1), P- the length of the code combination.

For example, the combination 1001111 ( n= 7) will be represented by a polynomial

With this representation, operations on code combinations are reduced to operations on polynomials. These operations are performed in accordance with ordinary algebra, except that the reduction of like terms is carried out modulo 2.

Error detection using a cyclic code is ensured by choosing as allowed combinations those that are divided without a remainder by some pre-selected polynomial G(x). If the received combination contains distorted characters, then division by a polynomial G(x) is carried out with the remainder. This generates a signal indicating an error. Polynomial G(x)is called generating.

The construction of combinations of a cyclic code is possible by multiplying the original combination BUT(X) to the generating polynomial G(x) with 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 divisible by the preselected degree polynomial P and the result of the multiplication is the remainder of the division.

Thus, all polynomials representing combinations of a cyclic code will have a degree below P.

Often, as a polynomial by which division is carried out, a polynomial is taken G(x)= +1. With such formation of code combinations, the positions of information and control symbols cannot be determined in advance.

A big advantage of cyclic codes is the ease of constructing encoders and decoders, which in their structure represent shift registers with feedback.

The number of bits of the register is chosen equal to the degree of the generating polynomial.

Feedback is carried out from the output of the register to some digits through adders, the number of which is chosen by one less than the number of non-zero members of the generating polynomial. Adders are installed at the inputs of those bits of the register, which correspond to non-zero members of the generating polynomial.

Figure 17 shows the coding register scheme for converting a four-bit combination to a seven-bit combination.

Figure 17 - Scheme of the coding register

In table. 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 cycles, the register will be filled, then the key is moved to position 2. The feedback is closed. Under the action of seven shift cycles, the formation of a seven-bit cyclic code takes place.

Table 4

Cyclic code properties:

1) the cyclic code detects all single errors if the generating polynomial contains more than one member. If a 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) a cyclic code with a generating polynomial G(x) degree r = n - k detects all group errors with a duration of r characters.

test questions

A class of linear codes, which are called Chinese 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 remainder by some selected polynomial, called the generator.

These properties are used in the construction of encoder and decoder codes, as well as in error detection and correction.

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. The cyclic code refers to systematic block (n, &)-codes, in which to the first bits are a combination of the primary code, and the next (l - to) digits are test.

The construction of cyclic codes is based on the operation of dividing the transmitted code combination by the generating irreducible polynomial of degree G. The remainder of the division is used in the formation of check bits. In this case, the division operation is preceded by the multiplication operation, which shifts the ^-bit information code combination to the left by G discharges.

When decoding the received n-bit code combination, the division into a generating (producing, forming) polynomial is again performed.

The error syndrome in these codes is the presence of the remainder from dividing the received code combination by the generating polynomial. If the syndrome is zero, then it is considered that there are no errors. AT otherwise with the help of the received syndrome, it is possible to determine the number of the digit of the received code combination in which an error occurred and correct it.

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

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

Table 2.6

Dependence of the total number of digits of combinations on the number of information and correctable digits

Increasing the difference (n - t), it is possible not only to increase the number of correctable bits s, but also to detect multiple errors. The percentages of detected multiple errors are given in Table. 2.7.

Table 2.7

Percentage of detected multiple errors

It is convenient to describe cyclic codes and construct them using polynomials (or polynomials). The combination record as a polynomial is used to display in a formalized way the operation of the cyclic shift of the original codeword. So, the "-element codeword can be described by the polynomial (P- 1) degree:

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

Let's present polynomials for specific 4-element combinations:

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

Examples of operations:

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

The cyclic shift of a code combination is the movement of 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 the name of cyclic codes are related to the fact that all allowed combinations of bits in the transmitted message (code words) can be obtained by the operation of a cyclic shift of some source code word.

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

Let's multiply Oh) on the X:

Since the maximum degree X in a code combination of length P 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"- one). Subtraction Oh"- 1) is called taking the remainder modulo (x p - 1).

The shift of the original combination by / measures can be represented as follows: a(x)? U - 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 P.

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

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

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

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

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

The generating 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 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 trace. With this in mind, another definition of a cyclic code can be given: a cyclic code is a code, all working combinations of which are divisible by a generating polynomial without a remainder.

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

Examples of generating polynomials are given in Table. 2.8.

Table 2.8

Examples of generating polynomials

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

Let the polynomial be given P (x) \u003d a g _ ( x g + a g _ 2 x r ~ 1 + ... + 1, which determines the corrective ability of the code, and the number of check digits to, as well as the original combination of a simple from-element code and information bits in the form of a polynomial A t (x).

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

1. We represent the original code combination as a polynomial A t (x). We multiply the polynomial of the original code combination by x z: A t (x) x g. Degree of the generating polynomial G equal to the value of the most significant digit of the original code combination.
2. We determine the check bits that supplement the original information combination to the allowed one, as the remainder of the division of the received in previous paragraph works on generative

polynomial:

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

3. The finally allowed codeword of the cyclic

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

To determine the errors in the received code combination, it is enough to divide it into a generating polynomial. If the accepted combination is allowed, then the remainder of the division will be zero. A non-zero remainder indicates that the received combination contains errors. According to the type of residue (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 error detection algorithm is as follows.

Let "-element combinations ( n = k + t).

1. We reveal the fact of the presence of an error. We get the remainder from dividing the accepted combination A n - (x) to the generating polynomial P(x): A(X)
--- = Rq(x). Presence of a balance R0(x) at (L 0 (x) f 0) testifies P(x)

about an error.

2. Divide the resulting polynomial # (x) \u003d L„_,(X) 0 Rq (x) on the generatrix R g(h): 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 increase the degree of the accepted polynomial by x and divide again:

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

R(x) = hell.

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

Corresponding to this word, from a formal variable x. It can be seen that this correspondence is not just one-to-one, but also isomorphic. Since the "words" consist of letters from the field, they can be added and multiplied (element by element), and the result will be in the same field. The polynomial corresponding to the linear combination of the pair of words and is equal to the linear combination of the polynomials of these words

This allows us to consider the set of words of length n over a finite field as a linear space of polynomials with degree at most n-1 over the field

Algebraic description

If the code word obtained by a cyclic shift by one bit to the right from the word , then its corresponding polynomial c 1 (x) is obtained from the previous one by multiplying by x:

Taking advantage of the fact that

Shift to the right and left, respectively j discharges:

If a m(x) is an arbitrary polynomial over the field GF(q) and c(x) - codeword of cyclic ( n,k) code, then m(x)c(x)mod(x n − 1) also the code word of this code.

Generating polynomial

Definition The generating polynomial of the cyclic ( n,k) code C is called such a non-zero polynomial from C, the degree of which is the smallest and the coefficient at the highest degree g r = 1 .

Theorem 1

If a C- cyclic ( n,k) code and g(x) is its generating polynomial, then the degree g(x) is equal to r = n − k and each codeword can be uniquely represented as

c(x) = m(x)g(x) ,

where degree m(x) less than or equal to k − 1 .

Theorem 2

g(x) is the generating polynomial of the cyclic ( n,k) of the code is a divisor of the binomial x n − 1

Consequences: thus, as a generating polynomial, you can choose any polynomial, divisor x n− 1 . The degree of the selected polynomial will determine the number of check symbols r, number of information symbols k = n − r .

Generative matrix

The polynomials are linearly independent, otherwise m(x)g(x) = 0 for nonzero m(x) , which is impossible.

This means that code words can be written, as for linear codes, as follows:

, where G is generating matrix, m(x) - informational polynomial.

Matrix G can be written in symbolic form:

Checking Matrix

For each codeword of a cyclic code, . That's why check matrix can be written as:

Coding

Unsystematic

With non-systematic coding, the code word is obtained as the product of an information polynomial by a generating polynomial

c(x) = m(x)g(x) .

It can be implemented using polynomial multipliers.

Systematic

With systematic coding, the code word is formed in the form of an information subblock and a check

Let the information word form the highest powers of the code word, then

c(x) = x r m(x) + s(x),r = n − k

Then from the condition , it follows

This equation defines the systematic coding rule. It can be implemented using multicycle linear filters (MLF)

Examples

Binary (7,4,3) code

As a divider x 7 − 1 we choose a generating polynomial of the third degree g(x) = x 3 + x + 1 , then the resulting code will have length n= 7 , number of check symbols (degree of the generating polynomial) r= 3 , number of information symbols k= 4 , minimum distance d = 3 .

Generative matrix code:

where the first line is a polynomial entry g(x) coefficients in ascending order. The remaining lines are cyclic shifts of the first line.

Check matrix:

where the i-th column, starting from the 0th, is the remainder of the division x i on a polynomial g(x) , written in ascending order of powers, starting from the top.

So, for example, the 3rd column is , or in vector notation .

It is easy to verify that GH T = 0 .

Binary (15,7,5) BCH code

As a generating polynomial g(x) you can choose the product of two divisors x 15 − 1 ^

g(x) = g 1 (x)g 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Then each code word can be obtained using the product of the information polynomial m(x) with degree k− 1 thus:

c(x) = m(x)g(x) .

For example, the information word corresponds to the polynomial m(x) = x 6 + x 5 + x 4 + 1 , then the code word c(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 , or in vector form

Links

Wikimedia Foundation. 2010 .

See what "Cyclic codes" are in other dictionaries:

shortened cyclic codes- - [L.G. Sumenko. English Russian Dictionary of Information Technologies. M.: GP TsNIIS, 2003.] Topics Information Technology in general EN shortened cyclic codes ...

Non-binary cyclic codes that allow you to correct errors in data blocks. The elements of the code vector are not bits, but groups of bits (blocks). Reed Solomon codes that work with bytes (octets) are very common. Reed Solomon's code is ... Wikipedia

Golay codes- A family of perfect linear block codes with error correction. The most useful is the binary Golay code. The ternary Golay code is also known. Golay codes can be thought of as cyclic codes. … … Technical Translator's Handbook

Error detection in communication technology is an action aimed at monitoring the integrity of data during recording / playback of information or during its transmission over communication lines. Error correction (error correction) procedure for recovering information after ... ... Wikipedia

This is a subclass of linear codes that have the gem property that a cyclic permutation of symbols in an encoded block yields another possible encoded block of the same code. Cyclic codes are based on the application of the ideas of the algebraic Galois field theory1.

Many of the most important noise-immune codes of communication systems, -

in particular cyclic, are based on finite arithmetic structures

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

Operation ranks are in quotation marks because they are not always generally accepted. arithmetic operations. The field always has a zero element (0), or zero, and a single element (1), or one. If number q elements of the field is limited, then the field is called final field, or finite Galois field, and is denoted GF(q) y where q- field order. The smallest Galois field is the two-element field 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 the elements of the field, the operations of addition and multiplication 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, commutativity - a + b = b + a and a b = b a and distributivity - a (b+ c) = a b + a With.

For each field element a there must be an inverse element by addition (-a) and if a not equal to zero, inverse element by 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 elements.

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

A cyclic code is called a linear block (n, k)- a code that is characterized by the property of cyclicity, i.e. a shift to the left by one step of any allowed code word also gives an allowed code word belonging to the same code, and for which the set of code words is represented by a set of polynomials of degree (P- 1) or less divisible by the generating polynomial g(x) degree r=n-ky which is a factor of a binomial X n+

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

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

For example, for the code combination 101101, the polynomial entry 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 related to the minimum code distance d0. All multiplicity errors are corrected q= cnt (d 0- l)/2 (here cnt means "integer part") and multiplicity errors are detected d 0 - 1. So, with odd parity d Q = 2 and single errors are detected. In Hamming code d 0 = 3. In addition to the information digits, L= log 2 Q redundant control bits, where Q- number of information bits. Parameter L rounded up to the next higher integer value. The L-bit control code is the inverted result of bitwise addition (modulo 2 addition) of the numbers of those information bits whose values are equal to one.

Example 7.7

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

Solution

We find that L= 3 and the complement code is

where P is the symbol of the bitwise addition operation, and after inversion we have 000. Now the additional one will be transmitted with the main code. In the receiver, the additional code is again calculated 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 digit of the main code. So, if the code 100010 is received, then the calculated additional code is equal to the inverse of 010Ш10 = 100, i.e. 011, which means an error in the 3rd digit.

A generalization of Hamming codes are cyclic BCH codes, which allow you to correct multiple errors in the received codeword.

Reed-Solomon codes are based on Galois fields, or finite zeros. Arithmetic operations addition, subtraction, multiplication, division, etc. over elements of a finite zero give a result that is also an element of that zero. The Reed-Solomon encoder or decoder must necessarily 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 character sets of one redundant code are considered as elementary information symbols of another redundant code. This association became known as cascading code. The great 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-cascaded codes of the same length and redundancy. Cascaded 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 parallel component encoders. Both block and convolutional codes, Hamming codes, PC code, BCH, etc. can be used as component codes. The use of perforation (puncturing) allows increasing the relative speed of the turbo code by adapting its correcting ability to the statistical characteristics of the communication channel. The principle of formation of the turbo code is as follows: the input signal X, 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 - reordered symbols - is fed to the respective elementary encoders. Binary sequences x p i= 1,2,..., JV, at the output of the encoder are check symbols, which, together with information bits, make up a single code word. The use of an interleaver makes it possible to prevent the occurrence of sequences of correlated errors when decoding turbo codes, which is important when using the traditional recurrent decoding method in processing. Depending on the choice of the component code, turbo codes are divided into convolutional turbo codes and block product codes.