Математические модели функционально избыточных дискретных систем

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Автореферат

диссертации на соискание ученой степени доктора физико-математических наук

Математические модели функционально избыточных дискретных систем

Общая характеристика работы

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

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

Одним из первых авторов, подробно рассмотревшим понятие «адаптивность» является Я.З. Цыпкин, указавший, что адаптивность системы достигается за счет возможности настройки режима ее функционирования для получения некоторого спектра требуемых реакций. Однако в его работах не рассматриваются вопросы достижения адаптивности на основе функциональной избыточности. Вопросами избыточности в рамках проблемы отказоустойчивости занимались представители советской школы технической диагностики М.Ф. Каравай, Е.С. Согомонян, П.П. Пархоменко, Ю.Г. Савченко, однако в их работах основное внимание уделено аппаратной избыточности.

Основы математического моделирования дискретных систем, способных реализовать некоторый спектр поведений, заложены в работах К. Шеннона, М. Минского, Дж. фон Неймона, А. Тьюринга, предложивших различные модели универсального автомата (машины, устройства). Универсальный автомат способен моделировать, порождать, воспроизводить заданный спектр поведений или объектов, соответственно по Шеннону, Минскому, фон Неймону. Изучение универсальных конечных автоматов осуществляловь Э.В. Евреиновым и И.В. Прангишвили, А.П. Горяшко, В.А. Мищенко, Э.А. Якубайтисом и многими другими c целью построения универсальных и многофункциональных модулей. Однако, превалирующей в этих работах была идея о достижении универсальности за счет перенастройки структуры технического объекта. Для описания функционально избыточных систем А.А. Сытником введена модель универсального автомата-перечислителя, однако в его работах эта модель используется только для решения задачи восстановления системы после возникновения различного рода неисправностей на этапе эксплуатации системы. Модель универсального автомата-перечислителя исследовалась также Н.С. Вагариной, Н.И. Посохиной, К.П. Вахлаевой и другими для отдельных классов дискретных систем, однако эти исследования имеют чисто теоретический характер и не затрагивают вопросы создания и эксплуатации функционально избыточных систем.

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

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

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

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

- разработка общих схем решения задач математического моделирования функционально избыточных дискретных систем;

- решение задач математического моделирования функционально избыточных систем для частных классов систем:

o систем, допускающих так называемое числовое моделирование (моделирование многочленами специального вида),

o систем без потери информации,

o регистров, представляющих собой один из базовых элементов современной электронной техники;

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

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

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

Научная новизна.

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

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

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

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

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

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

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

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

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

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

7. Исследована автоматная модель регистров различных типов, а именно регистров с последовательным приемом и параллельной выдачей информации, сдвиговых регистров, регистров с параллельным приемом и последовательной выдачей информации, регистров памяти. На основе свойств преобразований, реализуемых регистрами с последовательным приемом и параллельной выдачей информации при подаче входных сигналов 0 и 1, разработаны методы построения восстанавливающих последовательностей для данного класса объектов, методы синтеза универсальных перечислителей.

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

