Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей Чижов Андрей Алексеевич

Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей
<
Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей
>

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Чижов Андрей Алексеевич. Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей : Дис. ... канд. техн. наук : 05.13.05 Курск, 2005 185 с. РГБ ОД, 61:06-5/226

Содержание к диссертации

Введение

Задачи распознавания сигналов плезиохроннои и синхронной цифровой иерархии в цп вс. постановка задачи и выбор направлений исследований

1.1 Обзор цифровых систем передачи данных на основе плезиохронной и синхронной цифровой иерархии.

1.2 Анализ особенностей формирования ЦП в системах с плезиохронной и синхронной цифровой иерархией

1.2.1 Анализ особенностей PDH-иерархии для подсистемы доступа к данным

1.2 2 Анализ особенностей SDH-иерархии для подсистемы доступа к данным

1.3 Обзор устройств-мультиплексоров в высокоскоростных цифровых системах передачи

1.3.1 Плезиохронные мультиплексоры в высокоскоростных цифровых системах передачи

1.3.2 Гибкие мультиплексоры в высокоскоростных цифровых системах передачи

1.3.3 Синхронные мультиплексоры в высокоскоростных цифровых системах передачи

1.4 Обзор способов распознавания и сущность прелагаемого подхода

Выводы * 43

Разработка структурно-лингвистических описанрш 45 цп вс на основе систем синхронной цифровой иерархии

2.1 Обобщенная характеристика свойств метаграмматик и грамматик с управляемым предшествованием, используемых 45 для формального описания сигналов синхронной цифровой иерархии

2.2 Грамматики с управляемым предшествованием. Их применение для распознавания сигналов синхронной цифровой иерархии

2.3 Формальные свойства метаграмматик с управляемым предшествованием, используемых для структурно-лингвистического описания сигналов синхронной цифровой иерархии

2.4 Разработка эталонных транслирующих метаграмматик, описывающих сигналы синхронной цифровой иерархии

2.4.1 Построение структурно-лингвистических описаний фреймов синхронной цифровой иерархии

2.4.2 Построение транслирующей метаграмматики, специфицирующей синтаксическую структуру мультиплексирования сигналов синхронной цифровой иерархии

Выводы 64

Разработка структурно-лингвистического метода и 66 алгоритмов распознавания сигналов синхронной цифровой иерархии в цп вс

3.1 Разработка метода неполного синтаксического анализа транслирующих метаграмматик с управляемым предшествованием - 66

3.2 Разработка метода полного синтаксического анализа транслирующих метаграмматик с управляемым предшествованием - 84

3.3 Комбинированный структурно-лингвистический метод распознавания сигналов синхронной цифровой иерархии 93

Выводы 99

Особенности реализации устройства адаптршного демультиплексирования цп для вс на основе систем плезиохронной и синхронной цифровой иерархии

4. Разработка структурно-функциональной организации устройства адаптивного демультиплексирования ЦП для ВС, построенных на основе систем плезиохронной и синхронной цифровой иерархий

4.1.1 Обобщенный сравнительный анализ и обоснование выбора ]П?

использованной для реализации устройства АД в ВС

элементной базы

4.1.1.1 Анализ применимости элементной базы для реализации УАД в ВС

4.1.1.2 Основные особенности выбранного типа ППЛИС. 104

4.1.2 Анализ структур и параметров ЦП в ВС, построенных на 1П7 основе систем плезиохронной и синхронной цифровой иерархий

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

адаптивного демультиплексирования ЦП в ВС

4.2 Особенности реализации основных блоков устройства АД ЦП в ВС

4.2.1. Блок накопления и поиска синхронизма 118

4.2.2. Блок синтаксического анализа 122 А ПО г - 13

4.2.3. Блок управляемой трансляции

4. Результаты экспериментальных исследований устройства адаптивного демультиплексирования ЦП в ВС построенных на основе систем плезиохронной и синхронной цифровой иерархией

Выводы 136

Заключение 138

Литература

Введение к работе

