Работа умножителя двоичных чисел

Исследование методов моделирования, отличных от сетей Петри. Моделирование при помощи инструментария IDEF. Пример простейшей байесовской сети доверия. Анализ младшего разряда множителя. Сложение на сумматорах. Заполнение и анализ редактора сетей Петри.
Краткое сожержание материала:

Размещено на

1. Исследовательская часть

1.1 Исследование методов моделирования, отличных от сетей Петри

1.1.1 Стандарты IDEF

IDEF0 - методология функционального моделирования и графическая нотация, предназначенная для формализации и описания бизнес-процессов. Отличительной особенностью IDEF0 является её акцент на соподчинённость объектов. В IDEF0 рассматриваются логические отношения между работами, а не их временная последовательность. [5]

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

IDEF3 является стандартом документирования технологических процессов, происходящих на предприятии, и предоставляет инструментарий для наглядного исследования и моделирования их сценариев. [7]

Рис. 1. Пример IDEF3 диаграммы

На рис. 1 изображена диаграмма IDEF3, являющаяся графическим отображение сценария обработки детали. Прямоугольники на диаграмме IDEF3 называются функциональными блоками и обозначают событие, стадию процесса или принятие решения. Они имеют свое имя, отображаемое в глагольном наклонении и уникальный номер. [7]

Объект, обозначенный J1 - называется перекрестком. Перекрестки используются для отображения логики взаимодействия потоков. Перекресток не может использоваться одновременно для слияния и для разветвления. [7]

Покажем качество работы данного инструмента для моделирования. Промоделируем инструментарием IDEF3 работу мультиплексора (рис. 2).

Рис. 2. Моделирование при помощи инструментария IDEF

1.1.2 Стандарты UML

Unified Modeling Language (UML) - унифицированный язык моделирования.

Важным понятием UML является класс. Графически класс изображается в виде прямоугольника, который дополнительно может быть разделен горизонтальными линиями на разделы или секции. В этих разделах могут указываться имя класса, атрибуты (переменные) и операции (методы). Обязательным элементов обозначения класса является его имя. [2]

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

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

Кроме внутреннего устройства или структуры классов на соответствующей диаграмме указываются различные отношения между классами. Базовыми отношениями или связями в языке UML являются:

1. Отношение зависимости. Обозначается пунктирной линией со стрелкой. [2]

2. Отношение ассоциации. Обозначается сплошной прямой линией. [2]

3. Отношение обобщения. Обозначается прямой линией с треугольником на конце. [2]

4. Отношение агрегации. Обозначается прямой линией с ромбом на конце. [2]

5. Отношение композиции. Обозначается прямой линией с закрашенным ромбом на конце. [2]

Промоделируем взаимосвязь мультиплексора и сумматора при помощи UML (рис. 3).

Рис. 3. Моделирование с помощью инструментария UML

1.1.3 Байесовские сети

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

Графические модели представляют собой графы, узлы которых соответствуют случайным переменным. Если узлы (переменные) не соединены дугами, то их считают условно независимыми. [1]

С математической точки зрения БС - это модель для представления вероятностных зависимостей, а также отсутствия этих зависимостей. [1]

Байесовские сети доверия (БСД) используются в тех областях, которые характеризуются наследованной неопределённостью (рис. 4). Эта неопределённость может возникать вследствие: [1]

· неполного понимания предметной области;

· неполных знаний;

· когда задача характеризуется случайностью.

Рис. 4. Пример простейшей байесовской сети доверия

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



Рис. 5. Моделирование с помощью байесовских сетей

1.2 Исследование расширений сетей Петри

1.2.1 Цветные (раскрашенные) сети Петри

Фишкам раскрашенной сети приписывают атрибуты, которые называют цветами. Правила возбуждения переходов дополняются условиями, предполагающими выбор фишек определённых цветов из входных позиций перехода . Срабатывание переходов сопровождается посылкой в выходные позиции перехода фишек, с задаваемыми значениями цвета. [8]

Правила задания цветных сетей Петри:

1. Фишки вместо простого обозначения содержимого позиций преобразуются в объект, который может содержать в себе один или более параметров, каждый из которых может принимать дискретный набор значений. Чтобы отличать фишки различных типов их можно окрашивать в различные цвета (поэтому сети называют цветными). [8]

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

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

4. К дугам, исходящим из переходов, добавляется информация о типах фишек, порождаемых данным переходом. [8]

5. К начальной маркировке сети добавляется информация о значении цветов, содержащихся в фишках. [8]

Покажем качество работы данного метода моделирования. Для этого промоделируем данным методом работу мультиплексора (рис. 6).

Рис. 6. Моделирование с помощью цветных сетей Петри

1.2.2 Временные сети Петри

Для учета временных характеристик вводятся временные сети Петри. Во временных сетях Петри каждому переходу сопоставляются два момента времени: и . Переход , может быть запущен, только если он был разрешен к моменту времени . Если он является разрешенным, то должен быть запущен до наступления момента времени . [4]

Если переход возбуждается, то метки, вызвавшие запуск перехода, покидают входные позиции. Порождение меток в выходных позициях происходит через время . [4]

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

Промоделируем данным методом работу мультиплексора (рис. 7).

Рис. 7. Моделирование с помощью временных сетей Петри

1.2.3 WF-сети Петри

Сеть Петри называется WF-сетью, если выполняются следующие три условия:

1. Имеется только одна позиция-источник [3], такая что , т.е. отсутствуют переходы, входящие в ;

2. Имеется только одна позиция-сток [3], такая что , отсутствуют переходы, выходящие из ;

3. Каждая вершина находится на некотором пути от позиции к позиции . [3]

Для WF-сетей разработаны специальные методы анализа. Одним из основных критерием корректности WF-сети является свойство бездефектности (правильной завершаемости). [3]

WF-сеть называется бездефектной, если:

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

2. Состояние является единственным состоянием, которое достижимо из состояния и содержит хотя бы одну фишку в позиции . [3]

3. В WF-сети нет тупиковых, т.е. никогда не срабатывающих, переходов. [3]

Применим этот метод моделирования. Для этого промоделируем запись множимого в регистр множимого (рис.&...