DOI: https://doi.org/10.15588/1607-3274-2018-2-16

FACTORIAL CODE WITH A GIVEN NUMBER OF INVERSIONS

E. V. Faure, A. I. Shcherba, A. A. Kharin

Abstract


Context. 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.

Keywords


factorial coding; permutation; inversion; redundancy; class of residues; reliability of transmission; relative transmission rate.

References


Faure E’. V., Shvydkii V. V., and Shcherba A. I. Kontrol’ celostnosti informacii na osnove faktorial’noj sistemy schisleniya, Journal of Baku Engineering University, Mathematics and Computer Science, 2017, Vol. 1, No. 1, pp. 3–13.

Faure E’. V., Shvydkii V. V., and Shcherba V. A. Kombinirovannoe faktorial’noe kodirovanie i ego svoistva, Radіoelektronіka, іnformatika, upravlіnnya, 2016, No. 3, pp. 80–86. DOI:

15588/1607-3274-2016-3-10.

Rudnyc’kyj V. M., Faure E’. V., Shvydkyj V. V., and Shherba A. I. Pat. 107655 Ukrai’na, MPK G06F 21/64 (2013.01), H04L 1/16 (2006.01). Sposib kontrolju cilisnosti informacii’; zajavnyk ta patentovlasnyk Cherkas’kyj derzhavnyj tehnologichnyj universytet. – № a201505937; zajavl. 16.06.2015; opubl. 24.06.2016, Bjul. № 12.

Rudnyc’kyj V. M., Faure E’. V., Shvydkyj V. V., and Shherba A. I. Pat. 107657 Ukrai’na, MPK H03M 13/09 (2006.01), H04K 1/06 (2006.01), G09C 1/06 (2006.01). Sposib kombinovanogo

koduvannja informacii’; zajavnyk ta patentovlasnyk Cherkas’kyj derzhavnyj tehnologichnyj universytet. № a201508148 ; zajavl. 17.08.2015; opubl. 24.06.2016, Bjul. № 12.

Faure E’. V. Faktorial’noe kodirovanie s vosstanovleniem

dannykh, Vіsnik Cherkas’kogo derzhavnogo tekhnologіchnogo

unіversitetu, 2016, No. 2, pp. 33–39. DOI: 10.24025/

bulletinchstu.v1i2.82932.

Faure E’. V. Metod povysheniya effektivnosti faktorial’nogo

kodirovaniya s vosstanovleniem dannykh, Vіsnik Cherkas’kogo

derzhavnogo tekhnologіchnogo unіversitetu, 2016, No. 4,

pp. 57–61.

Faure E’. V. Faktorial’noe kodirovanie s neskol’kimi kontrol’nymi summami, Vіsnik Zhitomirs’kogo derzhavnogo tekhnologіchnogo unіversitetu, 2016, No. 3, pp. 104–113. DOI: 10.26642/tn-2016-3(78)-104-113.

Faure E’. V., Harin O. O., Shvydkyj V. V., and Shherba A. I. Pat. 117004 Ukrai’na, MPK H03M 13/09 (2006.01), H04L 1/16

(2006.01), G04C 1/06 (2006.01). Sposib faktorial’nogo koduvannja z vidnovlennjam danyh; zajavnyk ta patentovlasnyk Cherkas’kyj derzhavnyj tehnologichnyj universytet. № u201613641 ; zajavl.

12.2016; opubl. 12.06.2017, Bjul. № 11.

Faure E’. V. Faktorial’noe kodirovanie s ispravleniem oshibok, Radio Electronics, Computer Science, Control, 2017, No. 3, pp. 130–138. DOI: 10.15588/1607-3274-2017-3-15.

Graham R. L., Knuth D. E., and Patashnik O. Concrete

mathematics: a foundation for computer science. 2nd ed. Reading, Massachusetts, Addison-Wesley, 1994, 657 p. ISBN13: 978-0201558029, ISBN10: 0201558025.

MacMahon P. A. The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, American Journal of Mathematics, 1913, No. 35, Vol. 3, pp. 281–322. DOI: 10.2307/2370312.

Comtet L. Advanced Combinatorics, Dordrecht, D. Reidel

Publishing Company, 1974, 343 p. DOI: 10.1007/978-94-010-

-8.

Moritz R. H. and Williams R. C. A Coin-Tossing Problem and Some Related Combinatorics, Mathematics Magazine, 1988, No. 1, Vol. 61, pp. 24-29. DOI: 10.2307/2690326.

Mendes A. A Note on Alternating Permutations, The American Mathematical Monthly, 2007, No. 5, Vol. 114, pp. 437-440.

Stanley R. P. Enumerative Combinatorics, V.1., 2nd ed., New York, Cambridge University Press, 2011, 725 p. ISBN13: 978-1107602625, ISBN10: 1107602629.

The on-line encyclopedia of integer sequences. A008302, Rezhim dostupa: http://oeis.org/A008302.

Knuth Donald E. [Per. s angl. pod red. Tertyshnogo V. T. i

Krasikova I.V.]. Iskusstvo programmirovaniya. V 7 t. Vol. 3.

Sortirovka i poisk, 2-e izd., M, OOO «I.D. Vil’yams», 2007,

p. ISBN: 978-5-8459-0082-1.

Fink L. M. Teoriya peredachi diskretnykh soobshchenii.

