In this article, the 2 methods of formation shift indexes vector of the ring code are proposed. This article presents the matrix of the ring code in the form of binary elements (0,1) and in the form of polynomials, which consist of the sum of the arguments x of a certain category corresponding to the binary value of 1 code sequences of the ring code. With these two methods, shift indexes vectors are created using an example of a ring code of 7 × 7, each row containing 4 units and 3 zeros. The first method makes it possible to form VPS by implementing logical transformations (XOR, OR, or AND) over the binary elements of the generating matrix of the ring code. The second method makes it possible to form VPS by implementing logical transformations (XOR, OR, or AND) over the arguments x of a certain category corresponding to the binary value of 1 code sequences of the ring code. According to the proposed second method, as a result of the logical transformations of the XOR, OR, or AND arguments of polynomials of the matrix G, similar shift indexes vectors were formed. The first method allows developing an algorithm and implementing a program implementation of the formation shift indexes vector. The second method is more visual, by means of which you can mathematically describe the sequence of the formation shift indexes vector of the ring code.
The ring code is constructed on the principle of block-cyclic codes [
Cyclic codes have been widely used due to their efficiency in detecting and
correcting errors [
Cyclic codes are a subset of linear block codes. Linear (n, k) - Code C is called cyclic if the cyclic shift of any word c is also a word of that code. The cyclic shift of the code word с=(с0, с1,… сn-1) corresponds to the shift of all elements of the word Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). one position to the right, resulting in a code word с(1)= (сn-1, с0, с1,… сn-2). As a result of the i- multiple shift, we get the code word с(i)= (сn-i,…, сn-1, с0, с1,… сn-i-1).
The schematics of the encoding and decoding devices for these codes are extremely simple and are based on conventional shift registers. An example of a feedback register is shown in fig. 1.
The initial state of the register 0 С 1 С С …
С n-3
С n-2
С n-1 Register state after shifting items 1 position to the right С n-1 1 С С …
С n-4
С n-3
С n-2 2
0
It is convenient to consider cyclic codes by presenting a combination of binary code not as sequences of zeros and ones, but as a polynomial from a dummy variable х.
The code word с=(с0, с1,…сn-1) can be represented as the following polynomial: с(х) = с0х0 + с1х1 +…+ сn-1хn-1 = с0 + с1х +…+ сn-1хn-1 (1)
Where сi – are the numbers of the given system of calculus (in binary system 0 and 1).
The above comparison of code words and polynomials is unambiguous: each word corresponds to a polynomial and each polynomial corresponds to a word that is determined by the coefficients of that polynomial.
If с=(с0, с1,… сn-1) is a code word belonging to code С, then the corresponding
polynomial c (x) is also called a code word С [
According to the definition of the cyclic code for constructing the forming matrix n, k it is sufficient to select only one initial n-degree combination Ci(х). A cyclic shift can produce (п - 1) different combinations, of which any k combinations can be taken as starting points By summing the rows of the forming matrix in all possible combinations, other code combinations can be obtained.
Thus, the cyclic (n, k) - code is a set of polynomials forming a k-dimensional
linear subspace of the space of all polynomials of degree n-1 closed with respect to
the cyclic shift operation [
The cyclic shift of the combination with the unit in the higher n-th digit is
identical to the multiplication of the corresponding polynomial by x with the
simultaneous subtraction from the result of the polynomial (хn- 1) or (хn + 1), since the
operations are performed by module two. According to [
1) by multiplying a simple code combination of degree (k - 1) by the monomial xn-k and adding to this multiplication the residue obtained from dividing the resulting multiplication by the polynomial Р(х) of degree (п - k),
2) by multiplying a simple code combination of degree (k - 1) by the forming polynomial Р(х) of degree (п – k).
According to the first encoding method, the first k symbols of the resulting code combination match the corresponding symbols of the original simple code combination.
According to the second method, in the code combination obtained, the information symbols do not always coincide with the symbols of the original simple combination. This method is easy to implement, but because the resulting code combinations do not contain information symbols in explicit form, it complicates the decoding process.
In practice, the first method of obtaining a cyclic code is usually used.
The cyclic code can be represented as a formative matrix , , which consists of two submatrices: information and additional : , = , (2)
Information submatrix Uk, is a square unit matrix with the number of rows and
columns equal to k. The additional sub-matrix Нр contains р = п - k columns and
k rows and is formed by residues R(х)[
The forming matrix allows k code combinations to be obtained. Other combinations are formed by summing the modulus of two rows of the forming matrix in all possible combinations.
The forming matrix Pn,k can also be formed by multiplying the forming polynomial Р(х) of degree = n - k by the monomial xk-1 of the following k-1 shifts of the resulting combination. The number of rows and columns in the formative matrix may be arbitrary.
The forming matrix of ring code unlike the cyclic code is always a square matrix
of size N × N, each row of which contains m units and, accordingly, N – m zeros.
Each row of the forming matrix of cyclic code has the same number of elements and
the same structure of unitary and null character combinations. The first row of the
forming matrix of cyclic code is called the initial vector, or the initial sequence, and
the last row is the final vector of the cyclic shift of the code sequence elements. In this
case, the rows of the matrix seem to form a ring of a complete cycle of shift of
elements of code sequences [
An example of a matrix representation of a ring code For example is a ring code, the shift of elements of the code sequences, which is carried out, from right to left, with the leftmost symbol being transferred to the right at the end of the code sequence each time. Below are the forming of ring code matrices that contain elements of code sequences in a binary number system. The forming matrix G has a size of 7 × 7
and contains 4 units and 3 zeros, and the forming matrix P has a size of 9 х 9 P contains 4 units and 5 zeros. The first rows of the forming matrices are called the initial sequence. (3) (4) (5) ⎢⎢0101101⎥⎥ ⎢0110101⎥ ⎢1101010⎥ ⎣1010101⎦ 010010011 ⎡100100110⎤ ⎢⎢001001101⎥⎥ ⎢010011010⎥ ⎢001101001⎥ ⎢011010010⎥ ⎢110100100⎥ ⎣101001001⎦ ⎣ + + + + + + + + + + + + + + + + + + + + + ⎦ ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ The above forming matrices can also be represented in the form of polynomials that correspond to the code sequences represented in the binary number system and where x – is an argument of a particular digit corresponding to the binary value of 1 ring code. The structure of the code sequences of the forming matrix corresponds to the structure of the code sequences in the binary number system the forming matrix , the structure of the code sequences of the forming matrix structure of the code sequences in the binary number system the forming matrix: corresponds to the (6) Analysis of the structure of the polynomials of the and forming matrices indicates that the number of polynomials in the forming matrices depends on the number of elements in the code sequence, and, accordingly, on the number of code sequences. At that time, the number of members in each polynomial depends only on the number of units in the code sequence and does not depend on the number of elements in the code sequence.
Using the above matrices, we form the shift indexes vectors of the ring code by performing the binary transformations of XOR, AND and OR over the binary arguments of the polynomials of the matrices elements of the code sequences of the matrices and .
and , as well as over the of the code sequences, is performed. the shift indexes matrix. 3
The method of formation of shift indexes vector by performing logical transformations over the binary elements of the matrices and The shift indexes vector is the sequence of decimal numbers formed by summing the number of units resulting from the implementation of one of the binary transformations XOR, AND, OR (with or without negation) of the elements of the initial
sequence (first line) of the ring code and the rest of its lines.
According to [
AND. 3) The number of units is calculated in each row of the resulting shift indexes matrix (hereinafter referred to as the SIM). In doing so, the SIM is transformed into
number ring code Line number ring code 1 2 3 4 5 6 7 1 2 3 4 5 6 7 4 The method of forming a shift indexes vector by making logical transformations over the arguments of polynomials of the matrix Formation of the SIV by making logical transformations over the arguments of polynomials is carried out as follows: 1) Alternately the binary logical transformation XOR, OR, or AND of the arguments of the first polynomial and subsequent polynomials of the ring code matrix is performed. 2) Depending on the type of logical transformation (XOR, OR or AND) the following steps are performed: а) For logical XOR transformation: - paired arguments of the generated polynomial with identical digits are deleted; - counts the number of arguments left after deletion paired arguments with equal digits; b) For logical AND transformation: - remove the odd arguments of the polynomial; - paired arguments with equal digits are absorbed by one argument; - counts the number of arguments left after deletion and absorbing arguments; c) For OR logical transformation: - paired arguments with equal digits are absorbed by one argument; - counts the number of arguments left after the arguments are absorbed.
Tables 7 - 9 show the sequence of transformations of ring code a 9 × 9, each row containing 4 units and 5 zeros by performing logical transformations over the arguments of the polynomials of the forming matrix . 1 2 3 4 5 6 7 1 2 3 4 5 6
2 3 4 5 6 7
The ring code matrix As noted above, polynomials of the forming matrices and consist of arguments whose degrees correspond to the degrees of the binary elements of the code sequences of the forming matrices and of the ring code. The analysis of the above tables indicates that the algorithm for converting the ring code represented in the form of polynomials is similar to the algorithm for converting the ring code represented as binary elements. 5
Conclusions 1. The ring code can be represented in the form of a matrix, each line of which is a polynomial with arguments of a certain digit corresponding to the binary value of 1 ring code. 2. The shift indexes vector can be formed by two methods: - by making logical transformations (XOR, OR or AND) over the binary elements of the ring matrix-forming matrix; - by performing logical transformations (XOR, OR or AND) over the arguments of the forming matrix of polynomials.