Практическая ценность, реализация результатов работы. Результаты диссертационной работы могут быть использованы при решении таких практически значимых задач, как проектирование и эксплуатация адаптивных систем. Метод проектирования функционально избыточной программной системы использован при разработке АИС «Управление инфраструктурой научно-образовательной среды» по проекту «Работы по анализу и выбору базовых показателей, используемых в зарубежных странах для оценки использования и воздействия ИКТ на сферу образования, и разработке методик анализа данных, технологии сбора и обработки информации на основе выбранных показателей» (в рамках ФЦП «Электронная Россия» (2002-2010 годы)) и при разработке регионального образовательного портала по заказу министерства образования Саратовской области, имеются соответствующие акты о внедрении. Теоретические результаты, представленные в диссертации, внедрены в учебный процесс в Саратовском государственном социально-экономическом университете (дисциплина «Теория вычислительных процессов и структур» для специальности 010503.65 «Математическое обеспечение и администрирование информационных систем») и в Саратовском государственном техническом университете (дисциплина «Методы разработки программного обеспечения» магистерской программы 55.28.13. «Сети ЭВМ и телекоммуникаций»).

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на следующих конференциях: IV и VI Международных научных конференциях «Автоматизация проектирования дискретных систем CAD DD» (Минск, 2001, 2007), XXIV конференции молодых ученых МГУ (Москва, 2002), Международной научной конференции «Информационные технологии в естественных науках, экономике и образовании» (Саратов, 2002), V Международном конгрессе по математическом моделированию (Дубна, 2002), Всероссийской научной конференции «Научный сервис в сети Интернет» (Новороссийск, 2004), Всероссийской научно-практической конференции «Информационные технологии в образовании и науке» (Москва, 2006), XXII-XXIII Международных научных конференциях «Математические методы в технике и технологиях» (Псков, 2009, Саратов, 2010), постоянно действующем научном семинаре института проблем точной механики и управления РАН (Саратов, 2009), X Международной научно-методической конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2010), конференциях по итогам научно-исследовательской работы СГСЭУ (Саратов, ежегодно в 2004-2010 гг.).

В полном объеме диссертация докладывалась в ГОУ ВПО «Саратовский государственный технический университет» и ГОУ ВПО «Саратовский государственный социально-экономический университет».

Публикации. По основным результатам диссертации имеется 38 публикаций, в т.ч. числе одна монография и 11 статей в журналах, входящих в Перечень ВАК РФ.

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

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

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

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

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

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

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

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

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы, включающего 192 наименования, и трех приложений. Работа изложена на 363 страницах, содержит 8 рисунков и 5 таблиц.

Содержание работы

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

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

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

В качестве математической модели дискретных систем в разрабатываемой теории выбрана модель конечного детерминированного автомата Медведева

A=(X, S, ), (1)

где S ={s,…, s_m} - конечное множество внутренних состояний; X={x,…, x} - конечное множество входных сигналов; - функция переходов.

Пронумеруем состояния автомата натуральными числами S ={0, 1,…, m-1} и представим функцию переходов данного автомата в виде обобщенных подстановок:

, xX. (2)

Обозначим s = (0,1,…, m), . Для краткости также будем использовать запись подстановки (2) в виде .

Поведение автомата (1) может быть описано функцией , где - множество слов алфавита X.

