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

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

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]

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

Рис. 8. Моделирование с помощью WF-сетей

1.3 Инструментарий сетей Петри

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

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



Рис. 9. Типы узлов сетей Петри. а) позиция; б) переход

Маркировка сети Петри - это присвоение фишек позициям сети Петри. Фишка является примитивным понятием сетей Петри.

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

На графе сети Петри фишки изображаются маленькой точкой в позиции.

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

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

2. Конструкторская часть

2.1 Описание моделируемого устройства

Перед началом работы умножителя все микросхемы и управляющие сигналы установлены в исходное состояние, регистры сброшен в ноль (р1). На шину данных (шина данных восьмиразрядная, а числа шестнадцатиразрядные) сначала выставляются (t1) младшие разряды числа А, являющегося множимым. Устройство управления вырабатывает (t2) тактовый импульс, по которому младшие восемь разрядов числа А записываются (t3) в регистр множимого. Затем на шину данных выставляются (t4) старшие разряды числа А. Далее устройство управления вырабатывает (t5) следующий тактовый импульс, и старшие восемь разрядов числа А записываются (t6) в регистр множимого (рис. 10).

Рис. 10. Запись числа А (множимого) на регистр множимого

После того, как всё число А записано в регистр множимого, на шину данных выставляются (t7) младшие разряды числа В, являющегося множителем. Устройство управления вырабатывает (t8) тактовый импульс, и младшие восемь разрядов числа В, заносятся (t9) в регистр множителя. Затем на шину данных выставляются (t10) восемь старших разрядов числа В. Устройство управления вырабатывает (t11) тактовый импульс, по которому старшие разряды числа В записываются (t12) в регистр множителя (рис. 11).



Рис. 11. Запись числа В (множителя) на регистр множителя

Когда оба числа записаны в регистр, происходит сравнение чисел с нулем для сокращения выполняемых действий в случае равенства одного из чисел нулю. Сначала с нулем сравнивается число А, затем число В. Выбор нужного числа осуществляется четырьмя мультиплексорами 8х4, а сравнение на логических микросхемах И.Т.к. мультиплексоры уже установлены в исходное состояние, то устройство управления вырабатывает (t13) тактовый импульс, по которому старшие (р15, р16) и младшие (р17, р18) разряды числа А выбираются (t14) на мультиплексорах. Далее число А поступает (t15) на логические микросхемы И 4х1. Т.к. числа шестнадцатиразрядные, то требуется четыре логических микросхемы И 4х1. Микросхемы И выполняют (t16) логическое сложение, и результаты логического сложения старших (р23, р24) и младших (р25, р26) разрядов поступают (t17) на пятую микросхему И 4х1, которая, выполнив (t18) логическое сложение, выдает результат сравнения (р28). Если число А не равно нулю, то устройство управления выдает (t19) управляющий сигнал, переключающий (t20) каждый из четырех мультиплексоров в режим выбора числа В. Далее устройство управления вырабатывает (t21) тактовый импульс, по которому на мультиплексорах выбирается число В, и последовательность действий по сравнению числа с нулем повторяется (рис. 12).

В случае равенства одного из чисел нулю устройство управления выдает (t65) сигнал «Нулевой результат» (р129), на шину выхода выдается (t66) ноль, и процесс умножения завершается (t67) (рис. 12).



Рис. 12. Сравнение чисел А и В с нулем и выдача результата сравнения

Когда сравнение выполнено, и оба числа не равны нулю, начинается сам процесс умножения по алгоритму умножения с младших разрядов множителя с неподвижным множимым и сдвигом суммы частичных произведений вправо на один разряд. Т.к. числа могут быть как положительными, так и отрицательными, то в ходе умножения могут выполняться коррекции в виде модифицированного сдвига (занесение 1 в разряд при сдвиге вправо) или вычитания множимого. В связи с этим старший (знаковый) разряд множителя поступает (t22) на D-триггер. Впоследствии этот разряд будет определять, необходимо ли выполнять коррекцию в виде вычитания множимого. Устройство управления вырабатывает (t23) тактовый импульс, и знаковый разряд множителя запоминается (t24) на D-триггере. Параллельно с поступлением знакового разряда множителя на D-триггер происходит поступление (t22) старших (р37, р38) и младших (р39, р40) разрядов числа А на преобразователь кода, состоящий из четырех логических инверторов 4х4. Это необходимо, чтобы можно было выполнить коррекцию в виде вычитания множимого. Логические инверторы инвертируют (t25) по четыре разряда числа А (рис. 13). Результаты совместно со знаковым разрядом множителя с D-триггера (р36) поступают (t26) на четыре мультиплексора 8х4 (рис. 17).

