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

 

Союз Советскик

Социалистнческнк республик

on NCAHNK

ИЗОБРЕТЕН Ия

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (il) 920734 (63 ) Дополнительное к авт. свид-ву (22) Заявлено 20. 05.80 (2! ) 2954332/18-24 с нрисоединением заявки М (23) Приоритет

Опубликовано 15.04.82. Бюллетень № 14

Дата опубликования описания 17.04.82

t (5()М. Кл.

G06 Р 15/20

Гасударственный квинтет

СССР па лелем изобретений н открытий (53) УДК 681.333 (088.8) (72) Авторы изобретения

С. П. Присяжнюк и В. С. Тоискин (7т) Заявитель (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕЙ

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

Известны электронные модели при определении экстремальных путей на сетях (1) .

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

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

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

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

Пель изобретения - расширение функциональных возможностей устройства.

Поставленная цель достигается тем, что в устройство для моделирования сетей, содержащее модел и ветви, соед иненные согласно топологии исследуемой сети, каждая из меделей ветви включает в себя элемент И, счетчик импульсов, формирователь импульсов, блок выравнивания структуры, триггер формирования временного интервала и индикатор, причем выход элемента И соединен " входом счетчика импульсов, выход которого соединен с входом формирователя импульсов, первый выход которого является l 5 выходом модели ветви и соединен с входом индикатора, выход которого соединен с первым входом блока выравнивания структуры, являющимся входом модели ветви, выход блока выравнивания структуры соединен с входом триггера формирования временного интервала, выход которого соединен с первым входом элемента И, второй вход которого соединен с вторым входом блока выравнивания структуры и является тактовым входом модели ветви, выход счетчика импульсов соединен с нулевым входом триггера формирования:.ременного интервала, а второй выход формирователя импульсов З0 соединен с третьим входом блокЯ выравнивания структуры, в каждую модель ветви дополнительно введен блок коммутации, вход и выход которого соединены соответственно с выходом и входом модели ветви, а обратимые вход и выход блока коммутации соединены с соответствующими узлами устройства.

Блок коммутации содержит элементы

И, НЕ, линии задержки и триггера, при40 чем выход первого элемента HE соединен с первым входом первого элемента И, выход которого соединен с входом первого триггера, выход которого соединен, с первыми входами второго и третьего элементов И и через второй элемент

HE связан с первым входом четвертого эл е мента И, выход которого соед ине н с входом второго триггера, выход которого соединен с входом первого элемента

HE и с первыми входами пятого и шестого элеvñíòîâ И, причем второй вход третьего элемента И является входом блока и соединен с вторым входом шес того элемента И, выход которого является обратимым входом блока и соединен с вторым входом первого элемента И, связапцым через первую линию задержки

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

На фиг. 1 представлена схема устройства; на фиг. 2 — схема блока коммутации; на фиг. 3 — схема блока выравнивания структуры.

Устройство содержит элемент И 1, формирователь 2 импульсов, индикатор 3, блок 4 выравнивания структуры, триггер

5 формирования временного интервала, вход 6 модели ветви, счетчик 7 импульсов, блок 8 коммутации.

Блок 8 коммутации содержит элементы И 9-14, элементы НЕ 15 и ) 6, триггеры 17 и 18, линии 19 и 20 задержки, выход блока 8, подключен ко входу 6 модели ветви, вход блока 19, подключен к выходу модели ветви.

Блок 4 выравнивания структуры содержит триггер 21, элемент И 22, счетчик 23 импульсов, реверсивный счетчик

24 и м пульс ов.

Устройство работает следующим образом.

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

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

Если ветвь направленная, допустим, из обратимого входа к обратимому выходу, необходимо триггер 17 установить в единичное состояние, а триггер 18 в нулевое, если ветвь направленная наоборот, то триггер 18 устанавливается в единичное состояние, а триггер 17 — в нулевое.

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

Допустим, на модели сети решается задача определения кратчайшего пути и какая-то ветвь ненаправлена и первым во времени приходит сигнал на обратимый вход. Он устанавливает триггер 17 в единичное состояние. Этот сигнал проходит через элемент И 9, так как триггер 18 находится в нулевом состоянии, второй вход которого подан единичный потенциал с выхода триггера 18, и далее— на обратимый вход. Следовательно, устройство пропускает сигнал в направлении обратимый выход — вход, т.е. ветвь стала опять направленной, но противоположного направления.

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

Формула изобретения

5 9207 34 6 на выходе элемента НЕ 15 будет присутствовать единица, и поступая на первый вход элемента И 9, она разрешит прохождение импульса пуска на вход триггера 17. С выхода линии 19 задержки, которая учитывает конечное время перехода триггера из нуле.зого состояния в единичное, сигнал пуска через элемент

И 10 поступает на вход модели ветви, .где происходит его задержка на время !О пропорциональное длине ветви.

Перед началом работы должна быть выполнена процедура по структурному выравниванию сети.

На тактовый вход модели ветви подаются тактовые импульсы. Через определенное время на выходе модели появляется сигнал, он поступает на вход блока 8 коммутации и на вход элемен- щ та И 11. На второй вход элемента И 11 подается единичный потенциал с выхода триггера 17, поэтому сигнал с выхода модели ветви поступает на обратимый выход, подключенный к другому узлу 25 модели сети. Этот же сигнал поступает и на первый вход элемента И 12, на выходе этого элемента никаких изменений не происходит, так как на его второй вход подан нулевой потенциал триггера

18. Допустим, что в какой-то последуюший момент времени поступает сигнал на выход элемента И 12 с выхода инцидентных ветвей. Он поступает на второй вход элемента И 14, но на выходе никаких

35 изменений не происходит, „18 в единичное состояние не опрокидывается, так как триггер 17 находится в единичном состоянии и на выходе элемента

HE 16 - нулевой потенциал. Таким обра40 зом устройство пропускает сигнал только в направлении обратимого входа к выходу т.е. ветвь стала направленной. Если первым по времени приходит сигнал на обратный выход, то первым переходит в . единичное состояние триггер 18, единичный потенциал поступает на второй вход элемента И 13, на первый вход которого через линию задержки поступает пусковой сигнал, который через эле50 мент И 13 коммутируется на вход модели ветви. Единичный сигнал с выхода триггера 18 через элемент HE 15 запрешает прохождение сигналов на триггер 17, поступаюших на обратный вход. С выхода

55 модели ветви выделенный пу".ковой сигнал (после соответствуюшей задержки) подается на вход блока 8 коммутации и далее на первый вход элемента И 12, на

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

2. Устройство по п. 1, о т л и ч a— ю ш е е с я тем, что блок коммутации содержит элементы И, НЕ, линии задержки и триггеры, причем выход первого элемента HL. соединен с первил входом

7 920734 8 первого элемента И, выход которого сое- задержки с вторым входом второго эладинен с входом первого триггера, выход мента И, выход третьего элемента И которого соединен с первыми входами является обратимым выходом блока и второго и третьего элементов И через соединен с вторым входом четвертого второй элемент НЕ связан с первым вхо- элемента И, выход которого через вторую дом четвертого элемента, И, выход которо- линию задержки соединен с вторым вхо»

ro соединен с входом второго триггера, дом пятого элемента Й, выход которого выход которого соединен с входом перво- соединен с выходом второго элемента И го элемента HE и с первыми входами и является выходом блока. пятого и шестого элементов И, причем 10 Источники инфор мании, второй вход третьего элемента И являет принятые во внимание при экспертизе ся входом блока и соединен с вторым 1. Авторское свидетельство СССР входом шестого элемента И, выход кото- % 470811, кл. G 06 F 15/20, 1973. рого является обратимым входом блока 2. Авторское свидетельство СССР и соединен с вторым входом первого эле- >S М 534765, кл. G 06 Г 15/20, 1975 мента И, связанным через первую.линию (прототип).

9207 34

Составитель И. Лебедев

Редактор Л. Веселовская Техред А.Бабинец Корректор М. Демчик

Закаэ 2345/57 Тираж 732 Подписное

ВНИИПИ Государственного комитета СССР по де, ам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП Патент, r. Ужгород, ул. Проектная, 4