В настоящее время одним из магистральных направлений создания устройств вычислительной техники является разработка средств высокоскоростного доступа к данным в составе подсистем распределенной обработки информации. Современный этап развития подобных устройств вычислительной техники характеризуется полномасштабной интеграцией технологий обработки информации и глобальных систем обмена данными, использующими цифровые синхронные (SDH) и плезиохронные (PDH) иерархии. Сближение двух разных классов цифровых систем обусловило необходимость создания новых типов устройств вычислительной техники, выступающих как согласующее звено между существующими и перспективными цифровыми системами обмена данными и оконечным оборудованием в вычислительных сетях (ВС). Сложность решения задачи обработки цифровых потоков (ЦП) определяется большим разбросом скоростей передачи данных (от 1,5 Мбит/с до 40 Гбитс/с), сложной структурой данных, определяемой многоуровневой схемой мультиплексирования и наличием динамически изменяющихся параметров.

Анализ существующих устройств обработки PDH и SDH ЦП, показал, что большинство из них ориентированы на обработку ограниченных групп ЦП без возможности анализа и адаптивной перестройки. Это обстоятельство не позволяет использовать такие устройства для обработки постоянно расширяющегося класса ЦП. Указанные ограничения определили основное противоречие между объективной необходимостью обработки в едином устройстве большого количества структур высокоскоростных ЦП в ВС в реальном масштабе времени и недостаточной разработанностью методов и технических средств адаптивной обработки этих потоков.

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

числом априорно неизвестных параметров рассматривается как единая процедура многоэтапного структурно-лингвистического распознавания и многоэтапной трансляции входного языка цепочек высокоскоростных ЦП. При этом в качестве эталонного описания множества распознаваемых и транслируемых классов разнородных данных используются метаграмматики (МГ), представляющие собой взаимосвязанную многоуровневую систему формальных грамматик, описывающих правила формирования синтаксических структур обрабатываемых PDH и SDH ЦП. В этом случае процедуры распознавания и трансляции сводятся к процедурам синтаксического анализа в МГ.

В известных работах показано, что в рамках данного подхода возможно создание компактных структурно-метаграмматических описаний иерархических структур ЦП, позволяющих с позиций синтаксического анализа определять структуру ЦП, его параметры и осуществлять их последующее демультиплексирование. Вопросы применимости отдельных подклассов метаграмматик для описания сложноструктурированных объектов нашли отражение в работах Атакищева О.И., Городецкого В.И., Юсупова P.M., К. Фу и других ученых. Вместе с тем, анализ особенностей, рассматриваемых ЦП, показал, что они имеют специфическую многоуровневую структуру, существенно отличающуюся от уже рассмотренных структур ЦП. В связи с этим актуальной является научно-техническая задача разработки метода структурно-лингвистического анализа класса ЦП и устройства адаптивного демультиплексирования ЦП PDH- и SDH-иерархии с использованием современных технологических решений и элементной базы электронной вычислительной техники (ЭВТ).

Работа выполнялась в рамках плановых научно-исследовательских и опытно-конструкторских работ: в программе «Научные исследования высшей школы по приоритетным направлениям науки и техники» раздел «210.01. Инструментальные средства информационной поддержки жизненного цикла продукции», проект «Разработка методов информационной интеграции и

комплексной поддержки жизненного цикла сложных технических систем» (2003-2004г.г.); в программе «Разработка и внедрение комплексной компьютерной системы информационной поддержки жизненного цикла наукоемкой продукции» (2004г.).

Объект исследования - высокоскоростные устройства распределенной обработки разнородных данных в ВС.

Предмет исследования - процессы структурно-лингвистического анализа ЦП и демультиплексирования на базе средств ЭВТ в устройствах распределенной обработки разнородных данных в ВС.

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

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

1. Анализ тенденций развития подсистем обмена данными в ВС на базе PDH- и
SDH-иерархии и определение путей реализации устройств анализа и
демультиплексирования ЦП на элементах ЭВТ.

2. Обоснование и разработка эталонного формального структурно-
лингвистического описания ЦП в ВС.

