Устройство для моделирования сетей Советский патент 1985 года по МПК G06F15/173 

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

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

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕЙ, содержащее модели ветвей, соединенные согласно топологии сети, генератор импульсов, первый многовходозой элемент ИЛИ и блок управления, причемкаждая модель ветви содержит элементы И, триггеры, элемент индикации, формирователь временного интервала и три элемента ИЛИ, блок управления содержит первый, второй - третий ичетвертый триггеры, элементы И, элемент НЕ, первый элемент ШШ, счетчик импульсов, причем в.-каждой модели ветви выход первого элемента И подключен к нулевому входу первого триггера, первые входы первого и второго элементов И являются соот- . ветственно первым и вторым входами модели ветви и подключены соответственно к первому и второму выходам блока управления, выход первого элемента ИЛИ блока управления подключен к первому зходу первого элемента И модели ветви, выход второго элемента И блока управления соединен с нулевым входом первого триггера блока управления, нулевой выход которого подключен к первому входу третьего элемента И блока управления, единичный выход первого триггера блока управления соединен с первым входом четвертого элемента И блока управления, выход которого является первым выходом блока управления, единичный выход третьего триггера блока управления соединен с первым входом пятого элемента И блока уп- равления, единичный выход второго триггера подключен к первому входу второго элемента И блока управления выход шестого элемента И блока управления соединен с единичным входом второго триггера блока управления, (Л выход первого многовходового элемента ИЛИ подключен к первому входу седьмого элемента И и к входу элемента -НЕ блока управления, вход элемента НЕ. является первым входом блока управления, выход генератора импульсов соединен с вторым входой ч блока управления,, третьим выходом ю блока управления является выход вого элемента ИПИ, выход четвертого элемента И блока управления подключен к входу счетчика импульсов, выход которого соединен с первым входом первого элемента ИЛИ блока управления, второй вход которого подключен к выходу третьего элемента И бло- кд уцравления, выход пятого элемента И блока управления соединен с вторыми входами второго, третьего и четвертого элементов И блока управления, выход второго элемента И блока упр;авления подключен к первому входу шестого элемента И и едининичному входу четвертого триггера бло

1

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

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

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

Модель 1 ветви (фиг.1) содержит третий, четвертый, первый, рторой. триггеры 2- 5, формирователь 6 временного интервала, выполненный в виде счетчика импульсов, элемент 7 индикации, пятый, восьмой, четвертый, девятый, шестой, седьмой, третий, десятый, одиннадцатый, первый, второй и двенадцатый.элементы И 8 - 19, второй, первый и третий элементы ИЛИ 20 - 22. Блок 23 управления (фиг.2) содержит шестой, третий, первый, второй, четвертый, пятый триггеры 24 - 29, счетчик 30 импульсов, восьмой, девятый, седьмой, пятый, первый, четвертый, шестой, третий, второй, элементы И 31 - 39, второй и первый элементы ИЛИ 40 и 41, элемент НЕ 42. Кроме того, устройство содер сит генератор 43 импульсов, пер&ый и второй многовходовые элементу ИЛИ 44 и 45, второй и третий выходы 46 - 47 модели ветви, третий выход 48 блока 23 управления, восьмо выход 49, второй вход 50, второй выход 51 блока 23 управления, второй вход 52 модели 1 ветви, первый выход 53 модели ветви, входы 54,54 элемента ИЛИ 44 первый вход 55 блока 22 управления, первый выход

56блока 23 управления, первый вход

57мидели 1 ветви, четвертый выход

58Модели ветви, входы 59 - 59 а элемента ИЛИ 45, третий вход 60 блока 23 управления, пятый и, четвертый выходы 61 и 62 блока 23 управления, третий вход 63 модели 1, шестой вход 64 модели 1 ветви, пятый вход 65 модели.1 ветви, седьмой и шестой выходы 66 и 67 блока 23 управления, четвертый вход 68 модели 1 ветви. При описании работы устройства входы и выходы блока 23 управления и модели 1 ветви названы полюсами, Перед решением задачи определения пути с наименьшей пропускной способностью соединяют модели 1 ветвей между собой посредством полюсов 46 и 47 в соотвествии с конфигурацией моделируемой сети, подключают полюса 48 и 49 блока 23 управления к полюсам 46 или 47 тех моделей ветвей 1, между которыми отыскивается указанный путь, и заносят (N - qjj ) число импульсов в счетчики импульсов 6 всех моделей ветвей 1, где. N емкссть счетчиков импульсов 6 всех моделей ветвей 1 и счетчика 30 импул сов блока управления. Суть решения задачи определения пути с наименьшей пропускной способностью заключается в нахождении (} li - X ) разреза и множества разре зов К, вьщелении ветви разреза (х|, xj) с mtn q.;- , в исключении ветвей, у которых пропускная способность меньше или равна пропускной способности Выбранной ветви. В дальнейшем полюса 46 и 47 этих моделей ветвей 1 закорачиваются между собой, что исключает их из дальнейшего рассмотрения. Эти операции повторяются до тех пор, пока полюса, между которыми отыскивается путь, .не будут закорочены (т.е. не совпадут). После этого производится формирование самого пути и его индикация. .Тип решаемой задачи определяется состоянием триггера 24 блока 23 упра ления. При нулевом состоянии этого триггера устройство решает задачу оп ределения пути с наибольш.ей пропускн способностью. Работа устройства при шении задачи определения пути с наибольшей пропускной способностью соот ветствует работе устройства - прототипа. При единичном состоянии.тригге ра 24 решается задача определения пути с наименьшей пропускной способностью. Перед началом работы устройства триггеры 2-5 всех моделей ветвей 1 и триггеры 25 - 29 и счетчик 30 импульсов блока 23 управления устанавливаются в нулевое состояние. Триггер 24 блока 23 управления устанавливается в единичное состояние. Установочные шины на фиг. 1 и 2 не показаны. Работа устройства начинается с установки триггера 25 в единичное состояние. Единичное состояние триггера 25 выдает разрешение на вход элемента И 34, При этом импульсы генератора 43 импульсов, поступающие на полюс 50 блока 23 управления, проходят через элемент И 34 на входы элементов И 36, 38 и 39. Через элементы И 36 и 39 импульсы не проходят, так как они заблокированы нулевыми состо- яними триггеров 26 и 28, а через элемент И 38 импульсы проходят. Далее эти импульсы через элемент ИЛИ 41 поступают на полюс 48 блока 23 управления и одновременно с этим устанавливают триггер 29 в единичное состояние. Единичное состояние триггера 29 дает разрешение на вход элемента И 32. Через элементы И 32 и ИЛИ 40 разрешение поступает на полюс 51 блока 23 управления и, соответственно, на полюса 52 всех моделей ветвей 1.. Импульсы с полюса 48 блока 23 управления поступают на полюса 46 или 47 моделей ветвей.1, которые в результате коммутации этих полюсов между собой образуют вершину сети, из которой отыскивается путь с наименьшей пропускной способностью. В указанных моделях ветвей 1импульсы с полюса 46 поступают на вход элементов И 9, 11-13. Через элементы И 9, 11 и 13 импульсы не пройдут, так как на других входах нет разрешения. На всех входах элемента И 12 разрешение есть, поэтому с выхода этого элемента импульс проходит через элемент ИЖ 22 и устанавливает триггер 2 в единичное состояние. Аналогично, если импульсы поступят на полюс 47 модели 1 ветви они проходят только через элементы И 14 и ИЛИ 21 и устанвливают триггер 3 в единичное состояние. Единичное состояние триггеров 2 или 3 вьщает разрешение на вход элемента И 16 через элемент ИЛИ 20, Это разрешение поступает на полюс 53 модели ветви 1. Это возможно потому, что на другом входе элемента И 16 есть разрешение, снимаемое с нулевого выхода триггера 4.

