1. UJIT
  2. Всі випуски
  3. Том 2 · Номер 1 · 2020
  4. ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЦИКЛІЧНИХ КОДІВ МЕТОДАМИ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ

ПІДВИЩЕННЯ ЕФЕКТИВНОСТІ ЦИКЛІЧНИХ КОДІВ МЕТОДАМИ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ

UJIT.
2020;
Випуск 2, Номер 1
: 66-72
https://doi.org/10.23939/ujit2020.02.066
Надіслано: Лютий 18, 2020
Прийнято: Жовтень 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

Автори:
  1. В. В. Різник
  2. Д. Ю. Скрибайло-Леськів
1
Національний університет "Львівська політехніка", м. Львів, Україна
2
Національний університет "Львівська політехніка", м. Львів, Україна

Розглянуто методи підвищення ефективності циклічних кодів, побудованих на підставі комбінаторних конфігурацій типу "ідеальних кільцевих в'язанок" (ІКВ) за трьома чинниками – коректувальною здатністю, потужністю методу кодування та складністю процедури декодування. В основу методики покладено принцип комбінаторної оптимізації, який ґрунтується на алгебричній теорії впорядкованих цілочислових послідовностей з кільцевою структурою, причому усі числа разом з усіма сумами поруч розміщених чисел вичерпує значення чисел натурального ряду. Запропоновано два теоретично обґрунтовані підходи до підвищення завадостійкості циклічних кодів: впровадженням оптимізованого ІКВ-коду та монолітно-групового. Оптимізований циклічний ІКВ-код вигідно відрізняється від решти кодів цього класу вищою корегувальною здатністю при тій же довжині кодових слів. Оптимізовані ІКВ-коди становлять велику групу циклічних кодів, побудованих на комбінаторній різноманітності математичних моделей з добором відповідного співвідношення між параметрами коду для досягнення його заданих технічних характеристик. Завадостійкі монолітно-групові коди належать до групи самокоректувальних кодів з кільцевою структурою та ймовірнісною оцінкою рівня завадостійкості.

Ця властивість дає змогу за мажоритарним принципом миттєво виявляти певну частину, або усі хибні символи у кодовому слові. Здійснено математичні розрахунки для обчислення оптимізованих співвідношень між параметрами циклічних ІКВ-кодів, за яких вони досягають максимальної коректувальної спроможності. Розглянуто і проаналізовано алгоритм побудови та збільшення потужності методів кодування оптимізованих завадостійких ІКВ-кодів. Наведено конкретні приклади підвищення ефективності циклічних кодів методами комбінаторної оптимізації з відповідними розрахунками і таблицями. Проведено порівняльний аналіз ІКВ-кодів з кодами Голея та Боуза-Чоудхурі-Хоквінгема (БЧХ) за коректувальною здатністю, потужністю методу кодування та обчислювальною складністю процедур декодування. З'ясовано переваги та недоліки циклічних і кільцевих монолітно-групових ІКВ-кодів порівняно з класичними аналогами. Окреслено перспективи використання результатів дослідження в задачах інформаційно-комунікаційних технологій.

комбінаторна конфігурація
обчислювальна складність
коректувальний код
оптимізований циклічний код
ефективність коду
самокоректувальний монолітно-груповий код
  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].