Factorial code with a given number of inversions

Abstract

EN: Factorial coding with data recovery by permutation provides complex information protection from unauthorized reading and errors in communication channel and has the property of self-synchronization. At the same time, such coding does not allow to detect all low-weight errors that leads to a relatively small increase of reliability. The purpose of this work is to develop and study the method of factorial coding with a given number of inversions aimed at increasing the reliability of information transmission, by introducing additional redundancy by choosing a class of permutations that satisfy the given criterion. Method. The main idea of the proposed method is to introduce artificial redundancy by reducing the cardinality of used permutations. Such an approach makes it possible to select from a whole set of permutations a class that possesses the necessary, pre-assigned properties. It was suggested to use the correspondence of the number of permutation inversions to a given class of residues as a sign of belonging to the permutation class in use. A theoretical evaluation of code parameters was performed. Results. Signal-code constructions for the factorial code with a given number of inversions under the order of permutations M=8 are constructed. For each of the possible classes, the cardinality, code rate, estimates of the probability of undetected error and the relative transmission rate for systems with decision feedback and independent bit errors were investigated. It is shown that the code parameters are not invariant with respect to the selected class of residues for a given modulus. The structural schemes of encoding and decoding devices are developed. Conclusions. The method of factorial coding with data recovery by permutation has been developed. The use of permutations with a number of inversions that belongs to the selected class of residues allowed increasing the reliability of transmission in exchange for the loss of code rate. UK: Актуальність. Факторіальне кодування з відновленням даних за перестановкою забезпечує комплексний захист інформації від несанкціонованого читання і помилок в каналі зв’язку і має властивість самосинхронізації. У той же час, таке кодування не дозволяє виявити всі помилки малої кратності, що призводить до порівняно невеликого показника підвищення достовірності. Метою цієї роботи є розробка та дослідження методу факторіального кодування з заданим числом інверсій, спрямованого на підвищення достовірності передавання інформації за рахунок введення додаткової надлишковості шляхом вибору класу перестановок, які відповідають заданому критерію. Метод. Основна ідея пропонованого методу полягає в штучному внесенні надлишковості за рахунок зменшення потужності використовуваних перестановок. Такий підхід дозволяє з усієї множини перестановок виділити клас, який володіє необхідними, наперед заданими, властивостями. У якості ознаки приналежності до використовуваного класу перестановок у роботі запропоновано використовувати відповідність числа їх інверсій заданому класу лишків. Виконано теоретичну оцінку параметрів коду. Результати. Побудовано сигнально-кодові конструкції для факторіального коду з заданим числом інверсій для порядку перестановок М=8. Для кожного з можливих класів досліджено потужність, швидкість коду, оцінку ймовірності невиявленої помилки і відносної швидкості передавання для систем з вирішальним зворотним зв’язком і незалежними бітовими помилками. Показано, що параметри коду не є інваріантними по відношенню до вибраного класу лишків для заданого модуля. Розроблено структурні схеми пристроїв кодування та декодування. Висновки. Отримав подальший розвиток метод факторіального кодування з відновленням даних за перестановкою, який за рахунок використання перестановок, число інверсій у яких належить обраному класу лишків, дозволив підвищити достовірність передавання в обмін на втрату швидкості коду.