1. SISN
  2. All Volumes and Issues
  3. Volume 14, 2023
  4. Methods of Correcting Errors in Messages Encoded by Fibonacci Matrices

Methods of Correcting Errors in Messages Encoded by Fibonacci Matrices

SISN.
2023;
Volume 14
: pp. 327 - 347
https://doi.org/10.23939/sisn2023.14.327
Authors:
  1. Pavlo Grytsiuk
  2. Lubomyr Sikora
  3. Yurii Hrytsiuk
1
Lviv Polytechnic National University, Department of Automated Control Systems
2
Lviv Polytechnic National University, Lviv, Ukraine
3
Lviv Polytechnic National University, Lviv, Ukraine

The main problems of detection and available methods of correcting errors in encoded messages with Fibonacci matrices, which make it possible to find and correct one, two and three errors in the same or different lines of the code word, are analyzed. It has been found that even in the last decade, many scientists have published a significant number of various publications, each of which to one degree or another substantiates the expediency of using Fibonacci matrices for (de)coding data. It has been established that the elements of a codeword obtained by multiplying a message block by a Fibonacci matrix have many useful properties, which are the basis for the method for detecting and correcting errors in them. The statement is given, according to which the ratio of the corresponding elements of the code word is close to the golden ratio, which is important for the existing methods of correcting potential errors. This property of the elements makes it possible to identify the presence of double and triple false elements by checking whether their ratios belong to a fixed interval. It is found that the false affiliation indicates that there are two errors in different lines of the codeword, which require solving the corresponding Diophantine equations, the suitability of the solution of which must satisfy certain conditions for error correction. It was found that in order to correct two errors in one line of the code word, a condition was introduced according to which the set of blocks of the input message should contain only minimal matrices, which makes it possible to take the smallest solutions of the Diophantine equation, the suitability of which is specified by test ratios. It was found that in order to correct three errors in a codeword, it is necessary to check whether the relations of its corresponding elements belong to a fixed interval and to solve a nonlinear Diophantine equation, the implementation of which is extremely difficult. The proposed approach boils down to trial and error, according to which you first need to find the exact location of the erroneous elements, and only then correct them according to the appropriate methods.

