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

практической конференции «Научные исследования и их практическое применение. Современное состояние и пути развития '2011». Том 4. Технические науки. - Одесса: Черноморье, 2011. - Т. 4. Технические науки. -Вып. 30. - С. 3-8.

9. Федяев, А. Ю. Алгоритм линейного преобразования измерительных данных с рандомизированным выбором оптимальных параметров / A.B. Левенец, А.Ю. Федяев // Перспективы развития информационных технологий : сборник материалов VII Международной научно-практической конференции / Под общ. ред. С.С. Чернова. - Новосибирск: Изд-во НГТУ, 2012. - С. 286-291.

10. Федяев, А. Ю. Классификация данных телемеханики на основе использования алгоритмов предсказания, для задач сжатия / A.B. Левенец, А.Ю. Федяев // Высокие технологии, исследования, образование, экономика. Т. 1 : сборник статей Четырнадцатой международной научно-практической конференции «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности и экономике», Санкт-Петербург, 4—5 декабря 2012 года / под ред. А.П. Кудинова. - СПб.: Изд-во Политехи, ун-та, 2012. — С. 74-76.

11. Федяев, А. Ю. Оценка эффективности алгоритмов предсказания как процедуры предварительной обработки перед сжатием телемеханических данных / A.B. Левенец, А.Ю. Федяев // Сборник научных трудов SWorld : материалы международной научно-практической конференции «Научные исследования и их практическое применение. Современное состояние и пути развития '2012». - Вып. 3. - Т. 6. - Одесса: КУПРИЕНКО, 2012. - С. 7-11.

12. Федяев, А. Ю. Сравнение эффективности использования функций кодирования при осуществлении преобразования на плоскости / A.B. Левенец, А.Ю. Федяев // Высокие технологии, исследования, финансы. Т. 2: сборник статей Пятнадцатой международной научно-практической конференции «Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности и экономике», Санкт-Петербург, 25-26 апреля 2013 года / под ред. А.П. Кудинова. - СПб.: Изд-во Политехи, ун-та, 2013. -С. 58-60.

13. Fedyaev, A. Y. Selection Of Coding Function for Preliminary Data Preprocessing Using Coding on Plane Method / E.U. Chy, A.Y. Fedyaev, A.V. Levenets // Science, Technology and Higher Education: materials of the II international research and practice conference, Vol. II, Westwood, April 17th, 2013 -Westwood: Canada, 2013. - P. 106-111

14. Федяев, А. Ю. Способ кодирования на плоскости как процедура предварительного преобразования данных перед сжатием / A.B. Левенец, А.Ю. Федяев // Информационные технологии XXI века: материалы Международной научной конференции, Хабаровск, 20-24 мая 2013 г. - Хабаровск: Изд-во Тихоокеан. гос. ун-та, 2013. - С. 164-170.

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тихоокеанский государственный университет»

04201454463

шах рукописи

Федяев Александр Юрьевич

АЛГОРИТМЫ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ДЛЯ ЗАДАЧ СЖАТИЯ ДАННЫХ В ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНЫХ СИСТЕМАХ

05.11.16 - Информационно-измерительные и управляющие системы

(техника и технологии)

Диссертация на соискание учёной степени кандидата технических наук

Научный руководитель: д.т.н., профессор Чье Ен Ун

Хабаровск-2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 4

1 ДАННЫЕ И ИХ ОБРАБОТКА В ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНЫХ СИСТЕМАХ 11

1.1 Измерительные данные и их классификация 12

1.2 Алгоритмы сжатия данных в ИИС 15

1.3 Предварительная обработка данных перед сжатием 21 Выводы по главе 1 28

2 ПЕРВИЧНАЯ ОБРАБОТКА ИЗМЕРИТЕЛЬНЫХ ДАННЫХ 29

2.1 Способ представления данных отрезками фиксированной длины 29

2.2 Алгоритмы представления сигналов в виде отрезков фиксированной длины 35

2.3 Исследование способа на тестовых данных 41

2.3.1 Условия проведения исследования 41

2.3.2 Результаты исследования 42

2.3.3 Анализ избыточности преобразования 55 Выводы по главе 2 59

3 СПОСОБЫ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ 61

3.1 Способ кубического преобразования данных 61

3.1.1 Основы способа 63

3.1.2 Алгоритмы предварительной обработки измерительных данных с использованием кубических структур 65

3.1.3 Выбор критериев оценки эффективности преобразования 70

3.1.4 Выбор параметров алгоритма с использованием кубического преобразования 75

3.2 Способ линейного кодирования на плоскости 82

3.2.1 Основы способа 82

3.2.2 Выбор параметров для способа кодирования на плоскости 85

