Підвищення ефективності циклічних кодів методами комбінаторної оптимізації
Date
2020-09-23
Journal Title
Journal ISSN
Volume Title
Publisher
Видавництво Львівської політехніки
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.
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.
Description
Keywords
комбінаторна конфігурація, обчислювальна складність, коректувальний код, оптимізований циклічний код, ефективність коду, самокоректувальний монолітно-груповий код, combinatorial configuration, computational complexity, error-correcting code, optimized cyclic code, code effectiveness, self-correcting monolithic and group code
Citation
Різник В. В. Підвищення ефективності циклічних кодів методами комбінаторної оптимізації / В. В. Різник, Д. Ю. Скрибайло-Леськів // Український журнал інформаційних технологій. — Львів : Видавництво Львівської політехніки, 2020. — Том 2. — № 1. — С. 66–72.