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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК А 1 6 Р 15/ фЕ ОПИСАНИЕ ИЗОБРЕТ РСКОМУ СВИДЕТ ТВ ПРЕДЕПЕНИЯ ПАРАГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ(56) Авторское свидетельство СССР У 717777, кл. С 06 Р 15/20, 1977.Голованов О.Н. и др, Некоторые вопросы построения гибридных вычислителей. - В кн. Неоднородные вычислительные системы. Киев: Наукова дум ка, 1975, с,11380132549(57) Изобретение относится к вычислительной технике и может быть использовано для нахождения параметровграфов. Цель изобретения - расширение функциональных возможностей устройства за счет нахождения кратчайших путей из начальной в конечнуювершину графа. Поставленная цель достигаетсятем, что устройство содержит формирователь импульсов, с первого по третий регистры, с первогопо третий ключи, первый элемент ИЛИ,со второго по шестой элементы ИЛИ,счетчик, схему сравнения, первый регистр, с первого по девятнадцатыйэлементы задержки, с первого по пятый блоки моделирования вершин.1 ил.1325498 2Изобретение относится к вычисли-вход триггера 13 и устанавливает еготельной технике и мажет быть исполь- в единичное состояние. Аналогичнозовано для нахождения параметров се- перебрасывается в такое же состояниетевых структур, описываемых графами,триггер 13 модели Ог, Сигналы с вы 5Цель изобретения - расширение ходов триггеров 13 поступают на вхофункциональных возможностей устрой- ды записи регистров 14 (которые осства эа счет нахождения кратчайших . таются в нулевом состоянии) и на вхопутей из начальной в конечную верши" ды элементов эадержки 9 , 95, ану графа. 10 также 9 гь 9 г 9 г моделей ветвей,На чертеже представлена функцио- исходящих иэ узлов Б и Г соответстнальная схема устройства. вени о.Устройство содержит Формирователь Первым, согласно условиям примера,1 импульсов, с первого по третий ре- в узел В приходит импульс иэ узла Б.гистры 2 2 А 2 г с первого по тре Пройдя через элемент ИЛИ 12, он устий ключй 33 Зр первый элемент танавливает в единичное состояниеИЛИ 4, с второго по шестой элементы триггер 13, единичный сигнал с выИЛИ 5 5 8, 5 5 5 г счетчик 6, хода которого поступает на вход эаписхему .7 сравнения, первый регистр 8, си регистра 14, В это время на Б-мс первого по девятнадцатый элементы 20 разрядном входе регистра 14 (т.е,вхозадержки 96 9 96 9 И 985 де, соответствующем узлу Б) еще при 96 9 А 9 9 ц, 9 95 9сутствует сигнал, поступающий в узел9 Ае 9 А К 9 дВ 94 г 9 гк 9 гд 9 гб с В из узла Б через элемент 9 запервого по пятый блоки 10 . 10 10 держки, поскольку в устройстве эти1 О 1 Ог моделирования вершин вхо 25 элементы выдаютимпульсы достаточнойя вершин, вход11 наименьшего числа ветвей,продолжительности,задержанные на эаисходящих иэ начального узла данное времяотносительно переднегои входящих в конечный узел при этом ФРонта перепада напряжения поступаюкаждый блок моделирования вершин со- щего с выхода триггера 13. Поэтомудержит первый элемент ИЛИ 12, триг регистр 14 модели 1 Озапоминает 1гер 13, регистр 14, ключи 15, второй в Б-м разряде, что указывает по ка. элемент ИЛИ 16. кой ветви (в данном случае - по ветВ исходном статическом состоянии ви 9) пришел в узел В первый имрегистра 2, счетчик 6 и триггеры 3 пульс, Единичный потенциал с Б-го. обнулены, в регистр 8 занесено число разрядного выхода регистра 14 постуМ, равное наименьшему иэ чисел Н и О, пает на управляющий вход ключа 15где Н - число исходящих иэ начально- и открывает его.го узла ветвей, а О - число входящих Затем в узел В поступает импульсв конечный узел ветвей, С помощью из угла Г через элемент 9задержэлементов 9 задержки формируются ве ки однако он проходит лишь черезличины задержки, пропорциональные ве- элемент ИЛИ 12, не оказывая влияниясам ветвей. Ключи 3 открыты единич- на триггер 13, находящийся в единич. ным, а. ключи 15 закрыты нулевым по- ном состоянии, и не эаписываясь в ретенциалами на их управляющих входах. гистр ввиду непоступления импульсаРаботу устройства рассмотрим на 45 на его вход записи.примере графа с узлами А (начальный) В узел Е первым приходит импульсК (конечный), Б,В,Г,Д,Е (промежуточ- из узла В, а в узел Л - импульс иэные) и величинами задержки 1,32,4, Узла Г; поэтому в модели 1 Оединич 3,1,3,2,4,2,3,4 секунд в ветвях соот" ный сигнал записывается в В-й разрядветственно (А,Б),(А,Г),(Б,В),(БЕ), 50 Регистра 14 а в модели 1 О - в Г-йсА-в -й(В,Г), (В,Е), (В,Д), (Д,Г), (ДЕ) разряд регистра 14, при этом откры(ЕК) (ДК) (Г,К), ваются соответствующие ключи 15.После подачи пускового сигнала на Через 6 с импульс формирователяпусковой вход устройства формирова, пройдя через элементы .задержкитель 1 выдает импульс, распространяю 95 95, 9 5 9и модели 1 Ощийся по моделям 9 и 10 ветвей и уз и 10 с выхода элемента 9за- залов, Пройдя через элемент 9 за- держки поступает, во-первых,.черездержки, импульс поступает в узел Б, элемент ИЛИ 4 на вход счетчика 6,ко"де проходит через элемент ИЛИ 12 на торый увеличивает свое содержимое5498регистра 8, поэтому на инверсном выходе схемы 7 сравнения появляетсянулевой потенциал, поступающий на управляющие входы ключей 3, которыезакрываются. Тем самым содержимое регистра 2 не изменяется. 3132 на 1, во-вторых, через элемент ИЛИ 5 на вход Е-го разряда регистра 2 в-третьих, через открытый ключ 3- на вход записи регистра 2 , который записывает 1 в Е-й разряд. Кроме того, с выхода ключа 3 импульс через элемент ИЛИ 16 моделй 10 поступает на информационные входы ключей 15, из которых, как указывалось, открыт лишь ключ 15 о., С его выхода импульс проходит, во-первых, через элемент ИЛИ 5 на вход Д-го разряда регист 6ра 2, где и записывается 1 ввиду поступления импульса на вход записи этого регистра с выхода ключа 3 (имЕ пульс на входе записи присутствует во время подачи единичных сигналов на все соответствующие разрядные входы регистра 2).Далее импульс с выхода ключа 15 модели 10 проходит в узел В на вход элемента ИЛИ 16, с выхода которого импульс поступает на информационные входы ключей 15, из которых, как указывалось, открыт лишь ключ 155. С его выхода импульс проходит, во-первых, через элемент ИЛИ 55 на входы Б-х разрядов всех регистров 2, но 1 записывается лишь в Б-й разряд регистра 2, так как только на его входе записи присутствует импульс. Во-вторых, импульс с выхода ключа 156 модели 10 поступает на вход элемента ИЛИ 16 модели 10, но это значения не имеет, так как все ключи 15 в модели 105 закрыты.Таким образом, через 6 с в регистре 2 Е единицы записываются в Б-й, В-й, Е-й разряды, указывая, что первый кратчайший путь из узла А в узел К проходит через эти узлы. Ветви, через которые проходит этот путь, .указывают 1, записанные в разрядах регистров 14 моделей 105, 1 О , 10. Величина этого пути при необходимости ,определяется известным образом путем замера временного интервала между моментами появления импульса на выходе формирователя 1 и, элемента задержки 9 ек Аналогично через 7 с в Г-й разряд регистра 2 г записывается 1, указывающая, что второй кратчайший путь проходит через узел Г. При этом при поступлении второго импульса на вход счетчика 6 его содержимое (код числа 2) становится равным содержимому 15 20 25 30 35 40 45 50 55 Формула изобретения устройство для определения параметров графов, содержащее блоки моделирования вершин графа по числу промежуточных узлов графа, девятнадцать элементов задержки и блок формирования импульсов, вход запуска устройства подключен к входу запуска блока формирования импульсов, о т л и - ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет нахождения кратчайших путей из начальной в конечную вершину графа, оно содержит пять блоков моделирования вершин графа, шесть элементов ИЛИ, три ключа, четыре регистра, счетчик и схему сравнения, выход блока формирования импульсов подключен к входам первого и второго элементов задержки, выходы которых подключены соответственно к первым входам первого и второго блоков моделирования вершин, вход наименьшего числа ветвей, исходящих из начальной вершины графа и входящих в конечную вершину графа устройства, подключен к информационному входу первого регистра, выход которого подключен к первому входу схемы срав" нения, второй вход которой подключен к информационному выходу счетчика, инверсный выход схемы сравнения подключен к управляющим входам ключей с первого по третий и к выходу приз" нака окончания работы устройства, счетный вход счетчика подключен к выходу первого элемента ИЛИ, первый выход первого блока моделирования вершин подключен к входам третьего и четвертого элементов задержки, второй выход первого блока моделиро. вания вершин подключен к первому входу второго блока моделирования вершин и к первому входу второго элемента ИЛИ, третий выход первого блока моделирования вершин подключен к первому входу третьего блока моделирования вершин и к первому входу третьего элемента ИЛИ, первый выход третьего блока моделированиявершин подключен к входам элементовзадержки с пятого по восьмой и квторому входу третьего элемента ИЛИ,второй выход третьего блока моделирования вершин подключен к второмувходу первого блока моделированиявершин и к первому входу четвертогоэлемента ИЛИ, третий выход третьегоблока моделирования вершин подключенк второму входу второго блока моделирования вершин и к второму входувторого элемента ИЛИ, четвертый выход третьего блока моделированиявершин подключен к первому входу четвертого блока моделирования вершини к первому входу пятого элементаИЛИ, пятый выход третьего блока моделирования вершин подключен к второму входу пятого блока моделирования вершин и к первому входу шестого элемента ИЛИ, первый выход второго блока моделирования вершин подключен к второму входу третьего блока моделирования вершин и к третьему входу третьего элемента ИЛИ, второй выход второго блока моделирования вершин подключен к третьему входу первого блока моделирования вершин и к второму входу четвертого элемента ИЛИ, третий выхоц второго блока моделирования вершин подключен квторому входу четвертого блока моделирования вершин и к второму входупятого элемента ИЛИ, четвертый выход второго блока модепирования вершин подключен к входам элементов задержки с девятого по двенадцатый,первый выход четвертого блока моделирования вершин подключен к третьемувходу третьего блока моделированиявершин и к четвертому входу третьегоэлемента ИЛИ, второй выход четвертого блока моделирования вершин подключен к третьему входу второго блока моделирования вершин и к третьемувходу второго элемента ИЛИ, третийвыход четвертого блока моделированиявершин подключен к третьему входупятого блока моделирования вершин ик второму входу шестого элемента ИЛИ,четвертый выход четвертого блока моделирования вершин подключен к .вхоцам элементов задержки с тринадцатого по шестнадцатый, первый выход пятого блока моделирования вершин подключен к третьему входу четвертогоблока моделирования вершин и ктретьему входу пятого элемента ИЛИ,5 15 Я 25 ЗО 35 40 45 5 О 55 второй выход пятого блока моделирования вершин подключен к четвертомувходу третьего блока моделированияи к пятому входу третьего элементаИЛИ, третий выход пятого блока моделирования вершин подключен к входамэлементов задержки с семнадцатого подевятнадцатый, выходы элементов задержки с третьего по десятый подключены соответственно к четвертому входу второго блока моделирования вершин, к пятому входу третьего блокамоделирования вершин, к четвертомувходу первого блока моделированиявершин, к четвертому входу пятогоблока моделирования вершин, к четвертому входу четвертого блока моделирования вершин, к пятому входу второго блока моделирования вершин, кпятому входу четвертого блока моделирования вершин и к шестому входутретьего блока моделирования вершин,выход одиннадцатого элемента задержки подключен к четвертому входу второго элемента ИЛИ, и первому входупервого элемента ИЛИ и к информационному входу первого ключа, выходыдвенадцатого и тринадцатого элементов задержки подключены соответственно к пятому входу первого блока моделирования вершин и к шестому входувторого блока моделирования вершин,выход четырнадцатого элемента задержки подключен к второму входу первого элемента ИЛИ, к четвертому входупятого элемента ИЛИ и к информационному входу второго ключа, выходы пятнадцатого и шестнадцатого элементов задержки подключены соответственно к седьмому входу третьегоблока моделирования вершин и к пятому входу пятого блока моделированиявершин, выход семнадцатого элементазадержки подключен к третьему входушестого элемента ИЛИ, к третьемувходу первого элемента ИЛИ и к информационному входу третьего ключа,выходы восемнадцатого и девятнадцатого элементов задержки подключенысоответственно к шестому входу четвертого блока моделирования вершини к восьмому входу третьего блокамоделирования вершин, выход второгоэлемента ИЛИ подключен к первым информационным входам регистров с первого по третий, выход третьего элемента ИЛИ подключен к вторым информационным входам регистров с первого7 32549 ключен к входу записи второго регистра и к седьмому входу четвертого бло го 25 моделирования вершин подключен к вто 40 45 50 55 по третий, выход четвертого элемента ИЛИ подключен к третьим информационным входам регистров с первогопо третий, выход шестого элементаИЛИ подключен к четвертым информационным входам регистров с первого потретий, выход пятого элемента ИЛИподключен к пятым информационным входам регистров с первого по третий,выход первого ключа подключен к входу записипервого регистра и к седьмому входу второго блока моделирования вершин, выход второго ключа подка моделирования вершин, выходтретьего ключа подключен к входу записи третьего регистра и к шестому входу пятого блока моделирования вершин, при этом первый и пятый блокимоделирования вершин содержат по одному триггеру, по одному первому ипо одному второму элементу ИЛИ, подва ключа и по одному регистру каждый, причем в первом блоке моделирования вершин первый, второй и третий входы подключены соответственно к первому входу первого элемента ИЛИ первого блока моделирования вершин,к первому входу второго элемента ИЛИ первого блока моделирования вершини к второму входу второго элементаИЛИ первого блока моделирования вершин, четвертый вход первого блока рому входу первого элемента ИЛИ первого блока моделирования вершин и к первому информационному входу регистра первого блока моделирования вершин, пятый вход первого блока моделирования вершин подключен к третьему входу первого элемента ИЛИ первого блока моделирования вершин и к второму информационному входу регистра первого блока моделирования вершин, выход триггера первого блока моделирования вершин подключен к входу записи регистра первого блока моделирования вершин и к первому выходу первого блока моделирования вершин, выходы первого и второго ключейпервого блока моделирования вершинподключены соответственно к второмуи третьему выходам первого блока моделирования вершин, выход первогоэлемента ИЛИ первого блока моделирования вершин подключен к счетному входу триггера первого блока модели 8 8рования вершин, первый и второй выходы регистра первого блока моделирования вершин подключены к информационным входам соответствЕнно первого и второго ключей первого блока моделирования вершин, выход второго элемента ИЛИ первого блока моделирования вершин подключен к управляющим входам первого и второго ключей первого блока моделирования вершин,причем в пятом блоке моделирования вершин первый, второй и третий входы подключены соответственно к первому входу первого элемента ИЛИ пятого блока моделирования вершин, к первому входу второго элемента ИЛИ пятого блока моделирования вершин и к второму входу второго элемента ИЛИ пятого блока моделирования вершин,четвертый вход пятого блока моделирования вершин подключен к второму входу первого элемента ИЛИ пятого блока моделирования вершин и к первому информационному входу регистра пятого блока моделирования вершин, пятый вход пятого блока моделирования вершин подключен к третьему входу первого элемента ИЛИ пятого блока моделирования вершин и к второму информаЗ 0 ционному входу регистра пятого блокамоделирования вершин, шестой вход пятого блока моделирования вершин подключен к третьему входу второго элемента ИЛИ пятого блока моделирования вершин, первый и второй выходы пятого блока моделирования вершин подключены соответственно к выходам.первого и второго ключей пятого блока моделирования вершин, выход триггера пятого блока моделирования вершин подключен к входу записи регистра пятого блока моделирования вершин и к третьему выходу пятого блока моделирования вершин, выход первого элемента ИЛИ пятого блока моделирования вершин подключен к счетному входу триггера пятого блока моделирования вершин, первый и второй выходы регистра пятого блока моделирования вершин подключены к информа ционным входам соответственно первого и второго ключей пятого блока моделирования вершин, выход второго элемента ИЛИ пятого блока моделирования вершин подключен к управляющим входам первого и второго ключей пятого блока моделирования вершин, при этом второй и четвертый блоки модели"рования вершин содержат по два эле"мента ИЛИ, по триггеру, по региструи по три ключа каждый, причем во втором блоке моделирования вершин первьгй, второй и третий входы подключены соответственно к первому, второму,и третьему входам второго элементаИЛИ второго блока. моделирования вершин, четвертый вход второго блока,моделирования вершин подключен кпервому входу первого элемента ИЛИ второго блока моделирования вершин и к первому информационному входу регистра второго блока моделирования вершин, пятый входвторого блока моделирования вершинподключен к второму информационномувходу регистра второго блока моделирования вершин и к второму входу первого элемента ИЛИ второго блока моделирования вершин, шестой вход второго блока моделирования вершин подключен к третьему информационному входурегистра второго блока моделированиявершин и к третьему входу первогоэлемента. ИЛИ второго блока моделирования вершин, седьмой и восьмой входы второго блока моделирования верпан подключены соответственно к четвертому входу второго элемента ИЛИвторого блока моделирования вершини к входу записи регистра второгоблока моделирования вершин, с первого по третий выходы второго блока моделирования вершин подключены соответственно к выходам соответственнос первого по третий ключей второгоблока моделирования вершин, выходтриггера второго блока моделированиявершин подключен к четвертому выходувторого блока моделирования вершин,выход первого элемента ИЛИ второгоблока моделирования вершин подключен к счетному входу триггера второго блока моделирования вершин с перваго по третий выходы регистра второго блока моделирования вершин подключены соответственно к информационнымвходам ключей с первого по третийвторого блока моделирования вершин,выход второго элемента ИЛИ второгоблока моделирования вершин подключенк управляющим входам ключей с первого по третий второго блока моделирования вершин, причем в четвертом блоке моделирования вершин с первого потретий входы подключены соответственно к входам с первого по третий вто моделирования вершин и к второму информационному входу регистра четвер того блока моделирования вершин, шес.той вход четвертого блока моделирования вершин подключен к третьему вхо 25 30 40 50 510 рого элемента ИЛИ четвертого блокамоделирования вершин, четвертый входчетвертого блока моделирования вершин подключен к первому входу первогоэлемента ИЛИ четвертого блока моделирования вершин и к первому информационному входу регистра четвертогоблока моделирования вершин, пятыйвход четвертого блока моделированиявершин подключен к второму входу первого элемента ИЛИ четвертого блока ду первого элемента четвертого блока моделирования вершин и к третьемуинформационному входу регистра четвертого блока моделирования вершин,седьмой вход четвертого блока моделирования вершин подключен к четвертому входу второго элемента ИЛИ четвертого блока моделирования вершин,восьмой вход четвертого блока моделирования вершин подключен к входу записейрегистра четвертого блока моделирования вершин, выходы с первого по четвертый четвертого блока моделирования вершин подключены соответственнок выходам первого, второго, третьегоключей четвертого блока моделирования вершин и к выходу триггера четвертого блока моделирования вершин,первый, второй и третий выходы регистра четвертого блока моделированиявершин подключены к информационнымвходам соответственно первого, второго и третьего ключей четвертогоблока моделирования вершин, выходывторого элемента ИЛИ четвертого блока моделирования вершин подключен куправляющим входам первого, второго и третьего ключей четвертого блокамоделирования вершин, выход первого элемента ИЛИ четвертого блока моделирования вершин подключен к счетному входу триггера четвертого блока моделирования вершин, при этом третийблок моделирования вершин содержитдва элемента ИЛИ, четыре ключа, регистр и триггер, входы с первого почетвертый третьего блока моделирования вершин подключены соответственно по входам с первого по четвертый второго элемента ИЛИ третьего блока моделирования вершин, пятый вход третьего блока моделирования вершин, Москва, Ж, Рауш ПодписноеСССРй ИИПп30 итет крыт ая н аб д.4 Производственно-полиграфическое предприятие, г.ужгород, ул.Проектная,11 .132549 подключен к первому входу первого элемента ИЛИ третьего блока моделирования вершин и к первому информационному входу регистра третьего5 блока моделирования вершин, шестой вход третьего блока моделирования вершин подключен к второму входу первого элемента ИЛИ третьего блока моделирования вершин и к второму информационному входу регистра третьего блока моделирования вершин, седьмой вход третьего блока моделирования вершин подключен к третьему входу первого элемента ИЛИ третьего блока моделирования вершин и к третьему информационному входу регистра третьего блока моделирования вершин, восьмой вход третьего блока моделирования вершин подключен к четвертому входу первого элемента ИЛИ третьего блока моделирования вершин и к четвертому информационному входу регистра третьего блока моделирования вершин, выход триггера 25812третьего блока моделирования вершин подключен к первому выходу третьего блока моделирования вершин и к входу записи регистра третьего блока моделирования вершин, выходы с второго по пятый третьего блока моделирования вершин подключены соответственно к выходам ключей с первого по четвертый третьего блока моделирования вершин, выход первого элемента ИЛИ третьего блока моделирования вершин подключен к счетному входу триггера третьего блока моделирования вершин, выходы с первого по четвертый регистра третьего блока моделирования вершин подключены к информационным входам ключей соответственно с первого по четвертый третьего блока моделирования вершин, выход второго элементЫ ИЛИ третьего блока моделирования вершин подключен к управляющим входам ключей с первого по четвертый третьего блока моделирования вершин.