Алгоритм оптимального сжатия телеметрической информации, передаваемой с автономного технического средства по радиоканалам



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

Ключевые слова: сжатие информации, автономное техническое средство, телеметрическая информация, конечный автомат.

Постоянный рост объемов телеметрической информации (далее — ТМИ) в автономных технических средствах приводит к сложности оперативной обработки данных. Появляется необходимость разработки новых требований к процессу сжатия информации. Для сжатия телеметрической информации, как правило, применяют алгоритмы, обеспечивающие точное восстановление исходных данных с целью их дальнейшей обработки и анализа. Телеметрические данные, передаваемые с датчиков и устройств на пункт обработки, могут быть представлены в форме текста, изображений, аудио и различных других форматах. Сжатие этих данных позволяет эффективно использовать пропускную способность во время передачи потока информации и уменьшает ресурсы хранения пункта обработки. Однако, при разработке устройств и алгоритмов, проводящих сжатие ТМИ, требуется учитывать ширину канала передачи информации, а также обращать внимание на большую избыточность передаваемой информации. В системах с циклической дискретизацией избыточность данных возникает даже при правильно выбранной частоте опроса датчиков, так как при мало меняющихся во времени параметрах частота опроса остается той же, что и на участках, где такая частота является необходимой. Таким образом, целью сжатия данных является формирование минимального количества информации, обеспечивающей воспроизведение первичного сигнала с заданной вероятностью [1].

В последние годы разработано множество методов сжатия информации, используемых для передачи информации разного представления. Подробный анализ данных методов представлен в таблице 1 [2].

Таблица 1

№ п/п	Наименование метода	Достоинства	Недостатки
1.	Метод экстраполяции	Наиболее помехоустойчив к воздействию потенциального противника. Коэффициент сжатия около 70 процентов.	Сжатие требует запоминание последнего существенного отсчета.
2.	Метод адаптивной дискретизации	Позволяет уменьшить среднюю частоту дискретизации. Точка опроса не образует периодической последовательности.	Необходимо передавать дополнительную информацию в виде значений времени появления существенных выборок.
3.	Метод интерполяции	Позволяет исключить большее число избыточных отсчетов.	Величина коэффициента сжатия зависит от ширины апертуры.
4.	Метод автоматической регулировки частоты опроса сигнала	Можно передавать данные, занимающие полосу 80 кГц в реальном масштабе времени в полосе канала 3,2 кГц.	Сложность реализации алгоритмов сжатия данных.

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

При эксплуатации автономных технических средств требуется передача наиболее актуальной и достоверной ТМИ. Актуальность должна достигаться путем сокращения объема передаваемой ТМИ в канале передачи данных. Достоверность должна достигаться путем создания универсальных алгоритмов обработки получаемой информации на пункте обработки.

Таким образом, использование каждого метода по отдельности несет потери в том или ином качестве получаемой ТМИ. Предлагается рассмотреть передаваемую информацию как набор состояний конечного автомата.

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

Алгоритм сжатия ТМИ должен обладать свойством биекции, т. е. быть одновременно инъективным (однозначное соответствие между множествами зависимостей конечного автомата) и сюръективным, следовательно, алгоритм должен обладать взаимно однозначным соответствием между зависимостями конечного автомата.

На рис. 1а, 1б и 1в представлены графические изображения соответственно инъекции, сюръекции и биекции [3, 4].

а

б

в

Рис. 1. Графическое изображение свойств биекции

Пусть — конечное множество телеметрических датчиков, установленных на автономном техническом средстве, — множество натуральных чисел, а отображение сопоставляет каждому датчику его номер или адрес. Так как каждый датчик имеет свой единственный номер или адрес, и существуют натуральные числа, не являющиеся номерами датчиков, то — инъекция.

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

Соответствие между элементом множества телеметрических датчиков заводскому номеру этого датчика является биекцией [5].

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

Задан автомат . Состояние достижимо из состояния

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

Состояние -достижимо из , где , если существует достигающая последовательность для и

, длина которой .

Если -достижимо из , то -достижимо из для всех .

Если

-недостижимо из , то -достижимо из для всех .

Допустим, что задан автомат с числом состояний, равным , т. е. мощность множества состояний .

Пусть достижимо из , q ў № q , и x ₁ ,…, x _p — достигающая последовательность для и такая, что p > n -1. При этом qq ₁ ,…, q _p — последовательность состояний автомата А , в которые он последовательно переходит при выдаче входной последовательности x ₁ ,…, x _p , здесь q ў = q _p . Так как p > n -1, то число состояний в указанной последовательности состояний qq ₁ ,…, q _p больше n . Следовательно, некоторые состояния в этой последовательности встречаются дважды. Фрагмент последовательности x _{i +1} ,…, x _{i + r} переводит автомат А из состояния q _i в q _i снова.

