автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Метаграмматическая модель, алгоритм и вычислительное устройство для декодирования телематических данных

На правах рукописи

Атакищев Артур Олегович

- V,

МЕТАГРАММАТИЧЕСКАЯ МОДЕЛЬ, АЛГОРИТМ И ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ ТЕЛЕМАТИЧЕСКИХ ДАННЫХ

Специальность 05.13.05-Элементы и устройства вычислительной техники и систем управленім.

Автореферат диссертации на соискание ученой степени кандидата технических наук

1 г т ¿т

Курск-2013

005543299

Работа выполнена в Юго- Западном государственном университете на кафедре программного обеспечения вычислительной техники.

Научный руководитель доктор технических наук, профессор

Емельянов Сергей Геннадьевич

Официальные оппоненты: Сизов Александр Семенович

доктор технических наук, профессор, заслуженный деятель науки РФ, Научно-исследовательский центр (г, Курск) ФГУП «18 ЦНИИ» МО РФ, главный научный сотрудник

Ватутин Эдуард Игоревич кандидат технических наук Юго-Западный государственный университет, доцент кафедры вычислительной техники

Ведущая организация Государственный университет- учебно-

научно-производственный комплекс, г. Орел

Защита диссертации состоится 24 декабря 2013 г. в 16 часов в конференц-зале на заседании диссертационного совета Д 212.105.02 при Юго-Западном государственном университете по адресу: 305040, г. Курск, ул.50 лет Октября, 94.

С диссертацией можно ознакомиться в библиотеке Юго-Западного государственного университета.

Автореферат разослан 23 ноября 2013 г.

Учёный секретарь х ^

диссертационного совета / Титенко Евгений Анатольевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы.

В настоящее время одним основных направлений при создании перспективных портативных вычислительных систем (ЛВС) является реализация на практике парадигмы интегрированной аппаратно- программной обработки телематических данных, поступающих от различных подсистем сбора и хранения мониторинговой информации. При этом, телематические данные как правило поступают в ПВС в различных кодовых форматах и структурах, соответствующих международным (ISO, ITU-T) и фирменным системам стандартов многоуровневой «Эталонной модели взаимодействия открытых систем» (ЭМ ВОС).

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

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

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

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

Анализ предпосылок для преодоления данного противоречия, а также существенного увеличения быстродействия декодирования КТД показал, что в основу решения задачи декодирования КТД для ПВС наиболее целесообразно положить структурно- алгебраический подход к обработке сложноструктурированных данных (декодированию, трансляции искусственных языков, синтаксическому анализу сложноструктурированных данных), развиваемый в последние годы в работах ученых ведущих зарубежных и российских школ, созданных К.Фу, Н.Хомским, В.Кнутом, С.В.Абламейко, С.С.Аджемовым, В.И. Городецким, С.Г.Емельяновым, Ю.И.Журавлевым, И.А.Каляевым, А.И. Костогрызовым, А.В.Николаевым, А.С.Сизовым, В.С.Титовым, P.M. Юсуповым и др.

Тем не менее, вопросы применения метаграмматических моделей и разработки специализированных устройств декодирования с многоуровневой сегментацией КТД нашли частичное применение в современных системах управления и вычислительной технике.

В связи с вышеизложенным в качестве основной задачи диссертационных исследований выбрана разработка модели, алгоритма и структурно-функциональной организации устройства декодирования КТД на основе структурно- алгебраического подхода с применением формального аппарата метаграмматик.

Работа выполнялась в рамках плановых научно-исследовательских работ:

-«Методики и алгоритмы обработки и защиты информации в системах обработки конфиденциальных данных, подключенных к глобальной вычислительной сети Интернет» по направлению «Обработка, хранение, передача и защита информации» в рамках мероприятия 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] определены особенности развития систем обработки телематических данных, форматов кодирования данного класса сложноструктурированных данных, их структурные особенности. В работах [24,10] предложены модели основных классов телематических данных, в работах [6,7,11,12] аппаратно- ориентированный алгоритм декодирования телематических данных и результаты экспериментальных исследований, в патентах на изобретения [14,15] предложены технические решения по реализации процедур сравнения и трансляции на основе продукционных алгоритмов .

Структура и обьем работы. Диссертация состоит из введения, четырех разделов, заключения, списка использованной литературы (108 наименований). Текст диссертации включает 144 страницы, из них 114 страниц основного текста, 17 рисунков, 5 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первом разделе выполнен анализ тенденций внедрения в РФ и ведущих зарубежных странах систем и устройств обработки телематической информации,

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

