home Comp. literacy Educational and methodological center of language training avtf kts. Cyclic coding process Cyclic code

Educational and methodological center of language training avtf kts. Cyclic coding process Cyclic code

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 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 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, table methods requiring 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) degrees 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 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.

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.