Содержание к диссертации
Введение
1. Математические модели и методы дискретного анализа в технической диагностике и их новые направления 19
1.1. Основные модели и методы технической диагностики 19
1.2. Модели дискретного анализа в технической диагностике 28
1.2.1. Предварительные замечания об исследованиях в данной области 28
1.2.2. Определение булевых функций в конечных полях. 31
1.2.3. Базисы разложения булевых функций 34
1.2.4. Булевы производные: основные определения 38
1.2.5. Булевы производные: свойства 45
1.2.6. Аспекты применения рассматриваемых методов и моделей... 48
1.3. Задачи технической диагностики информационных систем 62
1.3.1. Задачи диагностики телекоммуникационных систем 64
1.3.2. Задачи диагностики программного обеспечения 70
1.3.3. Задачи математического моделирования диагностируемых систем
1.4. Задача онлайновой диагностики и синтеза контролируемых информационных систем 78
1.5. Выводы 82
2. Модели, методы и алгоритмы дискретного анализа логических функций 84
2.1. Развитие методов дифференциального исчисления булевых функций 84
2.1.1. Модели декомпозиции с двойственными операциями 84
2.1.2. Производная полностью определенных булевых функций 92
2.1.3. Производная частично определенных булевых функций 93
2.2. Логические дифференциальные операторы над конечными полями 97
2.2.1. Свойства логических дифференциальных операторов 97
2.2.2. Разложение логических функций над конечными полями 103
2.2.3. Общая модель дифференциальной дискретной системы 106
2.3. Модели спектрального представления логических функций над конечными полями 109
2.4. Алгоритмы спектральных преобразований булевых функций 118
2.5. Алгоритмы вычислений и символьных преобразований в булевом дифференциальном и интегральном исчислении 128
2.6. Выводы 138
3. Математические модели контролируемых динамических систем над конечными полями 140
3.1. Основные определения, обозначения и факты 143
3.1.1. Многочлены над конечными полями 149
3.1.2. Алгоритм вычисления поля разложения 157
3.2. Модели линейных стационарных динамических систем 158
3.2.1. Авторегрессионная модель 159
3.2.2. Модель типа вход-выход 160
3.2.3. Модели типа вход-состояние-выход 161
3.2.4. Связь между авторегрессионной моделью и моделью вход-выход 162
3.2.5. Связь между авторегрессионной моделью и моделью вход-состояние-выход 164
3.3. Постановка и решение задачи синтеза контролируемой системы и контрольных уравнений 164
3.3.1. Пример синтеза контролируемой системы 170
3.3.2. Синтез контрольного уравнения при возможности запаздывания 171
3.3.3. Пример синтеза контрольного уравнения 174
3.4. Нелинейные динамические системы над конечными полями 176
3.4.1. Пример нелинейной динамической системы над полем F2 177
3.4.2. Общий метод синтеза нелинейных контролируемых систем... 180
3.5. Выводы 185
4. Модели диагностики программного обеспечения в процессе функционирования информационных систем 186
4.1. Особенности диагностики программного обеспечения в процессе функционирования и задачи своевременного обнаружения ошибок 186
4.2. Обобщенная предикатная модель диагностики программного обеспечения 195
4.3. Дифференциальный метод диагностики программного обеспечения
4.3.1. Критерии анализа изменений спецификаций программ 206
4.3.2. Диагностика на основе предикатной производной
4.4. Метод своевременной диагностики программного обеспечения 221
4.5. Выводы 224
5. Практическая реализация методов моделирования, диагностики и синтеза информационных систем 225
5.1. Сравнительный анализ систем компьютерной алгебры: возможности логических преобразований в конечных полях 225
5.2. Программный комплекс моделирования и анализа задач технической диагностики информационных систем 231
5.2.1. Основные функциональные возможности комплекса 231
5.2.2. Модули реализации алгоритмов численных вычислений 235
5.3. Программный комплекс для синтеза отказоустойчивых контролируемых динамических дискретных систем 238
5.3.1. Модуль реализации алгоритмов синтеза контролируемых линейных систем 238
5.3.2. Модуль реализации алгоритмов синтеза нелинейных линеаризуемых систем 239
5.3.3. Модуль реализации алгоритмов онлайновой диагностики программного обеспечения 241
5.4. Аспекты реализации методов и моделей в существующих информационных системах 243
5.4.1. Диагностические комплексы информационно-управляющих систем железнодороэ/сного транспорта 243
5.4.2. Подсистемы управления качеством обслуживания в системах предоставления информационных услуг 248
5.5. Выводы 252
Заключение 254
Список литературы
- Предварительные замечания об исследованиях в данной области
- Логические дифференциальные операторы над конечными полями
- Постановка и решение задачи синтеза контролируемой системы и контрольных уравнений
- Аспекты реализации методов и моделей в существующих информационных системах
Введение к работе
Актуальность работы. Одной из существенных характеристик любой информационной системы (ИС) является уязвимость её к ошибкам и сбоям, что во многих случаях приводит к нештатным режимам и отказам функционирования. Из-за растущих потребностей современной промышленности, транспорта и других областей применения ИС неизбежным является усложнение их подсистем и устройств. Переход на новую элементную базу, программное обеспечение (ПО) ИС, функционирование в реальном времени приводит к изменению постановки задач математического моделирования в области технической диагностики ИС. Этим обуславливается необходимость разработки новых математических методов и моделей диагностики ИС, методов и алгоритмов синтеза ИС, обладающих возможностями самодиагностики, контроля технического состояния аппаратных и программных средств в процессе функционирования, в онлайновых режимах.
Предлагаемый в работе новый комплексный подход к решению задач моделирования и синтеза ИС является дальнейшим развитием математических методов исследования линейных и нелинейных дискретных систем, определяемых над конечными полями, которые используют усовершенствованные методы логического дифференциального, интегрального исчислений, спектральных и символьных преобразований логических функций. При этом использованы результаты основополагающих работ в области логико-алгебраического моделирования, математических моделей технической диагностики и синтеза надежных ИС, а именно труды: Биргера И.А., Дружинина Г.В., Журавлева Ю.И., Майерса Г., Не-молочнова О.Ф., Пархоменко П.П., Поспелова Д.А., СапожниковаВ.В., Сапож-никоваВл.В., Шубинского И.Б., Ушакова И.А.; в области дифференциального исчисления логических функций - работы Акерса СБ., Астола Р., Бохманна Д., Гиббса Д.Е., Горбатова В.А., Давно М.Д., Закревского А.Д., Сэллерса Ф.Ф., Тей-за А., Янушкевич С.Н.; в области алгебраического подхода к общей теории моделирования систем - труды Арбиба М., КалманаР.Е., Уонема М., Фалба П.Л.; в теории конечных полей - труды Лидла Р., Нидеррайдера Г.
Сочетание и развитие названных методов позволяет сформировать новое научное направление логико-алгебраического дискретного моделирования и синтеза ИС, обладающих системными свойствами контролируемости и своевременности обнаружения отказов в процессе функционирования. Основной научно-технической проблемой, решаемой в данной работе, является разработка методологии повышения надежности и устойчивости функционирования современных ИС. Кроме создания теоретических методов математического моделирования в рассматриваемом научном направлении разработаны численные методы и реализованы комплексы программ, предназначенные для вычислительных экспериментов с предложенными моделями, что является актуальным для решения задач анализа и проектирования ИС с заданными показателями надежности.
Актуальность работы определяется практической потребностью промышленности, транспорта, связи и других областей в ИС, обладающих возможностями обнаружения нештатных режимов и отказов в реальном времени.
Актуальность тематики подтверждается тем фактом, что работа подержана:
- грантом РФФИ 09-08-00097а «Дискретные динамические и стохастические
модели анализа информационно-управляющих систем на транспорте и синтеза
надежных цифровых структур» (2009 - 2011 гг.);
- грантом Федеральной целевой программы «Научные и научно-
педагогические кадры инновационной России» на 2009 - 2013 гг. (мероприятие
1.1 «Проведение научных исследований коллективами научно-образовательных
центров» - IV очередь), шифр 2009-1.1-113-050 «Проведение научных исследований коллективами научно-образовательных центров в области информатики», тема 2009-1.1-113-050-043 (2009-2011 гг.);
грантом программы «Развитие научного потенциала высшей школы (2006 -2008 гг.)» РНП.2.1.1.1038 темаРОСТ-НИЧ-692;
грантом научно-исследовательской и опытно-конструкторской разработки Южного федерального университета per. № 3793 (2009 г.).
Цель и задачи исследования. Основной целью исследования является развитие теории математического моделирования дискретных динамических систем с использованием методов логико-алгебраического анализа и синтеза над конечными полями.
Для достижения поставленной цели необходимо решение следующих задач.
-
Разработка адекватных моделей и методов обнаружения ошибок функционирования ИС в онлайновом режиме в момент их проявления, причем как для аппаратных средств, так и для ПО.
-
Разработка методологии синтеза само диагностируемых ИС.
-
Развитие методов логического дифференциального исчисления над конечными полями с учетом круга решаемых задач технической диагностики и моделирования.
-
Разработка моделей декомпозиции и полиномиальных разложений булевых функций в базисах, необходимых для синтеза самотестируемых и контролируемых систем.
-
Развитие методов линеаризации систем над конечными полями, описываемых полностью и частично определенными булевыми функциями.
-
Развитие логического дифференциального исчисления в базисах с двойственными бинарными операциями.
-
Разработка моделей спектрального преобразования логических функций, определяемых над конечными полями; разработка алгоритмов символьного вычисления логических производных, дифференциалов и интегралов.
-
Введение и исследование свойства контролируемости линейных и нелинейных дискретных динамических систем и синтез контрольных уравнений в формальном и алгоритмическом видах.
-
Разработка методов получения контрольных соотношений для определения отказов с минимальным запаздыванием; методов представления линейных стационарных динамических систем над конечными полями в виде различных типов математических моделей.
-
Экспериментальная проверка разработанных теоретических подходов и положений на адекватность в практических задачах технической диагностики ИС с использованием разработанного специализированного программного комплекса.
Объектом исследования в диссертации являются ИС различного назначения на базе цифровых программно-управляемых устройств.
Предметом исследования являются модели и методы анализа, синтеза и алгоритмической реализации контролируемых ИС с возможностями самодиагностики.
Методы исследования основываются на использовании фундаментальных исследований в области теории алгебраического описания и моделирования дискретных систем, логического дифференциального и интегрального исчислений, математического моделирования дискретных систем над конечными полями, со-
временных методов технической диагностики программного и аппаратного обеспечения ИС.
Экспериментальная проверка разработанных моделей и методов осуществлялась путем программной эмуляции, проведения имитационных экспериментов на моделях и реальных объектах ИС.
Объект, предмет и методы исследования отвечают формуле специальности 05.13.18, так как содержанием работы является разработка фундаментальных основ и применение математического моделирования, численных методов и комплексов программ для решения научно-технической прикладной проблемы, исследование математических моделей технических объектов и соответствуют пунктам паспорта специальности: «1. Разработка новых математических методов моделирования объектов и явлений...»; «2. Разработка, исследование и обоснование математических объектов...»; «5. Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента»; «6. Комплексное исследование научных и технических, фундаментальных и прикладных проблем с применением современной технологии математического моделирования и вычислительного эксперимента».
Научная новизна работы заключается в теоретическом обобщении и решении научно-технической проблемы, связанной с разработкой нового направления в анализе и синтезе контролируемых и самодиагностируемых ИС, в разработке на его основе нового класса моделей, базирующихся на логико-алгебраическом подходе, а также в развитии математического аппарата дифференциального и интегрального исчисления логических функций.
К наиболее существенным научным результатам работы относятся следующие.
1. На основе сравнительного анализа существующих моделей и методов в
технической диагностике ИС
- сделан вывод о необходимости совершенствования математического аппа
рата решения задач диагностики с учетом особенностей аппаратных устройств и
ПО современных ИС с привлечением методов булева дифференцирования; выяв
лены задачи диагностики телекоммуникационных систем и ПО; сформулированы
задачи математического моделирования диагностируемых систем; сформулиро
вана задача онлайновой диагностики и синтеза контролируемых ИС.
2. На основе анализа моделей и алгоритмов, которыми располагает логиче
ское дифференциальное исчисление
предложено развитие методов дифференциального исчисления булевых функций: разработаны модели декомпозиции с двойственными операциями; развиты методы нахождения производных как полностью, так и частично определенных булевых функций;
предложены методы разложения логических функций над конечными полями;
получена общая модель дифференциальной дискретной системы;
разработаны модели спектрального представления логических функций над конечными полями;
разработаны численные методы спектральных преобразований булевых функций, а также численные методы вычислений и символьных преобразований в булевом дифференциальном и интегральном исчислении.
3. На основе анализа описаний динамических систем над конечными поля
ми, а именно, моделей: авторегрессионной, типа вход-выход, вход-состояние-
выход;
введено свойство «контролируемости» системы и решена задача синтеза контролируемой системы;
для линейных стационарных динамических систем над произвольным конечным полем установлена связь между контролируемостью и фундаментальным свойством управляемости;
рассмотрены нелинейные динамические системы над конечными полями, методы их линеаризации, и предложен общий метод синтеза нелинейных контролируемых систем.
4. Разработаны математические методы и модели диагностики, которые по
зволяют анализировать состояние ПО в процессе функционирования ИС в онлай
новых режимах
получена предикатная логическая производная, как аналог логической производной, обобщенной для анализа спецификаций ПО;
разработан метод анализа изменений в спецификации ПО с помощью предикатной производной;
разработана обобщенная предикатная модель диагностики ПО ИС;
введено свойство «своевременности» обнаружения изменений в ПО, предложены временные диагностические операторы, учитывающие это свойство. Исследование и учет этого свойства позволяет не только формировать реакцию ИС на произошедшие изменения и принимать решения об изменении режимов функционирования, но и синтезировать ПО с возможностями повышения отказоустойчивости ИС в целом.
Основные результаты, выносимые на защиту.
-
Системный подход к исследованию математических моделей описания дискретных динамических систем, являющийся развитием и совершенствованием моделей логического дифференциального и интегрального исчислений.
-
Новые свойства дифференциальных операторов логических функций, которые определяются над конечными полями и далее обобщаются на математические модели, использующие поля расширений, что позволяет выполнять процедуры анализа для универсальных базисов и многозначных логических функций.
-
Постановка и решение задачи разработки модели онлайновой диагностики аппаратного и ПО.
-
Новые декомпозиционные модели представления булевых функций в базисах, наиболее подходящих для синтеза само диагностируемых систем.
-
Новые численные методы вычисления производных полностью и частично определенных логических функций и метод доопределения частично определенных логических функций.
-
Модели спектрального представления логических функций, позволяющие представлять эти функции полиномами над конечными полями, и алгоритмы численных расчетов.
-
Алгоритмы спектральных и символьных преобразований функций в логическом дифференциальном и интегральном исчислении при решении задач, связанных с анализом дискретных динамических систем.
-
Метод внесения минимальной избыточности для управляемых линейных систем с целью сделать систему контролируемой.
-
Метод синтеза контрольных уравнений с минимальным запаздыванием для линейной динамической системы.
-
Метод синтеза контрольных уравнений и метод внесения избыточности, распространенные на нелинейные динамические системы.
-
Алгоритмы синтеза контролируемой системы с минимальной избыточностью и синтеза контрольного уравнения с минимальным запаздыванием для линейных и линеаризуемых систем.
-
Предметно-ориентированный программный комплекс, реализующий предложенные численные методы и алгоритмы и предназначенный для проведения вычислительных экспериментов, а также практического внедрения.
Практическая ценность. Практическая значимость результатов работы состоит в том, что разработанные методы анализа функционирования ИС могут быть использованы при решении практических задач моделирования широкого класса ИС, применяемых на транспорте и в телекоммуникациях, методы синтеза можно использовать при проектировании отказоустойчивых автоматизированных информационно-управляющих систем. Предложенные теоретические подходы к логико-алгебраическому анализу и синтезу в задачах технической диагностики ИС реализованы в полнофункциональном предметно-ориентированном программном комплексе, который внедрен в ряде организаций, что подтверждено соответствующими актами о внедрении и использовании результатов диссертационного исследования.
Практическую ценность представляют следующие результаты.
1. Разработан комплекс программ, в котором реализованы:
алгоритмы декомпозиции булевых функций в базисах, подходящих для синтеза самодиагностируемых дискретных устройств;
алгоритмы вычисления булевых производных, в том числе частных и высших порядков; по подмножеству переменных;
алгоритмы для вычисления логических дифференциальных операторов над конечными полями;
алгоритмы спектральных преобразований логических функций над конечными полями методами символьного моделирования.
2. Разработан и реализован комплекс программ для синтеза отказоустойчи
вых контролируемых дискретных систем, состоящий из модулей синтеза отказо
устойчивых комбинационных схем, контролируемых линейных и линеаризуемых
динамических систем и позволяющий:
- проводить численные эксперименты с моделями линейных стационарных
динамических систем, представляемых в виде многочленов над конечными поля
ми;
анализировать функционирование дискретных динамических систем на основе линейных контрольных соотношений;
синтезировать контрольные соотношения для динамических систем с минимальным запаздыванием.
3. Разработано и внедрено ПО:
позволяющее определять критерии и строить диагностические операторы для анализа изменений спецификаций программ;
реализующее алгоритмы и программы диагностики на основе предикатной производной;
реализующее алгоритмы и программы диагностики программного обеспечения в процессе функционирования системы.
Достоверность научных и практических результатов работы. Научные положения, результаты и выводы, сформулированные в диссертации, аргументированы. Сформулированные в работе методы моделирования, разработанные
численные методы и алгоритмы основываются на известных в теории дискретного анализа и синтеза динамических систем, теории логического дифференциального исчисления, теории конечных полей фундаментальных понятиях и подходах. Достоверность теоретических результатов, связанных с проблемами разработки математических моделей в технической диагностике, подтверждается обоснованностью поставленных задач, формулировок основных утверждений и определений, корректностью математических доказательств. Достоверность результатов и выводов подтверждается данными экспериментальных исследований и имитационных экспериментов, а также результатами эксплуатации разработанных методов, моделей и комплексов программ, внедренных в качестве подсистем в функционирующие ИС.
Реализация результатов работы.
Результаты работы прошли успешную апробацию, внедрены и используются: в научно-производственном предприятии (НПП) «Югпромавтоматизация» при разработке диагностических подсистем для информационно-управляющих систем на транспорте; в Ростовском филиале Российского научно-исследовательского и проектно-конструкторского института информатизации, автоматизации и связи в контрольно-диагностическом комплексе устройств сортировочных станций; в телекоммуникационной компании «Альянс-Телеком» в системе мониторинга и контроля предоставления информационных услуг связи по передаче данных и доступу к сети Интернет. Разработанный автором программный комплекс зарегистрирован в отраслевом фонде алгоритмов и программ. Научные результаты работы используются в учебном процессе Ростовского государственного строительного университета.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на всероссийских симпозиумах по прикладной и промышленной математике (2001-2009 гг., Сочи, Ростов-на-Дону, Йошкар-Ола, Петрозаводск, Кисловодск, Волжский, Санкт-Петербург); на научно-практической конференции Санкт-Петербургского государственного политехнического университета (2008 г.) «Управление созданием и развитием систем, сетей и устройств телекоммуникаций»; на международных научно-практических конференциях Южно-Российского государственного технического университета (НПИ), Новочеркасск: «Теория, методы и средства измерений, контроля и диагностики» (2007 г.), «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем» (2007 г.); на межведомственных и международных конференциях «Телекоммуникационные и информационные технологии на транспорте России» (2001, 2006, 2007, 2008 гг., Сочи); на международных конференциях «Математика. Экономика. Образование» (2002, 2006 гг., Новороссийск); на международной научно-практической конференции «Организационно-экономические проблемы проектирования и применения информационных систем» (1996 г., Ростов-на-Дону); на ведомственной конференции МПС «Проблемы обеспечения информационной безопасности на федеральном железнодорожном транспорте» (2001 г., Санкт-Петербург); на научной конференции «Безопасность информационных технологий» (2002 г., Таганрог); на международной научно-технической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (2009 г., Коломна); на конференциях профессорско-преподавательского состава Ростовского государственного университета путей сообщения (РГУПС) (1999 - 2001 гг.), и Ростовского государственного строительного университета (РГСУ) (2009 г.); на научных семинарах кафедр «Информатика» РГУПС, «Прикладная математика и вычислительная
техника» РГСУ, «Алгебра и дискретная математика» Южного федерального университета.
Публикации. Полученные в диссертации теоретические и практические результаты нашли свое отражение в 52 печатных работах, в том числе монографии, 23 статьях в изданиях, рекомендованных ВАК РФ.
Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения, приложений, списка литературных источников из 175 наименований. Общий объем диссертации составляет 281 стр., из которых объем основного текста составляет 256 стр.
Предварительные замечания об исследованиях в данной области
Базовым понятием, необходимым для развития идей анализа динамических характеристик дискретных систем, является булева разность, также называемая булевой производной. Простейшее объяснение данного понятия, пригодного для анализа изменений в дискретных системах, заключается в следующем. Пусть имеется двоичная техническая система, у которой цифровой сигнал (,)є{0,і} может изменить свое значение после возникновения некоторого события, например, вследствие возникновения ошибки. Тогда ситуацию изменения сигнала можно выразить в виде s\ я\г) причем она обнаруживается только в случаях, когда значение изменяется с логического 0 на логическую 1 и наоборот. В остальных случаях обнаружение изменений невозможно, поскольку 0Ф0 = 0 и 11 = 0. Тогда получается, что для произвольной булевой функции изменения можно выявить, когда ft(xl,...,xj,...,xn)ft+l(xi,...,xj,....,xn) = l, а это возможно в случае, когда некоторая переменная х( изменила свое значение на противоположное. Определение 1.2
Производная булевой функции /(x1,...,x/,...,xn) (булева производная) по переменной xt представляет собой выражение вида /;.= - = f{xl,...,xi,...,xn)f(x1,...,xi\,...,xn).D (1.7) дхі Иногда к булевой производной по /-му аргументу -=— в смысле (1.7) дх{ применяют термин «простая» булева производная. Впервые определение «простой» булевой производной было дано в работе [156], а затем в работе [108]. В дальнейшем это понятие дало мощный импульс развитию анализа динамических характеристик двоичных систем методами булева дифференциального исчисления, фундаментальные основы которого заложены работами [10, 121, 172, 173]. Развитием подхода, использующего булевы производные, является диадическая производная на конечных диадических группах [127], показывающая связь между коэффициентами разложения булевой функции в ряд Уолша и булевыми разностями данной функции, называемая теперь производной Гиббса. На её базе построено гармоническое дифференциальное исчисление в полях Галуа, называемое также диадическими дифференциалами Гиббса [118, 168]. Первой работой, посвященной приложениям булевых производных для генерации тестов в комбинационных цифровых схемах, была работа [163], основной идеей которой является анализ чувствительности булевой функции, реализующей данную схему, к изменениям групп входных сигналов. Арифметические аналоги булевой производной и разложения её в ряды Тейлора и МакЛорена рассматривались в работах [65, 175]. Из современных работ, в которых достаточное внимание уделяется оп 40 ределению понятия булевых производных, заслуживают внимания работа [106] с обширной библиографией ранее выпущенных работ и [19].
Для начала раскроем сущность булевой производной в контексте нашего исследования. В рамках всей работы подразумевается, что базой для исследования являются дискретные двоичные динамические системы, которые на разных уровнях абстракции можно рассматривать как на микро-уровне (это цифровые логические элементы и схемы) так и на макро-уровне (цифровые программируемые информационно-управляющие системы и сети). И в одном и другом случае эти системы можно рассматривать как описываемые функциями алгебры логики, только на разных уровнях их описание может быть более или менее громоздким. Но и в том и в другом случае задачу идентификации их состояния, как часть задачи ТД, можно решать с помощью аппарата дифференцирования булевых функций, учитывая следующее фундаментальное свойство.
Свойство 1.1 Булева производная функции f обладает следующим свойством: / = 1, когда значение f изменяется при изменении значения переменной; f = 0, когда изменение значения переменной не приводит к изменению значения f .
Это свойство позволило автору работы [159] предложить один из известных алгоритмов диагностики цифровых схем. Этот алгоритм, относящийся к ранее упомянутому микро-уровню, был доработан и применен к макро-уровню в ряде последующих работ. На наш взгляд, для дальнейшего теоретического изучения свойств булевых производных более пригоден способ определения их с помощью аппарата логических остаточных функций в конечных полях.
Остаточными функциями по і-му аргументу называются функции размерности, на единицу меньшие размерности исходной функции f, а именно: У;(т1,...,тм, с1.+р...3тл) = /(т„...,тм,ст,т1.+1,...,тя)Л При а; = 0 функция / называется нулевой остаточной, а при а(. = 1 функция f} называется единичной остаточной функцией. Понятие остаточной функции индуктивно распространяется на множество аргументов ix,...,ik по набору а(. ,...,о\ , к п: При этом к называют порядком остаточной функции. Из определения
Логические дифференциальные операторы над конечными полями
Ряд публикаций автора [23, 66, 73, 76] посвящен анализу проблем, касающихся теории ТД, возникающих в связи с развитием новых информационных и телекоммуникационных технологий. Рассмотрим основные идеи вышеупомянутых работ автора. Перспективной методикой для ТД является символьное моделирование [57]. Приведем несколько примеров методик такого вида моделирования и остановимся на одной из основных задач, возникающих в области диагностики сетей: размерность символического описания должна быть сравнима с размерностью исследуемой сети, а само символическое описание должно быть ей функционально эквивалентно. Данные вопросы затрагивались в работе автора [91].
Одной из первых методик символьного моделирования в задачах ТД явилось D -исчисление (и упомянутый в параграфе 1.1 алгоритм Рота) [158]. Суть его состоит в конструировании булевой функции тестового набора по структуре изучаемой схемы без анализа её состояний при всех входных воздействиях на устройства, входящие в схему. Вводится понятие расширенной булевой функции fD = 0,1,D, }, где выходу приписывается символ D, когда при диагностическом воздействии имеется изменение 1 —» 0, и, соответственно, символ D, когда имеется изменение 0 — 1. Отслеживается, чтобы выходная линия устройства имела либо символ D, либо D, что при непустых операциях D -пересечений дает тестовый набор, диагностирующий данную неисправность.
Другой, более современный подход, основан на аппарате упорядоченных бинарных диаграмм решений [141], позволяющий компактно и однозначно представлять в таком виде любую булеву функцию. Бинарная диаграмма решений представляется в виде направленного ациклического графа (двоичного дерева) с одним корнем, у которого каждая нетерминальная вершина является функциональной переменной, а две терминальные вершины являются выходными значениями соответствующей булевой функции и помечаются 0 и 1. Особую роль играют именно принцип упорядоченности вер 64 шин графа и отыскание путей от корня к стокам при прохождении через все листья в восходящем порядке функциональных переменных. В [117] формулируется постановка задачи представления сети цифровых переключательных устройств в виде упорядоченных бинарных диаграмм решений, и показывается, что для анализа такой сети требуется решение системы булевых уравнений. Основная идея подхода к нахождению решения изложена в работе автора [99] в данном случае заключается в следующем.
Имеется упорядоченная бинарная диаграмма решений (V,E), где вершины V, дуги EcVxV , \V\ = n. Путь от корня к стоку а = (аг,...,ак)е F2", булево произведение элементов множества АеЕ обозначается лаеЛа, причем для пустого множества оно равно 1; аналогично булева сумма v asA а, а для пустого множества равна 0. Каждая вершина символически обозначается х,, i = \,2,...,n, если она встречается в пути д., и символ х есть x(v) є F2, для каждой вершины veV; символ А -это обозначение A(u,v)eF2" для каждой дуги (U,V)GE.
Система булевых уравнений [Л(,6], состоящая из дуг с символами А и вершин с символами Ь, Ь(у) є F2, v є V, имеет решение x(v) = b{v)v{Vjx(n)AA(u,v)],VvGV.
Внимание к вопросам диагностики ИС, к методологиям оценки их качества и вопросам сертификации ИС в настоящее время повышается по мере их развития и совершенствования. Учитывая относительность понятия «качество», необходимо отметить, что в данном случае под качеством ИС понимается совокупность её свойств, относящихся к способности выполнять предъявляемые к системе требования. Наиболее полно качество ИС проявляется в результате её эксплуатации, когда можно либо измерить свойства системы, либо собрать необходимые для подтверждения наличия или отсутствия свойства статистические данные. Но определение качества ИС по результатам её эксплуатации абсолютно недопустимо при внедрении ИС промышленного или транспортного назначения. От качества ИС зависит в дальнейшем не только перспективы ее использования, масштабы применения и коммерческая прибыль от её внедрения. Одним из важнейших факторов, требующих учета и измерения свойств ИС на этапе системного анализа, является степень её влияния на окружающую среду и степень риска для человеческих жизней в результате неправильного функционирования компьютерной управляющей системы. Данные вопросы для крупных ИС, к которым относятся в первую очередь автоматизированные системы управления на транспорте были рассмотрены в работах автора [28, 29].
Математические модели ТД и анализа качества функционирования технических объектов, которым посвящено значительное число научных публикаций, строятся на основе марковских и полумарковских вероятностных процессов. При этом в большинстве моделей изучаются процессы возникновения отказов технических объектов и способы борьбы с ними. Наиболее распространенными объектами ТД в области ИС являются автоматизированные системы управления [30], цифровые и микропроцессорные системы [36], ПО [43], вычислительные комплексы и сети [174]. Следует отметить, что несмотря на интенсивное развитие телекоммуникационных технологий, современные работы, например [164], посвященные моделям диагностики ИС, как и прежде рассматривают марковские модели. Не преуменьшая место указанных моделей в предмете математического аппарата ТД и надежности, автор считает, что усложнение, рост и совершенствование сетей телекоммуникаций, а также появившиеся в связи с этим новые системные свойства данных объектов обусловливают необходимость разработки некоторых новых направлений в рассматриваемой области. Одно из таких направлений рассматривалось автором в работе [25].
Рассмотрим сначала наиболее новые системные свойства моделей функционирования систем со сложной сетевой топологией. Аналитическими моделями таких систем сначала являлись регулярные графы, а затем в связи с усложнением топологии и принципов функционирования, наиболее адекватным аппаратом математического моделирования стали случайные графы [37], что в физическом смысле соответствует свойствам моделей малых миров. Это означает, что, несмотря на значительный размер сети в большинстве случаев существует сравнительно короткий путь между некоторыми двумя узлами сети. Показано [110], что если обозначить N - число узлов сети, М -среднее число связей для некоторых выбираемых узлов из состава входящих в сеть, то оказывается, что средняя длина пути между двумя узлами пропорциональна величине D = In NI In М, которая мала даже при больших ТУ. Однако в реальных сетях есть и наличие свойства кластерное, сгущений около небольшого количества узлов входящих в сеть. Распределение количества связей для узла сети, моделируемой как случайный граф, считают степенным, а сети с такими свойствами называют безмасштабными. Другим подходом, уже не соответствующим модели случайных графов, является применение решеток с полностью упорядоченными связями каждого узла с некоторым числом соседних, что позволяет смоделировать свойство кластерное.
Постановка и решение задачи синтеза контролируемой системы и контрольных уравнений
Заметим, что при построении алгебраических моделей технической диагностики зачастую по умолчанию подразумевается, что вектор входных параметров х є F полностью определен на всем векторном пространстве наборов длины п с компонентами из поля F2, и редко упоминается, что соответствующая некоторому вектору х булева функция /(х) определена полиостью. Тем не менее, в работах данной области проводятся исследования частично определенных булевых функций [116], которые также называют (на наш взгляд менее удачно) не полностью специфицированными булевыми функциями [138]. Целью данного раздела является развитие математического аппарата описания производных булевых функций при частично определенных векторах двоичных переменных. Основной идеей предлагаемого подхода является доопределение частично определенных булевых функций с помощью векторов состояний, содержащих логическую производную (указанный подход опубликован в работе автора [81]).
Пусть / - булева функция, которая при некотором наборе параметров получает значение 1, множество таких векторов обозначим Г(/). Аналогично, множество векторов, обращающих значение функции в 0 {false), обозначим F(f). Очевидно, что F(f) = F \Г(/). Предположим также, что некоторое подмножество Т сГ (/) содержит компоненты из множества М = {0,1, }, где знак « » обозначает не полностью определенное значение, то есть либо 0, либо 1. Обозначим векторное пространство наборов длины п с компонентами из М: МхМх...хМ1 = М". Аналогично определяется
Пусть на множествах Т, F введен лексикографический порядок, булева функция f является монотонной. Тогда если ТГЛ F = 0, то булеву функцию / T,F , для которой T,FciF , F![ с", называют частично определенной. Примером частично определенных функций при М4 могут являться fx =(l, ,0,l), f2-(l, , ,0). Физический смысл введения недоопределенного состояния « » достаточно прост и, в зависимости от типов ошибок, возникающих в дискретных системах, требуется введение доопределения наборов двоичных значений. Для принятия решения о значениях неопределенных переменных предлагается использовать не широко известные функции паритета (четности) и мажорирования (большинства), а аппарат булевых производных, применяемый следующим образом.
Введем понятие вектора доопределения частично определенной булевой функции, применяя утверждения 2.7 и 2.8, разложения (2.7) и (2.8), разложение 2.12.
Вектор доопределения частично определенной булевой функции, составляемый по переменной xv определяется как = [/(xt,...,x, = 0,...,x„),f(xl,...x,=l,...,xJI),f(x1,...,x, = 0,...,A;)J 3/W (2.15) /.Y,=0 /x=l " дх. 5/(х„...л:, =!,..., „)] = Выражение (2.15) может быть записано для двух переменных в виде Ф, (f(x, j))= Ф,. (/,=О),Ф, (л= К [ил/ ) Фх, (/ ,=о)»Ф , (Л,=і) - -«о, , а2/(х) dxtdxj (2.16) Рекурсивное применение выражений (2.15) и (2.16), которое допустимо, потому что рассматриваемые булевы функции являются монотонными, позволяет записывать вектор доопределения для п входных двоичных переменных в виде: V v J) m( ( Y\ 7mf J \\ dBf( )
Заметим, что выражение для вектора доопределения булевой функции п переменных представляет собой (їх 3й J матрицу, что очевидно при рассмотрении выражений (2.16) и (2.17), но при этом существенным обстоятельством ее построения является лексикографический порядок, то есть
Более компактной формой записи вектора доопределения булевой функции является матричная запись, которую предлагается определить следующим образом. Как и прежде, используем обозначение %, для одной из решеточных операций, и пусть ф будет являться дистрибутивной для операции ф. Пусть также еп и е_ обозначают нейтральные (нулевые) элементы для применяемых операций ф и ф, соответственно. Таким образом, матричная запись, учитывая что е является единичным элементом относительно операции ф, выглядит следующим образом:
Аспекты реализации методов и моделей в существующих информационных системах
Математические модели, использующие некоторые методы из современной алгебраической теории систем, являются в настоящее время одними из перспективных направлений в технических науках, дающих теоретическую базу для исследования и проектирования любых автоматических и автоматизированных систем. У таких моделей есть практические преимущества, состоящие в том, что применяемые исследователями частотные и временные методы можно рассматривать с единых позиций. В таком случае модели линейного представления динамических систем над конечными полями оказываются частным случаем моделей линейных динамических систем общего вида. Начальный этап алгебрапзации исследования дискретных динамических систем ознаменовался появлением сравнительно редко цитируемой монографии [52]. Опираясь на возможности векторного и матричного представления, были предложены линейные представления дискретных динамических систем над полями F2. В связи с возможностью таких представлений стало очевидным использование аппарата передаточных матриц в моделях динамических систем типа вход-выход, по аналогии с преобразованием Лапласа для непрерывных систем и Z -преобразованием для дискретных систем над бесконечными числовыми полями. Таким образом, для дискретных динамических систем с конечным пространством состояний более естественным стало их представление в виде моделей систем над конечными полями простых характеристик.
Следующим этапом становления рассматриваемого подхода явились фундаментальные работы Р. Е. Калмана [139, 140], в которых линейная стационарная дискретная динамическая система представлялась кольцом полиномов с коэффициентами из произвольного конечного поля и появилась возможность ее исследования как алгебраической структуры следующим образом.
Пусть Е - некоторая динамическая система, представляющая собой, по сути, правила преобразования набора входных воздействий в выходные воздействия в некоторые дискретные моменты времени t єТ, где т - вспомогательное множество моментов времени. Она также обладает несколькими свойствами: линейностью, в связи с чем все правила преобразования вход-выход являются линейными и позволяют использовать хорошо развитый математический аппарат матричной алгебры и стационарностью, в смысле того, что правила преобразования вход-выход системы с течением времени не изменяются.
В этом направлении ведутся исследования динамических систем, обладающих возможностями самодиагностики отказов, и актуальность развития новых методов технической диагностики подтверждается значительным числом работ.
Основной целью главы является разработка математических моделей синтеза контролируемых дискретных динамических систем над конечным полем. Понятие контролируемости рассматривается как внутреннее свойство системы, позволяющее построить наиболее простое контрольное соотношение, на основе которого можно определить сбой или отказ динамической системы во время ее функционирования. В главе рассматриваются линейные контрольные уравнения. Новые результаты, полученные в этой главе опубликованы в работах автора [5, 74, 84, 100].
Первый параграф, который использует результаты процесса алгебраи-зации математической теории систем, содержит основные определения и факты из теории конечных полей, необходимые для исследования. Определения и факты приведены по знаменитой и наиболее полной монографии [42]. Основное внимание уделяется вопросам расширения конечных полей.
Второй параграф содержит описание динамической системы над конечным полем. При этом использовалась классическая работа [16].
В третьем параграфе рассматривается представление вход-состояние-выход для линейной стационарной динамической системы над конечным полем. Определяется понятие - контролируемость, которое связывается с таким важным понятием как управляемость. Приводятся и подробно исследуются два метода синтеза контролируемых систем и контрольных уравнений. При этом используется аппарат расширения поля. Приводится пример синтеза контролируемой системы.
Четвертый параграф посвящен нелинейным динамическим системам над полем F2. Рассматривается линеаризация нелинейной динамической системы, а также описывается класс динамическим систем, для которого линеаризация возможна. Основной инструмент, который используется при линеаризации - это подробно изученная в предыдущих главах булева производная и представление булевых функций от многих переменных в виде многочленов. Разложение позволяет ввести дополнительные переменные, что в конечном итоге приводит к линеаризации нелинейной динамической системы. Линеаризация позволяет применить аппарат, развитый в третьем параграфе этой главы и предложить алгоритм синтеза контролируемых нелинейных динамических систем и контрольных уравнений.