Сделан вывод, что КТД можно рассматривать как один из основных классов форматов данных в современных и перспективных системах управления.

Проведен анализ структурных особенностей основных классов форматов КТД, используемых в вычислительных системах. Показано, что при декодировании таких форматов должны быть учтены их структурные особенности, определяемые телематическими стандартами прикладного, представительного, сеансового уровней ЭМ ВОС. Для стандартов этих уровней характерны: сложная многоуровневая структура, использование динамически изменяемой структуры служебных команд, блоков, сегментов и кодовых элементов переменной длины, сложных алгоритмов синхронизации и определения декодируемых элементов неравномерных кодов сжатия; трансляции исходных одиночных и составных неравномерных кодов в выходные последовательности декодированных данных с увеличением объема в десятки и сотни раз.

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

Это приводит к существенному увеличению времени декодирования при использовании подобных моделей и алгоритмов для обработки КТД.

Все это определяет актуальность развития структурно- лингвистического подхода в направлении учета в моделях и алгоритмах декодирования КТД

иерархичности и неравномерности выделения кодовых слов и полей переменной длины телематических данных.

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

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

На основе выявленных структурных особенностей данного класса КТД в диссертации предложено в качестве формальной основы моделирования использовать транслирующую метаграмматику (ТМГ) следующего вида: G1CTa=< {Gs i( 0}, {Gj2(l)}, {GijC3)}, {Gi4<4)}, {GTi3C3)}, {Gi6w}, {Gi7(7)}, {Gi8is:)}, {Gi9C,)}, {GT; 1 oC 1 o)} ^„д^.

В данной ТМГ грамматики {Сг„(1)}моделируют в рекурсивной форме структуры допустимых иерархических систем телематических стандартов прикладного, представительного и сеансового уровней ЭМ ВОС. Продукции этих грамматик имеют вид Ао -►UAiltüA:!- ■ • teiAis; A|-»w7.)Pi|wcP2|. .. ws3Pis Р,—>kiS|kt|,..Данные грамматики являются регулярными, в гак терминалы соответствуют обозначениям телематических стандартов прикладного, представительного и сеансового уровней ЭМ ВОС.

Грамматики множества {G-,2(2)} моделируют общие синтаксические правила конкретных схем кодирования КТД.В частности, для стандартов типа Т.4 они определяют порядок чередования схем кодирования МН и MR для различных коэффициентов К (для нестандартных схем- чередование схем Н, без сжатия). Аналогично, для формата Т.81- чередование используемых схем кодирования (равномерных и неравномерных, без сжатия, с потерей и без потери информации).

{Gij(,)} определяют с помощью регулярных продукций порядок чередования сегментов кодированных КТД (строк, блоков, матриц), {G;,(4)}- допустимые продукционные правила чередования кодовых слов (в том числе и составных) в схеме КТД. В частности, для формата Т.4 данные продукции имеют усеченный (по сравнению с известными моделями) вид: Ao-»IhAi|IrA6|IrtsA14; А,->1^:11.^311^; А2->-1в6Аз|1вбА4; Aj—>1отА5|1ачА1|1вчА4; A4->IFA0; Aj-^I^AIIUhA^

А6->1пА6|1,Л6|11А7|1пА4|1вА4; Ar-^IofiAsIlBßAglUAiolImAnlT^II^;