3. Разработка метода неполного синтаксического анализа и алгоритмов
обработки ЦП на основе регулярных транслирующих МГ.

4. Синтез структурно-функциональной организации и алгоритмов
функционирования программно-аппаратного устройства адаптивной обработки
ЦП.

5. Разработка технических решений блоков программно-аппаратного
устройства обработки ЦП, позволяющих сократить объем оборудования и
имеющих возможность самостоятельного использования. Экспериментальная
оценка качества функционирования предлагаемого программно-аппаратного
устройства.

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

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

  1. Создано эталонное формальное описание разнородных данных PDH и SDH на основе регулярных транслирующих МГ, позволившее в компактной форме задать основные правила формирования структур обрабатываемых на средствах ЭВТ классов ЦП в ВС.

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

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

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

Практическая ценность работы состоит в:

разработке структурно-функциональной организации

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

экономические и эксплуатационные характеристики, а также позволило существенно сократить объем оборудования;

- уменьшении в среднем на 15 % объема анализируемой выборки при
определении структуры ЦП и, как следствие, повышении скорости его
обработки;

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

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

  1. Эталонное формальное описание ЦП PDH и SDH-иерархии в виде регулярных транслирующих МГ(РТМГ).

  2. Метод и алгоритмы неполного синтаксического анализа PDH и SDH потоков, ориентированные на использование предложенного класса МГ.

3. Структурно-функциональная организация устройства адаптивного
демультиплексирования высокоскоростных ЦП.

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

Апробация и публикация. Основные положения диссертационной работы были доложены и получили положительную оценку на XIX научно-технической конференции (в/ч 45807-P/I, 2001г.) и на научной конференции «Распознавание-2003» (Курский ГТУ, 2003 г.). По теме диссертационной работы опубликовано 14 работ, в том числе: 6 статей, 5 изобретений, 3 тезисов докладов на научных конференциях.

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

функциональная организация устройства адаптивного демультиплексирования высокоскоростных ЦП и реализованы отдельные узлы устройства.

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

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

Проведенный анализ известных устройств мультиплексирования PDH и SDH сигналов показал, что большинство из них ориентированы на обработку фиксированных групп ЦП за счет внедрения в состав блоков управления (БУ) информации о структуре обрабатываемых данных, что определяет ограниченный характер их применимости. Конвейерная организация синхронных мультиплексоров создает достаточные предпосылки для высокоскоростного доступа ко всему классу иерархических SDH-форматов, имеющих модульную структуру формирования. Вместе с тем конвейерная организация должна быть дополнена возможностью адаптивной перестройки структуры устройства и алгоритмов обработки под постоянно расширяющийся класс ЦП и для условий априорной неопределенности относительно структуры и параметров ЦП.

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

Во втором разделе выполнена разработка формального аппарата для

^ эталонного продукционного описания ЦП в виде регулярных транслирующих

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

*f вычисления длин этих фрагментов обусловил необходимость использования

грамматик управляемого предшествования (ГУП), в которые введены дополнительные экстралингвистические правила.

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

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

^ при демультиплексировании, а использование ряда правил согласования и

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

В третьем разделе с ориентацией на предложенный класс формальных описаний ЦП PDH и SDH разрабатывается способ неполного синтаксического

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

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

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

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

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

Анализ особенностей формирования ЦП в системах с плезиохронной и синхронной цифровой иерархией

Перечень типов оборудования определяется основными функциональными задачами, решаемыми системой передачи:

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

2) транспортировка агрегатных блоков - задача транспортировки, решаемая мультиплексорами ввода/вывода;

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

4) объединение нескольких однотипных потоков задача концентрации, решаемая устройствами-концентраторами;

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

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

Мультиплексоры - устройства для объединения/разделения независимых исходных потоков данных из нескольких отдельных подчиненных каналов, служащих для их передачи по меньшему числу общих каналов/линий. Мультиплексоры для цифровых сетей отличаются большим разнообразием и возможностями: 1) по различным интерфейсным окончаниям; 2) схемами мультиплексирования (синхронными и асинхронными); 3) числом ступеней мультиплексирования (одноступенчатые и многоступенчатые); 4) линейными (станционными) интерфейсами; 5) емкостью (числом каналов); 6) резервированием и управлением, и т.д.

