УНИВЕРСАЛЬНОЕ КОДИРОВАНИЕ ТРОЙКАМИ ДЛЯ СЖАТИЯ И ЗАЩИТЫ ДВОИЧНЫХ ДАННЫХ

Виктор А. Шурыгин, Игорь М. Ядыкин

Аннотация


Статья посвящена актуальной проблеме сжатия обрабатываемых и передаваемых данных, хранения и защиты данных. Приводится анализ и особенности методов сжатия данных. Рассмотрен метод универсального кодирования тройками двоичных наборов (КТ). Метод предназначен для сжатия двоичных данных без потерь в условиях неизвестной статистики источника сообщений. Метод основан на разбиении исходной последовательности двоичных данных на блоки разрядностью n. Каждому блоку на основании анализа содержимого n–блока ставится в соответствие три параметра: количество единиц в блоке, сумма номеров позиций единиц, номер данной конкретной комбинации в соответствующем префиксном классе. Рассмотрены подходы к снижению трудоемкости процедур вычисления параметров КТ. Приводится табличный алгоритм вычисления коэффициентов и алгоритм заполнения строк таблиц с применением рекуррентного соотношения для элементов множеств, оценка объемов памяти для хранения таблиц и способы сокращения емкости памяти. Рассмотрена зависимость разрядности кодовых слов КТ от разрядности n-блоков. Анализируются подходы и особенности применения кодировании тройками для защиты информации.

Ключевые слова


сжатие данных, кодирование, хранение данных, защита данных, рекуррентное отношение, сжатие без потерь.

Полный текст:

PDF

Литература


1. Vavrenyuk A.B. Klarin A.P., Makarov V.V., Shurygin V.A. Data compression methods. Journal of Theoretical and Applied Information Technology. 2015. V. 80 (No 2). P. 423–438. ISSN 1992-8645. Е- ISSN 1817-3195. URL: http://www.jatit.org/volumes/Vol80No2/2Vol80No2.pdf. (дата обращения: 05.12.2020).

2. Wayner P. Compression algorithms for real programmers. // Morgan Kaufman, 1999. – 252 p.
ISBN: 9780127887746.

3. Уэлстид С. Фракталы и вейвлеты для сжатия изображений в действии. / Пер. с англ. М. Триумф,
2003. – 319 с. ISBN 5-89392-079-1.

4. Д. Сэломон. Сжатие данных, изображения и звука. М.: Техносфера, 2006. – 368 c. ISBN 5-94836-027-Х, 0-387-95260-8.

5. Ковалгин Ю.А., Вологдин Э.И.Цифровое кодирование
звуковых сигналов //М.: Корона-Принт,
2004. – 240 с. ISBN: 978-5-7931-0290–2.

6. Salomon D. Data compression: The complete reference. // Springer, 2006. – 1118 p. ISBN: 1-84628-602-6 (978-1-84628-602-5).
 
7. Соловьев В. Ф. Рациональное кодирование при передаче сообщений. М.: Энергия, Серия: Библиотека по автоматике, вып. 411, 1970. – 64 с.

8. William A. Pearlman, Amir Said. Digital signal compression: Principles and practice // Cambridge University Press, 2011. – 420 p. ISBN: 10-0521805031, 0521899826. URL: https://books.google.ru/books?id
=s3H8s8rdsHkC&printsec=frontcover&dq=inauthor:%22William+A.+Pearlman%22&hl=ru&sa=X&ved=2ahUKEwitn7HD3_DtAhUI-yoKHXmfAtoQ6AEwAnoECAEQAg#v=onepage&q&f=false (дата обращения: 05.12.2020).

9. Khalid Sayood, Introduction to data compression (4th Edition)// Printbook, 2012. – 768 p.
ISBN: 1849690308.

10. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: Диалог-МИФИ, 2002. – 384 с. ISBN 5-86404-170-X.

11. Новиков Г.Г., Шурыгин В.А., Ядыкин И.М. Устройство для упаковки данных. Патент RU 2701711 С1. Заявка RU 2019100240, 09.01.2019. Опубликовано 30.09.2019. Бюл. №28. МПК H03M 7/30.

12. Новиков Г.Г., Ядыкин И.М. Устройство для распаковки данных. Патент RU 2729509 С1. Заявка
RU 2019143298, 23.12.2019. Опубликовано 07.08.2020. Бюл. №28. МПК H03M 7/30.

13. Фитингоф Б.М. Сжатие дискретной информации. Проблемы передачи информации. Т 3. Вып. 3. 1967. С. 28–36. URL: http://www.mathnet.ru/php/archive.phtml?jrnid=ppi&option_lang=rus&paperid=
1909&wshow=paper (дата обращения: 05.12.2020).

14. Колмогоров А.Н. Три подхода к определению понятия «количество информации». Проблемы передачи информации. Т 1. Вып. 1. 1965. С. 3–11. URL: http://www.mathnet.ru/php/archive.phtml?jrnid=ppi&option
_lang=rus&paperid=68&wshow=paper (дата обращения: 05.12.2020).

15. Успенский В.А., Вьюгин В.В. Становление алгоритмической теории информации в России. Информационные процессы. Т. 10, № 2, 2010. С. 145–158. URL: http:// www.jip/ru/2010/145-158-2010/pdf (дата обращения: 05.12.2020).

16. Штарьков Ю.М. Универсальное кодирование. Теория и алгоритмы. М.: Физматлит, 2013 – 280 c.
ISBN: 9785922115179.

17. Александрович А.Е., Шурыгин В.А., Ядыкин И.М. Метод универсального кодирования двоичных данных. Вопросы радиоэлектроники, серия Электронная вычислительная техника, вып. 2, М.: 2011,
С. 94–115.

18. Кларин А.П., Шурыгин В.А. Исследование эффективности универсального кодирования в зависимости от длины блока. / Проблемы передачи информации, 1984. № 2. С. 105–110.
URL: http://www.mathnet.ru/php/archive.phtml?jrnid=ppi&option_lang=rus&paperid=1136&wshow=paper (дата обращения: 05.12.2020).

19. Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. – М.: ФИМА, МЦНМО, 2006. – 400 с. ISBN 5-89492-014-0 («ФИМА»), ISBN5-94057-230-8 (МЦНМО).
URL: https://fileskachat.com/download/31544_4f4851eee87775966184b8ca8056bd02.html (дата обращения: 10.12.2020).

20. Справочник по специальным функциям. Под ред. Абрамовица М. и Стиган И. //Пер. с англ. М.: Наука, 1979. – 835 с.

21. Андерсон, Джеймс А. Дискретная математика и комбинаторика. //Пер. с англ. М.: Диалектика / Вильямс, 2020. – 960 с. URL: https://fb2lib.ru/nauchnaya/diskretnaya-matematika-i-kombinatorika/ (дата обращения: 10.12.2020).

22. Швец А.Н. Perl. Примеры программ. URL: http://mech.math.msu.su/~shvetz/54/inf/perl-problems/index.xhtml (дата обращения: 10.12.2020).




DOI: http://dx.doi.org/10.26583/bit.2021.1.01

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.