А8->1ввА9| WW А9->1очА12|1вчА6| IpA,; Aio->IB4An|I,,(A4; Ац-Я^и^-А^вбА^ A,2->IBmA,JIctA4; А13—>IBGA6|IBr>A4.

В грамматике используются только регулярные продукции и обобщенные терминалы (типа I), которые соответствуют конкретному кодовому слову п стандарте Т.4. Продукции содержат нетерминалы, обозначаемые заглавными буквами А, соответствующими состояниям при переходах от кодовых слов различных длин и цветов в формате Т.4.

{(Зги .}- множества транслирующих грамматик, моделирующих правила трансляции исходных двоичных символов равномерного или неравномерного кода в выходные последовательности сигнализационных, символьных, растровых или блочных данных в соответствии с телематическими стандартами. В отличие от обычных грамматик более высоких уровней грамматики данного уровня имеют следующий вид:

0Т;5(з,=<5;,С5>,УМ5(5:),{УТвх;5(5), УТвых;5<!)} Д;5(5)>. В этой транслирующей грамматике множество терминалов разбито на два подмножества входных УТвХ15<5) и выходных Утвьтз(5) символов, соответствующих исходным кодовым словам и декодированным последовательностям, соответственно. Множество транслирующих продукций Я;/5' имеет вид: АЫ!(з)->а^<5)Ь;;3(5,Ай5<5), где АЬ!С!>, Аш<!>е адг^еУтвыД ^¡5(5)еУТвых;5С5>. В диссертационной работе транслирующие грамматики с подобными продукционными правилами предложено называть линейными транслирующими грамматиками (ЛИ), а метаграмматики, содержащие подобные грамматики,- линейными транслирующими метаграмматиками (ЛТМГ).

Грамматики {^6<б)} моделируют в рекурсивной форме допускаемые телематическими стандартами представительного уровня структуры последовательностей информационных блоков, {С17(Т)}- структуру полей этих блоков, {&18(8)}- допускаемые телематическими стандартами сеансового уровня структуры последовательностей служебных и информационных команд подуровней документа и сеанса; {(V9'}- структуру полей этих команд. {Сгпн>(10)}-множества транслирующих грамматик, моделирующих правила трансляции исходных двоичных символов полей информационных блоков и команд представительного и сеансового уровней в выходные коды параметров данных структур. Грамматики имеют вид, аналогичный {Оп5(5'}.

В схеме метаграмматики ^^гд правила согласования Т8(1) задают порядок декомпозиции терминалов грамматик верхнего уровня на цепочки, порождаемые грамматиками нижних уровней МГ. С помощью ТР(4) правил согласования задается порядок данной декомпозиции. Т8(3) правила согласования определяют переходы от терминалов к начальным символам грамматик нижележащих уровней.

Путем комбинированного использования в схеме \УПД правил согласования Т8(1), Т8(3) и ТР(4) в предложенной модели в отличие от известных возможна спецификация более сложных кодовых конструкций с использованием в ТМГ на большинстве уровней регулярных грамматик. При этом контекстно- свободные транслирующие грамматики являются линейными, что существенно упрощает процедуры их синтаксического разбора при декодировании и трансляции в декодированную последовательность. В случае использования для этих целей обычных формальных грамматик необходимы более сложные и громоздкие модели на основе грамматик непосредственно- составляющих по классификации Хомского.

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

дублирование продукций, что для рассматриваемого случая снижает более чем в 2,6 раза число продукций по сравнению с одноуровневой грамматикой.

В целом, проведенные исследования позволили сделать вывод, что применение ТМГ создает необходимые предпосылки для создания более эффективных (в плане снижения временной сложности) алгоритмов декодирования КТД большинства известных классов, используемых в вычислительных (в т.ч. портативных) системах.

В третьем разделе, базируясь на разработанной метаграмматической модели в рамках решения третьей частной задачи исследований, ¿Гоздан алгоритм декодирования КТД с многоуровневой сегментацией полей переменной длины.

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

Предложенный алгоритм декодирования КТД предусматривает выполнение следующих основных шагов.

1. Формирование заполнения эталонных ячеек памяти в соответствии со структурами переходов (правилами согласования и продукциями) и элементами разработанной метаграмматической модели КТД.

2. Формирование таблиц трансляции кодов и полей блоков и команд рассматриваемых уровней ЭМ ВОС в соответствии с транслирующими продукционными правилами метаграмматической модели.

3. Ввод цепочки декодируемой последовательности с обеспечением буферизации и привязкой к структурам блоков нижележащих уровней ЭМ ВОС, полученным при обработке КТД в процессе решения конкретных задач их сбора и предобработки.

4. В соответствии с текущей ситуацией многоуровневого синтаксического анализа ТМГ- анализ идентификационных структур команд подуровня документа и подуровня сеанса сеансового уровня, информационных блоков представительного уровня. Вычисление на основе транслирующих продукционных правил параметров их сегментации и сегментации текущих параметров и групп параметров.

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

6. Выделение в обрабатываемой последовательности данных состояний достижения границ кодовых последовательностей прикладного уровня ЭМВОС.

7. Выполнение для текущего состояния синтаксического анализа последовательно- параллельных процедур определения актуализируемых локальных таблиц декодирования начальной части анализируемой цепочки КТД прикладного уровня ЭМ ВОС.

8. Определение границ и структуры кодовых слов на текущем этапе разбора с использованием процедур поиска и сравнения равномерных и неравномерных кодов основных классов КТД (для режимов со сжатием, без сжатия, с предварительным распознаванием символов и отдельных элементов изображений).

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

10. Проверка достижения границы сегментированной последовательности прикладного уровня. При достижении границы-переход на шаг 11, в противном случае- на шаг 6.

11. Смена состояния в дереве разбора метаграмматической модели и переход к декодированию следующей сегментированной цепочки КТД Если достигнуто заключительное состояние в разборе КТД- выдача сигнала об окончании декодирования, в противном случае- переход на шаг 4.

При выполнении данного алгоритма осуществляется синтаксический анализ (грамматический разбор) предложенной метаграмматической модели с модификацией под особенности многоуровневых адаптивно сегментированных структур КТД рассматриваемых уровней.

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

На примере типовой одномерной схемы со сжатием формата ITU-T Т4 выполнены оценки емкостной и временной сложности процедур(«худший вариант») алгоритма при реализации предложенных решений. Оценки показали что первая из них имеет меньшую (в 5,7 раз) емкостную сложность (требует менынии объем эталонной памяти), но проигрывает по временной сложности в 4,3 раза При возрастании объемов локальных кодовых таблиц (^модифицированная схема Хаффмана) данная разница увеличивается

Проведенные теоретически*; оценки временной и емкостной сложности разработанного алгоритма в целом (при выборе второй процедуры) с учетом реальных размеров основных .и вспомогательных кодов ьк таблиц телематических кодов, показали, при реализации подобных процедур выигрыш по временной сложности составляет 1,6 раз, а проигрыш по емкостной- всего 1 2 раза. '

Сравнение с известными алгоритмами показало, что на аналогичных подклассах КТД предложенный алгоритм путем учета многоуровневых продукционных правил, отраженных в ТМГ, позволяет в 1,6-1,9 раза снизить общее число операций при декодировании по сравнению с лучшим из известных алгоритмов (адресно-наращиваемый алгоритм декодирования), по сравнению с ним также исключить ошибки сегментации различных классов КТД, обеспечить определение параметров сеансового и представительного уровней ЭМ БОС.

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

телематических данных.

В целом, полученные оценки подтверждают, что созданный алгоритм на основе ТМГ создает предпосылки для реализации более быстродействующих

устройств декодирования КТД.

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

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

На рис.1 представлена структурно-функциональная организация (СФО) устройства, реализующего созданный алгоритм декодирования КТД. В отличие от известной схемы устройства декодирования, реализующего процедуры декодирования префиксных кодов на основе адресно- наращиваемого алгоритма, структурной особенностью предлагаемой организации является использование дополнительных модулей эталонной памяти для задания правил согласования и продукционных переходов рассматриваемых уровней ЭМ ВОС, а также ряда модулей (выделены на рис.1 темным тоном), обеспечивающих реализацию процедур многоуровневого транслирующего синтаксического анализа ТМГ.

Особенностью заполнения дополнительных ячеек памяти является их разбиение на области, в соответствии с используемыми в ТМГ отдельными простыми и транслирующими грамматиками, правилами согласования, а также реализация привязки локального адреса ячейки с его содержимым по правилу «адрес-транслированное значение». Правила согласования и продукционные правила в большинстве рассматриваемых случаев задаются в виде «нетерминал-адрес строки в локальной области памяти», «терминал-номер ячейки в строке локальной области памяти».

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

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

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

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

Экспериментальная проверка работоспособности устройства проводилась при макетировании устройства с использованием встроенных модулей тестирования ПЛИС по реальным массивам телематических данных общим объемом более 4х 10б кодовых слов.

Зависимости времени декодирования массива данных объемом 0,86* 105 кодовых слов одного из наиболее сложных в обработке стандарта Т. 4 от допускаемого размера кодируемых строк (соответственно числа элементов кодовых таблиц) для предложенного технического решения и устройства на основе адресно-наращиваемого алгоритма представлены в таблице 1. В данной таблице также представлены оценки необходимого объема памяти для

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

Таблица 1

Размер кодируемых строк

1728 2048 2432 3072

Предложенное решение Время декодирования (сек) 0,34 0,38 0,46 0,58

Об! .ем памяти (Мбайт) 2,35 2,45 2,58 2,73

Устройство на основе адресно-наращивасмого алгоритма Время декодирования (сек) 0,58 0,68 0,84 1,11

Объем памяти (Мбайт) 2,12 2,17 2,24 2,29

Сравнение рассматриваемых вариантов

Выигрыш по времени декодирования 1,73 1,78 1,83 1,91

Проигрыш но общему объему используемой намята 1,11 1.13 1,15 1,19

Экспериментальная проверка устройства с учетом всех проводимых при декодировании КТД операций показала, что предложенные технические решения позволяют на основе реализованного алгоритма при использовании одинаковой элементной базы повысить общее быстродействие в 1,7-1,9 раза при декодировании вышеперечисленных типов КТД по сравнению с лучшим из известных технических решений, реализующих адресно- наращиваемый алгоритм декодирования. При этом, дополнительно возрастает объем необходимой памяти для хранения ТКДС не более чем в 1,2 раза.

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

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

В заключении сформулированы основные результаты диссертационной работы.

Входная

последош

ТбЛЬИОСТЪ

(данные и

такт.

сигналы)

к а

2 » п а

11 £ & I

Входное буферное ОЗУ 2

Входное буферное ОЗУ 1

Модуль управления сегментацией КТД

Модуль синтаксически

управляемого ОДЧИвЛЮШЯ

ітшілрол сегментации

Модуль многоуровневого

управления процедурами

декодирования КТД на основе ТМГ

Модуль вычисления

параметров составных

КОДОВЫХ конструкций

КТД

Модуль обработки

ошибок декодирования

КТД

Модуль упрощения поиском, МЛШОЮПХСМ ;Я*ІЄЄК памяти в счншвлиисм КС КТД в сооткегегаии с состоянием разбора ТМГ

Модуль преобразования КС КТД в вьгсодную последовательность декодированных данных

Модуль управления преобразованием КС и выходной буферизацией на основе ТМГ

Выходное буферное ОЗУ 2

Выходное буферное ОЗУ 1

Выход мая

послед ователь ность

Рис. 1. Структурно-функциональная организация устройства

Входы/выходы (шлейфные)

Рис. 2. Структурная схема модуля поиска соответствия кодовых слов КТД на базе ПЛИС

Сигнал считывания КТД

Рис. 3. Структурная схема модуля считывания транслированных кодовых слов

ОСНОВНЫЕ НАУЧНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

3. Предложен алгоритм декодирования КТД с многоуровневой сегментацией полей переменной длины, позволяющий в 1,6-1,9 раза снизить число операций при декодировании различных классов КТД.

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

5. Разработана структурно-функциональная организация устройства декодирования КТД отличающаяся введением дополнительных модулей, осуществляющих основные операции многоуровневой сегментации полей переменной длины в предложенном алгоритме декодирования с соответствующими связями и обеспечивающая увеличение быстродействия в 1,7-1,9 раза при декодировании основных классов КТД Экспериментальная проверка подтвердила совпадение теоретических и полученных на практике оценок.

Список публикаций по теме диссертации

Статьи в научных изданиях по перечню ВАКминобрнауки РФ

1. Атакищев, А О. Метаграмматическая модель кодированных телематических данных [Текст] / А.О.Атакищев // Известия Юго-Западного государственного университета.-2013.-№3(48).-С.49-52.

2. Атакищев, А. О. Основные особенности форматов кодирования телематических данных [Текст] / С.Г. Емельянов, А.О. Атакищев // Известия Юго-Западного государственного университета-2013.-№3(48).-С.52-58.

3. Атакищев, А.О. Использование квадродеревьев в динамических электронных фотокартах [Текст] / АО. Атакищев, A.B. Николаев, A.B. Белов // Известия Юго-Западного государственного университета.-2011 .-№6(39), ч.2.-С.36-40.

4. Метод, алгоритм и техническое решение параллельного поиска и подстановки на ассоциативной памяти [Текст] / А.О. Атакищев [и др.] // В мире научных открытий. Математика Механика Информатика-№1.1(25).-2012-С 45-47

5. Продукционные сети как модели генерации и анализа вариантов принимаемых управленческих решений [Текст] / А.О. Атакишев [и др.] // Т«СОММ Телекоммуникации и транспорт.-2008.-№4.-С. 23-24.

6. Применение контекстно- свободных грамматик для обработки текстов на естественном языке [Текст] / А.О. Атакищев [и др.] // Известия Юго-Западного государственного университета. Серия Управление, вычислительная техника, информатика. Медицинское приборостроение.-2012.-№2.. Ч.1.-С. 97-100.

7. Продукционная машина-генератор для обработки символьных данных дискретных объектов [Текст] / А. О. Атакищев [и др.] // Известия Юго-Западного государственного университета. Серия Управление, вычислительная техника, информатика. Медицинское приборосгроение.-2012.-№2, Ч.1.-С. 111-115.

Статьи и материалы конференций

8. Análisis de Soluciones Technicas para el Tratamiento de Alta Productividad de Information Simbólica [Text] / A.O. Atakishchev [et al]// Revista Eidos.-№5.-2012.-P. 22-27,

9. Атакищев, A.O. Основные особенности применения метаграмматик для формального описания вариантов сложноструктурированных стратегий поиска [Текст] / А.О. Атакищев, Н.И. Занун, С.А. Макаренков // Информационно-вычислительные технологии и их приложения: сборник статей XIII Международной научно-технической конференции.-Пенза: Академия информатизации образования РФ, 2010.-С. 19-22.

10. Атакищев, АО. Применение метаграмматик для формального описания вариантов сложно структур иро ванных стратегий поиска кодированных документов при управлений социальными и экономическими системами [Текст] / АО. Атакищев," Н.И. Занун, С.А. Макаренков // Инновационные подходы к развитию современной экономики, управления и образования: сборник научных статей Всероссийской научно- практической конференции.- Курск: РГСУ, 2010.-С. 35-38.

11. Продукционный алгоритм распознавания параметров обмена данными при тестировании сетей ЭВМ [Текст] / А.О. Атакищев [и др.] // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-2010:сборник материалов 9 Международной конференции Курск, гос. техн. ун-т.-Курск, 2010,-С. 216-218.

12. Атакищев, АО. Структурно-лингвистические методы в потоковых ГРИД-системах / О.И. Атакищев, Н.И. Занун, А О. Атакищев // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений "и символьной информации. Распознавание-2010: сборник материалов 9 Международной конференции Курск, гос. техн. ун-т.-Курск,2010-С. 167-168.

13. Атакищев, А О. Модель процедур обмена данными в высокоскоростных сетях ЭВМ [Текст] / А.О. Атакищев // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. Распознавание-2010: сборник материалов 9 Международной конференции Курск, гос. техн. ун-т.-Курск,2010.-С. 168-170.

Патентные материалы

14. Пат. 2430408 Российская Федерация, MITK7G06F17/30. Устройство для параллельного поиска вхождений и пересечений слов [Текст] / Атакищев АО. [и др.].-№2010112170/08; заявл. 29.03.2010; опубл. 27.09.2011, Бюл.№27.14 с.

15.Пат. 2469425 Российская Федерация, MITK7GllC15/00. Ассоциативная запоминающая матрица маскированного поиска вхождений [Текст] / Атакищев А.О. [и др.].-№2010119752/08; заявл. 17.05.2010; опубл. 10.12.2012, Бюл.№34.15с.

Соискатель . _.........—...,. Атакищев АО.

Подшгсаповпечагь20.11.2013 Фярмат60х&4 1/16.

Пот. л. 1 Тираж 120 dio. Заказ Юн>-3аиадный государственный упшкратгт 305040, г.К>рск, ул. 50 лет Октября, 94

Министерство образования и науки РФ

ФГБОУ ВПО Юго-Западный государственный университет

04201454167

МЕТА ГРА М МАГ И ЧЕС КАЯ МОДЕЛЬ, АЛГОРИТМ И ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО ДЛЯ ДЕКОДИРОВАНИЯ ТЕЛЕМАТИЧЕСКИХ ДАННЫХ

Специальность 05.13.05 Элементы и устройства вычислительной техники и систем управления.

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

Научный руководитель доктор технических наук, профессор Емельянов С.Г.

На правах рукописи

Атакищев Артур Олегович

Курск-2013

СОДЕРЖАНИЕ

Введение..............................................................................4

1. Анализ тенденций развития устройств декодирования телематических данных, используемых в портативных вычислительных системах, анализ предпосылок для их совершенствования. Определение основных направлений исследований...................................................12

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

вычислительных системах на современном этапе..................................12

1.2.Основные особенности форматов кодирования телематических

данных.......................................................................................17

1.3. Анализ предпосылок решения основной научной задачи и выбор

направлений диссертационных исследований......................................47

Выводы............................................................................80

2. Разработка метаграмматической модели декодируемых телематических данных.................................................................82

2.1. Особенности разработки метаграмматической модели декодируемых телематических данных...............................................82

2.2. Метаграмматическая модель декодируемых телематических данных, учитывающая их структурно- лингвистические особенности неравномерных префиксных кодов....................................................96

2.3. Основные свойства транслирующих метаграмматик.................99

Выводы..............................................................................103

3. Разработка алгоритма декодирования телематических данных на основе метаграмматической модели..................................................105

3.1. Общие особенности разработки алгоритмов декодирования на

основе метаграмматик..................................................................105

3.2. Разработка алгоритма декодирования телематических данных с

многоуровневой сегментацией полей переменной длины......................109

3.3. Общие характеристики предложенного алгоритма

декодирования............................................................................115

Выводы...........................................................................117

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

4.1. Основные особенности создания устройства декодирования телематических данных для портативных вычислительных систем......................................................................................119

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

4.3. Экспериментальная проверка устройства............................127

Выводы............................................................................128

Заключение......................................................................130

Список использованной литературы........................................132

ВВЕДЕНИЕ

В настоящее время одним основных направлений при создании перспективных портативных вычислительных систем (ЛВС) является реализация на практике парадигмы интегрированной аппаратно-программной обработки телематических данных, поступающих от различных подсистем сбора и хранения мониторинговой информации. При этом, телематические данные как правило поступают в 1IBC в различных кодовых форматах и структурах, соответствующих международным (ISO, ITU-T) и фирменным системам стандартов многоуровневой «Эталонной модели взаимодействия открытых систем» (ЭМ ВОС).

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

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

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

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

Анализ предпосылок для преодоления данного противоречия, а также существенного увеличения быстродействия декодирования КТД показал, что в основу решения задачи декодирования КТД для ПВС наиболее целесообразно положить структурно- алгебраический подход к обработке сложноструктурированных данных (декодированию, трансляции искусственных языков, синтаксическому анализу сложноструктурированных данных), развиваемый в последние годы в работах ученых ведущих зарубежных и российских школ, созданных К.Фу, Н.Хомским, В.Кнутом, С.В.Абламейко, С.С.Аджемовым, В.И. Городецким, С.Г.Емельяновым, Ю.И.Журавлевым, И.А.Каляевым, А.И. Костогрызовым, А.В.Николаевым, А.С.Сизовым, В.С.Титовым, P.M. Юсуповым и др.[1-3,31-39,43-45, 47,5458,64-69,73-75,100-102].

Тем не менее, вопросы применения метаграмматических моделей и разработки специализированных устройств декодирования с многоуровневой

сегментацией КТД нашли частичное применение в современных системах управления и вычислительной технике.

В связи с вышеизложенным в качестве основной задачи диссертационных исследований выбрана разработка модели, алгоритма и структурно- функциональной организации устройства декодирования КТД на основе структурно- алгебраического подхода с применением формального аппарата метаграмматик.

Работа выполнялась в рамках плановых научно-исследовательских работ:

-«Методики и алгоритмы обработки и защиты информации в системах обработки конфиденциальных данных, подключенных к глобальной вычислительной сети Интернет» по направлению «Обработка, хранение, передача и защита информации» в рамках мероприятия 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 патента.

Личный вклад автора. В работах, опубликованных в соавторстве, лично соискателем в работах [10,13,14] определены особенности развития систем обработки телематических данных, форматов кодирования данного класса сложноструктурированных данных, их структурные особенности. В работах [7-9,15] предложены модели основных классов телематических данных, в работах [11,12,16,17] аппаратно- ориентированный алгоритм декодирования телематических данных и результаты экспериментальных исследований, в патентах на изобретения [17,18] предложены технические решения по реализации процедур сравнения и трансляции на основе продукционных алгоритмов .

Структура работы.

Во введении обоснована актуальность темы, сформулированы цель и

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

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

Проведен анализ структурных особенностей основных классов форматов КТД, используемых в вычислительных системах.

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

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

В третьем разделе, базируясь на разработанной метаграмматической модели в рамках решения третьей частной задачи исследований, создан алгоритм декодирования КТД с многоуровневой сегментацией полей переменной длины.

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

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

В заключении сформулированы основные результаты диссертационной работы.

РАЗДЕЛ 1. Анализ тенденций развития устройств декодирования теле