Устройство для исследования сетей петри

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН ию а А(50 4 347 ОПИСАНИЕ ИЗОБРЕТЕН АВТОРСКОМУ СВИ ЛЬСТВУ юл. У 25 в, С.Ю.Переваров/347, 1972. видетел детель06 Р 1 СЕТ (57 тносится к вычисможет быть испольлинейных матричных эовано шен Фиг. ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ) Авторское с47687, кл, САвторское свиВ 482749, кл. С УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПЕТРИИзобретение оьной технике,уравнений и позволяет исследоватьматричное представление сетей Петрина достижимость, С этой целью в состав устройства входят три блока 1,2и 3 памяти, блок 4 регистров, группа 5 блоков 5-15-1 схем сравнения, где 1 - количество строк в исходных матрицах, регистр 6 результатов сравнения, блок 7 вычитания матриц, блок 8 умножения матриц, блок 9сумматоров, блок 10 сравнения с нулем, блок 11 синхронизации, информационный выход 12 устройства, вход 13начальной установки и вход 14 пускаустройства. В исходном состоянии вблоках 1 и 2 памяти записань 1 матри1322312 цы входа 3 и ВыходОн сети Петр) соответствеццо, а в блоке 4 - эц,3 чениеначальной маркировки, После пускапроизводится сра 33 нецие элемента 3 каждой строки матрицы входов с сс)от)3 етствуюшим элементом 55 аркировки, ириэтом результат сравнения - .Иииицддля тех строк, все элел 5 ецт 5 которыхбольше 3 пш равны соотстет зсц)нчэлементам маркировки, и И 015. - )3 противном случае - используется в качестве первого сомцожителя блока 8, цд53 ход второго сомцожит еля катар) гопоступает результат 55 и 5 тдци 5 мдтриИзобретение относится к вычис:штельной технике и может быт, исп)льзовацо для исследовдпия сетей Петри цд достижимость.Цель изобретения - расширеги 5 е клдаса решаемых задач зд счет осуществления дцдлизд сетей Петри цд дости,)имасть.Нд фиг.1 представлецд 1)угпциоцдльцдя схема устройстд; цд 1 Н 5 г.2 пример р длиздции 6 ока синхрош 5 здции устройства..строиство для исс 35 е 053 днил сее 5 Петр) со;ержит три блока 1-3 мяти, 6 лок . р. гистро, груш)у 5 ) оков 5 1) 3 1 схм срд 53 непия) г,),е 1 ко)и)чество сгрок исхо 5)ц),)х мдтрицдх, регис гр Г) ре 3 ул тато 3 .рд)3 цеци 5 63 Ох 7 )ы)5 итдци 5 мдт)иц, 650); 8 умцоже)и)я матриц, блок 9 сум;.)г 3 Оров, блок 10 сравнения с нуле. и 6:5 ок 11 сицхро)гизации, причем вход 6,ока 4 регистров почклю:5 ец к ходу первого слдгдемого блока 9 суммдторо и первому ил 1)ормдциоцному входу 5;дж;53 го блока 5-15 - 1 с схем срдш)ения группы, с первого по 1.-" в.5 хо,:). Нерого блока 1 памяти подк)цо 5 ец 5, к 53 хо 5 у вычитдемого 6.ока 7 вычитдцпя матриц и вторым входам с первого по 1-й 6 лоЗО ко 5-15-1. схем сравнен)гя группы 5, выходы признаков цеотр;5 цдте:5- ного результата которых иодклю 5 ецы к ицФормдционцому входу регис 1 ра б результатов сравнения, 53),5 хо; которога 35 подключен к входу первого сомцсжицы выходов. В блоке 9 полученное произ едецие суммируется со значениемцачдльцой маркировки и полученное новое значение маркировки записываетсяблок 4. Процесс продолжается дотех пор, пока результат сравненияие станет ранен нулю по всем строкамматрицы входов. В этом случае блок 101)ар)ирует сигнал, свидетельствующийо том, чго сеть Петри при даннойначальной маркировке достигла предела 5,)по 3)цимости, т.е. такого состояни, когда все переходы запрещены.2 ил,те 355 6 локд 8 умножения матриц и информационно)5 у входу блока 10 сравнения с улем, выход признака равенстванул 5 о которого подключен к входу останова блгка 11 синхронизации и является ицФормационным выходом 12 устройства, выход второго блока 2 памятиподключен к входу уменьшаемого блока7 вычитания матриц, выход которогоподключен к )и 1)ормациоцному входутретьего блока 3 памяти, выход которого подклочец к входу второго сомнож)ггеля блока 8 умножения матриц, выход которого подключен к входу второго слдгдемого блока 9 сумматоров,выход которого подключен к информационному входу блока 4 регистров, входц 3 чд)5 ьцо 3 установки блока 11 синхроциэдцпи подключен к входам начальнойустдиовки регистра б результатов сравцеция и третьего блока памяти и является входом 13 начальной установкиутройствд, вход пуска блока сицхро)5 здции является входом 14 пуска устрой 5 ства, с первого по седьмой выходы 1521 блока 11 сицхроциэацииподклн)чены к входам признака чтенияиерого и второго блоков 1 и 2 памят: и входу признака записи третьегоблока 3 памяти, к входу опроса блока 9 сумматоров, к входу признаказаписи блока 4 регистров, к входамопроса ка)кдого блока 5-1. ,5-1 ссхем сравнения группы и блока 7 вычитания матриц, к входу признака за.писи регистра б результатов сравне 3 1322 ния, к входу опроса блока 4 умножения матриц и входу призцака чтения третьего блока 3 памяти соответственно.Блок 11 синхронизации (фиг.2) со 5 держит триггер 22, элементы И 23-25, генератор 26 тактовых импульсов, счетчики 27 и 28, регистры 29 и 30, элементы НЕ 31 и 32, элементы 33-37 задержки и элемент ИЛИ 38. ОУстройство работает следующим образом.В исходном состоянии схемы в блоке 1 находится матрица входов Д например 5111000010010Фа в блоке 2 - матрица выходов Днапример10000210 312ющей ца первые входи всех блоков 5-1, ,5-с. Если результат сравнения больше или ранен нули по всем сравниваемым элементам строки матрицы Д , и соответствующий разряд регистра 6 записывается единица, иначе нуль.Таким образом, при сравнении первоначальной маркировки (1, О, 1, 0) со строками матрицы Д , только третья строка удовлетворяет правилу сравнения. Это означает, что срабатывание третьего перехода разрешено, В регистре 6 записано (О, О, 1).Параллельно информация иэ блока 2 поступает на вход умецьшаемого блока 7, на вход вычитаемого которого поступает информация с блока 1. Блок 7 под действием управляющих сигналов с блока 11 реализует операцию вычитания матриц по формуле:Д = Д+ - Д Значение полученной составной матрицы изменений Д записывается в блок 3. Она имеет вид:0001т.е. данная сеть Петри имеет четыреЗО позиции и три перехода. Первоначальная маркировка находится в блоке 4 и имеет вид:Требуется определить достижима ли маркировкаиз маркировкиПредполагают, что маркировка (и достижима из маркировки р , Тогла су40 ществует последовательность (возможно пустая) запусков переходов б , которая приводит изк. Это означает, что Г(б) является неотрицательным целым решением следующего матричного45 уравнения для Хр= ш+ х.д.Если р достижима из р, уравнение (1)50 имеет решение в неотрицательных целых, если уравнение (1) не имеет решения,не достижима изПод действием синхросигналов с блока 11 информация с выхода блока 1 поступает на вторые входы блоков5-15-Е схем сравнения группы, где происходит ее сравнение со значением начальной маркировки, поступа 0 - 1 - 100+2+1 в0 0 в 1 Дальше работа схемы направлена нареализацию формулы (1), Подставляяполученные значения, она имеет вид: 0 - 1 - 10 О+ 2+ 1 - 1 00 в 1 р =(1, О, 1, 0)+(О, О, ) Под действием управляющих сигналов с блока 11 информация из блока 3 поступает в блок 8, где происходит перемножение матриц, Результат умножения (О, О, - 1, +1) поступает в блок 9, где происходит сложение результата произведения со значением маркировки, в результате чего получается новая маркировка сети Петри (1, О, О, 1), которая заносится в блок 4. Процесс работы устройства повторяется.На каждом шаге работы устройства происходит проверка кода, находящегося в блоке 4, т.е. последовательности запуска переходов на нуль в блоке 10. Если информация больше нуля, процесс работы продолжается. Если последона 1322312тельность запуска перехопон равна нулю, блок 10 вырабатывает сигнал, свидетельствующий о том, что сеть Петри при данной начальной маркировке достигла предел выполнимости, т.е. 5 достигла такого состояния, когда все переходы запрещены.Таким образом, устройство для исследования сетей Петри позволяет производить анализ сетей Петри надостижимость.Блок 11 синхронизации (фиг.2) работает следующим образом.Первоначально триггер 22 нахо 15дится в нулевом состоянии. По сигналуначальной установки, который, пройдячерез элемент И 23, поступает ьавходы записи счетчиков 27 и 28, проэнодьтся запись информации с соответствующего регистра 2 Д, где хранит ся сО строк исходОй .ат 1 и 1,регстра 30, где хрантся с остобцон исходной матрицы. С нрпходомсигнала по входу 1 "Пус;" триггер 22переходит н единичное состсньче ивысокий потенциал с его пря:ого выхода разрешает прохо-ение тактовыхимпульсов с генератор 26 через элемен И 23. Импульсы;оступают на нычптающий нход счетчика 27 и прохо;яторсэ элемент И 2, от;рытый нысоким1 ОеиаЗом с выхода еей 0,неи 5счетчика 27,С ныхоца элемента И 2 ч импульсыпос гулант на первы выход 15 блока 11 35и нродл через элементы 36 и 37 эадстккк, поступают соответственно начетвертый и пятый выходя 18 и 19 блока 11,ос.е того как содержимое счетчика 27 станет равным нулю, на его выходе переполнения появится низкий потенциал, который закроет элемент И 2 Аи, пройдя через элемент НЕ 31, откроет элемент И 25. Тактовые импульсы 45начнут поступать на вычитаюший входсчетчика 28, на седьмой выход 21 блока и, пройдя через элементы 34 и 35задержки, на шестой и второй ньходы20 и 16 блока 11 соотнетстнсно.После обнуления счетчика 28 низкийпотенцал с его выхода пройдет черезэлемент НЕ 32, элемент 33 эа;сржки ипоступит на третий выхоц 17 блока 11,пройдет через элемент ИЛИ 38 и оступит на входы записи счетчиков 27 и 28и перепишет на них содержимое соответстнуощх регистров 2 Д и 30. Процесс работы блока повторяется. Работа продолжается до тех пор, пока навход 12 останова блока не поступитсигнал, который установит триггер 22в нулевое состояние, низкий потенциалс его прямого выхода запретит прохождение тактовых импульсов с генератора26 через элемент И 23,Таким образом, устройство для исследования сетей Петри позволяет выяснить возможность функционированиямодели, представленной в виде сетиПетри, т,е. произвести анализ на дос.тижимость,Формула изобретения/Устройство для исследования сетей Петри, содержащее два блока памяти, группу блоков схем сравнения, регистр результатов сравнения и блок сумматоров, о т л и ч а о щ е е с я тем, что, с целью расширения класса решаемых задач за счет осуществления анализа сетей Петри на достижимость, н него введены третий блок памяти, блок регистров, блок вычитания матриц, б:ок умножения матриц, блок сравнения с нулем и блок синхронизации, причем выход блока регистров подключен к входу первого слагаемого блока сумматоров и первым информациоим входам блоков схем сравнения группы, с первого по с-й выходы первого блока памяти, где Е - количество строк н исходных матрицах, подклюены .к входу вычитаемого блока вычитания матриц и вторым информационным входам с первого по 1-й блоков схем сравнения группы, выходы признаков неотрицательного результата которых подключены к информационному входу регистра результатов сравнения, выход которого подключен к входу первого сомножителя блока умножения матриц и информационному входу блока сравнения с нулем, выход признака равенства нулю которого подключен к входу останова блока синхронизации и является информационным выходом устройства, выход второго блока памяти подк;почен к входу уменьшаемого блокавычитания матриц, выход которого подключен к информационному входу третьего блока памяти, выход которого подключен к входу второго сомножителя блока умножения матриц, выход которого подключен к входу второго слагаемого блока сумматоров, выход ко1322312 вого и второго блоков памяти и входупризнака записи третьего блока памяти, к входу опроса блока сумматоров,к входу признака записи блока регистров, к входам опроса блоков схем сравнения группы и блока вычитания матриц, к входу признака записи регистра результатов сравнения, к входуопроса блока умножения матриц и квходу признака чтения третьего блока памяти соответственно. 1 б 2 Ф г.2 оставитель А.Мишиехред Л.Олийнык Корректор Г.Решетник Рогул акт каз 286 Тираж 672 сударственного ам изобретений ква, Ж, Раушодписно комитета Си открытиская наб./5 д, ул. Проектная,4 зводственно-полиграфическое предпр П г торого подключен к информационномувходу регистров, вход начальной установки блока синхронизации подключенк входам начаЛьной установки регистра результатов сравнения и третьегоблока памяти и является входом начальной установки устройства, вход пускаблока синхронизации является входомпуска устройства, с первого по седьмой выходы блока синхронизации под в 10ключены к входам признака чтения пер