С полюса 53 модели 1 ветви разрешение поступает на соответствующий вход 54( - 54 многовходового элемента ИЛИ 44. Причем на входы 54)54 многовходового элемента ИЛИ 44 поступают разрешения только от тех моделей ветвей 1, триггеры 2 или 3 которых находятся в единичном состо НИИ, Единичное состояние триггеров 2 или 3 свидетельствует о том, что данная модель ветви 1 принадлежит разрезу (х - xj) из множества разрезов k . Это соответствует первому шагу решения задачи

Выбор модели ветви, принадлежащей сформированному разрезу, с наименьшей пропускной способностью и исключение ее из дальнейшего рассмотрения, так же как и моделей ветвей, пропускные способности которых меньше или равны пропускной способности выбранной ветви, происходит по разрешению многовходового элмента ИЛИ 44. Это разрешение поступ на полюс 55 блока 23 управления. С полюса 55 через элемент И 33 разрешение поступит на единичный вход триггера 26 и установит его в единичное состояние.

Единичное состояние триггера 26 запрещает прохождение импульсов через элемент И 38 и ИЛИ 41 на полюс 48 блока управления 23 разрешает прохождение импульсов через элемент И 36 на вход счетчика 30 импульсов и на полюс 56 блока 23 управления. С полюса 56 блока 23 управления импульсы поступают на полюс 57 всех моделей 1 ветвей.

