Розробка методів стискаючого кодування даних на основі двійкових біноміальних чисел
DOI:
https://doi.org/10.15587/2312-8372.2019.169897Ключові слова:
двійкові біноміальні числа, біноміальні системи числення, стиснення двійкової інформаціїАнотація
Об'єктом дослідження є методи стискаючого кодування, які застосовуються для економного представлення даних в інформаційних системах. Методи стиску можуть використовуватися на різних етапах обробки даних, при передачі повідомлень і їх зберіганні. Одними із самих проблемних місць застосування методів стиску є високі вимоги до обчислювальних ресурсів, значні апаратно-програмні витрати при їхній реалізації й невисока швидкість кодування/декодування. При цьому особливий інтерес викликають методи, над результатами стиску яких можливі обчислювальні операції без їхнього зворотного відновлення.
У рамках підходу, коли в основі будь-якого коду можна виявити структурну систему числення, розроблені математичні моделі стиску на основі двійкових біноміальних чисел. У структурі послідовностей визначаються відповідні їм біноміальні числа на основі систем кодоформуючих обмежень. Як результат, кожній комбінації ставиться у відповідність біноміальне число, яке являє собою її стислий образ.
У ході дослідження сформульовані теореми про взаємно однозначну відповідність вихідних послідовностей і двійкових біноміальних чисел, які демонструють способи реалізації відображень на основі простих аналітичних співвідношень. Наведені приклади підтверджують простоту перетворень при стискаючому кодуванні й декодуванні.
Отримані моделі процесів стиску й відновлення, які характеризуються невеликою кількістю простих операцій. Як наслідок, розглянуті методи характеризуються високою швидкістю при сприйнятливих коефіцієнтах стиску. При цьому обсяг апаратно-програмних витрат при практичній реалізації є невеликим. Додатковим позитивним ефектом є те, що стислі образи мають властивості чисел.
Результати дослідження демонструють ефективність застосування стиску на основі двійкових біноміальних чисел в інформаційних системах з метою збільшення їх продуктивності й зменшення вартості обробки даних. При цьому в порівнянні з аналогічними відомими методами спостерігаються мінімальні витрати на їхнє впровадження при досягненні високої швидкості перетворень і гарному ступеню стиску двійкових даних будь-якого виду.
Посилання
- Sayood, Kh. (2017). Introduction to Data Compression. Morgan Kaufmann, 790.
- Vatolin, D., Ratushnjak, A., Smirnov, M., Jukin, V. (2003). Metody szhatia dannyh. Ustrojstvo arhivatorov, szhatie izobrazhenii i video. Moscow: DIALOG-MIFI, 384.
- Smirnov, M. А. (2004). Obzor primeneniya metodov bezusherbnogo szhatiya dannyh v SUBD. Saint Petersburg, 58. Available at: http://compression.ru/download/articles/db/smirnov_2003_database_compression_review.pdf
- Sayood, K., Memon, N. (2012). Lossless Compression Handbook. Academic Press, 488. doi: http://doi.org/10.1201/9781420041163-101
- Borysenko, О. А. (2007). Chislo i sistemi chislennya v elektronnih cifrovih sistemah. Bulletin of Sumy State University, 4, 71–76.
- Borysenko, O. A., Kulyk, I. A. (2010). Binomial'noe kodirovanie. Sumy: Sumy State University, 206.
- Borysenko, A. A. (2004). Binomialnyi schet. Teoriya i praktika. Sumy: ITD Universitetskaya kniga, 170.
- Kulyk, I. A., Cherednichenko, V. B., Kostel, S. V. (2008). Algoritm generirovaniya dvoichnyh binomialnyh chisel na osnove minimalnyh sistem kodoobrazuyushih ogranichenii. Bulletin of Sumy State University, Series Technical Sciences, 2, 45–52.
- Schalkwijk, J. (1972). An algorithm for source coding. IEEE Transactions on Information Theory, 18 (3), 395–399. doi: http://doi.org/10.1109/tit.1972.1054832
- Cover, T. (1973). Enumerative source encoding. IEEE Transactions on Information Theory, 19 (1), 73–77. doi: http://doi.org/10.1109/tit.1973.1054929
- Amelkin, V. A. (1986). Metody numeracionnogo kodirovaniya. Novosibirsk: Nauka, 155.
- Amelkin, V. A. (2008). Perechislitelnye zadachi serijnyh posledovatelnostei. Novosibirsk: IVMiMG SO RAN, 317.
- Kulyk, I. A., Borysenko, O. A., Onoriukpe, Adzhiri (2016). Modeli szhatija i vosstanovlenija dannyh na osnove dvoichnyh binomial'nyh chisel. Methods of information coding, defence and compression. Vinnytsya: Vinnitsa National Technical University, 101–105.
- Kulyk, I. A., Skordina, E. M., Kostel, S. V. (2011). Generirovanie kodov-sochetanij dlya resheniya informacionnyh zadach IUS. Automated management systems and automation devices, 155, 15–23.
- Greenfield, T., Reingold, E. M., Nievergeld, J., Deo, N. (1978). Combinatorial Algorithms: Theory and Practice. The Statistician, 27 (2), 138. doi: http://doi.org/10.2307/2987917
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2019 Igor Kulyk, Olga Berezhna, Marina Shevchenko
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
