https://oldena.lpnu.ua/handle/ntb/56890| Title: | Підвищення ефективності циклічних кодів методами комбінаторної оптимізації |
| Other Titles: | Improvement of cyclic codes effectiveness by combinatorial optimization methods |
| Authors: | Різник, В. В. Скрибайло-Леськів, Д. Ю. Riznyk, V. V. Skrybaylo-Leskiv, D. Yu. |
| Affiliation: | Національний університет “Львівська політехніка” Lviv Polytechnic National University |
| Bibliographic description (Ukraine): | Різник В. В. Підвищення ефективності циклічних кодів методами комбінаторної оптимізації / В. В. Різник, Д. Ю. Скрибайло-Леськів // Український журнал інформаційних технологій. — Львів : Видавництво Львівської політехніки, 2020. — Том 2. — № 1. — С. 66–72. |
| Bibliographic description (International): | Riznyk V. V. Improvement of cyclic codes effectiveness by combinatorial optimization methods / V. V. Riznyk, D. Yu. Skrybaylo-Leskiv // Ukrainian Journal of Information Technology. — Lviv : Vydavnytstvo Lvivskoi politekhniky, 2020. — Vol 2. — No 1. — P. 66–72. |
| Is part of: | Український журнал інформаційних технологій, 1 (2), 2020 Ukrainian Journal of Information Technology, 1 (2), 2020 |
| Journal/Collection: | Український журнал інформаційних технологій |
| Issue: | 1 |
| Volume: | 2 |
| Issue Date: | 23-Sep-2020 |
| Publisher: | Видавництво Львівської політехніки |
| Place of the edition/event: | Львів Lviv |
| Keywords: | комбінаторна конфігурація обчислювальна складність коректувальний код оптимізований циклічний код ефективність коду самокоректувальний монолітно-груповий код combinatorial configuration computational complexity error-correcting code optimized cyclic code code effectiveness self-correcting monolithic and group code |
| Number of pages: | 7 |
| Page range: | 66-72 |
| Start page: | 66 |
| End page: | 72 |
| Abstract: | Розглянуто методи підвищення ефективності циклічних кодів, побудованих на підставі комбінаторних конфігурацій
типу "ідеальних кільцевих в'язанок" (ІКВ) за трьома чинниками – коректувальною здатністю, потужністю методу
кодування та складністю процедури декодування. В основу методики покладено принцип комбінаторної оптимізації, який
ґрунтується на алгебричній теорії впорядкованих цілочислових послідовностей з кільцевою структурою, причому усі
числа разом з усіма сумами поруч розміщених чисел вичерпує значення чисел натурального ряду. Запропоновано два
теоретично обґрунтовані підходи до підвищення завадостійкості циклічних кодів: впровадженням оптимізованого
ІКВ-коду та монолітно-групового. Оптимізований циклічний ІКВ-код вигідно відрізняється від решти кодів цього класу вищою
корегувальною здатністю при тій же довжині кодових слів. Оптимізовані ІКВ-коди становлять велику групу циклічних
кодів, побудованих на комбінаторній різноманітності математичних моделей з добором відповідного співвідношення
між параметрами коду для досягнення його заданих технічних характеристик. Завадостійкі монолітно-групові коди
належать до групи самокоректувальних кодів з кільцевою структурою та ймовірнісною оцінкою рівня завадостійкості.
Ця властивість дає змогу за мажоритарним принципом миттєво виявляти певну частину, або усі хибні символи у
кодовому слові. Здійснено математичні розрахунки для обчислення оптимізованих співвідношень між параметрами
циклічних ІКВ-кодів, за яких вони досягають максимальної коректувальної спроможності. Розглянуто і проаналізовано
алгоритм побудови та збільшення потужності методів кодування оптимізованих завадостійких ІКВ-кодів. Наведено
конкретні приклади підвищення ефективності циклічних кодів методами комбінаторної оптимізації з відповідними
розрахунками і таблицями. Проведено порівняльний аналіз ІКВ-кодів з кодами Голея та Боуза-Чоудхурі-Хоквінгема (БЧХ) за
коректувальною здатністю, потужністю методу кодування та обчислювальною складністю процедур декодування.
З'ясовано переваги та недоліки циклічних і кільцевих монолітно-групових ІКВ-кодів порівняно з класичними аналогами.
Окреслено перспективи використання результатів дослідження в задачах інформаційно-комунікаційних технологій. 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. |
| URI: | https://ena.lpnu.ua/handle/ntb/56890 |
| Copyright owner: | © Національний університет “Львівська політехніка”, 2020 |
| URL for reference material: | https://en.wikipedia.org/wiki/BCH_code http://www.ccsds.org https://www.sciencedirect.com/topics/engineering/cyclic-code https://doi.org/10.1109/TCSET.2016.7452098 https://doi.org/10.1109/stc-csit.2015.7325433 http://nbuv.gov.ua/UJRN/Psvz_2015_11_7 https://doi.org/10.1109/stccsit.2019.8929778 https://en.wikipedia https://doi.org/10.1007/978-1-4612-0617-0._15 http://mathworld.wolfram.com/GolayCode.html |
| References (Ukraine): | [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/stccsit.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]. Ukrainian Journal of Information Technology, 2020, 72 vol. 2, no. 1 [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]. |
| References (International): | [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/stccsit.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]. Ukrainian Journal of Information Technology, 2020, 72 vol. 2, no. 1 [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]. |
| Content type: | Article |
| Appears in Collections: | Ukrainian Journal of Information Technology. – 2020. – Vol. 2, No. 1 |
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2020v2n1_Riznyk_V_V-Improvement_of_cyclic_codes_66-72.pdf | 1.62 MB | Adobe PDF | View/Open | |
| 2020v2n1_Riznyk_V_V-Improvement_of_cyclic_codes_66-72__COVER.png | 1.89 MB | image/png | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.