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

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

Занун Набил Имхаммед Мохсен ¡Р* |

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

s I (JAP tin

Курск-2011

4841586

Работа выполнена в ГОУ ВПО «Юго-Западный государственный университет».

Научный руководитель

- доктор технических наук, профессор Атакищев Олег Игоревич

Официальные оппоненты: - доктор технических наук, профессор,

Дрейзин Валерий Элезарович - кандидат технических наук Елагин Владислав Васильевич

Ведущая организация

- ФГОУ ВПО «Государственный университет -учебно-научно-производственный комплекс» (г. Орел)

Защита состоится «15» апреля 2011 г. в 15 часов на заседании диссертационного совета Д 212.105.02 при Юго-Западном государственном университете по адресу: г. Курск, ул. 50 лет Октября, 94 (конференц-зал).

Заверенные отзывы на автореферат просьба направлять в двух экземплярах по адресу: 305040, г. Курск, ул. 50 лет Октября, 94, ученому секретарю диссертационного совета Д 212.105.02.

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

Автореферат разослан «14» марта 2011 г.

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

диссертационного совета

Титенко Е. А.

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

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

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

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

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

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

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

Работа выполнялась в рамках плановой научно-исследовательской работы «Методики и алгоритмы обработки и защиты информации в системах обработки конфиденциальных данных, подключенных к глобальной вычислительной сети Интернет» по направлению «Обработка, хранение, передача и защита информации» в рамках мероприятия 1.2.1 ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы.

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

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

Предмет исследования - средства декодирования неравномерных префиксных кодов при обработке графических и видеоданных.

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

1. Анализ тенденций развития подсистем декодирования данных в GRID- системах. Выявление недостатков существующих алгоритмов и устройств декодирования неравномерных префиксных кодов. Постановка общей и частных задач исследований.

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

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

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

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

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

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

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

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

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

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

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

-повышении быстродействия декодера для типовых видов неравномерных префиксных кодов в 2,1-2,4 раза;

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

Реализация и внедрение результатов исследования. Результаты диссертационной работы внедрены в Юго-Западном государственном университете, а также при создании перспективных распределенных вычислительных систем ООО «Центр- капитал» (г.Курск).

Апробация и публикация. Основные положения диссертационной работы были доложены и получили положительную оценку на 4 международных и всероссийских конференциях. По теме диссертационной работы опубликовано 11 научных работ (в том числе: 7 статей (из них 3 статьи в изданиях по перечню ВАК), 4 материала докладов на научных конференциях, подана заявка на изобретние.

Личный вклад автора. В работах, опубликованных в соавторстве, лично соискателем в работах [8,9] определены особенности развития GRID- систем, кодирования в них потоковых видео и графических данных с использованием основных классов неравномерных префиксных кодов, их структурные особенности, в работах [1-4,10] предложены элементы модели неравномерных префиксных кодов, в работах [6,7] аппаратно- ориентированный адресно- наращиваемый алгоритм декодирования неравномерных префиксных кодов и результаты экспериментальных исследований.

Структура и объем работы. Диссертация состоит из введения, четырех разделов, заключения, списка использованной литературы (98 наименований). Текст диссертации включает 134 страницы, из них 104 страницы основного текста, 14 рисунков, 5 таблиц.

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

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

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

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

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

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

ных системах данных, ориентированные на достаточно простые в алгоритмическом плане процедуры кодирования и декодирования неравномерных префиксных кодов.

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

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

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

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

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

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

Для моделирования структурных особенностей декодируемых неравномерных префиксных кодов рассматриваемого класса предложена метаграмма-тическая модель (МГМ) следующего вида.

G -<Gm iG<2>! Gm Gw G(5,(G(64 W >

В данной МГМ, грамматика G,(0) специфицирует синтаксические правила и структурные особенности чередования строк MH/MR с соответствующими кодовыми словами, грамматика G]<0) моделирует основные структурные особенности чередования кодовых слов в декомпозируемых строках кодов МН и MR.

Gi'0) учитывает возможность сегментации префиксных кодов в потоковых данных GRID -систем. В этом случае схема грамматики содержит продукции:

A0->lHA,[IRA6|IRTSAi4!I*„BiH|I*RB6R|I*RTSAi4;

А1-»106А2|1,6А3|1,6А4|1*обВ2об|1*,бВз.б|1*.бВ4,б;

А2-»1,бАз|1,6А4|1*,6Вз,б|1*.бВ4.б; Аз->1очА5|1вчА1|1>чА4|1*очВ5ОЧ|1*„В1,ч|1*.чВ4.,;

■ч

А6-»1пА6|1,А6|1гА7|1пА4|1.А4|1*пВ6„|1*.В6»|1*гВ7г|1*пВ4п|1*.В4,;

A7^I<^8|I.6A9|I0^lo[I.^пlI.6A4|I.чA4|I*o6B8o6lI^6B9,6lI*oчB1o0,|I^чB,1.ч|I^бв4JI^чв4.,; А8-»1,бА9| 1,6А4[1,',1,6В9В6|1*В6В4,6; А9->1(НА12|1вчАб| 1»чА4|1*очВ12оч|1вчВ6,ч|1*1,чВ4ВЧ; Аю~*1«ЧАЦ|1в,А4|1*ВчВ11>,|1*ВЧВ4ВЧ; А11-^1о6А1з|1в6А6|1в6А4|1*0бВ1з0б|1*вбВбвб|1*»бВ4Вб; А12^1ВЧА«|1,ЧА4|1*В,В6ВЧ|1*В,В4ВЧ; А1з-^1.бА6|1,бА4|1*ВбВ6,6|1*,6В4в6;В1н->1*«нА1; Вба->1**кАб; В2об-»1**обА2; В3в6->1**в5А3; В4вб->1**11бА4; В5оч->1**очА5; В,в6->1**вчА,; В4вч->1**ВчА4; Во6-»1**РА0; В6п->1**„А5; В6в->1**вА6; В7г->1**гА7; В4п-^1**„А4; Вд.-^.А,; Вм-^Р*^; В9„6->1**в6А9; В10ОЧ-»1**О,А10;

Вог->1**рАо-

В грамматике О/0) обобщенные терминалы со звездочкой (типа 1*н) означают начальную часть (префикс) соответствующего кодового слова, "разрываемого" при декомпозиции полей кадров (пакетов), обобщенные терминалы с двумя звездочками (типа I „>,)- заключительную часть этого кодового слова, присоединяемую в начало поля следующей команды сеансового уровня. Правила, содержащие дополнительные нетерминалы, обозначаемые заглавными буквами В с соответствующими индексами, обеспечивают возможность учета сегментации кодовых слов. Грамматики {011<,)}, {С,2(2)}

определяют декомпозицию обобщенных терминалов грамматики в/0* и их представление в виде конкретных кодовых слов с однозначной идентификацией для строк МН и МЯ цвета и кодируемых длин серий.

Грамматика в/3' используется в вспомогательных целях для отслеживания порядка изменения цвета в строке МЯ (это необходимо для правильного определения "цвета" первого кодового слова для горизонтального режима кодирования). Грамматика 0|(3) "отслеживает" длины кодированных строк МН/МЯ и может использоваться для определения используемого стандарта на время передачи строки изображения.

Грамматики в/4' и С| определяют преобразование кодовых слов в цепочки длин серий белого/черного в строке изображения и преобразование этих длин серий к формату меток начала серий (МНС), используемому при представлении декодированной информации в используемых средствах декодирования неравномерных префиксных кодов.

Грамматики {С,6(6)} определяют преобразование кодовых слов строки МЛ в соответствии с составом цепочки МНС, полученной предшествующей кодовой строки, в коды МНС текущей строки МЛ.

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

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

Входящие в схему метаграмматики TS(I) правила согласования задают декомпозицию терминалов определенных грамматик на цепочки, порождаемые связанными с ними грамматиками. Эти правила представляются в следующем виде:

(DATAH)-»A10(,); (DATAr)->A2oU); (EOLh)->A10(,); (EOLR)-»A20®;

(RTS)-»A3O(2); IF-> A(0<2); Ioe-> Aso«2»; I04-> A60(2); Ibe-»A70(2);

1вч-* A80(2); Ib-> A9o<2); In-» A,oo(2); Ip-» Ano'2'.

В целом, за счет комбинированного использования TS(I), TS(3) и ТР(4) в предложенной модели в отличие от известных возможна спецификация следующих синтаксических правил, задающих кодовую структуру схемы MH/MR:

- правила чередования строк МН и MR в различных стандартах (к=2,4 и

т.п.);

- правила чередования кодовых слов при кодировании различных строк изображения;

- стандарты на допустимые минимальные длины кодированных строк;

- стандарты на длины строк изображений и чередования длин серий.

Проведенный анализ показал, что при использовании для этих целей

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

При необходимости спецификации перспективных неравномерных префиксных схем кодирования в предложенной модели достаточно изменять лишь отдельные грамматики и соответствующие правила согласования. В частности, грамматика, специфицирующая полную синтаксическую структуру кода M2R (Рек. ITU-T Т.6 ) получается из предложенной путем модификации грамматики и удаления грамматики Gi(l) с соответствующими правилами согласования. При изменении структуры кодовых слов и их соответствия длинам серий подлежат изменениям только грамматики {G¡(2)} и соответствующие правила согласования с грамматиками Gf(3) и G|(4).

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

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

Это создает необходимый теоретический задел для разработки эффективного алгоритма и создания устройств декодирования.

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

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

1. Адресно- управляемое заполнение эталонных ячеек памяти транслируемыми кодами длин серий (ТКДС) декодированной последовательности (транслируемых длин серий и т.п.) в соответствии с правилами предложенной выше метаграмматической модели.

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

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

4. Добавление к префиксу следующего элемента цепочки и возврат на шаг 3. Если добавление невозможно- выдача сигнала конца декодирования.

5. Смена состояния в дереве разбора метаграмматической модели в соответствии с полученным кодовым словом.

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

7. Пересчет ТКДС в соответствии с текущим состоянием в дереве разбора метаграмматики и полученными ранее ТКДС.

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

9. Сдвиг метки привязки начала декодирования на число элементов оттранслированного префикса, возврат на шаг 3.

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

памяти поиске соответствия двоичной структуры префиксного кодового слова его транслируемому (декодированному) значению.

Проведенные оценки числа выполняемых в предложенном алгоритме стандартных операций для различных классов неравномерных префиксных кодов показали, что подобная процедура поиска обеспечивает снижение в 3,54 раза числа операций при выделении префиксов декодируемого потока данных. В то же время происходит возрастание числа эталонных ячеек памяти, необходимых для хранения ТКДС префиксных кодов, в 1,8 раза.

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

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

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

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

является учет неравномерности длин префиксных кодовых слов, объем необ-

»

ходимой памяти для заполнения не превышает значение V=^2"*, где Кг чис-

<•1

ло кодовых таблиц в схеме неравномерного префиксного кода, nt- максимальная длина префиксного кода в k-й таблице. Реализация подобной СФО позволяет реализовать все основные этапы предложенного алгоритма. Другой отличительной особенностью данной СФО является реализация процедур выдачи декодированной информации с промежуточным представлением в виде ТКДС, соответствующий для большинства префиксных кодов кодам длин серий изображений," квантованных коэффициентов дискретного косинусного преобразования для схШ Trnia JPEG и MPEG. - .-.>-.

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

Структурная схема модуля поиска соответствия префикса на базе ПЛИС, реализующего основной этап декодирования, приведена на рис.2.

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

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

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

Экспериментальная проверка работоспособности устройства проводилась при макетировании устройства с использованием встроенных модулей тестирования ПЛИС. Усредненные оценки выигрыша по числу типовых операций и проигрыша по числу ячеек памяти при декодировании стандартных изображений №1-5 (Рекомендация ITU-T Т.З, Т.4, Т.6) с с кодовыми схемами MH/MR и MMR по сравнению со одним из стандартных алгоритмов - алгоритмом последовательного поиска в таблицах по возрастанию длин префиксов представлены в таблице 1. Для данных стандартных изображений число обработанных префиксных кодовых слов составило 1,2*105. При этом доверительный интервал полученных оценок не превышает 0,7*10"4.

Таблица 1

средний максимальный

Выигрыш по числу операций MH/MR 3,97 8,05

MMR 3,53 6,45

Возрастание числа эталонных ячеек MH\MR 1,95 1,95

MMR 1,68 1,68

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

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

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

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

Входная последовательность (инф. и такт, сигналы)

2.

5 1

о 2

s I

Я ft

i-s

к «с

II

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

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

Модуль общего управления процедурами декодирования на основе ММГ

|

В j s

в $ £

U-

о л § Ш « •■. S

I-S-1 S '

в X

|3S 1

S 6 8

Модул» загрузки атрнбу-" тов в модули памяти

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

Модуль обработки ошибок декодирования строк и составных конструкций

ЯШ в«

S3 §

I'-S

5=

ii *Ц щ

л ю

3

25**

1ё

а: Я

1»

if

Модуль см кгавания "ПСДСНЛК (промежуточных декодироваяныхзна-чений атрибутов ММГ)

Модуль преобразования ТКДС НПК (итоговых декодированных значений в виде меток серий)

образованием меток серий и выходной буферизацией на основе ММГ

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

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

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

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

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

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

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

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

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

4. Разработана структурно-функциональная организация устройства декодирования неравномерных префиксных кодов при обработке данных в GRID системах, отличающаяся введением дополнительных модулей (общего управления процедурами декодирования на основе метаграмматической модели, управления формированием префикса кода, поиска соответствия префикса, памяти для таблиц неравномерных префиксных кодов, считывания транслированных кодов длин серий, их преобразования, управления преобразованием меток серий и выходной буферизацией на основе метаграмматической модели) с соответствующими связями и характеризуемая высокоскоростной адресно- наращиваемой организацией поиска текущего префикса в декодируемом потоке данных, обеспечивающая увеличение в 2,1-2,4 быстродействие при декодировании известных видов префиксных кодов.

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

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

1. Занун, Н.И. Особенности применения метаграмматик для моделирования процессов обработки префиксных кодов в GRID системах [Текст]/ Н.И.Занун,О.И.Атакищев// Изв. Курск, гос. техн. ун-та. 2010. №4(33). С.49-52.

2. Занун, Н.И. Структурно-лингвистическая модель неравномерных префиксных кодов, используемых для передачи документальной информации [текст]/ Н.И.Занун, О.И.Атакищев [и др.]// Т*С О М М Телекоммуникации и транспорт. 2010. №11. С.15-17.

3. Занун, Н.И. Особенности применения метаграмматик для формального описания протоколов передачи потоковых данных в GRID систем [Текст]/ Н.И.Занун, О.И.Атакищев и др.// Т-С О М М Телекоммуникации и транспорт. 2010. №11. С.13-14.

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

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

5. Занун, Н.И. Основные особенности создания устройств декодирования неравномерных префиксных кодов при обработке высокоскоростных потоковых данных [Текст]/ Н.И.Занун // Информационно-вычислительные технологии и их приложения: сб. ст. XIII Междунар. науч.-технич. конф., (Пенза, 2010 г.) Пенза: Академия информатизации образования РФ, Межотраслевой науч.-информ. центр ПГСХА, 2010. С.49-54.

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

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

8. Занун, Н.И. Особенности подхода к динамической реконфигурации логической топологии GRID системы, построенной по сценарию мультикла-стер [Текст]/ Н.И. Занун, О.И. Атакищев // Образование, инновации, качество: материалы IV Междунар. науч.- метод, конф. Курск: 2010. С.240-242.

9. Занун, Н.И. Обобщенный анализ GRID систем, используемых для решения научно-образовательных задач [Текст]/ О.И. Атакищев, Н.И. Занун [и др.]// Образование, инновации, качество: материалы IV Междунар. науч,-метод. конф. Курск: 2010. С.255-258.

10. Занун, Н.И. Структурно-лингвистические модели потоковых данных в GRID системах [Текст]/ Н.И. Занун, О.И. Атакищев // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание-2010): материалы IX Междунар. конф. Курск, 2010. Курск: 2010. С. 167-168.

11. Занун, Н.И. Особенности адаптивной распределенной обработки разнородных десегментированных потоковых данных в GRID системах [Текст]/ Н.И. Занун.// Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание-2010): материалы IX Междунар. конф. Курск, 2010. Курск: 2010. С. 170-172.

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

12. Заявка N 2010112170/08. Устройство для параллельного поиска вхождений и пересечений слов Н.И. Занун [ и др. ] (РФ) М.: РосПатент; заявлено 29.03.2010., приоритет 29.03.2010.

Соискатель ) • о Занун Н.И.

Подписано в печать 14.03.2011 Формат 60x84 1/16. Бумага офсетная. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 120 экз. Заказ Юго-Западный государственный университет. 305040, г. Курск, ул. 50 лет Октября, 94. Отпечатано в ЮЗГУ

Введение.

1. Анализ тенденций создания подсистем декодирования неравномерных префиксных кодов в GRID- системах. Постановка общей и частных задач исследований.

1.1. Общие особенности развития GRID- систем на современном этапе.

1.2. Неравномерные префиксные коды как основа сжатия данных обрабатываемых в современных GRID- системах.

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

Выводы.

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

2.1. Основные классы метаграмматик, оценка возможности их использования для моделирования неравномерных префиксных кодов.

2.2. Метаграмматическая модель неравномерных префиксных кодов.

Выводы.

3. Разработка адресно- наращиваемого алгоритма декодирования неравномерных префиксных кодов.

3.1.Вводные замечания.

3.2. Адресно- наращиваемый алгоритм декодирования неравномерных префиксных кодов.

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

Выводы.

4. Особенности создания устройства декодирования неравномерных' префиксных кодов при обработке данных в GRID системах.

4.1. Основные особенности создания устройства декодирования неравномерных префиксных кодов при обработке кодированных данных в GRID системах.

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

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

Выводы.

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

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

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

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

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

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

Работа выполнялась в рамках плановой научно-исследовательской работы «Методики и алгоритмы обработки и защиты информации в системах обработки конфиденциальных данных, подключенных к глобальной вычислительной сети Интернет» по направлению «Обработка, хранение, передача и защита информации» в рамках мероприятия 1.2.1 ФЦП «Научные и научно- педагогические кадры инновационной России» на 20092013 годы.

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

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

Предмет исследования. - средства декодирования неравномерных префиксных кодов при обработке графических и видеоданных.

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

1. Анализ тенденций развития подсистем декодирования данных в GRID- системах. Выявление недостатков существующих алгоритмов и устройств декодирования неравномерных префиксных кодов. Постановка общей и частных задач исследований.

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

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

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

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

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

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

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

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

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

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

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

-повышении быстродействия декодера для типовых видов неравномерных префиксных кодов в 2,1-2,4 раза;

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

Реализация и внедрение результатов исследования Результаты диссертационной работы внедрены в Юго-Западном государственном университете, а также при создании перспективных распределенных вычислительных систем ООО «Центр- капитал» (г.Курск).

Апробация и публикация. Основные положения диссертационной работы были доложены и получили положительную оценку на 4 международных и всероссийских конференциях. По теме диссертационной работы опубликовано 11 научных работ (в том числе: 7 статей (из них 3 статьи в изданиях по перечню ВАК), 4 материала докладов на научных конференциях, подана заявка на изобретние.

Личный вклад автора. В работах, опубликованных в соавторстве, лично соискателем в работах [8,9] определены особенности развития GRID-систем, кодирования в них потоковых видео и графических данных с использованием основных классов неравномерных префиксных кодов, их структурные особенности, в работах [1-4,10] предложены элементы модели неравномерных префиксных кодов, в работах [6,7] аппаратно-ориентированный адресно- наращиваемый алгоритм декодирования неравномерных префиксных кодов и результаты экспериментальных исследований.

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

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

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

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

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

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

В заключении представлены основные результаты проведенных исследований.

Выводы

1. Разработана структурно-функциональная организация устройства декодирования неравномерных префиксных кодов при обработке данных в GRID системах, отличающаяся введением дополнительных модулей (общего управления процедурами декодирования на основе метаграмматической модели, управления формированием префикса кода, поиска соответствия префикса, памяти для таблиц неравномерных префиксных кодов, считывания транслированных кодов длин серий, их преобразования, управления преобразованием меток серий и выходной буферизацией на основе метаграмматической модели) с соответствующими связями и характеризуемая высокоскоростной адресно-наращиваемой организацией поиска текущего префикса в декодируемом потоке данных, обеспечивающая увеличение в 2,1-2,4 быстродействие при декодировании известных видов префиксных кодов.

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

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

ЗАКЛЮЧЕНИЕ

При выполнении диссертационных исследований получены следующие основные результаты.

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

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

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

4. Разработана структурно-функциональная организация устройства декодирования неравномерных префиксных кодов при обработке данных в GRID системах, отличающаяся введением дополнительных модулей (общего управления процедурами декодирования на основе метаграмматической модели, управления формированием префикса кода, поиска соответствия префикса, памяти для таблиц неравномерных префиксных кодов, считывания транслированных кодов длин серий, их преобразования, управления преобразованием меток серий и выходной буферизацией на основе метаграмматической модели) с соответствующими связями и характеризуемая высокоскоростной адресно- наращиваемой организацией поиска текущего префикса в декодируемом потоке данных, обеспечивающая увеличение в 2,1-2,4 быстродействие при декодировании известных видов префиксных кодов.

1. Кирьянов, А.К Введение в технологию Грид. Текст./ А.К Кирьянов, Ю.Ф. Рябов Изд-во СПБ института ядерной физики им. Б.П. Константинова РАН, Спб, 2006.

2. Айзерман, М.Д. Динамический подход к анализу структур, описываемых графами основы графодинамики. 4.1, 2 / М.Д. Айзерман, Л.А. Гусев, И.М. Смирнова, С.В. Петров // Автоматика и телемеханика. 1977. №7, 9.

3. Кирмайер М.Мультимедиа; Пер.с нем.-СПб., 1994.

4. Рекомендация ITU-T Т.4 «Стандартизация факсимильной аппаратуры (ФА) группы 3 (G3) для передачи документов». Standardization of group 3 facsimile apparatus for document transmission, октябрь 1997.

5. Рекомендация ITU-T T.6 «Схемы факсимильного кодирования и функции управления кодированием для ФА G4». Facsimile coding schemes and coding control functions for group 4 facsimile apparatus, ноябрь 1988.

6. Васильева В. Новости графики: JPEG2000//Mnp ПК, январь 2001.

7. Рекомендация ITU-T T.42 «Метод представления тонового цвета для факсимиле». Continuous-tone color representation method for facsimile, февраль 1996.

8. Барцев, С.И. Адаптивные сети обработки информации Текст.: препринт N 59Б/ С.И. Барцев, В.А. Охонин . Красноярск : Ин-т физики СО АН СССР, 1986. 20с.

9. Безкоровайный, М.М. Инструментально- моделирующий комплекс оценки качества функционирования информационных систем «КОК» Текст. / М.М. Безкоровайный, А.И. Костогрызов, В.М.Львов. М.: «Вооружение. Политика. Конверсия», 2001.304 с.

10. Льюис, П. Атрибутные трансляции Текст. / П. Льюис, Д. Розенкранц, Р. Стирнз // Семантика языков программирования. М.: Мир, 1980. 278с.

11. Искусственный интеллект Текст.: в 3-х кн.: справочник/под ред. Д.А. Поспелова. М.: Радио и связь, 1990.

12. Люггер, Дж . Искусственный интеллект: стратегии и методы решения сложных проблем Текст.: пер. с англ. /Дж.Ф. Люгер. М.: Изд. Дом «Вильяме», 2005. 864 с.

13. Сизов, А.С.Концепция информационного подхода к оценке эффективности функционирования сложных систем Текст. / A.C. Сизов // Распознание-2005: сб. материалов VII Междунар. конф. Курск, 2005 С. 1011.

14. Гинзбург, С. Математическая теория контекстно-свободных языков Текст. / С. Гинзбург // М.:Мир, 1970.

15. Методы анализа данных Текст.: пер. с фр. / под ред. С.А. Айвазяна, В.М. Бухштабера. М.: Финансы и статистика, 1985. 360 с.

16. Городецкий, В.И. Многоуровневые атрибутные грамматики для моделирования сложных структурно-динамических систем Текст. / В.И. Городецкий, В.В. Дрожжин, P.M. Юсупов // Изв. АН СССР. Техническая кибернетика. 1986. №1. С. 165.

17. Николаев, A.B. Продукционная машина генератор для параллельных стратегий выводов Текст. / А.В.Николаев, С.Г.Емельянов, Е.А.Титенко [и др.]// Искусственный интеллект в XXI веке: сб. статей Всеросс. науч.- техн. конф. / Пенза, 2003. С. 107-110.

18. Емельянов, С.Г. Формальные грамматики и грамматические сети. Вопросы практического применения при решении задач распознавания и обработки сложноструктурированных данных и знаний Текст. / С.Г.Емельянов, A.B. Николаев. М.: Высш. шк., 2005.251 с.

19. Кириллов, А.Н. Об оценке адекватности моделей объектов в задачах управления / А.Н. Кириллов, P.M. Юсупов // Науч.-техн. сб. (тр.). Вып.592. 1979. С. 18-21.

20. Фомин, Я.А. Оптимизация распознающих систем / Я.А. Фомин, A.B. Савич. М.: Машиностроение, 1993.

21. Атакищев, О.И. Особенности применения метаграмматик для формального описания структуры сложных технических систем / О.И. Атакищев, О.Г. Добросердов // Методы и средства систем обработки информации: сб. науч. с. Курск, 1997. С.5-14.

22. Городецкий, В. И. Прикладная алгебра и дискретная математика. Ч. П.

23. Формальные системы нелогического типа Текст. / В. И. Городецкий. М.: МО СССР, 1986. 200 с.

24. Атакищев О.И. Метаграмматики и особенности их применения для формального описания сигналов и протоколов документальных служб связи и передачи данных. Часть 2. Классификация метаграмматик //Телекоммуникации. 2001. № 12, 2 6с.

25. Атакищев О.И., Медведев Г. Н., Варганов А. В. Особенности кодирования цифровых факсимильных сообщений. Часть 2. Схемы кодирования цветных и полутоновых изображений JPEG и JPEG2000 //Телекоммуникации. 2001. № 12, 21 -28с.

26. Атакищев О.И., Варганов А. В., Старков Ф. А. и др. Технологии сетей связи. Особенности кодирования цифровых факсимильных сообщений //Учебное пособие, КГТУ. г. Курск, - 2002. - 159с.

27. Атакищев О.И. Метаграмматики и особенности их применения для формального описания сигналов и протоколов документальных служб связи и передачи данных. Часть 2. Классификация метаграмматик // Телекоммуникации. 2001. № 12, 2 8с.

28. Городецкий, В.И. Распознающие системы Текст. / В.И. Васильев. Киев: Наукова думка, 1983.424 с.

29. Загоруйко, Н.Г. Прикладные методы анализа данных и знаний Текст. / Н.Г. Загоруйко. Новосибирск: Изд-во Института математики, 1999. 270 с.

30. Занун, Н.И. Особенности применения метаграмматик для моделирования процессов обработки префиксных кодов в GRID системах Текст./ Н.И.Занун,О.И.Атакищев// Изв. Курск, гос. техн. ун-та. 2010. №4(33). С.49-52.

31. Занун, Н.И. Структурно-лингвистическая модель неравномерных префиксных кодов, используемых для передачи документальной информации текст./ Н.И.Занун, О.И.Атакищев [и др.]// Т*С О M M Телекоммуникации и транспорт. 2010. №11. С. 15-17.

32. Занун, Н.И. Особенности применения метаграмматик для формального описания протоколов передачи потоковых данных в GRID систем Текст./ Н.И.Занун, О.И.Атакищев и др.// Т*С О M M Телекоммуникации итранспорт. 2010. №11. С.13-14.

33. Занун, Н.И. Обобщенный анализ GRID систем, используемых для решения научно-образовательных задач Текст./ О.И. Атакищев, Н.И. Занун [и др.]// Образование, инновации, качество: материалы IV Междунар. науч.- метод, конф. Курск: 2010. С.255-258.

34. Занун, Н.И. Структурно-лингвистические модели потоковых данных в

35. Сизов, А.С. Распознание объектов по структурным признакам в условиях нечеткости их описаний Текст. / А.С. Сизов, Д.А. Стребков // Распознание-2005: сб. материалов VII Междунар. конф. Курск, 2005 С. 1011.

36. Кнут, Д.Э. Семантика контекстно-свободных языков Текст. / Д.Э. Кнут// Семантика языков программирования. М.: Мир, 1980. С. 137-161.

37. Фу, К. Структурные методы в распознавании образов Текст. / К. Фу. М.: Наука, 1977. 273 с.

38. Хьюз, Д. Структурный подход к программированию Текст. / Д. Хьюз, Д. Мичток. М.: Мир, 1980. 278 с.

39. Климов А. С. Форматы графических файлов. К.: НИПФ «ДиаСофт Лтд.», 1995.-480с.

40. Левин Б.Р. Теоретические основы статистической радиотехники. -М.: Сов. Радио, 1974-1976, кн. 1-3.

41. Мельников Д.А. Информационные процессы в компьютерных сетях. М.: КУДИЦ-ОБРАЗ, 1999. - 256с.

42. Патрик Э. Основы теории распознавания образов. М.: Сов. радио, 1980.

43. Куцык, Б.С. Структура данных и управление Текст. / Б.С. Куцык. М.: Наука, 1975. 654 с.

44. Льюис, П. Теоретические основы проектирования компиляторов / П. Льюис, Д. Розенкранц, Р. Стирнз // М.: Мир, 1979. 654 с.

45. Севастьянов Б.А. Теория ветвящихся процессов Текст. / Б.А. Севастьянов // Успехи математических наук. 1970. 7.

46. Ахо А. Теория синтаксического анализа, перевода и компиляции Текст. / А. Ахо, Дж. Ульман // М: Мир, 1978. Кн.1, 2.

47. Фатхутдинов, Р.А. Управленческие решения Текст. / Р.А. Фатхутдинов. М.: ИНФРА-М, 2005. 344 с.

48. Формальные грамматики и их применение в распознавании образов Текст. / О.И. Атакищев, А.П. Волков, Ф.А Старков, B.C. Титов ; Курск, гос. техн. ун-т. Курск, 2000. 115 с.

49. Элементы теории испытаний и контроля технических систем/ под. ред. P.M. Юсупова. Л.: Энергия, 1978. 192 с.

50. I. Foster, С. Kesselman. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers, 1998.

51. I. Foster, C. Kesselman, S. Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International J. Supercomputer Applications, 15(3), 2001, http://www.globus.org/research/papers/anatomy.pdf

52. I. Foster, C. Kesselman, S. Tuecke, J. M. Nick. The Physiology of the Grid: An Open Grid Services Architecture for Distributed Systems Integration. -Morgan Kaufmann Publishers, 2002.

53. I. Foster, H. Kishimoto, A. Savva, D. Berry et al. The Open Grid Services Architecture. Global Grid Forum, 2005, http://www.ggf.org/documents/GFD.30.pdf

54. I. Foster, D. Gannon, H. Kishimoto et al. Open Grid Services Architecture Use Cases. Global Grid Forum, 2004, http ://www. ggf.org/documents/GFD.29 .pdf

55. J. Treadwell, M. Behrens, D. Berry et al. Open Grid Services Architecture Glossary of Terms. Global Grid Forum, 2005, http://www.ggf.org/documents/GFD.44.pdf

56. I Foster, C. Kesselman. Globus: A Metacomputing Infrastructure Toolkit. ftp://ftp.globus.org/pub/globus/papers/globus.pdf

57. I. Foster, C. Kesselman. The Globus Project: A Status Report. ftp://ftp.globus.org/pub/globus/papers/globus hcw98.pdf

58. Overview of the Grid Security Infrastructure, http://www.globus.org/security/overview.html

59. RSL Specification, http://www fp.globus.org/gram/rslspecl .html

60. Kuno, S. A context recognition procedure Text. / S. Kuno // Math. Linguistics and Automatic Translation Rep. NSF-18 / Computation Lab., Harvard Univ., Cambridge. Massachusetts, 1967.

61. Lee, H.C. A syntactic pattern recognition with learning capability Text. / H.C. Lee, K.S. Fu // Int. Symp. Comput. Inform. Sei. 4th. December 14-16. Miami Beach, Florida, 1972. New York: Academic Press, 1972.

62. Pavlidis, T. Analysis of set pattern Text. / T. Pavlidis // Pattern Recognition 1968. №1.

63. Foster, J.M Automatic Syntactic Analysis Text. / J.M. Foster // Amer. Elsevier .New York, 1970; Автоматический синтаксический анализ / Фостер, Дж. М.: Мир, 1975.)

64. Woods W.A. Context-sensitive parsing Text. / W.A. Woods // Comm. ACM. 1970. 13. P. 437-445.

65. Duda, R.O. Experiments in scene analysis Text. / R.O. Duda, P.E. Hart // Proc. Nat. Symp. Ind. Robots, 1st (2-3 april 1970. Chicago, Illinois.

66. Greibach, S. Formal parsing systems Text. / S. Greibach //Comm. ACM. 1964. 7. P. 499.

67. Harangozo, J. Formal representation of the protocol hierarchy Text. / J. Harangozo // Eurocomp. 78 Proc. Eur. Comput. Congr. London; Uxbridge, 1978. P.403-414.

68. Goldberg, D. Genetic Algorithms in Machine Learning, Optimization and Search Text. /D. Goldberg. Addison-Wesley, 1988.

69. Aho, A.V. Indexed grammars — An extension of context-free grammars Text. / A.V. Aho// Assoc. Comput. Mach. 1968. №15. P. 647-671; Индексные грамматики — расширение контекстно-свободных грамматик / A.B. Ахо // Языки и автоматы. М.: Мир, 1975. С.

70. Jones, A.J. Nets of formal grammars. Applications Text. / A.J. Jones // Linguistics and Automatic Translation Rep. NSF-46 / Computation Lab., Harvard Univ., Cambridge. Massachusetts, 2000.

71. Van-Dake, R.E. Neural networks for syntactic analysis and syntactic pattern recognition Text. / R.E. Van-Dake // Comput. Graphics and Image Process. 1993. № 9. P. 99-173.

72. Learner, A. Note on transformating context-free grammars to Wirth Text. / A. Learner, A.L. Lim // Weber precedence form. Comput. 1970. №13. P. 142— 144.

73. Fu, K.S. On stochastic automata and languages Text. /K.S. Fu, T. Li // Information Sei. 1969. № 1. P. 403-419.

74. Fu, K.S. On syntactic pattern recognition Text. / K.S. Fu, P.H. Swain // Int. Symp. Comput. and Inform. Sei. Bai Harbour. Florida, 1969.

75. Fu, K.S. On syntactic pattern recognition and stochastic languages Text. / K.S. Fu, S. Watanabe [edet al.] // Frontiers of Pattern Recognition / Academic Press. New York, 1972.

76. Harangozo, J. Protocol definition with formal grammars Text. / J. Harangozo // Comput. Network Protocol Proc. Symp. Liege, 1978. (Liege S.A. F 6/1-F 6/10).

77. Pavlidis, T. Representation of figures by labeled graphs Text. / T. Pavlidis // Pattern Recognition. 1972. №4. P. 5-16.

78. Grenander, J. Syntax-Controlled Probabilities Text. / J. Grenander // Tech. Rep. Div. of Appl. Math. / Brown Univ. Providence, Rhode Island, 1967.

79. Floyd R.W. The syntax of programming languages A survey Text. / R.W. Floyd // IEEE Trans. Electron. Comput., EC-13. 1964. P. 346-353.

80. Feldman, J. Translator writing systems Text. / J. Feldman, D. Cries // Comm. ACM. 1968. №11, P. 77-113

81. Overview of the Grid Security Infrastructure, http://www.globus.org/security/overview.html

82. EGEE (Enabling Grids for E-sciencE) http://www.eu-egee.org/