Реализация метод а экономного кодирования Хаффмана в информационно-телеметрических системах

Автор: Артюшкин Андрей Борисович, Обрученков Виктор Петрович, Бельских Марк Андреевич

Журнал: Вестник Российского нового университета. Серия: Сложные системы: модели, анализ и управление @vestnik-rosnou-complex-systems-models-analysis-management

Рубрика: Математическое моделирование

Статья в выпуске: 2, 2021 года.

Бесплатный доступ

Описывается подход к сокращению времени обработки данных при их кодировании экономным кодом Хаффмана, что позволяет значительно расширить возможности цифровых систем связи. Предлагаются два алгоритма - сортировки и поиска позиции числа в упорядоченном числовом массиве. Установлено, что экономия времени достигается сокращением количества требуемых элементарных операций за счет использования дополнительных объемов рабочей памяти кодера. Выявлено, что временная сложность алгоритма сортировки составляет O(3 N ), а при совместном со вторым алгоритмом использовании в кодере Хаффмана - O(2 N ). При этом временную сложность метода Хаффмана удается снизить с вида O( Nk log N ) до вида O( Nk ) .

Еще

Метод хаффмана, экономное кодирование, сортировка данных, сложность алгоритмов

Короткий адрес: https://sciup.org/148321555

IDR: 148321555   |   DOI: 10.25586/RNU.V9187.21.02.P.020

Список литературы Реализация метод а экономного кодирования Хаффмана в информационно-телеметрических системах

  • Абрамов С. А. Лекции о сложности алгоритмов. М.: Изд-во Московского центра непрерывного математического образования, 2012. 246 с.
  • Александров О.Е. Компрессия данных или измерение и избыточность информации. Метод Хаффмана: Методические указания к лабораторной работе. Екатеринбург: Изд-во Ухтинского государственного технического ун-та, 2000. 52 с.
  • Артюшкин А.Б., Куксенко М. А., Пантенков А.П. Экономное кодирование как метод повышения скорости передачи информации в телеметрических системах // Вестник Российского нового университета. Серия "Сложные системы: модели, анализ, управление". 2020. Вып. 1. С. 43-54. DOI: 10.25586/RNU.V9187.20.01.P.043
  • Горячкин О.В. Теория информации и кодирования: учеб. пособие. Часть 2. Самара: Изд-во Поволжского государственного ун-та телекоммуникаций и информатики, 2017. 138 с.
  • Кнут Д.Э. Искусство программирования: пер. с англ. 2-е изд. Т. 3. Сортировки и поиск. М.: Вильямс, 2007. 832 с.
  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ / пер. с англ. И.В. Красикова, Н.А. Ореховой, В.Н. Романова; под ред. И.В. Красикова. 2-е изд. М.: Вильямс, 2005. 1296 с.
  • Лоскутов А.И., Бянкин А. А., Козырев Г.И., Сакулин А.Н. и др. Телеметрия: учебник / под общ. ред. А.И. Лоскутова. СПб.: Изд-во Военно-космической академии им. А.Ф. Можайского, 2017. 342 с.
  • Разова Е.В. Дополнительная подготовка школьников по дисциплине "Информационные технологии". Учебный модуль "Сложность алгоритмов". Владимир: Изд-во Владимирского государственного гуманитарного ун-та, 2011. 30 с.
  • Семенюк В.В. Экономное кодирование дискретной информации. СПб.: Изд-во Ун-та ИТМО, 2001. 115 с.
  • Эльшафеи М. А., Сидякин И.М., Харитонов С.В., Ворнычев Д.С. Исследование методов обратимого сжатия ТМИ // Вестник МГТУ им. Н.Э. Баумана. Серия "Приборостроение". 2014. № 3. С. 92-104.
Еще
Статья научная