Стандартные схемы мультиплексирования потоков данных разработаны ITU и описаны в рекомендациях G.704, 732, 741, 707, 708, 709. На рисунке 1.3 приведена общая схема мультиплексирования данных в плезиохронной и синхронной цифровых иерархиях. В таблице 1.1 приведены сводные характеристики мультиплексоров ЦП SDH по ведущим фирмам-производителям. Анализ информационно-технических характеристик мультиплексоров, приведенных в таблице, показывает, что для передачи высокоскоростных ЦП данных используется разнотипное оконечное оборудование, которое, в общем случае, не является полнофункциональным и взаимозаменяемым без внесения изменений в состав самой системы передачи данных или в схему мультиплексирования [20, 29, 50, 65]. Кроме того, в настоящее время производителями мультиплексоров протестированы не все режимы функционирования, что определяется рядом объективных (стоимость оборудования, развитие технологической базы и т.п.) и субъективных причин (увеличение объемов и скоростей передаваемых данных, ужесточением эксплуатационных требований) [50, 65].

Таким образом, в дополнение к пяти существующим задачам систем передачи данных формируется дополнительная задача информационно вычислительного характера, связанная с необходимостью структурно параметрического анализа мультиплексированных структур данных в ЦП PDH и SDH иерархии. Данная задача анализа относится к уровню оконечного вычислительного оборудования вычислительных сетей и включает в себя: 1) структурно-параметрический анализ новых или модифицированных структур ЦП с целью определения их параметров, прежде всего положения поля полезной нагрузки; 2) текущий контроль способов группообразования и управления передачей данных, что позволит своевременно реагировать на различные $ их модификации и корректировать алгоритмы обработки, что, в свою

очередь, позволит уменьшить потери времени на выделение и предобработку принятых данных.

Грамматики с управляемым предшествованием. Их применение 48 для распознавания сигналов синхронной цифровой иерархии

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

Грамматики с управляемым предшествованием (ГУП) являются модификацией обычных грамматик (по классификации Хомского [68]) и учитывают дополнительные отношения между синтаксическими элементами сигналов SDH, а именно отношения, определяющие значения смещения поля полезной нагрузки относительно начала контейнера соответствующего уровня и порядок вычисления длин этих полей и значений указателя. Полученные модификации грамматик, в отличие от грамматик с управляемым предшествованием, позволяют управлять «выбором» значения отношения предшествования в тех случаях, когда связанные с его помощью элементы сигнала непосредственно не примыкают друг к другу.