Fibonacci numbers
recurrent sequence
code word
Golden ratio
Diophantine equation
error correction method
  1. Basu, M., & Prasad, B. (2011). Coding theory on the (m,t)-extension of the Fibonacci p-numbers. Discrete Mathematics, Algorithms and Applications, Vol. 3, 259–267. https://doi.org/10.1142/S1793830911001097
  2. Basu, Manjusri, & Das, Monojit. (2017). Coding theory on generalized Fibonacci n-step polynomials. Journal of Information and Optimization Sciences, Vol. 38, Issue 1, 83–131. https://doi.org/10.1080/02522667.2016.1160618
  3. Basu, Manjusri, & Prasad, Bandhu. (2009). The generalized relations among the code elements for Fibonacci coding theory. Chaos, Solitons, & Fractals, Vol. 41, Iss. 5(15), 2517–2525. https://doi.org/10.1016/j.chaos.2008.09.030
  4. Basu, Manjusri, & Prasad, Bandhu. (2009, November). Coding theory on the m-extension of the Fibonacci p-numbers. Chaos, Solitons, & Fractals, Vol. 42, Iss. 4, 30, 2522–2530. https://doi.org/10.1016/j.chaos.2009.03.197
  5. Bellini, Emanuele, Marcolla, Chiara, & Murru, Nadir. (2020, March). On the decoding of 1-Fibonacci error correcting codes. Discrete Mathematics, Algorithms and Applications, Vol. 13, No. 05, 2150056. https://doi.org/10.13140/RG.2.2.27280.97281;       https://doi.org/10.1142/S1793830921500567
  6. Esmaeili, M., Esmaeili, M., & Gulliver, T. A. (2011). High-rate Fibonacci polynomial codes. In: Proceedings of IEEE International Symposium on Information Theory Proceedings, St. Petersburg, Russia, 1921–1924. https://doi.org/10.1109/ISIT.2011.6033886
  7. Esmaili, M., Moosavi, M., & Gulliver, T. A. (2017, January). A new class of Fibonacci sequence based error correcting codes. Cryptography and Communications, Vol. 9, 379–396. https://doi.org/10.1007/s12095-015-0178-x
  8. Esmaili, Mostafa, & Esmaeili, Morteza. (2010). A Fibonacci-polynomial based coding method with error detection and correction. Computers and Mathematics with Applications, 60, 2738–2752. https://doi.org/10.1016/j.camwa.2010.08.091
  9. Gryciuk, Yurij, Grytsyuk, Pavlo. (2015). Perfecting of the matrix Affine cryptosystem information security. Computer Science and Information Technologies: Proceedings of Xth International Scientific and Technical Conference (CSIT'2015), 14–17 September, 2015, 67–69. https://doi.org/10.1109/stc-csit.2015.7325433
  10. Grytsiuk, P. Yu., & Hrytsiuk, Yu. I. (2015). Peculiarities of the implementation of the matrix Athena cryptosystem of information protection. Scientific Bulletin of UNFU, 25(5), 346–356. URL: https://nv.nltu.edu.ua/index.php/journal/article/view/1092
  11. Hrytsiuk, Yu. I., & Grytsiuk, P. Yu. (2015). Implementation of cryptographic transformations using Fibonacci G()-matrices. Mathematical and software support of intelligent systems: materials of the 13th International Scientific and Practical Conference, 53–54, November 18–20, 2015, Dnipropetrovsk, Ukraine. Dnipropetrovsk: Department of Dnipropetrovsk National University named after Olesya Honchara.
  12. Hrytsiuk, Yu. I., & Grytsiuk, P. Yu. (2015). Methods and means of generating Fibonacci Qp-matrices – keys for implementing cryptographic transformations. Scientific Bulletin of UNFU, 25(6), 334–351. URL: https://nv.nltu.edu.ua/index.php/journal/article/view/974
  13. Hrytsiuk, Yu. I., & Grytsiuk, P. Yu. (2016). Features of generating Fibonacci Qp-matrices – keys for implementing cryptographic transformations. Bulletin of the Lviv Polytechnic National University. Series: Computer Science and Information Technology, Vol. 843, 251–263. URL: https://vlp.com.ua/taxonomy/term/3448
  14. Hrytsiuk, Yu. I., & Grytsiuk, P. Yu. (2016). Features of generating Fibonacci Gp()-matrices for implementation of cryptographic transformations. Information extraction and processing: interdepartmental collection of scientific papers, 43(119), 86–95.
  15. Hrytsiuk, Yuriy, & Grytsyuk, Pavlo (2016). Generation of Fibonacci Qp()-matrices – keys for data encryption. Information protection and security of information systems: materials of the 5th International Scientific and Technical Conference,  39–40, June 02–03, 2016, Lviv, Ukraine. Lviv: Lviv Polytechnic State University.
  16. Hrytsiuk, Yuriy, Grytsyuk, Pavlo, Dyak, Tetiana, & Hrynyk, Heorhiy. (2019). Software Development Risk Modeling. IEEE 2019 14th International Scientific and Technical Conference on Computer Sciences and Information Technologies (CSIT 2019), Vol. 2,  134–137, 17–20 September, Lviv, Ukraine. Lviv: Lviv Polytechnic National University, 206 p. https://doi.org/10.1109/stc-csit.2019.8929778
  17. Kuhapatanakul, K. (2015). The Lucas p-matrix. International Journal of Mathematical Education in Science and Technology. https://doi.org/10.1080/0020739X.2015.1026612
  18. Lagun, A. E., & Hrytsiuk, Yu. I. (2016). Information theory and coding. Tutorial. Lviv: SPOLOM Publishing House, 168 p.
  19. Nihal Tas, Sumeyra Ucar, Nihal Yilmaz Ozgur, & Oztunc Kaymak. (2018). A new coding/decoding algorithm using Fibonacci numbers. Discrete Mathematics, Algorithms and Applications, Vol. 10, No. 02, 1850028. https://doi.org/10.1142/S1793830918500283;      https://doi.org/10.48550/arXiv.1712.02262
  20. Prasad, Bandhu. (2014). Coding theory on (h(x), g(y))-extension of Fibonacci p-numbers polynomials. Universal Journal of Computational Mathematics, Vol. 2(1), 6–10. https://doi.org/10.13189/ujcmj.2014.020102
  21. Prasad, Bandhu. (2014). High  rates of  Fibonacci polynomials coding theory. Discrete Mathematics, Algorithms and Applications, Vol. 06, No. 04, 1450053. https://doi.org/10.1142/S1793830914500530
  22. Prasad, Bandhu. (2016). Coding theory on Lucas p-numbers. Discrete Mathematics, Algorithms and Applications, Vol. 08, No. 04, 1650074. https://doi.org/10.1142/S1793830916500749
  23. Prasad, Bandhu. (2019). The generalized relations among the code elements for a new complex Fibonacci matrix. Discrete Mathematics, Algorithms and Applications, Vol. 11, No. 02, 1950026. https://doi.org/10.1142/S1793830919500265
  24. Samoilenko, M. I., & Ufimtseva, V. B. (2012). On the possibilities of using Fibonacci arithmetic to increase the efficiency of cryptographic transformations. Trinitarian Academy, 77–656. URL: http://www/trinitas/ru/rus/doc/0232/013a/02322115/htm. [In Russian].p
  25. Samoilenko, N. I., & Ufimtseva, V. B. (2003). Properties of p-numbers and Stakhov Qn -matrices in the ring of  integers  Z/(q).  Radioelectronics  and  computer  science.  Kharkov:  KNURE.  No.  1,            111–115.  URL: https://cyberleninka.ru/article/n/svoystva-r-chisel-i-qp-matrits-stahova-v-koltse-tselyh-chisel-z-q.    [In    Russian].
  26. Sentürk, G. Y., Gürses, N., & Yüce, S. (2022). Construction of dual-generalized complex Fibonacci and Lucas quaternions. Carpathian Mathematical Publications, 14(2), 406–418. https://doi.org/10.15330/cmp.14.2.406-418
  27. Sergio Falcon. (2017, Jan.-Feb.). On the K-Fibonacci Hankel and the 4 X 4 Skew Symmetric K-Fibonacci Matrices. IOSR Journal of Mathematics (IOSR-JM), 13(01), 52–58. https://doi.org/10.9790/5728-1301035258
  28. Singh, Sweta, Kanwar, Neeraj, & Zindani, Divya. (2023, April). Linear diophantine uncertain linguistic- based prospect theory approach for performance evaluation of islanded microgrid-system scenarios. Clean Energy, Vol. 7, Iss. 2, 263–282. https://doi.org/10.1093/ce/zkac066
  29. Skuratovsky, R. V. (2017). Factorization of an integer of the form n = pq. Mathematical and computer modeling. Series: Physical and mathematical sciences: collection of scientific papers. Kamianets-Podilskyi National University. Vol. 15,  201–207. URI: http://dspace.nbuv.gov.ua/handle/123456789/133957
  30. Slyusarenko, V. (2008). Fibonacci numbers and the golden ratio. Mathematics. Kyiv: School World Publishing House, No. 8(452),  18–24.
  31. Slyusarenko, V. (2008). Fibonacci numbers and the golden ratio. Math. Kyiv: School World Publishing House, No. 8(452),  18–24.
  32. Stakhov, A. P. (2006, October). Fibonacci matrices, a generalization of the “Cassini formula”, and a new coding theory. Chaos, Solitons, & Fractals, Vol. 30, Iss. 1, 56–66. https://doi.org/10.1016/j.chaos.2005.12.054
  33. Stakhov, Alexey, & Olsen, Scott. (2009). The Mathematics of Harmony: From Euclid to Contemporary Mathematics and Computer Science. Series on Knots and Everything, 22. World Scientific Publishing Company; First Edition, 748 p. URL: https://www.amazon.com/Mathematics-Harmony-Contemporary-Computer- Everything/dp/981277582X
  34. Sundarayya, P., & Prasad, M. G. Vara. (2019). Coding theory on Pell-Lucas p-numbers. Journal of Physics: Conference Series, 1344. https://doi.org/10.1088/1742-6596/1344/1/012017
  35. Ufimtseva, V. B., & Karpenko, N. Yu. (2015). Using sequences of generalized Fibonacci numbers in cryptographic algorithms. Information processing systems. Vol. 8, pp. 106–110. URL: http://nbuv.gov.ua/UJRN/soi_2015_8_24. [In Russian].
  36. Ufimtseva, Victoria (2005). On the possibilities of using Fibonacci arithmetic to increase the efficiency of cryptographic transformations. Legal, regulatory and metrological support of the information protection system in Ukraine: scientific and technical collection. Vol. 10, 137–142. URL: https://ela.kpi.ua/handle/123456789/11453. [In Russian].