Методи достовірного передавання інформації в системах з нероздільним факторіальним кодуванням даних за високої ймовірності бітової помилки

Abstract

Ступка Б.А. Методи достовірного передавання інформації в системах з нероздільним факторіальним кодуванням даних за високої ймовірності бітової помилки. – Кваліфікаційна наукова праця на правах рукопису. Дисертація на здобуття ступеня доктора філософії за спеціальністю 123 – Комп’ютерна інженерія. – Черкаський державний технологічний університет, Черкаси, 2024. Дисертаційна робота спрямована на вирішення актуальної науково-технічної задачі, що полягає в забезпеченні достовірності передавання інформації на основі використання нероздільного факторіального кодування даних. Ця задача передбачає необхідність створення методів встановлення циклової синхронізації та методу достовірного передавання перестановки в системах з нероздільним факторіальним кодуванням даних з каналами зв’язку з високою ймовірністю бітової помилки. Проведений у роботі аналіз методів нероздільного факторіального кодування даних свідчить, що вони одночасно вирішують проблеми криптографічного захисту інформації та завадостійкого кодування. Виконано аналіз методів циклової синхронізації. Показано, що існують методи, які використовують підхід грубої сили та передбачають буферизацію даних двох довжин кадру й декодування за кожним можливим зміщенням синхрокомбінації. Інші методи для підвищення ефективності циклової синхронізації використовують операцію XOR для синхрокомбінацій з потоком даних. Існують також методи циклової синхронізації, які не використовують символи преамбули та передбачають адаптацію формату кадру. Разом з тим, розглянуті методи циклової синхронізації мають обмеження, що призводять до значної обчислювальної складності алгоритмів, що їх реалізують, і неможливості застосування в комунікаційних системах із блоковими кодами. Розглянуто існуючі застосування, що реалізують нероздільне факторіальне кодування, зокрема трьохетапний криптографічний протокол на основі перестановок, який дає змогу захищеним шляхом передавати повідомлення між двома сторонами без необхідності передавання або оголошення відкритого чи закритого ключа. Разом з тим, особливістю таких протоколів є те, що вони потребують більш високих показників достовірності, оскільки для передавання одного повідомлення дані передають тричі, що збільшує ймовірність їх ураження завадою, що особливо відчутно в умовах високого їх рівня. Виконаний аналіз дав змогу чітко сформулювати задачі роботи. Вони полягають у розробці методу циклової синхронізації для комунікаційних систем передавання інформації з нероздільним факторіальним кодуванням, у тому числі, за ймовірності бітової помилки, близької до 0.5, а також у розробці методу достовірного передавання інформації в системах зв’язку з нероздільним факторіальним кодуванням даних за такої ж імовірності бітової помилки. З метою верифікації та дослідження ефективності розроблених методів циклової синхронізації, достовірного передавання інформації, а також для формулювання рекомендацій щодо їх застосування, заключна задача дисертаційного дослідження полягає у виконанні порівняльної експериментальної оцінки ефективності розроблених методів. У дисертаційній роботі представлено вперше розроблений метод циклової синхронізації, який за рахунок використання як синхрокомбінації перестановки чисел, її поділу на префіксну та суфіксну частини, а також за рахунок мажоритарної обробки прийнятих фрагментів, дозволяє забезпечити циклову синхронізацію приймальної та передавальної станцій комунікаційних систем передавання інформації з нероздільним факторіальним кодуванням. Розроблено структурну схему пристрою циклової синхронізації. Побудовано програмну модель передавання даних, в якій реалізовано розроблений алгоритм встановлення циклового синхронізму Розроблений метод дає змогу для довжини кодового слова в 8 елементів (24 біти) в каналах зв’язку з імовірністю бітової помилки отримати значення відносної частоти встановлення правильного синхронізму та відносної частоти хибної синхронізації для максимального коефіцієнту накопичення фрагментів (2174472 біт). У той же час, розроблений метод дає змогу забезпечити встановлення синхронізму, в середньому, після отримання 4, 7, 15, 54, 14526 фрагментів (96, 168, 360, 1296, 348624 біт) за ймовірностей бітової помилки . відповідно. Набув подальшого розвитку метод циклової синхронізації нероздільного факторіального коду, який за рахунок використання як синхрокомбінації перестановки, яка має максимальне значення мінімальної відстані Хеммінга від її двійкового представлення до всіх її циклічних зсувів, а також за рахунок кореляційної та мажоритарної обробки фрагментів даних, що передаються каналом зв'язку, де довжина фрагмента дорівнює довжині синхрокомбінації, дозволяє забезпечити циклову синхронізацію за ймовірності бітової помилки, близької до 0.5. Розроблено структурну схему пристрою циклової синхронізації. Побудовано програмну модель передавання даних, в якій реалізовано розроблений алгоритм встановлення циклового синхронізму. Застосування розробленого методу циклової синхронізації дозволило забезпечити ймовірність правильної синхронізації та ймовірність хибної синхронізації у модельній системі передавання даних з незалежними бітовими помилками з імовірністю їх появи для синхрокомбінації-перестановки з 8 елементів (24 бітів) за максимального коефіцієнту накопичення (734472 біт) та за середньої кількості прийнятих фрагментів, що необхідна для встановлення синхронізму, 15787 фрагментів (378888 біт). Розроблено та досліджено алгоритм перемішування прийнятих з каналу зв’язку фрагментів, що дозволяє додатково зменшити необхідний коефіцієнт накопичення для встановлення циклового синхронізму. Так, різниця між середнім значенням кількості накопичених фрагментів для систем синхронізації з перемішуванням і без перемішування накопичених фрагментів з параметрами, визначеними для ймовірності бітової помилки та довжини синхрокомбінації-перестановки 8 елементів (24 біта), дорівнює 4607 фрагментам (110 568 бітам) за , 9.1 фрагментам за і 2.6 фрагментам за , що зменшує необхідний час встановлення синхронізму. Розроблений метод може бути ефективним для реалізації не тільки в системах з нероздільним факторіальним кодуванням, а й у класичних системах передавання даних, де використовується стандартний роздільник між кадрами. Вперше розроблено метод достовірного передавання перестановок, який за рахунок подання кожного елементу перестановки, що передається, у вигляді циклічного двійкового зсуву перестановки-переносника, що має максимальне значення мінімальної відстані Хеммінга від її двійкового представлення до всіх її циклічних зсувів, дозволяє забезпечити інформаційний обмін трьохетапним криптографічним протоколом на основі перестановок за ймовірності бітової помилки, близької до 0,5. Для підвищення достовірності передавання перестановок метод також використовує мажоритарну та кореляційну обробку фрагментів, отриманих з каналу зв'язку. Розроблено математичну модель системи передавання даних. Розроблено та реалізовано алгоритм, що застосовує запропонований метод та дає змогу за ймовірності бітової помилки досягти ймовірності приймання перестановок без помилок і ймовірність невиявленої помилки . Результати побудованої імітаційної програмної моделі системи передавання даних підтверджують ефективність розробленого методу в порівнянні з традиційним методом DSSS: для досягнення заданої ймовірності приймання перестановок без помилок і ймовірності невиявленої помилки, що вказані вище, метод DSSS потребує приймання фрагментів ( біт), в той час, як розроблений метод, потребує фрагментів ( біт). У заключній частині дисертаційної роботи досліджено ефективність методів циклової синхронізації систем передавання інформації з нероздільним факторіальним кодуванням: методу, який базувався на використанні як синхрокомбінації перестановки чисел з її поділом на префіксну та суфіксну частини, та методу, що використовує як синхрокомбінацію перестановку, що має максимальне значення мінімальної відстані Хеммінга від її двійкового представлення до всіх її циклічних зсувів. Розроблено та описано структурні схеми імітаційних моделей системи передавання даних для кожного з методів. Описано середовище розробки та параметри апаратної частини, на якій виконувалося моделювання. Побудовано програмні імітаційні моделі систем передавання даних, у яких реалізовано алгоритми встановлення циклового синхронізму для кожного з наведених методів. Обґрунтовано основні модулі, які використовувалися як для реалізації моделей, так і для інтерпретації результатів. Розроблено рекомендації щодо застосування розроблених методів циклової синхронізації в каналах зв’язку з високою ймовірністю бітової помилки з використанням нероздільного факторіального кодування. Зокрема, продемонстровано, що за параметрів циклової синхронізації, визначених для , імовірність правильної синхронізації є вищою для методу на основі поділу синхрокомбінації на префіксну й суфіксну частини за і вищою для методу на основі кореляційної обробки за . Разом з тим, варто враховувати, що реалізація методу на основі поділу синхрокомбінації на префіксну й суфіксну частини має вищі значення ймовірності хибного фазування за у порівняння з методом на основі кореляційної обробки. Для прикладу, швидкість встановлення циклового синхронізму за та вища для методу на основі поділу синхрокомбінації на префіксну й суфіксну частини, в середньому, на 73.29% та 11,83 % відповідно, а за - вища для методу на основі кореляційної обробки, в середньому, на 56,94%; у той же час, відносна частота хибної синхронізації за , та є меншою для методу на основі кореляційної обробки (0 для 10000 експериментів) порівняно з методом на основі поділу синхрокомбінації на префіксну й суфіксну частини (0.003, 0.006 та 0.008 відповідно, для 10000 експериментів). Stupka B.A. Methods of reliable information transmission in systems with non-separable factorial data coding at high bit error probability. – Qualifying scientific work on the rights of the manuscript. Dissertation for the degree of Doctor of Philosophy in specialty 123 – Computer Engineering. – Cherkasy State Technological University, Cherkasy, 2024. The dissertation is aimed at solving an urgent scientific and technical problem, which is to increase the reliability of information transmission through the use of factorial data coding. This task implies the need to create methods for establishing cyclic synchronization and a method for reliable permutation transmission using non-separable factorial coding in communication channels with a high bit error probability. The analysis of non-separable factorial data coding methods in this paper shows that they simultaneously solve the problems of cryptographic information protection and noise-resistant coding. The methods of cyclic synchronization are analyzed. It is shown that there are methods that use a brute force approach and involve buffering data of two frame lengths and decoding for each possible synchronization offset. Other methods use an XOR operation to synchronize the data stream to increase the efficiency of the cyclic synchronization. There are also cyclic synchronization methods that do not use preamble characters and provide for adaptation of the frame format. At the same time, the considered methods of cyclic synchronization have limitations that lead to significant computational complexity of the algorithms that implement them and the impossibility of using them in communication systems with block codes. Existing applications that implement non-separable factorial coding are considered, in particular a three-pass permutation-based cryptographic protocol that allows secure transmission of messages between two parties without the need to transmit or declare a public or private key. At the same time, the peculiarity of such protocols is that they require higher reliability indicators, since data is transmitted three times to transmit one message, which increases the probability of its being affected by interference, which is especially noticeable in conditions of high security. The analysis made it possible to clearly formulate the tasks of the work. They consist in developing a method of cyclic synchronization for communication systems of information transmission with non-separable factorial coding, including with a bit error probability close to 0.5, as well as in developing a method of reliable information transmission in communication systems with non-separable factorial data coding with the same bit error probability. In order to verify and study the effectiveness of the developed methods of cyclic synchronization, reliable information transmission, as well as to formulate recommendations for their application, the final task of the dissertation research is to perform a comparative experimental evaluation of the effectiveness of the developed methods. The thesis presents the first developed method of cyclic synchronization, which, by using a permutation of numbers as a syncword, its division into prefix and suffix parts, as well as by majority processing of received fragments, allows for cyclic synchronization of the receiving and transmitting stations of communication systems for transmitting information with non-separable factorial coding. A structural diagram of the cyclic synchronization device is developed. A software model of data transmission is built, in which the developed algorithm for establishing cyclic synchronism is implemented The developed method allows for a codeword length of 8 elements (24 bits) in communication channels with a bit error probability , get value of relative frequency setting the correct synchronization and the relative frequency of false synchronization , for the parameters , for maximum accumulation rate (2174472 bits). At the same time, the developed method makes it possible to ensure synchronization, on average, after obtaining 4, 7, 15, 54, 14526 fragments (96, 168, 360, 1296, 348624 bits) with bit error probabilities of , accordingly. The method of cyclic synchronization of an indivisible factorial code has been further developed, which, by using as a syncword a permutation that has the maximum value of the minimum Hamming distance from its binary representation to all its cyclic shifts, and also due to correlation and majoritarian processing of data fragments transmitted by the communication channel, where the length of the fragment is equal to the length of the syncword, allows to provide cyclic synchronization with a bit error probability close to 0.5. A block diagram of the cyclic synchronization device was developed. A software model of data transmission was built, which implements the developed algorithm for establishing cyclic synchronization. The application of the developed method of cyclic synchronization made it possible to ensure the probability of correct synchronization and the possibility of false synchronization in the model system transmission of data with independent bit errors with the probability of their occurrence for a syncword-permutation of 8 elements (24 bits) with the maximum accumulation factor (734472 bits) and with the average number of received fragments required to establish synchronization, 15787 fragments (378888 bits). An algorithm for mixing fragments received from the communication channel has been developed and studied, which allows to further reduce the required accumulation factor for establishing cyclic synchronism. Thus, the difference between the average value of the number of accumulated fragments for synchronization systems with and without mixing of accumulated fragments with parameters defined for the bit error probability and the length of the syncword-permutation of 8 elements (24 bits), is equal to 4607 fragments (110 568 bits) for , 9.1 fragments for і 2.6 fragments for , which reduces the required time for establishing synchronization. The developed method can be effective for implementation not only in systems with non-separable factorial coding, but also in classical data transmission systems that use a standard frame separator. For the first time, a method of reliable transmission of permutations has been developed, which, by representing each element of the transmitted permutation as a cyclic binary shift of the carrier permutation, which has the maximum value of the minimum Hamming distance from its binary representation to all its cyclic shifts, allows for information exchange using a three-pass cryptographic protocol based on permutations with a bit error probability close to 0.5. To increase the reliability of permutation transmission, the method also uses majority and correlation processing of fragments received from the communication channel. Developed mathematical model of the data transmission system. An algorithm is developed and implemented that applies the proposed method and allows, given the bit error probability achieve the probability of accepting permutations without errors and the probability of an undetected error . The results of the constructed simulation software model of the data transmission system confirm the effectiveness of the developed method in comparison with the traditional DSSS method: to achieve the given probability of accepting permutations without errors and the probability of an undetected error, as indicated above, the DSSS method requires accepting fragments ( bits), while the developed method requires fragments ( bits). The final part of the dissertation investigates the effectiveness of methods of cyclic synchronization of information transmission systems with non-separable factorial coding: a method based on the use of a permutation of numbers with its division into prefix and suffix parts as a syncword, and a method that uses as a syncword a permutation that has the maximum value of the minimum Hamming distance from its binary representation to all its cyclic shifts. The structural diagrams of the simulation models of the data transmission system for each of the methods are developed and described. The development environment and parameters of the hardware on which the simulation was performed are described. Software simulation models of data transmission systems are built, which implement algorithms for establishing cyclic synchronism for each of the above methods. The main modules used to implement the models and to interpret the results are substantiated. Recommendations for the application of the developed methods of cyclic synchronization in communication channels with a high bit error probability using non-separable factorial coding are developed. In particular, the probability of correct synchronization is higher for the method based on the division of the syncword into prefix and suffix parts by and higher for the method based on correlation processing for . At the same time, it should be borne in mind that the implementation of the method based on the division of the syncword into prefix and suffix parts has a higher probability of false phasing compared to the method based on correlation processing. For example, the speed of establishing cyclic synchronism for and is higher for the method based on the division of the syncword into prefix and suffix parts, on average, by 73.29% and 11.83%, respectively, and for - is higher for the method based on correlation processing, on average, by 56.94%; at the same time, the relative frequency of false synchronization for , and is smaller for the method based on correlation processing (0 for 10000 experiments) compared to the method based on dividing the syncword into prefix and suffix parts (0.003, 0.006 and 0.008, respectively, for 10000 experiments).