Грамматика с (3-управляемым предшествованием представляется в виде четверки [6] G = VT, VN, S, Р , где (1) Vj - множество терминальных символов, VT = VTo u Vjn; VN - множество нетерминальных символов, VN = VN0 U VNn; S - начальный символ, S є VNo, V = VT u VN, VTnVN = 0; P - множество продукций, Р = Р0 U Рп и Рв и Рс и Рм В грамматиках с Р-управляемым предшествованием множества VTo, VNo и Ро соответствуют множествам терминалов, нетерминалов и продукций, используемых в обычных грамматиках для описания синтаксиса сигналов SDH.

Кроме того, во множества VT, VN и Р дополнительно включены специальные элементы, образующие следующие подмножества: VTn - подмножество выделенных терминальных символов, соответствующих возможным длинам полей и смещению начала поля полезной нагрузки относительно начала фрейма; VNn - подмножество выделенных нетерминальных символов, обозначающих синтаксически различные идентификаторы длин и смещения; Рп - множество продукций, задаваемых в виде сс$ (Х,и определяющих ч отношения управляемого предшествования: цепочка символов ctj предшествует цепочке символов Oj, Pij - расстояние между началами этих цепочек (число элементов входной цепочки от начала а; до начала а,, которые надо пропустить); Рв - множество продукций, задаваемых в виде а—юсіруссг и определяющих положение pij є VNn в цепочке aiPjjOt2 (а, осі, а2 є V4"); Рс - множество продукций вида Pi— Ру, где р} є VNn и Ру є VNn+, определяющих представление PJ В виде цепочки составляющих его отрезков; Рм - множество продукций вида a.ty.ea} и определяющих расстояние между началами цепочек а; и ctj, ру - количество терминальных символов 0, которые должны быть приписаны справа к порождаемой при грамматическом разборе входной последовательности цепочке терминалов.

Таким образом, грамматики с управляемым предшествованием могут рассматриваться как некоторая модификация специального подкласса атрибутных грамматик [73] и грамматик управляемого предшествования [5].

Применение грамматик с управляемым предшествованием создает широкие возможности для описания структур цифровых сигналов, между элементами которых существуют аналогичные отношения предшествования [6]. Построение таких описаний позволяет в процессе синтаксического анализа производить сегментацию входных цепочек цифровых сигналов и выделять в них заголовки контейнеров, поля служебной информации за счет чего устраняется неоднозначность структурно-лингвистических описаний сигналов SDH и повышается эффективность процедур синтаксического анализа при «разбиении» задачи анализа на ряд подзадач меньшей размерности.

Использование МГ с управляемым предшествованием при распознавании сигналов SDH определяет необходимость исследования их основных формальных свойств: мощности порождаемых семейств языков и их замкнутости относительно основных алгебраических операций. Определение мощности семейства формальных языков, порождаемого конкретным подклассом метаграмматик, необходимо при оценивании возможности описания конкретного класса сигналов SDH с использованием таких грамматик. Замкнутость относительно основных алгебраических операций позволяет в процессе ведения разведки производить дополнения и изменения формальных грамматических описаний при изменении структуры известных и появлении новых сигналов SDH.

Разработка метода полного синтаксического анализа транслирующих метаграмматик с управляемым предшествованием

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

Исследование особенностей синтаксической структуры ЦП SDH и синтезированных метаграмматических структурно-лингвистических описаний показало, что для реализации эффективных методов их синтаксического анализа на базе известных существуют следующие предпосылки.

1. Наличие у ЦП SDH свойств локальной регулярности и локальной идентифицируемости [7,41].

2. Возможность синтаксически управляемой сегментации входных цепочек сигналов SDH с использованием грамматик с управляемым предшествованием и алгоритмов неполного синтаксического анализа, предложенных в подразделе 3.1.

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

Рассмотрим модификацию известных методов синтаксического анализа «сверху-вниз» и «снизу-вверх», проведем теоретические и экспериментальные оценки их эффективности (временной и емкостной сложности) и определим предпочтительные области применения при распознавании подклассов сигналов SDH.

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

Суть модифицированного метода синтаксического анализа «сверху-вниз» заключается в выполнении рекурсивной процедуры нисходящего по TS правилам согласования грамматического разбора с последовательным предсказанием терминалов в грамматиках всех уровней, кроме самого нижнего (уровень М). Для выбора очередных шагов синтаксического анализа применяются ТР правила согласования [7]. Определяемая таким образом грамматика уровня М применяется для синтаксического анализа левой неразобранной части входной цепочки символов вплоть до позиций, определяемых с помощью отношений управляемого предшествования. Определяемые в ходе синтаксического анализа значения отдельных параметров соответствуют терминальным или нетерминальным символам отдельных грамматик, входящих в ЭФО распознаваемого класса. Эти символы подаются на выход синтаксического анализатора.

Суть модифицированного метода синтаксического анализа «снизу-вверх» заключается в проверке возможности разбора входной цепочки сигналов с использованием инверсных TS правил согласования. ТР правила согласования применяются также, как и в рассмотренном выше методе. В предлагаемом методе проверяется возможность распознавания левой неразобранной части входной цепочки с использованием одной из грамматик М-го уровня и возможность свертки таким же образом всей входной цепочки сигналов в начальный нетерминал Sn(1) одной из грамматик первого уровня. Выделение параметров производится аналогично приведенному выше.

Рассматриваемые методы синтаксического анализа ориентированы на применение регулярных МГ с TSP правилами согласования регулярных грамматик в стандартной праволинейной форме, входящих в состав различных уровней эталонного метаграмматического описания [41]. На TS и ТР правила согласования наложены ограничения, аналогичные определенным в [2, 7].

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

Анализ применимости элементной базы для реализации УАД в ВС

Из проведенного анализа [71] возможности применения ПЛИС для решения задачи аппаратной реализации процедуры адаптивного демультиплексирования ЦП следует, что наиболее целесообразно использование микросхем типа «система на кристалле», так как на одной микросхеме возможно создать сложную цифровую систему логической емкостью до 8 миллионов системных вентилей с высоким быстродействием и малым потреблением энергии. При этом время разработки значительно меньше, чем разработка аналогичной по функциональности заказной интегральной схемы. Микросхемы идеально подходят для использования в устройствах передачи данных и устройствах цифровой обработки сигналов. На микросхемах данного типа реализуются законченные решения в области телекоммуникаций, беспроводной связи, построения сетей, цифровой обработки сигналов с использованием интерфейсов PCI, LVDS и DDR.

В качестве программируемой системы на кристалле можно выделить СБИС ПЛ серии Virtex (Virtex, Virtex-E, Virtex-II Virtex-II Pro) фирмы Xilinx. Данная серия обладает высоким уровнем интеграции, позволяющим разместить на кристалле схему высокой сложности (систему), при этом разные по функционированию блоки реализуются одними и теми же аппаратными средствами благодаря их программируемое.

Данные СБИС имеют специализированные области - аппаратные ядра, выделенные на кристалле для определенных функций, например: - блоки ОЗУ, что позволяет изменять организацию памяти, возможность иметь асинхронный и синхронный режимы работы, организовать буферы FIFO и двухпортовую память, а также, организовывать ассоциативную память; - ядра интерфейса JTAG; - контроллеры шины PCI.

Кроме того, данное семейство СБИС имеет самое высокое быстродействие из всех известных.

В таблице 4.1 приведены основные параметры некоторых СБИС типа «система на кристалле» фирм Xilinx (Virtex) и Altera (APEX).

Таким образом, сравнение характеристик рассматриваемых ПЛИС «система на кристалле» по показателям: объем системных ресурсов, высокая производительность (системные частоты более 400 МГц), высокая гибкость архитектуры с множеством системных особенностей, возможность инициализации и верификации через JTAG, возможность программирования непосредственно в системе, короткий цикл проектирования, недорогие

средства проектирования и т. д. позволяет сделать вывод, что приоритетными для решения задачи демультиплексирования высокоскоростных ЦП следует считать микросхемы серии Virtex. Такой выбор позволит максимально полно удовлетворить требованиям быстродействия, параметрической и алгоритмической адаптации, предъявляемым к устройству, с учетом критерия «цена - качество».

Анализ структур и параметров ЦП в ВС, построенных на основе систем плезиохронной и синхронной цифровой иерархий Недостатком большинства известных устройств [57-61, 65] демультиплексирования ЦП или аналогичных по выполняемым функциям систем является невозможность одним устройством осуществлять демультиплексирование различных ЦП плезиохронной и синхронной цифровых иерархий, что ограничивает возможность их широкого применения в ВС.

Структурно-функциональная организация (СФО) устройства адаптивного демультиплексирования (УАД) должна удовлетворять условиям получения на своем выходе пользовательских информационных потоков из всего разнообразия ЦП PDH и SDH на входе.

Процедура демультиплексирования сигналов PDH из различных виртуальных контейнеров первого и нулевого уровней SDH (STM-Synchronous Transport Module-1 - Европейский стандарт и STS -Synchronous Transport Signal-3 - Американский стандарт), подробно описаны в рекомендации ITU G.707.

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

Похожие диссертации на Метод и устройство адаптивного демультиплексирования высокоскоростных групповых потоков для вычислительных сетей