The article discusses a method for converting ring codes into shift index vectors, which are designed to compress information and protect it from unauthorized access. The structure of the shift index vectors and the patterns of change in the decimal values of the shift index vectors are analyzed. The properties of shift index vectors created by transforming ring codes using binary transformations of the XOR, AND, OR elements of the initial sequence (first line) of the ring code and sequentially on each subsequent line are investigated. It has been established that the limits of change in the decimal values of the elements of the shift index vectors depend both on the length and number of ones in the code combinations of ring codes, and on the ratio of ones and zeros in the code combination. Analysis of the structure of shift index vectors of ring codes shows that for a family of ring codes of a certain type there is an unambiguous dependence of the decimal values of elements of shift index vectors and the limits of their location in the vector index on the number of elements and ones in the code combination. The set of decimal values of the shift index vector consists of three sequences. Using the family of ring codes like 000111 as an example, it is shown that the limits of each of the three sets are uniquely described depending on the ratio of the number of elements and ones in the codeword.
The ring code is built on the principle of forming a cyclic code by shifting a certain number of elements to the right or left in the code combination and differs from the cyclic code that highest element of the code combination is shifted in place of the youngest element as if forming a ring. The ring code matrix is a square of size
N × N, each line containing m ones and N - m zeros [1-5]. At the same time each line of the matrix re-peats the previous line with a simultaneous ring shift of characters by a certain number of digits to the right or left. Based on the above, the ring code, which is formed by shifting one character of the code sequence from right to left, can be represented as the following matrix G: ⎣ 2
⎣ 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 . . . . . . . .
… … 2 2 … 2 2 2 ⎥ ⎤ ⎥ ⎥ ⎥ ⎦ where k is a binary element of the code combination, which takes on the value 0 or 1 depending on its structure. as follows:
According to [1-5] the ring code is characterized by a shift indexes vector (SIV), which is formed - the binary logical transformation XOR, AND or OR is performed alternately over the elements of the first row and subsequent rows of the ring code matrix placed at the same positions of the code sequences. In this case the matrix of the ring code is converted into a shift indexes matrix; - in each row of the resulting shift indexes matrix the number of elements corresponding to one is counted. At that, the shift indexes matrix transformed into a shift indexes vector.
The formula of transformation of matrix G into the shift indexes vector using the binary logical transformation XOR takes on the following form:
The formula of transformation of matrix G into the shift indexes vector using the binary logical transformation AND takes on the following form: 2 2 2 ⋯ 2 2
The formula of transformation of matrix G into the shift indexes vector using the binary logical transformation OR takes on the following form: 2. Analysis of the dependence of the shift index vectors structure on the type of the ring codes family
Each line (code sequence) of the ring code is characterized by a delta factor - the distribution of zeroes and ones between two extreme ones, separated by the largest number of zero symbols for a 2 2 2 2 2 2 2 2 ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ 2 2 2 2 2 2 2 2 2 2 2 ⎥ ⎤ ⎥ ⎥ ⎥ ⎦ 2 2 ⎥ ⎤ ⎥ ⎥ ⎥ ⎦ 2 2 2 ⎥ ⎤ ⎥ ⎥ ⎥ ⎦ Each family of ring codes is characterized by the length of N code sequences and the number of m ones [6-8].
Each line (code sequence) of the ring code is characterized by a delta factor - the distribution of zeroes and ones between two extreme ones, separated by the largest number of zero symbols for a given initial vector. Ring codes having a delta factor of a particular type form a family of ring codes. Each family of ring codes is characterized by the length of N code sequences and the number of m ones [6-8].
In [9-11], the properties of families of ring codes are analyzed based on the delta factor of type 0011100 (ones in the code sequence are placed without interruption), type 010101 (ones and zeroes alternate) and type 001011. For these types of families of ring codes, mathematical models are built the formation of families based on the analysis of the values of code combinations in the decimal number system.
Table 1 shows the results of converting the families of ring codes of types 0011100, 010101, and 001011 to shift index vectors using the logical transformations XOR, AND and OR.
Analysis of the structure of the shift index vectors allows us to conclude that, within the family of ring codes, the sequence of changes in the decimal values of the shift indexes vector is identical. The shift index vectors within the family differ in the number of decimal values and their values, which depend on the length of the codeword and the number of ones in each codeword.
Let us consider in greater detail the patterns of change in the values of the elements of the shift index vectors for family of the type 0011100. 3. Common factors of change in the values of shift indexes vector elements for ring codes family of the type 001110 1 2 3 7 4 5 6 1 2 3 8 4 5 6 7 1 2 3 9 4 5 6 7 8
An analysis of the dependence of the decimal values D of the elements of the shift index vectors from the position number of their placement in the shift indexes vector V suggesting that the set of decimal values of the shift indexes vector PV consists of 3 subsets: ∪
∪ , where P1 is a sequence of decimal values that are within the position of their placement in the shift indexes
vector from left to right from 1 to m at m ≤ N-m and from 1 to N-m at m > N-m. In this case, N is the number of elements in the code combination, and m is the number of ones;
P2 is a sequence of decimal values, located within the position of their placement in the shift indexes vector from left to right from m+1 to N-m-1 when m<N-m and from N-m +1 to m-1 when |N-2m| > 1. For |N-2m| ≤1, the sequence is zero;
P3 is a sequence of decimal values that are within the position of their placement in the shift indexes vector from left to right from N-m to N-1 at m<N-m and from m to N -1 at m>N-m. Provided that m = N-m, the sequence P3 is in the range of positions from N-m + 1 to N-1.In general, the mathematical model for determining the limits of the sequences P1, P2 and P3 is as follows: ∈ 1, 1 1, 1, , ; ∅ , | 2 , .
, , ; , ; , , ; shift indicators on the number of the placement position in the shift indexes vector V, formed using the XOR logical operation of ring codes of the 011100 family with different codeword length N and the number of codeword ones m = 4.
Based on the analysis of the structure of the shift index vectors, it is possible to construct formulas for calculating the sums of the decimal values of the elements of the shift index vectors depending on the number of elements, the number of ones and zeros in the code combination.
Below is a mathematical model for calculating the sums of decimal values of the elements of the vectors of displacement indicators, formed using the logical XOR transformation: where S1 is the sum of the decimal values of the elements of the shift indexes vector, which is within the P1 sequence; S2 is the sum of the decimal values of the elements of the shift indexes vector, which is within the P2 sequence; S3 is the sum of the decimal values of the elements of the shift indexes vector, which is within the P3 sequence.
Mathematical models for calculating the sums S1, S2 and S3 are as follows:
| 2 | 1; where N is the number of elements in the code combination of the ring code, m is the number of ones in the code combination of the ring code. 4. Common factors of change in the values of shift indexes vector elements using the logical transformations XOR, AND and OR. indicators on the position number of the placement in the vector of 01010101 type shift index vectors, formed using the logical operation XOR for different lengths of code combinations N. Results of transforming ring codes of the 01010101 family into shift index vectors using logical transformations XOR, AND and OR
XOR transformation
AND transformation
OR transformation
, , ∑ ∑ ⋯ ∑ 2, ; 2, . ⋯
0, | 2 2 2, ; ∑ 2
2, .
N m 3 4 3 4 8 9 1
Structure of the ring code Figure 3. Graph of the dependence of the decimal values of the elements of the vectors of shift indicators on the position number of the placement in the vector of 01010101 type shift index vectors, formed using the logical operation XOR for different lengths of code combinations N 5. Common factors of change in the values of shift indexes vector elements for ring codes family of the type 1011100 Figure 4. Graph of the dependence of the decimal values D of the elements of the shift index vectors from the position number of their placement in the shift indexes vector V 0001011 0010111 0101111 00001011 00010111 00101111 01011111 000001011 000010111 4 9 5 000101111 44666644 6 001011111 44466444 7 010111111 42444424 3 0000001011 444666444 4 0000010111 446686644 5 00000101111 446868644 1 6 0001011111 446686644 0 7 0010111111 444666444 8 0101111111 424444424
The method of converting ring codes into shift index vectors can be used to compress information transmitted over communication channels and improve the security of information transmission. In this case, at the receiving end of the communication channel, it is necessary to solve the problem of decoding the vector of shift indices into a ring code in order to obtain reliable information. The analysis of the structure of the shift index vectors, presented in this paper, allows you to see the patterns of change in the decimal values of the elements of the shift index vectors and their dependence on the length and the number of units in the code combination. An analysis of the change in the decimal values of the elements of the shift index vectors m, formed using logical XOR-transformations of the ring code of the type 011100, allows us to note that there is an unambiguous dependence of their decimal values on the number of elements N in the code combination, the number of ones m in the code combination and the value of the ratio of ones and zeros in each codeword of the ring code. At the same time, the limits of positions for placing the decimal values of the elements of the shift index vectors are uniquely defined. These patterns in the future makes it possible to develop the algorithm for converting shift index vectors into ring codes.
[1] V.B. Tolubko, S.I. Otrokh, L.N. Berkman, V.I. Kravchenko Manipulation coding of signal ndimensional multi-position constellations based on the optimal noise immunity of regular structures– Kyiv: Telecomunication and information texnology –2017 – No 3(56) – p.5-11 (in Russian). [2] S.I. Otrokh, V.A. Kuzminykh, I.O. Sosnovsky Future network in action, online life– Kyiv:
Communication –2018 – No 6 – p.42-45 (in Russian). [3] L.M. Hryshchenko Patterns of formation of ring codes. Mathematical model – Kyiv:
Communication – 2016 – No 5(123). – p.27-31 (in Ukrainian). [4] L.M. Hryshchenko Mathematical model for creating the 010101 type family ring code– Kyiv:
Communication – 2017– No 1(125). – p.58-61 (in Ukrainian). [5] E.V. Havrylko, S.I. Otrokh, V.I. Yarosh, L.M. Hryshchenko Improving the quality 8. of the future network by using the ring– Minsk: Communication Herald –2018 –No2 –p.60-64(in Russian). [6] Security of information systems (in Russian) [Electronic Resource]. Mode of access: http://intuit.valrkl.ru/course-1312/index.html. [7] S. Otrokh, V. Kuzminykh, O. Hryshchenko, Method of forming the ring codes// CEUR
WorkshopProceedings - Vol-2318, - 2018, pp. 188-198. [8] B. Zhurakovskyi, S. Toliupa, S. Otrokh, H.Dudarieva, V. Zhurakovskyi,
Coding for information systems security and viability //CEUR orkshop Proceedings, 2021,Vol 2859, pp. 71–84. [9] V. Tilavat, Y. Shukla, Simplification of procedure for decoding Reed–Solomon codes using various algorithms: an introductory survey. International Journal of Engineering Development and Research, 2(1), (2014). 279-283. [10] D. Sarwate, R. Morrison, Decoder malfunction in BCH decoders. Information Theory, IEEE
Transactions on, 36(4), 884-889. [11] E. Richard, Blahut, "Algebraic Codes for Data Transmission", chapter 7.6 "Decoding in Time
Domain", 2003. [12] S. Lin, W. Chung, Y. Han, (2014, October). Novel polynomial basis and its application to reedsolomon erasure codes. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on (pp. 316-325). IEEE. [13] Y. Wu. "Implementation of parallel and serial concatenated convolutional codes." Dissertation submitted to the Faculty of theVirginia Polytechnic Institute and State University. April, 2000. 206 p. [14] M.Vivek, N. Tilavat, Shukla Simplification of Procedure for Decoding Reed- Solomon Codes Using Various Algorithms: An Introductory Survey, 2014, INTERNATIONAL JOURNAL OF ENGINEERING DEVELOPMENT AND RESEARCH (IJEDR) (ISSN:2321-9939). [15] M. Al-Bassam, A. Sonnino, V. Buterin, I. Khoffi, Fraud and Data Availability Proofs: Detecting Invalid Blocks in Light Clients. Financial Cryptography and Data Security: 25th International Conference, FC 2021, Virtual Event, March 1–5, 2021, Revised Selected Papers, Part II, Mar 2021, Pages 279–298. https://doi.org/10.1007/978-3-662-64331-0_15. [16] S.-J. Lin, W. Chung, Y. Han, Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes. Published 13 April 2014, Computer Science, 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. Conference Paper | Publisher: IEEE. Cited by: Papers (26).