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

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

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

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

Таблица 1

Проанализировав методы сжатия, используемые для передачи ТМИ, можно сделать вывод, что все указанные в таблице 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.