[Izd. 2-e.]. M., Sovetskoe radio, 1970, 728 p.


GOST Style Citations


1. Фауре Э. В. Контроль целостности информации на основе
факториальной системы счисления/ Э. В. Фауре, В. В. Швыд-
кий, А. И. Щерба // Journal of Baku Engineering University –
Mathematics and Computer Science. – 2017. – Vol. 1, № 1. –
P. 3–13.
2. Фауре Э. В. Комбинированное факториальное кодирование и
его свойства / Э. В. Фауре, В. В. Швыдкий, В. А. Щерба //
Радіоелектроніка, інформатика, управління. – 2016. – № 3. –
С. 80–86. DOI: 10.15588/1607-3274-2016-3-10.
3. Пат. 107655 Україна, МПК G06F21/64 (2013.01), H04L1/16
(2006.01). Спосіб контролю цілісності інформації / Рудниць-
кий В. М., Фауре Е. В., Швидкий В. В., Щерба А. І. ; заявник та
патентовласник Черкаський державний технологічний універ-
ситет. – № a201505937 ; заявл. 16.06.2015; опубл. 24.06.2016,
Бюл. № 12.
4. Пат. 107657 Україна, МПК H03M13/09 (2006.01), H04K1/06
(2006.01), G09C1/06 (2006.01). Спосіб комбінованого коду-
вання інформації / Рудницький В. М., Фауре Е. В.,
Швидкий В. В., Щерба А. І. ; заявник та патентовласник Чер-
каський державний технологічний університет. –
№ a201508148 ; заявл. 17.08.2015; опубл. 24.06.2016, Бюл.
№ 12.
5. Фауре Э. В. Факториальное кодирование с восстановлением
данных / Э. В. Фауре // Вісник Черкаського державного техно-
логічного університету. – 2016. – № 2. – С. 33–39.
DOI: 10.24025/bulletinchstu.v1i2.82932.
6. Фауре Э. В. Метод повышения эффективности факториально-
го кодирования с восстановлением данных / Э. В. Фауре //
Вісник Черкаського державного технологічного університе-
ту. – 2016. – №4. – С. 57–61.
7. Фауре Э. В. Факториальное кодирование с несколькими конт-
рольными суммами / Э. В. Фауре // Вісник Житомирського
державного технологічного університету. – 2016. – №3. –
С. 104–113. DOI: 10.26642/tn-2016-3(78)-104-113.
8. Пат. 117004 Україна, МПК H03M13/09 (2006.01), H04L1/16
(2006.01), G04C1/06 (2006.01). Спосіб факторіального коду-
вання з відновленням даних / Фауре Е. В., Харін О. О., Швид-
кий В. В., Щерба А. І. ; заявник та патентовласник Черкаський
державний технологічний університет. – №u201613641; за-
явл.30.12.2016; опубл.12.06.2017, Бюл.№11.
9. Фауре Э. В. Факториальное кодирование с исправлением оши-
бок / Э. В. Фауре // Радіоелектроніка, інформатика, управлін-
ня. – 2017. – № 3. – С. 130–138. DOI: 10.15588/1607-3274-
2017-3-15.10. Graham R. L. Concrete mathematics: a foundation for computer
science / Ronald L. Graham, Donald E. Knuth, Oren Patashnik. –
2nd ed. – Reading: Addison-Wesley, 1994. – 657 p. ISBN13: 978-
0201558029, ISBN10: 0201558025.
11. MacMahon P. A. The indices of permutations and the derivation
therefrom of functions of a single variable associated with the
permutations of any assemblage of objects / P. A. MacMahon //
American Journal of Mathematics. – 1913. – № 35 (3). – Р.
281–322. DOI: 10.2307/2370312.
12. Comtet L. Advanced Combinatorics / Louis Comtet. – Dordrecht:
D. Reidel Publishing Company, 1974. – 343 p. DOI: 10.1007/
978-94-010-2196-8.
13. Moritz R. H. A Coin-Tossing Problem and Some Related
Combinatorics / Roger H. Moritz, Robert C. Williams //
Mathematics Magazine. – 1988. – №1. – Vol. 61. – P. 24–29.
DOI: 10.2307/2690326.
14. Mendes A. A Note on Alternating Permutations / Anthony Mendes
// The American Mathematical Monthly. – 2007. – Vol. 114,
№ 5. – P. 437–440.
15.Stanley R. P. Enumerative Combinatorics / Richard P. Stanley. –
V.1. – 2nd ed. – New York : Cambridge University Press, 2011. –
725 p. ISBN13: 978-1107602625, ISBN10: 1107602629.
16. The on-line encyclopedia of integer sequences. A008302. – Ре-
жим доступа : http://oeis.org/A008302.
17. Кнут Дональд Э. Искусство программирования. В 7 т. Т.3.
Сортировка и поиск, 2-е изд. / Дональд Эрвин Кнут ; пер. с
англ. под ред. В. Т. Тертышного и И. В. Красикова. – М. : ООО
«И. Д. Вильямс», 2007. – 832 с. ISBN: 978-5-8459-0082-1.
18.Финк Л. М. Теория передачи дискретных сообщений /
Л. М. Финк Изд. 2-е. – М. : Советское радио, 1970. – 728 с.






Copyright (c) 2018 E. V. Faure, A. I. Shcherba, A. A. Kharin

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.