Устройство для исследования сетей Советский патент 1980 года по МПК G06G7/122 

(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СЕТЕЙ

I

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

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

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

Из известных устройств наиболее близким к изобретению по технической сущности является устройство, содержащее генератор импульсов, выход которого подключен к первому входу блока управления, первый выход которого соединен с входом распределителя, выходы которого подключены к nepBijiM входам моделей узлов, моДели ветвей, блок инцикации и дополнительные логические э;1 ементы 2}.V. .Т L , Л v

Известное устройство не обеспечивает достаточную точность анализа систем сетевой структуры. . -;-J

Целью изобр ения являетсй повышение точности устройства.

Поставленная цель достигается тем, что в устройство 1ввёд ёны элемент ИЛИ и наборное поле, первые группы входов 10 и.выходов которого соединены соответственно с первыми выходами и вторыми входами моделей узлов, вторые выходы которых подключены к входам ёлёйента ИЛИ, выход которого соединен с вторым 15 входом блока управления, третий вход которого подключён к выходу наборного поля, вторые группы входов и выходов которого соединены соотве1х:Тв нно с первыми выходами и входами моделей вет- 20 вей, вторые, третьи и четвертые входы которых подключены соЪтвётстБённо к второму, третьему и четвертому выходам блока управления, пятый выход котороГ ос.оёдйнен с одним входом блока 25 индикации, другие входы которого nojaключень к вторым выходам моделей ветвей, пятые и шестые входы которых сое- динены с группой выходов генератора импулйсов, кроме того блок управления со- держит элементы И, элемент ИЛИ, триггеры, Элемент НЕ, элементы задержки и генератор одиночного импульса, входы которого подключены соответственно к выходам первого элемента И и элемента 35 задержки, вход которого соединен с первыми входами второго и третьего (элементов И и подключен к выходу элемента НЕ, вход которого соединен с первым входом первого триггера и является 40 BTopbiM входом блока управления, первый вход которого подключен к первым входам четвертого и пятого элементов И, второй вход которого соединен с первым входом шестого элемента И и подключен 45 к первому выходу второго триггера, второй выход которого соединен с первыми Ш:бШми седьмого эдёмёнта И йэлемента ИЛй,и является вторым выходом блока управления, второй вход седьмого50 элемента И соединен с первым входом восьмого элемента И и является третьим вхоДом блока управления, второй вход восьмого элемента И подключен к первому выходу третьего триггера, первый 55 вход которого соединен с выходом седьмого элемента И, второй входтретьего триггера соединен с первыми входами второго триггера и первого элемента, И

и подключен к выходу второго элемента задержки, первый вход которого соединен с выходом четвертого элемента И, второй вход которого подключен к выходу элемента ИЛИ, второй вход которого соединен с вторыми входами первого и шестого элементов И и подключен к первому выходу первого триггера, второй выход которого соединен с третьим входом пятого элемента И четвертый вход которого соединен с третьим входом шестого элемента И, с вторым входом второго элe лeнтa И и подключен к второму вь1ходу третьего триггера, выходы BTopbrq ПЯТОГО и шестого элементов И являются соответственно пятым, первым и третьим выходами блока управления, выход генератора одиночного импульса соединен с вторым входом первого три гера, второго элемента задержки и третьего элемента И и является четвертым выходом блока управления , выходы третьего и Восьмого элементов И подключены с:оответстБенно к второму и третьему входам второго триггера.

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

Устройство содержит модели 1 ветве: генератор 2 импульсов, блок 3 управления, блок 4 индикации, модели 5 .узлов, наборное поле 6, распределитель 7 импульсов, многовходовый элемент ИЛИ 8, Каждая модель 1 ветвей содержит формирователь 9 временного интервала, триггеры 10 и 11, элементы И 12-15, инвертор 16, элементы И-НЕ 17 и 18, элемент 19 инДикации, диоды 20 - 22, полюса,23-30. моделей выходы 31 моделей узлов выходы и входь I . / .32-39 бяока управления вход 40 и выходы 41 распределителя, входы 42 и выхбды 43 моделей 5 узлов, выходы 4446 генератора импульсов, входы 47 .и 48 блока индикации.

Блок управления содержит триггеры 49-51, инвертор 52, элементы И 5360, элемент ИЛИ 61, элементы 63 и 64 задержки, генератор 65 одиночного импульса.; , Устройство работает следуюшим образом.

В исходном состоянии, перед решение задачи на устройстве, модели 1 ветвей и модели 5 узлов скоммутированы между собой на наборном поле 6 в соответстви с топологией графа, В формирователи 9 временных интервалов моделей 1 ветвей

записана в импульсной форме информация о длительностях ветвей. Триггеры всех моделей 1 ветвей сброшены в исходное нулевое состояние.

При подаче сигнала логической едийиды с выхода 32 блока 3 управления на шину решения задачи о длинейшем пути на выходах 2 9 моделей 1 ветвей и на выходах 31 моделей 5 узлов будут сигналы нулевого логического уровня. После Ю ся подачи сигнала решения задачи о длиннейшем пути, запускаются формировател 9 временного интервала моделей i вётвей, принадпежащих началу графа. Формирователи 9 временного интервала запущенных моделей 1 ветвей, отработав их длительность, со своих выходов выдают сигналы логической единицы, которые через элементы И 12 поступают на единичные входы триггеров 10. Сигналами логической единицы и единичных выходов триггеров 10 устанавливаю ся в единичное состояние триггеры 11. Перебросом триггера 11 меняется на ноль сигнал логической единицы с его нулевого выхода и входа элемента И-НЕ 18, подключенного вторым входом к шине решения задачи о длиннейшем пути. На выходе элемента И-НЕ 18 поя ляется сигнал логической единицы, который поступает на подпор диода 21. Диоды 21 моделей 1 ветвей, соединенных вместе своими выходными полюсами образуют логическую схему И. Резистором этой схемы будут параллельно соединены выходные сопротивления элементов И-НЕ 17 или резистор на входе соьтветствующей модели 5 узла. Выходные полюсы 29 соединенных вместе моделей 1 ветвей являются выходом скоммутированной Схемы И и подсоединяются к входному полюсу 40 модели 5 узла. Ког да срабатывают триггеры 11 всех моделей 1 ветвей, входящих в данный узел, на выходе 40 модели 5 узла появляется сигнал логической единицы с выхода вышеописанной схемы И. Через выходной полюс 31 модели 5 узла единичный сигнал передается на входные полюсы 23 моделей 1 ветвей, исходящих дальше из данного узла. Но модели 1 ветвей, боёдиненные в данном узле, срабатывают не обязательно одновременно. В тех моделях 1 ветвей, которые срабатывают рань ше других, на выходных полюсах 29 при сутствует нулевой логический уровень, который через инвертор 16 поступает на вход элемента И 13 как разрешение

на прохождение тактовых Импульсов через элемент И 13, и сигналом логической единицы с выхода этого элемента происходит возврат в нулевое состояние триггера Ю. Как только срабатывает модель 1 ветви, формирующаяся последней в данном узле, на входе 40 модели 5 узла и выходных полюсах 29 моделей 1 ветвей, подключенных к нему, появляетсигнал логической единицы, который через инверторы 16 блокирует сброс в О триггеров 10. Триггер 1О модели 1 ветви, формирующейся щоследней в данном узле, останется в единичном состоянии, и будет сигнализировать о том, что эта ветвь принадлежит экстремальному дереву моделируемого графа. Вычислительш й процесс протекает выше описанным образом дальше без вме- шательства блока управления, подобно тому как это происходит в реальных процессах, путем формирования ветвей и срабатывания узлов. ЕСЛИ граф составлен и набран правильно, и не произошло отказа ни в одной Из моделей 1 ветвей, то через некоторое время на выходньтх полюсах 2 9 моделей 1 ветвей, образующих конец графа появляется сигнал логической единицы, который свидетельствует об отсутствии ошибок. Этот сигнал через вход 38 блока 3 управления поступает для останова всего устройства. В противонрм случае, если в решаемой сети есть логические ошибки, такие как замкнутые контуры, , тупики, или произошел сбой в одной или нескольких моделях ветвей, сигнал в конце графа не появляется. Как указано на фиг. 2 в графе будет граница , сосостояшая из несформированных узлов, блокирующих достижение конца- графа. Эта граница будет иметь всегда место, если не сформируется хотя бы одна ветвь иля узел из-за вышеуказанных ошибок. Если через наперед заданное время -fc задержки на входе 38 блока 3 управления не появляется сигнал логической единицы с выходов моделей 1 ветвей, образуюших конец графа, то блок 3 управления снимает сигнал с шины решения задачи длиннейшем пути и импульсы с его выхода 34 поступают на обший вход 4О распределителя 7 импульсор, который последовательно через входь 42 опрашивает модели 5 узлов. Если в модели 5 узла на выходном полюсе 31, и значит на входном полкюе 40 так же, присутствует сигнал логической единицы, то при опросе эта модель 5 узла не выдает информационного сигнала на свой вьрсод 43. И, наоборот, когда при опросе обнаруживается какая-либо модель 5 узла, у которой на выходном полюсе 31 присутствует сигнал нуля, то с ее выхода 4 на один из входов многовходового элемента ИЛИ 8 поступает единичный логический сигнал, который с его вьосода поступает на вход 37 блока 3 управления. По поступлению этого сигнаяа блок 3 управления прекращает выдачу импульсов на общий вход 40 распределителя 7 импульсов, в котором остается зафиксированньтм адрес интересующей нас модели 5 узла. Одновремен:нЬ блокЗ уйравлёнйя с своего выхода ЗЗ выдаёт сигнал логической единицы на шину реше ния задачи о кратчайшем пути. В отличие от задачи о длиннейшем. пути, решение задачи о кратчайшем пути допускает наличие кс нтуров или несформ фование ветви. Это дает возможность проникнуть за границу несформироеанных событий. Известные модёл узлов, как и модели ветвей, однонаправлены от вход ного полюса к выходному полюсу, г При подаче сигнала логической единицы на щину решения задачи о кратчайшем пути автоматически происходат запуск в реньше зафиксированной на распредели теле 7 импульсов модели 5 узла. На выходе 31 этой модели 5 узла появляется сигнал логической единицы, который запускает все модели 1 ветвей из него исходя щие. Аналогично вышеописанному, формирователи 9 временного интервала этих моделей 1 ветвей, сформировав их длительности, выдают с своего выхода па вход элемента И 12 сигнал на установку в код 1 триггера 10, единичный логический уровень с единичного Ъыхода которого устанавливает в состояние григгер 11. На входаом Цолюсе 40 бой модели 5 узла пЬявляетсй ло гической единицы, если оканчивает CBOlO работу хотя бы одна модель 1 подключенная своим выходным Полюсом к нему. Переключением в состояние триггера 11 снимается сигнал логическо

единицы на выходе элемента К-НЕ 17 и единичный логический уровень t его вьЬсода через диод 2 О поступает на в.ыходной полюс 29 (диода 21 решения задачи о кратчайшем пути во всех моделях 1 ветвей заперты напрянаружении признака контора с выхода 43 зафиксированной модели 5 узла снимается сигнал логической единицы, и на входе . 37 блока 3 управления появляется сигнал логического нуля. При этом блок 3 управления с выхода 35 выдает на блок 4 жением логической единицы с выходов элементов И-НЕ 18). Появление сигналалогической единицы на входе 40 модели 5 узла после окончания работы одной или однобременно нескольких моделей 1 ветвей, подключенных своими выходными полюсами 29 к нему, блоктфует срабатывание элементов И 12 и 13 остальных, еще не отработавших моделей 1 ветвей, входящих в данный узел, так как на выходе инвертора 16 будет сигнал логического нуля. Триггеры 10 этих моделей Г ветвей не установлены в единичное состояние потому, что эти ветви уже не несут никакой информации о кратчайших путях, проходящих через данный узел. Если зафиксированный узел принадлежит замкнутому контуру, то в режиме решения задачи о кратчайшем пути этот узел проходится больше чем один раз. После второго прохождения на выходном полюсе 31 его модели 5 узла появляет- ся уровень логического нуля. Аналогично тому, как это делается в известных моделях подобного типа, после того как на устройстве определена конфигурация различных деревьев, что фиксируется в данном устройстве триггерами 1О моделей 1 ветвей, и на полюсах моделей присутствуют сигналы логической единицы. Сигналы, индицирующие различные пути . и.контуры, имеют характер прбтйвопр ложный сигналам измерения, т.е. индикация путей или контуров производится сигналами нулевого логического уровня. Нулевой логический уровень с выходного полюса 31 модели 5 узла передается на его входной полюс 40, который в свою очередь соединен с выходными полюсами 29 моделей 1 ветвей. Если в модели 1 ветви триггер 10 находится в единичном Состоянии, то через элемент 19индикации и диод 22 сигнал логического нуля передается на ее входной полюс 23, который дальше соединен с выходньхм полюсом 31 предыдухцих моделей 5 узлов, и нулевой логический уровень передается на его входной по-. люс 40, и т.д. пока не придет в зафиксированную точку. Таким образом, можно проследить путь или контур. При обиндикации бигнал, по которому отменаются все модели 1 ветвей, принадлежащих одному или нескольким контурам, в которые вхоЦит зафиксированный узел. Модели 1 ветвей, принадлежащие этим контурам, с своих индикационн1,1Х выходов 30 выдают сигналы логического нуля на свои индивидуальные входы 47 в блоке 4 индикации,

После отметки моделей ветвей, принадлежащих обнаруженному замкнутому контуру, через некоторое время г задержки блок 3 управления с выхода 32 снова выдает сигнал логической единицы на шину решения задачи о длиннейшем пути. Одновременно сигналом с выхода 36 блока 3 управления сбрасываются в нулевое состояние триггеры 11 моделей 1 ветвей, которые участвовали в формировании кратчайших путей, за исключением той модели ветви, которая принадлежала обнаруженному контуру и блокировала формирование узла ,так как теперь она уже сформирована при поиске кратчайших путей. Этим самым как бы разрывается контур и имеется возможность проникнуть дальше в граф.. На вхоном полюсе 40 ранее опрашивавшегося узла появляется сигнал логической единицы и идет дальше формирование дпвннейших путей и проверка правильности избранного графа. При этом мы можем или достигнуть конца графа или прийти к новой границе. В первом случае проверка окончена, .и устройство останавливается, во втором случае начинается аналогично проверка узлов этой НОЁОЙ границы.

При поиске ошибок и неисправностей может быть случай, когда не все узлы границы несформированных узлов принадлежат контуру, или как это случается при наличии тупика или технической неисправности мЪделей 1 ветвей, вообще контура не будет. В первом случае опрашиваемый узел блокируется позже ветречаемым контуром, и если после задержки t-j в его входной полюс-модели 5 узла не приходит сигнал логической единицы, то на ее выходе 43 и на входе 37 блока 3 управления не появляется сиграл логического нуля. Блок 3 управления с выхода 34 начинает подавать тактовые импульсы на вход 40 распределителя 7 импульсрв, который переходит к опросу следующих моделей 5 узлов до тех пор пока не бУДет обнаружена следующая модель 5 узла, в которой обнаруживается признак контура. Работа устройства будет аналогична вышеописанному. Во втором случае распределителем 7 импульсов перебираются все модели 5 узлов границы j . Одновременно с перебором моделей 5 узлов запускаются в режиме )ешения задачи о кратчайшем пути все модели 1 ветвей, лежащие после границы несформированных событий, и формируются соответствующие узлы. В тех моделях 1 ветвей, которые не исправнь, в режиме решения задачи о длиннейшем пути на входных полюсах 23 моделей 1 ветвей присутствуют единичные логические уровни, а на вьтходных полюсах 2 9 их нет. Сигнал о сбое внутри модели 1 ветви образуется элементом И 15. Сигнал логического нуля на выходном полюсе 29 инвертируется и на обоих входах элемента И 15 в случае вышеуказанного сбоя присутствуют сигналы логической ; единицы. Элемент И 15 подключен к входу элемента 19 индикации, который через индикационный выход 30 модели 1 ветви выдает на свой индивидуальный вход 47 блока 4 индикации нулевой логический уровень. После проверки всех моделей 5 узлов с выхода 35 блока 3 управления подается сигнал, по которому фиксируются все неисправные модели 1 ветвей.

