1. UJIT
  2. All Volumes and Issues
  3. Volume 2 · Number 1
  4. IMPROVEMENT OF CYCLIC CODES EFFECTIVENESS BY COMBINATORIAL OPTIMIZATION METHODS

IMPROVEMENT OF CYCLIC CODES EFFECTIVENESS BY COMBINATORIAL OPTIMIZATION METHODS

UJIT.
2020;
Volume 2, Number 1
: 66-72
https://doi.org/10.23939/ujit2020.02.066
Received: February 18, 2020
Accepted: October 25, 2020

Цитування за ДСТУ: Різник В. В., Скрибайло-Леськів Д. Ю. Підвищення ефективності циклічних кодів методами комбінаторної оптимізації. Український журнал інформаційних технологій. 2020, т. 2, № 1. С. 66–72.

Citation APA: Riznyk, V. V., & Skrybaylo-Leskiv, D. Yu. (2020). Improvement of cyclic codes effectiveness by combinatorial optimization methods. Ukrainian Journal of Information Technology, 2(1), 66–72. https://doi.org/10.23939/ujit2020.02.066

Authors:
  1. V. V. Riznyk
  2. D. Yu. Skrybaylo-Leskiv
1
Lviv Polytechnic National University, Lviv, Ukraine
2
Lviv Polytechnic National University, Lviv, Ukraine

The methods of improving the cyclic codes efficiency constructed on the basis of combinatorial configurations of the type "ideal ring bundles" (IRB) s by three factors – correction ability, power of coding method and complexity of the decoding procedure are considered. The method is based on the principle of combinatorial optimization, grounded on the algebraic theory of ordered integer sequences with a circular structure, all the numbers, as well as all sums of consecutive numbers exhaust the value sofnatural row numbers. Two theoretically grounded approaches to increase of noise immunity of cyclic codes are offered: implementation of optimized IRB-code, as well as monolithic and group one. Optimized cyclic IRB-code favorably differs from the rest of the codes of this class by the highest correction capacity at the same length of code words. Optimized IRB-codes constitute a large group of cyclic codes designed on a combinatorial models with selection of corresponding relationships between the parameters of the code to achieve its specified technical characteristics. Noise protected monolithic and group codes belong to the group of self-correcting codes with a ring structure and probabilistic assessment of the level of noise protection. This property allow so instant lydetect a particular part or all invalid characters in the code word by the majority principle. Mathematical calculations have been performed to calculate the optimized ratios between the parameters of cyclic IRB-codes, under which they reach maximum correction capacity. The algorithm of constructing and increasing the power of coding methods of optimized noise-resistant IRB-codes is examined and analyzed. The concrete examples of increase efficiency of combinatorial optimization cyclic codes methods with appropriate calculations and tables are given. The comparative analysis of the IRB-codes with the Golay codes and Bose – Chaudhuri – Hocquenghe (BCH) codes with respect to correction ability, power encoding method and computational complexity of decoding procedures is carried out. The advantages and disadvantages of cyclic, and ringmonolithic and group IRB-codes in comparison with classical analogues are determined. The prospect so fusing the research results in the problems of information and communication technologies are outlined.