Рис. 13. Выполнение подготовительных операций для коррекции в виде вычитания множимого

Далее старшие (р45, р46) и младшие (р47, р48) разряды числа А поступают (t27) на четыре мультиплексора 8х4, также туда поступает (t27) младший разряд множителя (р49), который будет определять, с чем складывать сумму частичных произведений: с нулем, если разряд равен нулю, или с множимым, если разряд равен единице. Ноль уже находится на входах мультиплексора, т. к. умножитель был установлен в исходное состояние. Если младший разряд множителя равен единице, то мультиплексоры переключаются (t28) в режим выбора множимого. Если младший разряд множителя равен нулю, то мультиплексоры переключаются (t29) в режим выбора нуля. Далее устройство управления вырабатывает (t30) тактовый импульс, и на мультиплексорах выбирается (t31) либо множимое, либо ноль (рис. 14).



Рис. 14. Анализ младшего разряда множителя

Затем либо множимое, либо ноль поступают (t32) на четыре сумматора 8х4, на которые также поступает содержимое регистра частичных произведений. Регистр частичных произведений представляет собой часть регистра результата, который включает в себя также и регистр множителя. В регистре частичных произведений хранятся старшие разряды результата, в регистре множителя в итоге будут находиться младшие разряды результата. На сумматорах по четыре разряда производится сложение (t33) разрядов множимого (либо нуля) с содержимым регистра частичных произведений. Старшие (р63, р64) и младшие (р65, р66) разряды результата поступают (t34, t35) на регистр частичных произведений, также туда поступает старший (знаковый) разряд множимого (р69). Устройство управления вырабатывает (t36) тактовый импульс, по которому результат сложения записывается (t37) в регистр частичных произведений (р71, р72) (рис. 15).



Рис. 15. Сложение на сумматорах

Далее устройство управления выдает (t38) управляющий сигнал, переключающий (t39) регистр частичных произведений (p74, p75) и регистр множителя (p76, p77) в режим сдвига. Затем устройство управления выдает (t40) следующий тактовый импульс, и в регистре частичных произведений, и в регистре множителя осуществляется сдвиг на один разряд вправо обычный (t41) или модифицированный (t42) в зависимости от знакового разряда множимого (р69). Затем устройство управления выдает (t43) управляющий сигнал, и регистр частичных произведений (р84, р85) и регистр множителя (р86, р87) переключаются (t44) вновь в режим записи (рис. 16).

Устройство управления вырабатывает (t45) тактовый импульс, по которому счетчик тактов уменьшается (t46) на единицу. Если счетчик тактов не равен нулю, то последовательность действий повторяется (начиная с t27). Если счетчик тактов равен нулю, то в этом случае может выполняться коррекция результата в виде вычитания множимого в зависимости от запомненного ранее на D-триггере знакового разряда множимого (р36).



Рис. 16. Сдвиг результата

Как было описано выше множимое с преобразователя кода совместно со знаковым разрядом множителя с D-триггера (р36) поступило (t26) на четыре мультиплексора 8х4 - мультиплексоры для старших (p90, p91) и младших (p92, p93) разрядов. Если знаковый разряд множителя (p94) равен нулю, то мультиплексоры переключились в режим выбора нуля (t47), если равен единице - в режим выбора преобразованного множимого (t48). Т.к. счетчик тактов равен нулю, то устройство управления вырабатывает (t49) тактовый импульс и на мультиплексорах выбирается (t50) либо ноль, либо преобразованное множимое (рис. 17).

Рис. 17. Коррекция результата

