entranceLoop coding. Educational-methodical center for language training avtf kc
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 Consequently, 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 transposed 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 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. Consequently, 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 great 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 is 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 by the generating (generating, generating) polynomial is again performed.
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 carry 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 the 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 recording 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 other(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 a polynomial be given 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 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 t (x)? x r + R (x).
To determine the errors in the received codeword, it is enough 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 the "-element combinations ( n = k + t).
- 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)
Matching this word, from formal variable x... It can be seen that this correspondence is not only one-to-one, but also isomorphic. Since "words" consist of letters from a field, they can be added and multiplied (element by element), and the result will be in the same field. The polynomial corresponding to a linear combination of a pair of words and is equal to a 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 codeword obtained by cyclically shifting one bit to the right from the word, then the 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, by j digits:
If m(x) is an arbitrary polynomial over the field GF(q) and c(x) is the codeword of the cyclic ( n,k) code, then m(x)c(x)mod(x n − 1) is also the codeword of this code.
Generating polynomial
Definition The generating polynomial of the cyclic ( n,k) code C is called such a nonzero polynomial 
from C, the degree of which is the smallest and the coefficient at the highest degree g r = 1
.
Theorem 1
If 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 the degree m(x) is less than or equal to k − 1 .
Theorem 2
g(x) is the generator 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, the divisor x n- 1. The degree of the selected polynomial will determine the number of check symbols r, the number of information symbols k = n − r .
Generative matrix
The polynomials are linearly independent, otherwise m(x)g(x) = 0 at non-zero m(x), which is impossible.
This means that codewords can be written, as for linear codes, as follows:
, where G is an generating matrix, m(x)
- information polynomial.
The matrix G can be written in symbolic form: 
Check matrix
For each codeword of the cyclic code is true. That's why check matrix can be written as:
Coding
Unsystematic
With non-systematic coding, the code word is obtained in the form of the product of the information polynomial by the generating
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 sub-block 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 sets the rule for systematic coding. It can be implemented using multi-cycle linear filters (MLF)
Examples of
Binary (7,4,3) code
As a divisor x 7 - 1 we choose the generating polynomial of the third degree g(x) = x 3 + x + 1 , then the resulting code will have length n= 7, the number of check symbols (the degree of the generating polynomial) r= 3, the number of information symbols k= 4, minimum distance d = 3 .
Generative matrix code:
,
where the first line represents the polynomial notation g(x) coefficients in ascending degree. The rest of the lines are cyclic shifts of the first line.
Check matrix:
,
where the i-th column, starting from the 0-th, is the remainder of the division x i by polynomial g(x), written in ascending degrees, starting from the top.
So, for example, the 3rd column is obtained, or in vector notation.
It is easy to see 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 codeword can be obtained using the product of the information polynomial m(x) with degree k- 1 in this way:
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 codeword 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
see also
Links
Wikimedia Foundation. 2010.
- Cyclic forms in music
- Cyclic boundary conditions
See what "Cyclic codes" are in other dictionaries:
shortened cyclic codes- - [L.G. Sumenko. The English Russian Dictionary of Information Technology. M .: GP TsNIIS, 2003.] Subjects information Technology in general EN shortened cyclic codes ...
Reed-Solomon codes- non-binary cyclic codes 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 Golay binary code. The ternary Golay code is also known. Golay codes can be thought of as cyclic codes. ... ... Technical translator's guide
Error correction codes
Error correcting codes- Detection of errors in communication technology, an action aimed at monitoring the integrity of data during recording / playback of information or during its transmission over communication lines. Correction of errors (correction of errors) the procedure for restoring information after ... ... Wikipedia
Error Correcting Codes- Detection of errors in communication technology, an action aimed at monitoring the integrity of data during recording / playback of information or during its transmission over communication lines. Correction of errors (correction of errors) the procedure for restoring information after ... ... Wikipedia
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 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 for
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, commutativity - 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 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-checked codes, repetition codes, Hamming codes, PC codes, and turbo codes.
Hamming Code... The error correction capabilities of the Hamming code are related to the minimum coding distance d 0. All multiplicity errors are fixed q= cnt (d 0- l) / 2 (here cnt stands for "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 bits, 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 of 010SH10 = 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 equipment 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 component codes, you 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 recursive 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.
Cyclic codes are named so because in them part of the code combinations or all combinations can be obtained by cyclic shifting of one or more code combinations. Cyclic shift is carried out from right to left, and the leftmost character is transferred to the end of the combination each time. Cyclic codes, practically, all refer to systematic codes, in them the control and information digits are located in strictly defined places. In addition, codes are classified as block codes. Each block (one letter is a special case of a block) is coded independently.
The idea of constructing cyclic codes is based on the use of polynomials irreducible in the field of binary numbers. Irreducible polynomials are called 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 unity.
Irreducible polynomials in the theory of cyclic codes play the role of generators of polynomials. If the given code combination is multiplied by the selected irreducible polynomial, then we get a cyclic code, the correcting capabilities of which are determined by the irreducible polynomial.
Suppose you want to encode one of the combinations of the four-digit binary code... Suppose also that this combination G (x) = x 3 + x 2 + 1 ® 1011. While not substantiating our choice, we take from the table of irreducible polynomials as a generating polynomial P (x) = x 3 + x + 1 ® 1011. Then we 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 in the polynomial will increase by n, which is equivalent to assigning n zeros on the side of the least significant bits of the polynomial. Since the degree of the selected irreducible polynomial is equal to 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 in the place of these zeros it would be possible to write correction digits.
The value of the correcting digits is found from the results from division G (x) x n 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)¾ private, and R (x)¾ remainder of division G (x) × x n on P (x).
Since in binary arithmetic 1 Å 1 = 0, which means -1 = 1, it is possible, when adding binary numbers, to transfer terms from one part to another without changing the sign (if it is convenient), therefore, an equality of the form a Å b = 0 can 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.
Polynomial 1101001 is the desired combination, where 1101 is an information part, and 001 is control characters. Note that we would get the desired combination both as a result of multiplying one of the combinations of the full four-digit binary code (in this case 1111) by the generator polynomial, and by multiplying the given combination by a monomial having the same degree as the chosen generator polynomial (in In our case, the combination 1101000 was thus obtained) with the subsequent addition to the resulting product of the remainder of the division of this product by the generating polynomial (in our example, the remainder has the form 001).
And here the decisive role is played by the properties of the generating polynomial P (x)... The method of 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 by the generator without a remainder. But only those polynomials that belong to the given code are divisible without remainder, that is, the generating polynomial allows you to choose the allowed combinations from all possible ones. If, when dividing the cyclic code by the generating polynomial, a remainder is obtained, then either an error has occurred in the code, or it is a combination of some other code (forbidden combination). By the remainder, the presence of a forbidden combination is detected, that is, an error is detected. The remainder of the division of the polynomials are the error recognizers of cyclic codes.
On the other hand, the remainders of dividing one with zeros by the generating polynomial are used to construct cyclic codes.
When dividing one with zeros by a generating polynomial, it should be remembered that the length of the remainder must be at least the number of check digits, therefore, in case of a shortage of digits in the remainder, the necessary number of zeros is assigned to the right of the remainder.
01100 11111+
starting from the eighth, the remainders will be repeated.
The remainders from division are used to construct generating matrices, which, due to their clarity and convenience in obtaining derivative combinations, are widely used for constructing cyclic codes. The construction of a generating matrix is reduced to the compilation of a unit transposed and additional matrix, the elements of which are the remainders of dividing one with zeros by the generating polynomial P (x)... Recall that the transposed identity matrix is a square matrix, all elements of which are zeros, except for the elements located diagonally from right to left from top to bottom (in an untransposed matrix, the diagonal with identity elements is from left to right from top to bottom). The elements of the additional matrix are assigned to the right of the identity transposed matrix. Only those residues whose weight is W ³ d 0- 1, where d 0 Is the minimum code distance. The length of the residues must be at least the number of check bits, and the number of residues must be equal to the number of information bits.
The rows of the generating matrix are the first combinations source code... The remaining combinations of the code 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 a code with a length of up to 16 bits
| n | k | ρ | n | k | ρ |
According to the table, this value will be k = 11, while r = 4, a
n = 15. We also choose the generator polynomial x 4 + x 3 +1.
The complete generating matrix is constructed from the unit transpose matrix in the canonical form and an additional matrix corresponding to the check digits.
Transpose matrix for k = 11 looks like:
An additional matrix can be constructed from the remainder of division of a combination in the form of one followed by zeros (the last row of the identity transposed matrix) by the selected generating polynomial.
The full generator matrix will look like this:
The above method for constructing generating matrices is not the only one. The generator matrix can be constructed as a result of direct multiplication of the elements of the identity matrix by the generator polynomial. This is often more convenient than finding the remainder of a division. The resulting codes do not differ in any way from codes constructed from generating matrices, in which the additional matrix consists of the remainders of dividing one with zeros by the generating polynomial.
The generating matrix can be constructed in the same way by cyclic shift of the combination obtained as a result of multiplying the row of the identity matrix of rank k on the generator polynomial.
Errors in cyclic codes are detected using the remainders of dividing the resulting combination by the generating polynomial. The remainder of the division 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 “fitted” to the remainder in such a way that, together with the remainder, it gives the corrected codeword. In this case, the remainder is nothing more than the difference between the distorted and correct symbols, the units in the remainder stand exactly at the places of the distorted bits in the combination adjusted by cyclic shifts. The distorted combination is adjusted until the number of ones in the remainder is equal to the number of errors in the code. In this case, naturally, the number of ones 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 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 the “one-time” action of the generating polynomial, that is, it is enough to get one remainder, the weight of which is 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 building specific codes.