Сжатие измерительной информации методом Хаффмана с использованием таблицы уникальных величин

Размещено на http://allbest.ru

Волжский политехнический институт (филиал)

Волгоградского государственного технического университета

Сжатие измерительной информации методом Хаффмана с использованием таблицы уникальных величин

Капля Виктор Иванович,

кандидат технических наук, доцент,

Бурцев Андрей Георгиевич, аспирант,

Тимофеев Илья Игоревич, студент

Процессы хранения большого объёма информации в памяти контроллера и последующей её передачи на ЭВМ ограничены ресурсами устройства, а также временными рамками. В данной работе рассматривается возможность модернизации алгоритма Хаффмана для сжатия измерительной информации в контроллере.

Особенностью измерительных данных является то, что они изменяются во времени с небольшой скоростью. Следовательно, выгодней работать не с абсолютными значениями, а с разностями значений соседних измерений, т. к. они располагаются в более узком интервале.

Алгоритм Хаффмана требует построения бинарного дерева на основе частот появления символов алфавита (в данном случае подразумеваются величины разностей) в сообщении, т. е. перед формированием динамической таблицы частот необходимо проанализировать все данные [1]. Эта операция приводит к затратам по ресурсам и по времени, что недопустимо при использовании алгоритма в контроллере. Целесообразней использовать статическую таблицу частот.

Формирование статической таблицы частот основано на статистической обработке представительной выборки последовательности измерений. В работе используются экспериментальные данные о мощности электрической энергии, расходуемой в процессе плавки кристаллического материала. Результаты измерений периодически заносятся в память ПЛК в виде вектора.

Статическая таблица частот формируется для вектора разностных величин смежных измерений путём усреднения экспериментальных данных по всем выборкам. Целесообразно аппроксимировать элементы статической таблицы частот, что позволит сгладить шумы, присущие ограниченным выборкам экспериментальных данных.

Пример результата усреднения экспериментальных данных приведён на рисунке 1. Тонкими линиями обозначены количества появлений различных значений разностей N для выборок с чётными индексами, а толстой линией -- усреднённое значение по всем наборам.

Рис. 1. Частоты экспериментальных выборок и результат их усреднения.

Сглаживание осуществлялось для логарифмированных значений с помощью полиномов.

График усреднённых частот в точке N = 0 имеет острый пик, поэтому положительные значения были аппроксимированы полиномом 11 степени, а отрицательные -- полиномом 9 степени.

Результат аппроксимации для диапазона разностей [-25; 18] приведён на рисунке 2.

информация хаффман контроллер кодирование

Рис. 2. Аппроксимированные значения таблицы частот.

Частоты больших значений разностных величин весьма малы, поэтому с целью уменьшения размера статической таблицы целесообразно оставить в ней только те величины, которые попадают в диапазон кодирования.

Величины, не попадающие в этот диапазон, заносятся в специальную таблицу уникальных величин, в кодируемой последовательности все они заменяются единым уникальным символом.

Частота этого символа очевидно равна сумме значений частот символов, не попавших в диапазон кодирования.

Рассмотренные алгоритмы сжатия были реализованы в среде CoDeSys на языке ST.

С помощью этой программы была исследована зависимость коэффициента сжатия и частоты появления уникальных символов от положения границ диапазона кодирования. Результаты исследования представлены на рисунке 3.

Рис. 3. Зависимость логарифма коэффициента сжатия и частоты уникальных символов от положения границ диапазона кодирования. Dl -- расстояние от 0 до левой границы отрезка, Dh -- расстояние от 0 до правой границы отрезка.

Анализ зависимости коэффициента сжатия от положения диапазона кодирования показывает, что образуется плато значений, соответствующих предельной степени сжатия.

Статическая таблица позволяет сразу кодировать очередное измерение, при этом вычислительные ресурсы и время расходуются только на поиск кодовой замены.

Например, выбор диапазона [_13; 3] вместо [-25; 18] приводит к тому, что коэффициент сжатия изменяется с 11.02 до 9.97, т. е. в 1.11 раз, но при этом размер таблицы Хаффмана и соответствующее время поиска замены уменьшается в 2.38 раза.

Пример построения дерева Хаффмана по полученным данным при Dl = Dh = 5 приведён на рисунке 4.

Длина интервала выбрана небольшой, т. к. её увеличение приводит к усложнению графического изображения дерева (в скобках указано количество символов в кодируемом сообщении).

Рис. 4. Дерево Хаффмана.

Выводы

Ограничение диапазона кодируемых величин позволяет управлять размером таблицы Хаффмана. Результаты измерений, которые не попали в диапазон кодирования, необходимо сохранять в специальном массиве, что несколько увеличивает размер архива, но при этом существенно сокращается длительность цикла архивирования.

Наличие представительной выборки результатов измерений позволяет создать статическую таблицу Хаффмана для заданного диапазона кодирования и освободить контроллер от ресурсоёмкой задачи постоянного обновления кодируемой таблицы.

Литература

1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2003. - 384 с.

Размещено на Allbest.ru