В исходном состоянии триггеры 4951 сброшены в срстояниеО. По внешнему сигналу пуска триггер 49 устанавливается в состояние 1. Уровень логической единицы с единичного выхода триггера 49 служит сигналом решения задачи о длиннейшем пути. Сброс в нулевое состояние триггера 49 происходит по сигналу логической единвды, поступающему с моделей 1 ветвей, образующих конец графа набранной задачи, через входной полюс 38 на вход элемента И 55 а также по сигналу с выхода элемента 63 задержки, поступающему всякий раз, Kipraa мы опрашиваем модели 5 узлов, принадлежащих границе несформированных узлов. При этом, если модель 5 узла принадлежит контуру, запуск генератора 65 одиночного импульса происходит положительным фронтом перепада напряжений на выходе инвертора 52 через время прохождения этого сигнала через элемент 64 задержки. В противном случае, когда модель 5 узла не принадлежит контуру, запуск генератора 65 одиночного импульса производится по сигналу с выхода элемента И 59. Время задержки i прозГожденйясигнала через элемент 63 задержки может регулироваться для задач данного класса о дпрннейшем пути, В качестве элемента 63 «регулируемой задержки можно использовать известные счетчико-регистровые структуры. Триггер 50 служит для различия режимов решения задач о длиннейшем и кратчайшем путях. Триггер 51 устанавливается в состояние, 1 всякий ра когда обнаруживается несформированная модель 5 узла границы. Сброс в нулевое состояние триггера 51 производится после конца анализа обнаруженной сшибки. .Элемент И 58 служит для разрешени прохождения импульсов тактового генера тора с выхода 34 блока 3 управления на общий вход 40 распределителя 7 импуль Сов при соответствующих состояний триг геров 49-51. Выход генератора 2- тактовых импульсов подключен к входу 39 блока 3 управления. Элемент И 58 формирует сигнал решения задачи о кратчай шем пути по состояниям триггеров 4951. Элемент И 6О предназначен для выдачи с вьЕхода 35 блока 3 управления на яод блока 4 индикации сигнала разрешения индикации. Время индикадии определяется элементом 64 задержки, . Устройство для анализа систек сетевой структуры выгоднйртли ается от ране известных устройств, тем, что наряду с решением задач об экстремальных путях , в системах сетевой cтpyF тypы, оно поз воляет автоматизировать определение ошибок, допущенных при подготовке задачи к решению, наборе стр уктуры, а также технических неисправностей однотипных моделей, Составляющих основу таких структур. Формула изобретения 1. Устройство для исследования сете содержащее генератор импульсов, выход которого подключен к первому Bxof бло ка управления, первый выход которого соединен с входом распределителя, выходы которого подключены к первым входам моделей узлов, модели ветвей и блок индикации, отличают еес я тем, что, с целью повышения точности, в устройство введены элемент ИЛИ и наборное псзле, первые группы входов и выходов к торого соединены соответственно с первыми выходами и вторыми входами моделей узлов, вторые ВЫХОДЫ которых подключены к входам элемента ИЛИ, выход которого соединен с вторым входом блока управления, третий вход которого подк1йочен к выходу наборного поля, вторые группы входов и выходов которого соединены соответственно с первьши выходами и входами моделей ветвей, вторые, третьи и четвертые входы которых подключены соответственно к второму, третьему и четвертому выходам блока управления, пятый выход которого соединен с одним входом блока индикации, другие входы которого подключены к вторым выходам моделей, ветвей, пятые и шестые входы которых соединены с группой выходов генератора импульсов. 2. Устройство по п. 1, о т л и ч а ющ е е с я тем,что блок управления содержит элементы И, элемент ИЛИ, триггеры, элемент НЕ, элементы задержки и генератор одиночного импульса, входы которого подключены соответственно к выходам первого элемента И и эдемента задержки, вход которого соединен с первыми входами, второго и третьего элементов И и подключен к выходу элемента НЕ, вход которого соединен с первым входом первого триггера и является вторым входом блока управления, первый вход которого подключен к первым входам четвертого и пятого элементов И, второй вход которого соединен с первым входом шестого элемента И и подключен к первому выходу второго триггера, второй выход которого соединен с первыми входами седьмого элемента И. и элемента ИЛИ и является вторым выходом блока управления, второй, вход седьмого элемента И соединен с первым входом восьмого элемента И и является третьим входом блока управления, второй вход восьмого элемента Иподключен к первому, выходу третьего триггера, первый вход которого соединен с выходом седьмого .элемента И, второй вход третьего триггера ;оединен с первыми входами второго триггера и первого элeмeнta И и подключен к выходу второго элемента задержки, первый вход которого соединен с выходом четвертого элемента И, второй вход которого подключен к выходу мента ИЛИ, второй вход которого соеfSmeH с вторыми входами первого и шестого элементов И и подключен к первому выходу первого триггера, второй выход которого соединен с третьим входом пятого элемента И, четвертый вход которого соединен с третьим входом шестого элемента И, с вторым входом второго элемента И и подключен к второму выходу третьего триггера, выходы , пятого и шестого элементов И являются соответственно пятым, первым и третьим выходами блока управления, выход генератора одиночного импульса сбёййНён с вторы м входом первого триггера, второго элемента задержки и третьего эле- мента И и является четвертым выходом

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

Источники информации, принятые во внимание при экспертюе

№ 305484, кл. Q- 06 Q- 7/122, 1969.

N9 486339, кл. б- Об & 7/48, 1971, (прототип).

JJ