Далее ноль или преобразованное множимое поступают (t51) на сумматоры, куда также поступает произведение с регистра частичных произведений. На сумматорах по четыре разряда выполняется (t52) сложение, и старшие (p108, p109) и младшие (p110, p111) разряды результата поступают (t53, t54) на выходные восьмиразрядные регистры (р112, р114), а также на выходные регистры поступает содержимое регистра множителя (р113, р115) (рис. 18).

Рис. 18. Коррекция на сумматорах

Далее устройство управления выдает (t55) управляющий сигнал, который разрешает (t56) запись выходных регистров по входной шине. Затем устройство управления вырабатывает (t57) тактовый импульс, и младшие восемь разрядов с регистра множителя выдаются (t58) на восьмиразрядную выходную шину. Затем устройство управления вырабатывает (t59) еще один тактовый импульс, и следующие восемь разрядов с регистра множителя выдаются (t60) на шину выхода. Потом устройство управления вырабатывает (t61) следующий тактовый импульс, по которому еще восемь разрядов, но уже с сумматоров, выдаются (t62) на шину выхода. Наконец устройство управления вырабатывает (t63) последний тактовый импульс, и старшие восемь разрядов выдаются (t64) на выходную шину. Процесс умножения завершается (t68) (рис. 19).



Рис. 19. Выдача результата

2.2 Анализ полученной сети Петри

Проведем анализ полученной сети Петри.

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

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

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

3. Технологическая часть

3.1 Описание редактора сетей Петри

Чтобы наглядно представить процесс выполнения полученной сети Петри был использован редактор сетей Петри. Покажем его работу на примере небольшой сети Петри (рис. 20).

Рис. 20. Пример сети Петри

Запуск редактора открывает стартовое окно. В этом окне пользователь может выбрать любой из четырех пунктов меню или сразу приступить к заполнению сети Петри (рис. 21).

Рис. 21. Заполненная сеть Петри

Пункт «Файл» содержит четыре подпункта. При выборе подпункта «Создать» откроется диалоговое окно, в котором можно задать количество позиций и переходов сети Петри (рис. 22). Нажатие на кнопку «Создать» создаст заново таблицы входов и выходов и таблицу маркировок.

Рис. 22. Создание сети Петри

Подпункты «Открыть» и «Сохранить» открывают стандартные диалоговые окна открытия и сохранения файлов. Редактор сетей Петри сохраняет файлы в текстовом формате с расширением *.pnf.

Кнопка «Выход» закрывает редактор.

Подпункт «Редактирование» позволяет добавлять и удалять позиции и переходы. Добавление позиции или перехода сопровождается простым добавлением еще одного столбца или строки к таблицам. Удаление позиций или переходов открывает соответствующие диалоговые окна, в которых можно выбрать ту позицию или переход, которые необходимо удалить (рис. 23).

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

а)	б)

Рис. 23. Удаление а) позиции, б) перехода.

Рис. 24. Информация о позициях и переходах

Подпункт «Запуск переходов» открывает диалоговое окно, в котором в выпадающем списке отображены все разрешенные в данной маркировке переходы (рис. 25).

Рис. 25. Запуск переходов

Нажатие на кнопку «Запуск» изменяет маркировку сети Петри в соответствии с данными таблиц (рис. 26). Кнопка «Шаг назад» возвращает сеть к предыдущей маркировке.

Рис. 26. Новая маркировка

3.2 Структура сохраняемого файла

Редактор сетей Петри сохраняет файлы в текстовом формате с расширением *.pnf. Приведем структуру сохраняемого файла для небольшой сети Петри (рис. 27).

Рис. 27. Пример сети Петри

Структура сохраняемого файла показана на рис. 28.

Рис. 28. Структура сохраняемого файла

Данные из таблиц сохраняются в файл последовательно для каждой таблицы:

· Первая строка - количество позиций в таблице входов

· Вторая строка - количество переходов в таблице входов

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

· Четвертая строка - содержимое ячейки для второй позиции и первого перехода в таблице входов.

· Пятая строка - содержимое ячейки для третьей позиции и первого перехода в таблице входов.

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

Заключение

петри моделирование сеть сумматор

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

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

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

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

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

Размещено на Allbest.ru