3.3 Сегментирование измерительных данных 90

3.3.1 Основы способа 90

3.3.2 Выбор параметров алгоритма для способа сегментирования95

Выводы по главе 3: 98

4 ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА ДАННЫХ ТЕЛЕМЕХАНИКИ 100

4.1 Классификация телемеханических данных 102

4.2 Оценка эффективности предварительной обработки телемеханических данных 105

4.2.1 Оценка эффективности алгоритмов предсказания 105

4.2.2 Исследование эффективности преобразования кубическими структурами 113

4.2.3 Оценка эффективности алгоритмов сегментирования 125 Выводы по главе 4: 130

ЗАКЛЮЧЕНИЕ 132

СПИСОК ЛИТЕРАТУРЫ 134

ПРИЛОЖЕНИЕ А 144

ПРИЛОЖЕНИЕ Б 147

ПРИЛОЖЕНИЕ В 159

ПРИЛОЖЕНИЕ Г 164

ПРИЛОЖЕНИЕ Д 165

ПРИЛОЖЕНИЕ Е 167

ВВЕДЕНИЕ

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

Следствием быстрых темпов развития систем телеметрии для решения задач контроля, управления и испытания сложными объектами и вычислительными комплексами стало увеличение объемов передаваемой по каналам связи информации, что в результате привело к достижению возможных границ по расширению полосы частот каналов связи, а также объемов памяти устройств регистрации. Вместе с этим, по оценкам ряда исследований передаваемые данные содержат значительную избыточность. Так, например, согласно работе Д. Вебера [20] около 90% временных затрат приходится на передачу, получение и обработку избыточной информации. Данный факт послужил причиной создания большого количества способов и алгоритмов сжатия информации, в том числе адаптивных [1, 3-5,14,17,21,23,26,28,30,32,36,39,63,71, 80], позволяющих снизить требования к пропускной способности каналов связи измерительных систем и повысить эффективность систем обработки информации за счет потери несущественных с точки зрения решаемой задачи данных.

На настоящий момент рост производительности вычислительных средств и систем позволяет не просто выделять существенную информацию, но и проводить её анализ, выявляя скрытые закономерности и связи, с целью более компактного описания. Это способствует повышению оперативности управления сложными объектами, сокращению объемов передачи информации. В настоящее время процедуры сжатия информации используются в системах обработки и передачи информации с повышенной информативностью, к которым относятся телеметрические системы [62, 63, 86], системы передачи измерительной, биомедицинской или радиолокационной информации [11, 58, 80], системы передачи речи и телевизионных сообщений [64, 100], системы телемеханики [13, 16,59] и др. При этом наиболее актуальной задачей, связанной с проблемой сжатия

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

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

На данный момент существует целый ряд способов предварительного преобразования, ориентированных на улучшение работы существующих методов сжатия [16, 19, 33, 70, 94, 97, 105, 106]. Однако следует отметить, что лишь немногие процедуры предварительной обработки ориентированы на измерительные данные. Этот факт существенно ограничивает применение существующих способов предварительной обработки в информационно-измерительных системах. Таким образом, актуальной является задача поиска процедур предварительной обработки, способных эффективно работать с измерительными данными.

Целью работы является исследование и разработка способов предварительного преобразования измерительных данных для увеличения эффективности их последующего сжатия в информационно-измерительных системах (ИИС).

Для достижения поставленных целей требуется решение следующих задач:

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

2. Разработка алгоритмов предварительного преобразования повышающих эффективность алгоритмов сжатия используемых в ИИС;

3. Разработка программных средств, на базе предложенных алгоритмов.

Основные методы исследования базируются на математическом аппарате

теории случайных процессов, теории кодирования, теории цифровой обработки сигналов, теории алгоритмов, теории групп и математической статистике. Для экспериментального исследования применены методы математического моделирования, средства объектно-ориентированного программирования, язык объектно-ориентированного программирования Java.

Научная новизна состоит в следующем:

1. Предложен способ представления данных в виде отрезков фиксированной длины для компактного описания измерительных сигналов;

2. Разработан и исследован способ преобразования данных с помощью кубических структур, позволяющий повысить степень сжатия небольших объемов измерительных данных;

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

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

5. Предложена классификация данных телемеханики, основанная на статистическом анализе разностных рядов, даны рекомендации по использованию алгоритмов предварительного преобразования для данных различных классов.

Практическая значимость:

1. На базе предложенных способов разработаны алгоритмы предварительной обработки измерительных данных, ориентированные на работу с рядом широко распространенных алгоритмов сжатия;

2. Разработаны программные комплексы для исследования предложенных способов предварительной обработки;

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