Определение 1.2.1. Пусть текущее поведение системы M моделируется автоматом A=(X, S,d), X={x₁, x₂,…, x_n}, а требуемое - автоматом B = (X, S,d'), X={x₁, x₂,…, x_n}. Без ограничения общности будем считать Система M является функционально избыточной системой относительно требуемых поведений , если такое, что . Последовательность t_i будем называть восстанавливающей последовательностью для преобразования (или для входного сигнала x_i).

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

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

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

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

Определение 1.2.4. Конечный детерминированный автомат является универсальным перечислителем для автоматов семейства I, если выполняется следующее условие:  , где - множество, перечислимое автоматом A,  - множество, перечислимое автоматом .

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

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

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

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

Постановка задачи в терминах теории универсальных автоматов (задача анализа универсального автомата): для автомата A построить семейство автоматов , для которого автомат А является универсальным.

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

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

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

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

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

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

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

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

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

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

Постановка задачи в терминах теории универсальных автоматов: для каждого автомата A_i семейства I построить множество отображений , каждое из которых удовлетворяет условию , т.е. предложить метод построения восстанавливающих последовательностей автомата А, приложение которых моделирует все преобразования автоматов семейства .

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

На основе результатов теории универсальных автоматов и теории полугрупп показана алгоритмическая неразрешимость поставленных задач на множестве дискретных систем (теорема 1.3.2).

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

Опишем общие подходы к решению поставленных задач.

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

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

1. На вход МВП подается сигнал о необходимости настройки системы на требуемое поведение.

2. МВП отключает систему от внешних воздействий (с целью исключения возможных состязаний на входе системы).

3. На вход МВП подается некоторый входной сигнал x.

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

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

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

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

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

(3)

Тогда автомат U_m = (Х, S, ), где X = {0,1,2}, S = {0,1,…, m-1},  = {₀, ₁, ₂}, где функции ₀, ₁, ₂ представлены автоматными преобразованиями типа (3), является универсальным перечислителем для любого автомата с m состояниями. Построение для него восстанавливающих последовательностей, т.е. задача выразимости произвольного элемента полугруппы преобразований степени m через элементы системы образующих, является неразрешимой. Однако она может быть решена при наложении ограничений на вид моделируемых автоматных подстановок.

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

Вход: класс требуемых поведений системы.

Выход: универсальный перечислитель общего вида, совокупность восстанавливающих последовательностей.

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

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

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

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

Кроме того, предлагается построение автомата с управляющим входным каналом, являющийся универсальным для любого автомата с m состояниями, который имеет вид:

C_m = ({X, Xґ}, S, ), (4)

где S = {0, 1,…, m-1}; X множество информационных входных сигналов; X множество управляющих входных сигналов; :SЧ{XЧXґ}S, (s, (_x,л_xґ))=л^-1(_х(л_xґ(s))), где xX, xґXґ, s = (0, 1, …, m-1);  представители классов эквивалентности автоматных преобразований на множестве {0, 1, …, m-1}; преобразования, являющиеся решениями уравнений =л_xл^-1_, где xX ( преобразование, эквивалентное _x).

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

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

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

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

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

,,, xX, (5)

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

Определение 2.2.1. Поведение автомата А вида (1) моделируется семейством многочленов вида (5), если преобразование представимо многочленом , т.е. , т.е. автомат А вида (1) задан числовой моделью, если задано множество входных сигналов , количество состояний m и множество многочленов вида (5).

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

Теорема 2.2.1. Пусть , разложение числа состояний m автомата А вида (1) на простые множители. Тогда старшая степень l произвольного моделирующего многочлена вида (5) для данного автомата определяется по формуле , где индекс полугруппы преобразований , период полугруппы преобразований , которые вычисляются по формулам:

где НОК наибольшее общее кратное.

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

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

 (6)

2. Если СЛАС вида (6) неразрешима, то для заданной автоматной подстановки невозможно построить моделирующий многочлен, т.е. не всякий автомат может быть представлен с помощью числовой модели.

3. Если СЛАС вида (6) разрешима, то в общем случае она имеет несколько решений, т.е. автоматная подстановка может моделироваться различными многочленами вида (5).

4. Если число состояний автомата m - простое число, система (6) имеет единственное решение. Это означает, что в этом случае для автоматной подстановки существует единственный моделирующий многочлен вида (5) (теорема 2.3.1).

5. Для построения числовой модели автомата необходимо для каждого входного сигнала x решить СЛАС вида (6), а именно найти хотя бы одно ее решение.

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

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

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

Теорема 2.3.2. Пусть дан конечный детерминированный автомат А = (X, S,), |S| = m и каноническое разложение числа состояний автомата m имеет вид . Для того чтобы поведение автомата А моделировалось семейством многочленов вида (5), необходимо, чтобы любое его отображение переходов вида (2) удовлетворяло системе m-p₁ сравнений, из которых m₁-1 имеют вид

,

а остальные имеют вид ,

где .

Для частного случая числа состояний автомата m=2p, где p - простое число, предложены в аналитическом виде критерии моделируемости автомата системой многочленов с целыми и рациональными коэффициентами.

Теорема 2.3.3. Пусть дан конечный детерминированный автомат А = (X, S,), |S| = m и каноническое разложение числа состояний автомата m имеет вид m = 2p, где p - простое число. Для того чтобы поведение автомата А моделировалось семейством многочленов вида (5), необходимо и достаточно, чтобы любое его отображение переходов вида (2) удовлетворяло следующей системе сравнений:

, ,

,,

, ,

, .

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

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

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

Определение 2.5.1. Пусть дан автомат A = (X, S,), X = {x₁, x₂,…, x_n}, который допускает моделирование семейством многочленов . Назовем множество различных элементов полугруппы, порожденных функциями , порождающим множеством многочленов автомата А.

Также предложен критерий универсальности автомата рассматриваемого класса, представленный следующей теоремой.

Теорема 2.5.1. Автомат A=(X, S,), который допускает моделирование семейством многочленов , является универсальным перечислителем для семейства автоматов , где А_i допускает моделирование семейством многочленов , тогда и только тогда, когда , где - порождающее множество многочленов автомата А.

На основе этого критерия решаются задачи анализа и синтеза универсального автомата рассматриваемого класса.

Основным результатом главы является решение задачи реализации требуемых поведений функционально избыточных системам, допускающими численное моделирование, а именно метод построения восстанавливающей последовательности для заданного входного сигнала (метод 2.6.1). На входе метода считается заданным автомат В = (X, S, ) типа (1), многочлены вида (5), моделирующие требуемое поведение автомата, многочлен вида (5), моделирующий текущее поведение автомата В при подаче входного сигнала x_h. Выходом метода является последовательность входных символов t_h, порождающая после своего приложения структуру переходов внутренних состояний, соответствующую требуемому преобразованию, моделируемому функцией или вывод о невозможности реализации данного преобразования. Данный метод основан на свойствах полугруппы многочленов вида (5).

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

Определение 3.2.2. Автомат вида (1) называют групповым или перестановочным, если функция переходов данного автомата представима в виде подстановки

.

Обозначим , - перестановка на множестве {1, …, m}.

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

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

Определение 3.2.7. Длиной группы G в системе образующих Gen называют максимальную из длин ее элементов группы, где длина элемента группы - это минимальное число сомножителей из Gen в представлении элемента. Длиной группового автомата A будем называть длину его группы.

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

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

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

Утверждение 3.2.1. Групповой автомат с m состояниями является универсальным перечислителем для класса GA_m тогда и только тогда, когда он порождает симметрическую группу степени m или, иными словами, когда его порядок равен m!

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

Теорема 3.3.1. Групповой автомат A=(X, S, ₁), |S|=m, |X|=, функции переходов которого представлены множеством всех транспозиций ₁={, }, является универсальным перечислителем для класса автоматов GA_m. Длина восстанавливающей последовательности для данного универсального перечислителя относительно любого заданного преобразования с числом состояний m не превышает m-1.

Теорема 3.3.2. Групповой автомат A = (X, S, ₂), |S| = m>2, |X| = m-1, функции переходов которого представлены подстановками ₂ ={(1, i), }, является универсальным перечислителем для класса автоматов GA_m. Длина восстанавливающей последовательности для данного универсального перечислителя относительного любого заданного преобразования с числом состояний m не превышает 3 (m/2-1)+1, если m - четное и 3 [m/2], если m - нечетное.

Теорема 3.3.3. Групповой автомат A=(X, S, ₃), |S|=m>2, |X|=m-1, функции переходов которого представлены подстановками ₃ ={(i, i+1), }, является универсальным перечислителем для класса автоматов GA_m. Длина восстанавливающей последовательности для данного универсального перечислителя относительного любого заданного преобразования с числом состояний m не превышает m (m-1)/2.

Теорема 3.3.4. Групповой автомат A = (X, S, ₄), |S| = m>2, |X| = 2, функции переходов которого представлены подстановками ₄ ={(1,2), (1,2,…, m)}, является универсальным перечислителем для класса автоматов GA_m, причем его длина при m = 3 равна 2, а при m>3 больше длины универсального перечислителя с системой порождающих подстановок ₃.

Теорема 3.3.5. Групповой автомат A=(X, S, ₅), |S|=m>2, |X|=2, функции переходов которого представлены подстановками ₅ ={(1,2…, m-1), (1,2,…, m)}, является универсальным перечислителем для класса автоматов GA_m, причем его длина при m = 3 равна 2, а при m>3 меньше длины универсального перечислителя с системой порождающих подстановок ₄.

В табл. 1 приведены зависимости между основными характеристиками универсальных перечислителей для класса GA_m (рассмотренных в теоремах 3.3.1-3.3.5), а именно зависимости между числом входных сигналов n, максимальными длинами восстанавливающих последовательностей d и числом состояний группового автомата m.

...