Этот фрагмент последовательности можно удалить и последовательность все равно будет достижимой для q _i и . Указанное сокращение входной достигающей последовательности возможно до тех пор, пока в соответствующей ей последовательности состояний имеются хотя бы два одинаковых состояния, а такое однозначно имеет место, если p > n -1.

Если состояние достижимо из состояния , то состояние q ў ( n -1) достижимо из .

Соответственно, если q ў ( n -1)-недостижимо из , то оно вообще недостижимо из .

Входная последовательность x ₁ … x _p задает обход состояний автомата из состояния , если в последовательности состояний qq ₁ ,…, q _p при выдаче x ₁ ,…, x _p встречаются все состояния автомата А и q _p = q , т. е. автомат А после выдачи входной последовательности x ₁ ,…, x _p вернулся в исходное состояние.

Состояния и 0-эквивалентны, если j ( q ) = j ( q ў), т. е. состояния и имеют одинаковые выходные символы.

Состояния и k -эквивалентны, k = 1,2,..., если они 0-эквивалентны и для всякой входной последовательности x ₁ ,…, x _p , длина которой p Ј k , выходные последовательности, которые порождаются из состояний и входной последовательностью x ₁ ,…, x _p , совпадают.

Если состояния и k -эквивалентны, то они r -эквивалентны для любого r < k .

Состояния и 0-различимы, если j ( q ) № j ( q ў).

Состояния и k -различимы, если они либо 0-различимы, либо существует минимальная входная последовательность x ₁ ,…, x _k , такая, что выходные последовательности, порождаемые из состояний и при выдаче x ₁ ,…, x _k , различны.

Если состояния и q ў k -различимы, где k = 0,1,2,..., то они s -различимы для любого s > k .

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

Следовательно, любая совокупность состояний, обеспечивающая требуемые зависимости между входом и выходом, может быть выбрана в качестве множества состояний автомата [6].

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

Минимизация числа состояний автомата связана с анализом эквивалентности его состояний.

Пусть задан некоторый автомат А с n состояниями. Сопоставим автомату А автомат В следующим образом. Пусть X _B = X _A , Y _B = Y _A , т. е. множества входных и выходных переменных (алфавиты входных и выходных символов) автоматов А и В совпадают.

Множество состояний Q _B = P _{n -2} , где P _{n -2} = { S ₁ ,..., S _r } — множество классов ( n -2)-эквивалентности, образованное из множества Q _А , |P _{n -2} | Ј |Q _А | = n . Функция выходов j _В ( S _i ) = j _А ( q ), если q О S _i . Функция переходов f _B ( x , S _i ) = S _j , если при q О S _i f _А ( x , q ) = q ўО S _j .

Построенный таким образом автомат В называется минимальной формой автомата А , а автомат В имеет минимальное число состояний среди эквивалентных автоматов автомату А .

Минимальная форма автомата А является приведенным автоматом.

[7] Пусть задан автомат А с четырьмя состояниями, т. е. n = 4,|Q| = 4 (Рис. 2).

Рис. 2. Конечный автомат А

Произведем анализ эквивалентности состояний автомата А .

Отсюда автомат В , являющийся минимальной формой автомата А , т. е. являющийся эквивалентным автомату А с минимальным числом состояний, будет выглядеть следующим образом (Рис. 3):

Рис. 3. Автомат В — минимальная форма автомата А

Исходя из полученного анализа алгоритм преобразования конечного автомата можно представить следующим образом (Рис. 4):

Рис. 4. Алгоритм сжатия ТМИ путем автоматного представления данных

Литература:

1. Верба В. С., Меркулов В. И., Попов Е. В., Чернов В. С. Интеграция данных в многодатчиковых бортовых информационно-управляющих системах. — Информационно-измерительные и управляющие системы, 2014.
2. Симонович С. В. Информатика. — СПб.: Питер, 2008.
3. Вернер М. Основы кодирования — М.: Техносфера, 2004.
4. Сэломон Д. Сжатие данных, изображение и звука — М.: Техносфера, 2006.
5. Сергеев В. В. Анализ и обработка изображений, получаемых при наблюдениях земли из космоса. — Компьютерная оптика, 2006.
6. Эльшафеи М. А., Сидякин И. М., Харитонов С. В., Ворнычев Д. С. Исследование методов обратимого сжатия телеметрической информации. — Вестник МГТУ им. Н. Э. Баумана. Сер. «Приборостроение», 2014.
7. Чье Ен Ун, Левенец А. В., Нильга В. В. Представление телемеханических данных однородными n-мерными структурами как предварительная обработка в задачах сжатия. — Информационно-управляющие системы, 2011.