Введение к работе
Актуальность темы.
В настоящее время одним основных направлений при создании перспективных портативных вычислительных систем (ПВС) является реализация на практике парадигмы интегрированной аппаратно- программной обработки телематических данных, поступающих от различных подсистем сбора и хранения мониторинговой информации. При этом, телематические данные как правило поступают в ПВС в различных кодовых форматах и структурах, соответствующих международным (ISO, ITU-T) и фирменным системам стандартов многоуровневой «Эталонной модели взаимодействия открытых систем» (ЭМ ВОС).
Особую актуальность при этом представляет решение задачи разработки моделей, алгоритмов и высокопроизводительных устройств декодирования разнородных по структуре и параметрам двоичных последовательностей кодированных телематических данных (КТД) прикладного, представительного и сеансового уровней ЭМ ВОС. Телематические стандарты данных уровней определяют сложные многоуровневые структуры сегментированных неравномерных кодов с адаптивным определением границ и параметров кодовых структур, а также сжатия данных с использованием статистических и алгебраических особенностей конкретных классов телематической информации.
Современный этап разработки алгоритмов и создания специализированных устройств вычислительной техники характеризуется наличием отдельных моделей, программно- и аппаратно- ориентированных алгоритмов и реализаций устройств обработки (определения параметров, уникальных кодовых структур, декодирования, определения ошибок и т.п.) отдельных классов КТД (ряда подклассов сигнализационных форматов, стандартов кодирования равномерных кодов, растровых и блочных форматов кодирования графических данных), обеспечивающих достаточно низкую скорость обработки существующих и перспективных классов КТД в ПВС.
Проведенные исследования в рассматриваемой проблемной области показали, что достаточно низкая производительность существующих устройств в основном определяется неполнотой учета в известных моделях структурно- статистических и алгебраических особенностей декодируемых телематических данных, высокой сложностью известных аппаратно- ориентированных алгоритмов обработки рассматриваемого класса кодированных данных, включенных в поля специфических двоичных структур КТД стандартов ЭМ ВОС.
Все вышеизложенное позволило определить в качестве основного противоречие между объективной необходимостью повышения быстродействия устройств декодирования КТД для ПВС и недостаточной разработанностью аппаратно- ориентированных моделей, алгоритмов и структурно- функциональной организации перспективных устройств декодирования рассматриваемых достаточно новых классов телематических форматов.
Анализ предпосылок для преодоления данного противоречия, а также существенного увеличения быстродействия декодирования КТД показал, что в основу решения задачи декодирования КТД для ПВС наиболее целесообразно положить структурно- алгебраический подход к обработке сложноструктурированных данных (декодированию, трансляции искусственных языков, синтаксическому анализу сложноструктурированных данных), развиваемый в последние годы в работах ученых ведущих зарубежных и российских школ, созданных К.Фу, Н.Хомским, В.Кнутом, С.В.Абламейко, С.С.Аджемовым, В.И. Городецким, С.Г.Емельяновым, Ю.И.Журавлевым, И.А.Каляевым, А.И. Костогрызовым, А.В.Николаевым, А.С.Сизовым, В.С.Титовым, Р.М. Юсуповым и др.
Тем не менее, вопросы применения метаграмматических моделей и разработки специализированных устройств декодирования с многоуровневой сегментацией КТД нашли частичное применение в современных системах управления и вычислительной технике.
В связи с вышеизложенным в качестве основной задачи диссертационных исследований выбрана разработка модели, алгоритма и структурно- функциональной организации устройства декодирования КТД на основе структурно- алгебраического подхода с применением формального аппарата метаграмматик.
Работа выполнялась в рамках плановых научно-исследовательских работ:
-«Методики и алгоритмы обработки и защиты информации в системах обработки конфиденциальных данных, подключенных к глобальной вычислительной сети Интернет» по направлению «Обработка, хранение, передача и защита информации» в рамках мероприятия 1.2.1 ФЦП «Научные и научно- педагогические кадры инновационной России» на 2009-2013 годы;
-«Модели и устройства для обоснования и поддержки ветвящихся продукционных вычислений»;
-«Исследование научно- технических путей создания систем обработки мониторинговой геопространственной информации» шифр «Ассистентка-К».
Целью диссертации является повышение быстродействия вычислительных устройств декодирования КТД для портативных ВС систем путем создания метаграмматической модели данного класса кодированных данных, алгоритма их декодирования с многоуровневой сегментацией полей переменной длины, а также разработки соответствующих технических решений на этой основе.
Объект исследования – портативные вычислительные устройства декодирования КТД.
Предмет исследования – модели, алгоритмы и структурно- функциональная организация вычислительного устройства декодирования телематических данных.
Достижение поставленной цели предполагает решение следующих частных задач:
1. Анализ тенденций развития устройств декодирования КТД, используемых в портативных ВС. Выявление ограничений существующих алгоритмов и устройств, анализ предпосылок для их совершенствования. Определение основных направлений исследований.
2. Разработка метаграмматической модели декодируемых КТД, учитывающей их основные структурно- алгебраические особенности.
3. Разработка алгоритма декодирования КТД на основе метаграмматической модели.
4. Разработка структурно-функциональной организации, технических решений устройства декодирования КТД. Экспериментальная оценка полученных результатов.
Методы и математический аппарат исследования. При проведении исследований использовались методы теории формальных грамматик и метаграмматик, кодирования/декодирования, проектирования элементов и устройств ЭВМ, принятия решений, а также теории алгоритмов.
Научная новизна и основные положения, выносимые на защиту.
Научная новизна заключается в получении следующих результатов, представленных в виде основных положений, выносимых на защиту.
1. Метаграмматическая модель декодируемых КТД, отличающаяся использованием транслирующих метаграмматик, позволившая в компактной форме задать основные правила формирования и преобразования структур КТД при их декодировании, снизить продукционную сложность используемых транслирующих грамматик по Хомскому до сложности линейных контекстно- свободных грамматик.
2. Алгоритм декодирования КТД, отличающийся использованием процедур многоуровневой сегментации полей переменной длины, позволяющий в 1,6-1,9 раза снизить число операций при декодировании различных классов КТД.
3. Структурно-функциональная организация устройства декодирования КТД, отличающаяся введением дополнительных модулей, осуществляющих основные операции многоуровневой сегментации полей переменной длины в предложенном алгоритме декодирования с соответствующими связями, обеспечивающая увеличение в 1,7-1,9 раз быстродействия при декодировании основных классов КТД.
Практическая ценность работы состоит в:
-разработке структурно-функциональной организации устройства декодирования основных классов КТД с использованием современной элементной базы, что улучшило эксплуатационные характеристики портативных вычислительных систем;
-существенном сокращении дублирования продукций в метаграмматической модели в 2,6 раза по сравнению с традиционной одноуровневой грамматикой, что позволило расширить область применения портативных вычислительных устройств;
-повышении быстродействия декодера для наиболее распространенных классов КТД в 1,7-1,9 раза;
-разработке технических решений для создания перспективных портативных вычислительных устройств декодирования КТД, используемых в системах сбора и обработки мониторинговой информации различного назначения.
Реализация и внедрение результатов исследования. Результаты диссертационной работы внедрены в НИР и учебном процессе кафедры программного обеспечения вычислительной техники Юго-Западного государственного университета при проведении занятий по дисциплине «Сети ЭВМ и телекоммуникаций», а также при создании подсистем обработки мониторинговых данных для перспективных портативных вычислительных систем НИИ прикладной математики и сертификации (г.Москва), ООО «Центр- капитал» (г.Курск).
Соответствие паспорту специальности.
Тематика, рассмотренная в диссертации, соответствует пунктам 1 и 2 паспорта специальности 05.13.05- Элементы и устройства вычислительной техники и систем управления: «1. Разработка научных основ создания и исследования общих свойств и принципов функционирования элементов, схем и устройств вычислительной техники и систем управления. 2. Теоретический анализ и экспериментальное исследование функционирования элементов и устройств вычислительной техники и систем управления в нормальных и специальных условиях с целью улучшения технико- экономических и эксплуатационных характеристик».
Апробация и публикация. Основные положения диссертационной работы были доложены и получили положительную оценку на 4 международных и всероссийских конференциях. По теме диссертационной работы опубликовано 13 научных работ (в том числе: 8 статей (из них 7 статей в изданиях по перечню ВАК), 5 материалов докладов на научных конференциях, получено 2 патента.
Личный вклад автора. В работах, опубликованных в соавторстве, лично соискателем в работах [5,8,9] определены особенности развития систем обработки телематических данных, форматов кодирования данного класса сложноструктурированных данных, их структурные особенности. В работах [2-4,10] предложены модели основных классов телематических данных, в работах [6,7,11,12] аппаратно- ориентированный алгоритм декодирования телематических данных и результаты экспериментальных исследований, в патентах на изобретения [14,15] предложены технические решения по реализации процедур сравнения и трансляции на основе продукционных алгоритмов .
Структура и объем работы. Диссертация состоит из введения, четырех разделов, заключения, списка использованной литературы (108 наименований). Текст диссертации включает 144 страницы, из них 114 страниц основного текста, 17 рисунков, 5 таблиц.
