FACTORIAL CODE WITH A GIVEN NUMBER OF INVERSIONS
DOI:
https://doi.org/10.15588/1607-3274-2018-2-16Keywords:
factorial coding, permutation, inversion, redundancy, class of residues, reliability of transmission, relative transmission rate.Abstract
Context. Factorial coding with data recovery by permutation provides complex information protection from unauthorized reading anderrors 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.
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.
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2018 E. V. Faure, A. I. Shcherba, A. A. Kharin
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