В моделях 1 ветвей импульсы с полюса 57 поступают на вход счетчика 6 импульсов до его переполнения. Импульс переполнения счетчика 6 модели ветви устанавливает триггер. 4 в единичное состояние, поступает на нулевые входы триггеров 2 и 3 и через элемент И 19 - на полюс 58 тех 1 ветвей, которые принадлежат выбранному разрезу.

Единичное состояние триггера 4 модели 1 ветви через элемент И 18 устанавливает в единичное состояние триггер 5.. В этом случае триггер 4 остается в единичном состоянии, так как единичное состояние триггер

5 запрещает прохождение очередного импульса с полюса 57 через элемент И 17 на нулевой вход триггера 4.

Импульс, поступивший на нулевой вход триггера 2 или 3 с выхода счетчика импульсов 6, устанавливает его в нулевое состояние.

С полюса 58 модели 1 ветви импуль поступает на полюс 59 и, пройдя многовходовой элемент ИЛИ 45 и полюс 60 блока 23 управления, nocTjrnaет-на нулевой вход триггера 29. Первый импульс, появившийся на полюсе 58 модели ветви, производит выбор модели ветви, у которой наименьшая пропускная способность среди всех выделенных ветвей. Это происходит в результате того, что нулевое состояние триггера 29 снимает разрешение через элемент И 32 с полюса 51 блока 23 управления и, соответственно, с полюса 52 йсех моделей 1 ветвей.

Единичное состояние триггера 5 вьщает разрешение на входы элементов И 8 и 9, что исключает модели ветвей из дальнейшего рассмотрения и закорачивает полюса 46 и 47 модели 1 ветви. Таким образом, в моделях 1 ветвей, у которых пропускная способность меньше или равна пропускной способности выбранной модели триггеры 4 и 5 установлены в единичное состояние и их полюса 46 и 47 .закорочены.

После снятия разрешения с полюса 51 блока 23 управления и, следовательно i с полюса 52 модели 1 ветви триггер 4 устанавливается в ну.левое состояние очередным им- пульсом поступившим на полюс 57 тех моделей 1 ветвей, триггер 5 которых находится в нулевом состоянии. Конец этого шага работы устройства определяется появлением импульса переполнения счетчика 30 блока 23 управления. К этому моменту в счетчиках 6 всех моделей -1 ветвей восстанавливается информация о их пропускной способности, т.е. происходит регенерация. Роль регенерационного счетчика для счетчиков.6 импульсов всех моделей ветвей 1 выполняет счетчик 30 импульсов блока 23 управления. Он начинает счет с О и емкость его равна N . Счетчики 6 импульсов всех моделей ветвей 1 начинают счет с (N - ) .

Импульс переполнения счетчика 30 импульсов блока 23 управления поступа ет через элемент ИЛИ 41 на полюс 48 блока 23 управления 23 и затем на полюса 46 и 47 моделей 1 ветвей и весь процесс работы повторяется аналогично описанному вьше.

Такие процессы будут повторяться до тех пор, пока импульс переполнени счетчика 30 импульсов блока 23 упраления, поступающий на полюс 48, не появится на полюсе 49. Это происходит потому, что импульс с полюса 48 поступает на полюс 46 или 47 моделей 1 ветвей и, проходя соответственно элементы И 8 или 9, появлдется на полюсе 47 или, соответственно, 46 модели 1 ветви.

В момент появления импульса на полюсе 49 блока 23 управления все множество ветвей моделируемой сети будет разбито на два подмножества. .Одно подмножетство содержит ветви, пропускная способность qj: которых удовлетворяет условию (1),и в соответствуювдах им моделях 1 ветвей триггеры 4 и 5 находятся в единичном состоянии. Другое подмножество содержит ветви с пропускными cnocd6- ностями, которые не удовлетворяют условию (1), и их триггеры 4 и 5 остаются в нулевом состоянии. Эти модели ветвей из дальнейшего рассмотрения исключаются, что обеспечивается отсутствием разрешений на одном из входов элементов И 13 и 15.