Основные положения выносимые на защиту:

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

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

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

4. Алгоритмы сегментирования измерительных данных позволяют повысить эффективность сжатия на основе LZ методов.

Реализация результатов работы. Исследования и разработки, выполненные в диссертационной работе, проводились в рамках федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы по теме «Программно-аппаратная платформа для промышленно-ориентированных сенсорных сетей ISM диапазонов» (номер гос. per. 01201276122), в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» проект «Совершенствование аппаратно-программного обеспечения адаптивных систем передачи данных распределенных информационно-измерительных систем», 2012-1014 гг. (номер гос. per. 01201256236). Проведенные теоретические исследования и разработки

использованы в проектно-конструкторской и исследовательской деятельности ООО ГК «РосАвтоматизация ДВ», ООО НВФ «Сенсоры, модули, системы ДВ».

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на:

1. VI Всероссийской НПК студентов, аспирантов и молодых ученых "Молодежь и современные информационные технологии", г. Томск 2008 г.;

2. Региональной НПК "Молодежь и научно-технический прогресс", г. Владивосток, 2010 г.;

3. Всероссийской НТК студентов, аспирантов и молодых ученых: "Научная сессия ТУСУР-2010", г. Томск, 2010 г.;

4. XII Международной НПК: "Фундаментальные и прикладные Исследования, разработка и применение высоких технологий в промышленности", г. Санкт-Петербург, 2011 г.;

5. Международной НПК "Научные исследования и их практическое применение. Современное состояние и пути развития '2011", г. Одесса, 2011 г.;

6. VII Международной НПК: "Перспективы развития информационных технологий", г. Новосибирск, 2012 г.;

7. Международной НПК "Научные исследования и их практическое применение. Современное состояние и пути развития 2012", г. Одесса, 2012 г.;

8. XIV Международной НПК: "Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности и экономике", г. Санкт-Петербург, 2012 г.;

9. XV Международной НПК "Фундаментальные и прикладные исследования, разработка и применение высоких технологий в промышленности и экономике", г. Санкт-Петербург, 2013 г.;

10. II international research and practice conference "Science, Technology and Higher Education", Canada, 2013 r.

И. Международная НПК "Информационные технологии XXI века", г. Хабаровск, 2013 г.

Публикации. По результатам выполненных исследований опубликовано 14 работ, в том числе две работы в журналах из перечня ВАК, два свидетельства о государственной регистрации программ для ЭВМ, одиннадцать докладов на международных конференциях.

Объем работы. Работа состоит из введения, четырех глав, заключения, списка литературы, семи приложений и содержит 121 страницу основного текста, 10 таблиц и 65 рисунков, 112 наименований библиографических источников.

Содержание работы

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

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

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

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

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

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

1 ДАННЫЕ И ИХ ОБРАБОТКА В ИНФОРМАЦИОННО-ИЗМЕРИТЕЛЬНЫХ СИСТЕМАХ

Информационно измерительные системы (ИИС) необходимы для автоматического получения необходимой информации непосредственно от контролируемого объекта, ее преобразования, обработки с целью представления потребителю в требуемом виде, либо для осуществления функций автоматического контроля, технической диагностики, идентификации и др. Таким образом основное предназначение ИИС - автоматический сбор, обработка и передача больших массивов измерительных данных [65, 81, 88].

Особым видом ИИС являются системы телемеханики. На данный момент данные системы представляют большой интерес с точки зрения вопросов сжатия данных. Это связано с особыми требованиями предъявляемыми к данным системам, в частности:

- передачей сигналов с постоянной и переменной составляющими и очень медленно меняющимися данными;

- недопустимостью длительных задержек сигналов, т.е. возможностью передачи данных в режиме реального времени или «мягкого» реального времени, что подразумевает необходимость поступления на объекты управления командной или контрольной информации в темпе текущего управляемого технологического процесса. Допустимые временные рамки запаздывания информации, обеспечивающие режим реального времени зависят от скорости протекания контролируемых процессов и могут составлять от миллисекунд до нескольких секунд;

- необходимостью достаточно высокой точности передачи измеряемых величин (до 0,1%);

- высокой надежностью передачи команд управления (вероятность возникновения ложной команды должна быть не более 10"6-Ю"10;

- централизованностью переработки информации;

- высокой степенью автоматизации процессов сбора и использования информации.

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

1.1 Измерительные данные и их классификация

Под данными подразумеваются сведения, являющиеся объектом обработки в информационных человеко-машинных системах [87]. По природе происхождения данные обрабатываемые в ИИС можно классифицировать на следующие основные виды:

- Текстовые данные. Значительное количество компьютерных про