Development of binary information compression methods based on the binomial numerical function
DOI:
https://doi.org/10.15587/1729-4061.2021.234492Keywords:
binomial numbering systems, binomial numerical function, binomial numbers, compression of binary informationAbstract
The application of data compression methods is an effective means of improving the performance of information systems. At the same time, interest is aroused to the methods of compression without information loss which are distinguished by their versatility, low needs of costs during implementation, and the possibility of self-control.
In this regard, the application of binomial numbering systems is promising. The numerical function of the binomial numbering system is used for compression. It makes it possible to put sequences in one-to-one compliance with their numbers. In this case, the transition from binary combinations to binomial numbers is used as an intermediate stage.
During the study, theorems were formulated that indicate properties of compressing and restoring the mappings as well as the ways of their implementation. Models of compression processes were obtained on the basis of a numerical function, both for the case of compressible equilibrium combinations and the case when sequences of a general form are to be compressed. The compression models include coding steps based on binary binomials.
The study results show the effectiveness of applying the compression based on the binomial numerical function. A 1.02 times increase in speed of information transmission through a communication channel was observed in the worst case and 18.29 times in the best case depending on the number of ones in 128-bit equilibrium combinations. The proposed methods are advantageous due to their high compression ratio (from 1.01 to 16 times for general 128-bit sequences) and versatility: combinations are compressed in which the number of ones is 75 % of their total variation range. The developed methods ensure control of errors during conversions. They are undemanding to computation resources and feature low implementation costs.
References
- Sayood, K. (2018). Introduction to Data Compression. Morgan Kaufmann, 790. doi: https://doi.org/10.1016/C2015-0-06248-7
- Sayood, K. (2003). Lossless Compression Handbook. Academic Press, 488. doi: https://doi.org/10.1016/B978-0-12-620861-0.X5000-1
- Smirnov, M. A. (2004). Obzor primeneniya metodov bezuscherbnogo szhatiya dannyh v SUBD. Saint Petersburg. Available at: http://compression.ru/download/articles/db/smirnov_2003_database_compression_review.pdf
- Krasnobayev, V., Kuznetsov, A., Koshman, S., Rassomakhin, S., Zamula, A., Kavun, S. (2018). Effective Data Processing in Coding, Digital Signals and Cryptography. ASC Academic Publishing, 352. Available at: https://www.amazon.com/effective-processing-digital-signals-cryptography-ebook/dp/B07CSJHHN1
- Yuan, Y., Zhang, Y., Liu, Z., Guan, X. (2017). Lossless coding scheme for data acquisition under limited communication bandwidth. Digital Signal Processing, 69, 204–211. doi: https://doi.org/10.1016/j.dsp.2017.06.028
- Amel'kin, V. A. (1986). Metody numeratsionnogo kodirovaniya. Novosibirsk: Nauka, 155.
- Amel'kin, V. A. (2008). Perechislitel'nye zadachi seriynyh posledovatel'nostey. Novosibirsk: IVMiMG SO RAN, 317.
- Stakhov, A. P. (2014). A History, the Main Mathematical Results and Applications for the Mathematics of Harmony. Applied Mathematics, 05 (03), 363–386. doi: https://doi.org/10.4236/am.2014.53039
- Polyakov, V. I., Skorubsky, V. I., Ekalo, Yu. V. (2015). Application of Factorial System to Combinatorial Problems Solving. Izvestiâ vysših učebnyh zavedenij. Priborostroenie, 58 (6), 436–442. doi: https://doi.org/10.17586/0021-3454-2015-58-6-436-442
- Borisenko, A. A. (2004). Binomial'niy schet. Teoriya i praktika. Sumy: ITD "Universitetskaya kniga", 170. Available at: https://essuir.sumdu.edu.ua/handle/123456789/55161
- Kulyk, I., Shevchenko, M. (2020). Development of information-management systems on basis of binary binomial number systems. Information Processing Systems, 2 (161), 78–85. doi: https://doi.org/10.30748/soi.2020.161.09
- Kulyk, I., Berezhna, O., Shevchenko, M. (2018). Development of data compressing coding methods on basis of binary binomial numbers. Technology Audit and Production Reserves, 2 (2 (46)), 12–18. doi: https://doi.org/10.15587/2312-8372.2019.169897
- Kulyk, Y. A., Novhorodtsev, A. Y., Skordyna, E. M. (2016), Binomial model of vector representation for database with columnar structure. Information Processing Systems, 4 (141), 50–55. Available at: http://www.hups.mil.gov.ua/periodic-app/article/16556
- Schalkwijk, J. (1972). An algorithm for source coding. IEEE Transactions on Information Theory, 18 (3), 395–399. doi: https://doi.org/10.1109/tit.1972.1054832
- Knuth, D. (1997). The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley Professional, 672. Available at: https://www.amazon.com/Art-Computer-Programming-Vol-Fundamental/dp/0201896834
- Anderson, J. A., Anderson, J., Bell, J. (2000). Discrete mathematics with combinatorics. Prentice Hall College Div, 799. Available at: https://www.amazon.com/Discrete-Mathematics-Combina-torics-James-Anderson/dp/0130869988
- Kohzuki, K., Tokiwa, K., Tanaka, H. (1997). A class of single error correcting constant weight codes. Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 80 (7), 55–64. doi: https://doi.org/10.1002/(sici)1520-6440(199707)80:7<55::aid-ecjc7>3.0.co;2-0
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Igor Kulyk, Olga Berezhna, Anatoliy Novhorodtsev, Maryna Shevchenko
This work is licensed under a Creative Commons Attribution 4.0 International License.
The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.
A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.