В дальнейшем устройство формирует путь, с наименьшей пропускйой способностью и индицирует его. Для этого в блоке 23 управления импульс, поступивший на полюс 49, устанавлива ет триггер 26 в нулевое состояние а триггер 28 - в единичное.

Нулевое состояние триггера 26 запрещает прохождение импульсов генератора 43 импульсов с полюса 56 через элемент И 36 и, следовательно, на вход счетчика 30 импульсов. При этом на полюса 57 всех моделей ветвей импульсы не поступают.

Единичное состояние триггера 28 снимает разрешение с полюса 61 блока 23 управления и вьщает сигнал на полюс fi2. Соответственно с полюса

63 всех моделей ветвей разрешение .будет снято. Сигнал, появившийся на полюсе 62 блока 23 управления поступает на полюс 64 всех моделей 1 ветвей и устанавливает триггер 5 в нулевое состояние, чем разрывает закоротку полюсов 46 и 47. Это происходит за счет того, что с входов элементов И 8 и 9 снимается разрешение. Одновременно с этим импульсы генератора 43 опять поступают через полюс 50, элемента И 34, 38 и ИЛИ 41 нА полюс 48 блока 23 управления. С полюса 48 импульсы поступают на полюса 46 или 47 моделей 1 ветвей, к полюсам которых подключен полюс 48 блока 23 управления. В указанных моделях 1 ветвей импульсы с полюса 46 поступают на вход элемента И 13 тех моделей, триггер 4 которых нахог дится в единич.ном состоянии, и проходят через него. При этом на другом входе элемента И 13 есть разрешение, поступающее с полюса 65 модели ветви через полюс 66 блока 23 управления, которое снимается с нулевого выхода триггера 27 блока 23 управления .

В модели 1 ветви импульсы поступают через элемент ИЛИ 22 на единичн 11й вход триггера 2. По первому импульсу из всей серии импульсов, поступивших в модель 1 ветви на полюс 46, тригге 2 устанавливается в единичное состояние. Единичное состояние триггера 2 вьщает разрешение на элемент И 11. Поэтому остальные импульсы из всей серии с полюса 46 через элемент И 11 поступают на полюс 47 модели 1 ветви Таким образом, импульсы распространяются по сети до тех пор, пока они не появятся на полюсе 49 блока 23 управления.

Поступивший на полюс 49 блока 23 управления импульс проходит через элемент И 37, так как триггер 28 находится в единичном состоянии, и устанавливает триггер 27 в единичное

состояние. Единичное состояние триггера 27 вьщает разрешение на полюс 67 и снимает разрешение с полюса 66, выдает разрешение на элементы И 35 и 39 и снимает разрешение с элемента И 38. При этом с полюсов 65 моделей 1 ветвей снимается разрешение, что заблокирует их элементы И 13, на полюсах 68 появляется разрешение

на прохождение сигналов через элемент И 16. Одновременно импульсы генератора 43 импульсов через элементы И 34 и 39 поступают на полюс 49 и j далее на полюса 47 моделей ветвей 1, к которым подключен полюсом 47 блок 23 управления.

С полюса 47 в модели 1 ветви импуль сы через элемент И 15 и ИЛИ 21 посту- о пают на единичный вход триггера 3. По первому импульсу из серии импульсов, поступивших на полюс 47, триггер 3 устанавливается в единичное состояние, которое вьщает разрешение на элемент 15 И 10. Поэтому остальные импульсы проходят через элемент И 10 и поступают на полюс 46. Это происходит только в тех моделях ветвей 1, триггер 4

которых находится в единичном состоянии. Таким образом, импульсы распространяются по сети через модели 1 ветвей с полюса 47 на полюс 46 до тех пор, пока не появятся на полюсе 48 блока 23 управления.

С полюса 48 блока 23 управления через элемент И 35 импульс поступает на нулевой вход триггера 25 и устанавливает его в нуле.чое состояние. Нулевое состояние триггера 25 сигнализирует о конце решения задачи.При этом модели 1 ветвей, у которых триггеры 2 и 3 находятся одновременно в единичном состоянии, принадлежат искомому пути. Эти модели индицируются элементом 7 индикации.

л

фуг. Г

Sttn

56 53пЧ5,

si53

23

фиг- 2