=Paper=
{{Paper
|id=Vol-2577/paper21
|storemode=property
|title=Method of formation shift indexes vector by minimization of polynomials
|pdfUrl=https://ceur-ws.org/Vol-2577/paper21.pdf
|volume=Vol-2577
|authors=Liubov Berkman,Serhiy Otrokh,Valeriy Kuzminykh,Olena Hryshchenko
|dblpUrl=https://dblp.org/rec/conf/its2/BerkmanOKH19
}}
==Method of formation shift indexes vector by minimization of polynomials==
https://ceur-ws.org/Vol-2577/paper21.pdf
259
Method of formation shift indexes vector by minimization
of polynomials
© Liubov Berkman1, © Serhiy Otrokh2, © Valeriy Kuzminykh2
and © Olena Hryshchenko1
1 State University of Telecommunications, Kyiv, Ukraine
2 National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Kyiv,
Ukraine
berkmanlubov@gmail.com, 2411197@ukr.net, vakuz0202@gmail.com,
elena.grischenko1@gmail.com
Abstract. 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.
Keywords: matrix of ring code, polynomial, logical transformations of the
XOR, OR, or AND arguments, shift indexes vector.
1 Introduction
The ring code is constructed on the principle of block-cyclic codes [8], the rows of the
forming matrices of which are linked by the condition of cyclicity.
Cyclic codes have been widely used due to their efficiency in detecting and
correcting errors [1, 2].
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).
260
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 2 n-3 n-2 n-1
Register state after shifting items 1 position to the right
С С С … С С С
n-1 1 0 n-4 n-3 n-2
Fig. 1. The feedback register.
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 pol-
ynomial:
с(х) = с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 С [3, 4].
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.
261
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 [5].
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 simulta-
neous subtraction from the result of the polynomial (хn- 1) or (хn + 1), since the
operations are performed by module two. According to [6], the code combination of
the cyclic (п, k)- code can be obtained in two ways:
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(х)[3].
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 pol-
ynomial Р(х) 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 [7].
262
2 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.
0101011
⎡1010110⎤
⎢ ⎥
⎢0101101⎥
𝐺 = ⎢1011010⎥ (3)
⎢0110101⎥
⎢1101010⎥
⎣1010101⎦
010010011
⎡100100110⎤
⎢001001101⎥
⎢ ⎥
⎢010011010⎥
𝑃 = ⎢100110100⎥ (4)
⎢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 𝑃 corresponds to the
structure of the code sequences in the binary number system the forming matrix:
𝑥 +𝑥 + 𝑥 + 𝑥
⎡ ⎤
𝑥 +𝑥 + 𝑥 + 𝑥
⎢ ⎥
⎢ 𝑥 +𝑥 +𝑥 +𝑥 ⎥
𝐺 = ⎢ 𝑥 +𝑥 +𝑥 + 𝑥 ⎥ (5)
⎢ 𝑥 +𝑥 +𝑥 +𝑥 ⎥
⎢ 𝑥 +𝑥 +𝑥 + 𝑥 ⎥
⎣𝑥 + 𝑥 + 𝑥 + 𝑥 ⎦
263
𝑥 +𝑥 + 𝑥 + 𝑥
⎡ ⎤
𝑥 +𝑥 + 𝑥 + 𝑥
⎢ ⎥
⎢ 𝑥 +𝑥 + 𝑥 + 𝑥 ⎥
⎢ 𝑥 +𝑥 + 𝑥 + 𝑥 ⎥
𝑃 = ⎢ 𝑥 +𝑥 + 𝑥 + 𝑥 ⎥ (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
elements of the code sequences of the matrices 𝐺 and 𝑃, as well as over the
arguments of the polynomials of the matrices 𝐺 and 𝑃 .
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 [8] the shift indexes vector (hereinafter referred to as SIV) is formed
in three stages:
1) Alternatively, the binary logical transformation of XOR, OR, AND elements of the
first line and the next rows of the matrix of the ring code, placed at the same positions
of the code sequences, is performed.
2) The binary elements (0, 1), resulting from the logical transformation are written to
the shift indexes matrix.
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
SIV.
Tables 1 - 3 present the sequence of transformations of ring code a 7 × 7, each
row containing 4 units and 3 zeros, in the SIV using logical transformations XOR, OR,
AND.
264
Table 1. The sequence of the formation of SIV by logical transformation XOR.
Line Structures of Line numbers Structures The sums of
number code between elements forming the single
ring code sequences of which the vectors elements of the
operation was forming
performed XOR vectors
1 0101011 1-2 1111101 6
2 1010110 1-3 0000110 2
3 0101101 1-4 1110001 4
4 1011010 1-5 0011110 4
5 0110101 1-6 1000001 2
6 1101010 1-7 1111110 6
7 1010101
Table 2. The sequence of the formation of the SIV by logical transformation AND.
Line Structures of Line numbers Structures The sums of
number code between elements forming the single
ring code sequences of which the vectors elements of the
operation was forming
performed AND vectors
1 0101011 1-2 0000010 1
2 1010110 1-3 0101001 3
3 0101101 1-4 0001010 2
4 1011010 1-5 0100001 2
5 0110101 1-6 0101010 3
6 1101010 1-7 0000001 1
7 1010101
Table 3. The sequence of the formation of SIV using logical OR transformation.
Line Structures of Line numbers Structures The sums of
number code between elements of forming the single
ring code sequences which the operation vectors elements of the
was performed OR forming vectors
1 0101011 1-2 1111111 7
2 1010110 1-3 0101111 5
3 0101101 1-4 1111011 6
4 1011010 1-5 0111111 6
5 0110101 1-6 1101011 5
6 1101010 1-7 1111111 7
7 1010101
265
Tables 4 - 6 present the sequence of transformations of ring code a 9 × 9, each row
containing 4 units and 5 zeros, in the SIV using logical transformations XOR, OR and
AND.
Table 4. The sequence of the formation of the SIV by logical transformation XOR.
Line Structures of Line numbers Structures The sums of the
number code sequences that have binary forming single elements
ring code transformations vectors of the forming
between elements vectors
1 010010011 1-2 110110101 6
2 100100110 1-3 011011110 6
3 001001101 1–4 000001001 2
4 010011010 1–5 110100111 6
5 100110100 1–6 011111010 6
6 001101001 1–7 001000001 2
7 011010010 1–8 100110111 6
8 110100100 1–9 111011010 6
9 101001001
Table 5. The sequence of the formation of SIV using logical AND transformation.
Line number Structures Line numbers Structures The sums of the
ring code of that have binary forming single elements
code sequences transformations vectors of the forming
between elements vectors
1 010010011 1-2 000000010 1
2 100100110 1-3 000000001 1
3 001001101 1–4 010010010 3
4 010011010 1–5 000010000 1
5 100110100 1–6 000000001 1
6 001101001 1–7 010010010 3
7 011010010 1–8 010000000 1
8 110100100 1–9 000000001 1
9 101001001
266
Table 6. The sequence of the formation of SIV using logical OR transformation.
Line number Structures Line numbers Structures The sums of the
ring code of that have binary forming single elements
code sequences transformations vectors of the forming
between elements vectors
1 010010011 1-2 110110111 7
2 100100110 1-3 011011111 7
3 001001101 1–4 010011011 5
4 010011010 1–5 110110111 7
5 100110100 1–6 011111011 7
6 001101001 1–7 011010011 5
7 011010010 1–8 110110111 7
8 110100100 1–9 111011011 7
9 101001001
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 pol-
ynomials 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 𝐺 .
267
Table 7. The sequence of the formation of SIV by logical transformation XOR.
Line The ring Numbers Shift indexes Result Total
number code matrix rows matrix addition number
RC matrix RC modulo 2 elements SIV
1 х5+ х3+ х1+ х0 1-2 х5+ х3+ х1+ х0 х5+ х3+ х0 6
х6+ х4+ х2+ х1 х6+ х4+ х2
2 х6+ х4+ х2+ х1 1-3 х5+ х3+ х1+ х0+ х1+ х2 2
х5+ х3+ х2+ х0
3 х5+ х3+ х2+ х0 1-4 х5+ х3+ х1+ х0+ х5+ х1+ х6+х2 4
х6+ х3+ х2+ х0
4 х6+ х3+ х2+ х0 1-5 х5+ х3+ х1+ х3+х1+х4+х2 4
х0+х5+ х4+ х2+
х0
5 х5+ х4+ х2+ х0 1-6 х5+ х3+ х1+ х0+ х0+х6 2
х6+ х5+ х3+ х1
6 х6+ х5+ х3+ х1 1-7 х5+ х3+ х1+ х0 х5+ х3+ х1+ 6
х6+ х4+ х2+ х0 х6+ х4+ х2
7 х6+ х4+ х2+ х0
Table 8. The sequence of the formation of SIV by logical transformation AND.
Line The Numbers Shift indexes Result Total
number ring rows matrix conjunctive number
RC code matrix matrix elements
absorption
RC SIV
1 х5+ х3+ х1+ х0 1-2 х5^ х3^ х1^х0^ х1^х1= х1 1
х6^ х4^ х2^ х1
2 х6+ х4+ х2+ х1 1-3 х5^ х3^ х1^ х0^ x5^х5= х5 3
х5^ х3^ х2^ х0 x3^х3= х3
x0^х0= х0
3 х5+ х3+ х2+ х0 1-4 х5^ х3^ х1 ^ х0^ x3^х3= х3 2
х6 ^х3 ^ х2 ^ х0 x0^х0= х0
4 х6+ х3+ х2+ х0 1-5 х5 ^ х3^ х1^ х0^ x5^х5= х5 2
х5^ х4 ^ х2 ^ х0 x0^х0= х0
5 х5+ х4+ х2+ х0 1-6 х5 ^ х3^ х1^ х0^ x5^х5= х5 3
х6 ^ х5 ^ х3^ х1 x3^х3= х3
x1^х1= х1
6 х6+ х5+ х3+ х1 1-7 х5^ х3^ х1^ х0 x0^х0= х0 1
х6^ х4^ х2^ х0
7 х6+ х4+ х2+ х0
Table 9. The sequence of the formation of SIV by logical transformation AND.
268
Line The Numbers Shift indexes Result Total
number ring rows matrix disjunctive number
RC code matrix matrix elements
absorption
RC SIV
1 х5+ х3+ х1+ х0 1-2 х5v х3v х1vх0v х1v х1= х1 7
х6v х4v х2v х1 (х5vх3vх1vх0vх6vх4v
х2)
2 х6+ х4+ х2+ х1 1-3 х5v х3v х1v х0v x5vх5= х5 5
х5v х3v х2v х0 x3vх3= х3
x0vх0= х0
(х5vх3vх2vx1vх0)
3 х5+ х3+ х2+ х0 1-4 х5^ х3^ х1 ^ х0^ x3^х3= х3 6
х6 ^х3 ^ х2 ^ х0 x0^х0= х0
(х5vх6vх3vх1vх2vх0)
4 х6+ х3+ х2+ х0 1-5 х5 ^ х3^ х1^ х0^ x5^х5= х5 6
х5^ х4 ^ х2 ^ х0 x0^х0= х0
(х5vх4vх3vх1vх2vх0)
5 х5+ х4+ х2+ х0 1-6 х5 ^ х3^ х1^ х0^ x5^х5= х5 5
х6 ^ х5 ^ х3^ х1 x3^х3= х3
x1^х1= х1
(х5vх6vх3vх1vх0)
6 х6+ х5+ х3+ х1 1-7 х5^ х3^ х1^ х0 x0^х0= х0 7
х6^ х4^ х2^ х0 (х5vх6vх3vх4vх1vх2v
х0)
7 х6+ х4+ х2+ х0
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.
269
3. The first method allows you to develop an algorithm and perform software
implementation of the formation of the shift indexes vector.
4. The second method is more visual and allows you to mathematically describe the
sequence of formation of the shift indexes vector of the ring code.
References
1. D. Augot, E. Betti, E. Orsini.: An introduction to linear and cyclic codes. Journal
of Symbolic Computation, 47-68 (2009).
2. L. M. J. Bazzi and S. K. Mitter.: Some randomized code constructions from
group actions. IEEE Trans. on In. Theory, vol. 52, pp. 3210–3219 (2006).
3. J. Yuan, C. Ding, Senior Member.: IEEE Secret Sharing Schemes from Three
Classes of Linear Codes, IEEE Trans. on Inf. Theory, 52 (1), 206-212 (2006).
4. A. Vardy.: Algorithmic complexity in coding theory and the minimum distance
problem, STOC ’97: Proceedings of the twenty-ninth annual ACM symposium on
Theory of Computing, pp. 92–109 (1997).
5. A. Ashikmin, A. Barg.: Minimal vectors in linear codes, IEEE Transactions on
Information Theory 44 (5) (1998).
6. G. Castagnoli, J. L. Massey, P. A. Schoeller, and N. von Seeman.: On repeated
root cyclic codes, IEEE Trans. on Inf. Theory, vol. 37, pp. 337-342 (1991).
7. Gavrilko E.V., Otrokh S.I., Yarosh V.A., Grishchenko L.N.: Improving the quality
of the functioning of the network of the future through the use of ring codes.
Vesnik svyazi (2), 60-64 (in Russian) (2018).
8. S. Otrokh, V. Kuzminykh, O. Hryshchenko.: Method of forming the ring codes.
CEUR Workshop Proceedings, vol. 2318, pp. 188-198 (2018).