combinatorial configuration
computational complexity
error-correcting code
optimized cyclic code
code effectiveness
self-correcting monolithic and group code
  1. Akulinichev, Iu. P. (2010). Teoriia elektricheskoi sviazi. Tutorial. St. Petersburg: Lan, 240 p. [In Russian].
  2. Banket, V. L., Ivashchenko, P. V., & Ishchenko, M. O. (2011). Zavadostiike koduvannia v telekomunikatsiinykh systemakh. Odesa: ONAZ im. O. S. Popova, 100 p. [In Ukrainian].
  3. Banket, V. L., Ivashhenko, P. V., & Geer, A. E. (1996). Tcifrovye metody peredachi informatcii v sputnikovykh sistemakh sviazi. Odessa: UGAS, 180 p. [In Russian].
  4. BCH code. (2020). From Wikipedia, the free encyclopedia. Retrieved from: https://en.wikipedia.org/wiki/BCH_code
  5. Berrou C., Glavieux A., & Thitiumjshima, P. (1993). Near Shannon limit error correcting coding: Turbo codesiu International Conf. on Commun. Geneva, Switzerland, May 1993, pp. 1064–1070.
  6. Blahut, R. E. (1986). Theory and Practice of Error Control Codes. Moscow: Mir, 576 p.
  7. Bleikhut, R. (1986). Teoriia i praktika kodov, kontroliruiushhikh oshibki. (Trans. from English). Moscow: Mir, 576 p. [In Russian].
  8. Consultative Committee for Space Data Systems (CCSDS). (1998). Recommendations for space data systems, telemetry channel coding. Blue Book. May 1998. Retrieved from: http://www.ccsds.org.
  9. DrM D Macleod, M. A. (1993). Cyclic Code. In: Telecommunications Engineers Reference Book. MIEEE. Retrieved from: https://www.sciencedirect.com/topics/engineering/cyclic-code
  10. Giancristofaro D., Giubilei R., Novello R., Piloni V., & Toush, J. (2000). Performances of Novel DVB-RCS Standard Turbo Code and its Use in On-Board Processing Satellites. Proceedings of the EMPS workshop, in IEEE EMPS/PIMRC. London, 17–21 September, pp. 345–349.
  11. Golay, M. J. E. (1949). NotesonDigitalCoding, Proc. IRE journal. Vol. 37, 657 p.
  12. Griess, R. L. (1998). TwelveSporadicGroups. Springer, 167 p.
  13. Gryciuk, Y., & Grytsyuk, P. (2016). Implementation details for the cipher key generation Cardano permutation. Modern Problems of Radio Engineering, Telecommunications and Computer Science. Proceedings of the 13th International Conference on TCSET'2016, pp. 498–502. https://doi.org/10.1109/TCSET.2016.7452098
  14. Gryciuk, Yu., & Grytsyuk, P. (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. pp. 67–69. https://doi.org/10.1109/stc-csit.2015.7325433
  15. Hall, M. Jr. (1986). Combinatorial Theory. John Wiley & Sons, 464 p.
  16. Hrebeniuk, O. P., Melenskyi, V. D., & Korinenko, V. I. (2015). Zastosuvannia zavadostiikoho koduvannia v systemakh zviazku i peredachi danykh kompleksiv radiomonitorynhu dlia zabezpechennia dostovirnosti informatsiinoho obminu. Problemy stvorennia, vyprobuvannia, zastosuvannia ta ekspluatatsii skladnykh informatsiinykh system, 11, 44–50. Retrieved from: http://nbuv.gov.ua/UJRN/Psvz_2015_11_7. [In Ukrainian].
  17. Hrytsiuk, Yu., & Bilas, O. (2019). Visualization of Software Quality Expert Assessment. IEEE 2019 14th International Scientific and Technical Conference on Computer Sciences and Information Technologies (CSIT 2019), (Vol. 2, pp. 156–160), 17–20 September, 2019. https://doi.org/10.1109/stc-csit.2019.8929778
  18. Ideal ring bundle. (2019). Retrieved from: https://en.wikipedia.org/wiki/Ideal_ring_bundle
  19. Klark, Dzh.-ml., & Kein, Dzh. (1987). Kodirovanie s ispravleniem oshibok v sistemakh tcifrovoi sviazi. (Trans. from English) (Tcybakova, B. S. Scientific Ed.). Moscow: Radio i sviaz, 392 p. [In Russian].
  20. Kuzmin, I. V., & Kedrus, V. A. (1986). Osnovy teorii informatcii i kodirovaniia. (2nd ed. add. and revised). Kyiv: Vishha shk. Golovnoe izd-vo, 238 p. [In Russian].
  21. Lagutenko, O. I. (2002). Sovremennye modemy. Moscow: EkoTrendz, 343 p. [In Russian].
  22. Morelos-Saragosa, R. (2005). Iskusstvo pomekhoustoichivogo kodirovaniia. Metody, algoritmy, primenenie. Moscow: Tekhnosfera, 320 p. [In Russian].
  23. Panfilov, I. P., Dyrda, V. Yu., & Kapatsin, A. V. (1998). Teoriia elektrychnoho zviazku: pidruchnyk dlia studentiv vuziv I ta II rivniv akredytatsii. Kyiv: Tekhnika, 328 p. [In Ukrainian].
  24. Panin, V. V. (2004). Osnovy teorii informatcii. Chast 2. Vvedenie v teoriiu kodirovaniia. Textbook. Moscow: MIFI, FGUP ISS, 391 p. [In Russian].
  25. Peterson, W. Wesley, & Weldon, E. J. (1972). Error-correcting codes, The MIT Press; secondedition, 560 p.
  26. Piterson, U., & Ueldon, E. (1976). Kody, ispravliaiushhie oshibki. (Trans. from English) (R. L. Dobrushina i S. I. Samoilenko Scientific Eds.). Moscow: Mir, 593 p. [In Russian].
  27. Riznyk, V. V. (2019). Combinatorial optimization of multidimensional systems. Models of multidimensional intelligent systems Lviv: Publishing Lvivskoji Politekhniky, 168 p. [In Ukrainian].
  28. Riznyk, V. V. (2019). Methods of multidimensional signal processing under toroidal coordinate systems. Kyiv: Bulletin of NTUU KPI, Series Radiotekhnique. Radioapparatus building, 77, pp. 5–12. [In Ukrainian].
  29. Rotman, J. (1998). GaloisExtensions. Universitext, pp. 79–82. https://doi.org/10.1007/978-1-4612-0617-0._15
  30. Sahalovich, Y. L. (2007). The introduction to algebraic codes. Moscow: MFTI, 262 p. [In Russian].
  31. Shvartcman, V. O., Emelianov, G. A. (1979). Teoriia peredachi diskretnoi informatcii. Textbook for universities. Moscow: Sviaz, 424 p. [In Russian].
  32. Sidelnikov, V. M. (2006). Teoriia kodirovaniia. Spravochnik po printcipam i metodam kodirovaniia. Moscow: Moskovskii gosudarstvennyi universitet im. M. V. Lomonosova (MGU), 289 p. [In Russian].
  33. Skliar, B. (2003). Tcifrovaia sviaz. Teoreticheskie osnovy i prakticheskoe primenenie. (2nd ed. add. and revised). (Trans. from English). Moscow: Publishing House "Viliams", 1104 p. [In Russian].
  34. Tsymbal, V. P. (1977). Theory of information and coding. Kyiv: Vyshcha shkola, 288 p. [In Russian].
  35. Wolfram Math World. (2019). Built with Mathematical Technology. Retrieved from: http://mathworld.wolfram.com/ GolayCode.html
  36. Ziuko, A. G., & Klovskii, D. D. (1998). Teoriia elektricheskoi sviazi. Textbook for universities. (Klovskogo, D. D. Scientific Ed.). Moscow: Radio i sviaz, 432 p. [In Russian].
  37. Ziuko, A. G., Falko, A. I., & Panfilov, I. P. (1985). Pomekhoustoichivost i effektivnost sistem peredachi informatcii. (Ziuko, A. G. Scientific Ed.). Moscow: Radio i sviaz, 282 p. [In Russian].
  38. Ziuko, A. G., Klovskii, D. D., Nazarov, M. V., & Fink, L. M. (1986). Teoriia peredachi signalov. Textbook for universities. Moscow: Radio i sviaz, 304 p. [In Russian].
  39. Zolotarev, V. V., & Ovechkin, G. V. (2004). Pomekhoustoichivoe kodirovanie. Metody i algoritmy. Spravochnik. Moscow: Goriachaia liniia – Telekom, 126 p. [In Russian].