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

ОП ИСАНИЕИЗОБРЕТЕН ИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз Советских Социалистических Республик(и) 534765 61) Дополнительное к авт. свид-ву 22) Заявлено 21.03.75(21) 2115634 1 5/20 соединением заявки - Приоритет -Гасударственный комитет Совете Министров СССР по делам изооретений и открытий3) Опубликовано 05 БюллетеньДата опубликования описа донов, В, В. ФеВ, В. Хаджинов В,Н. В, Федотов и(71) Заявите Украинской СС Институт электро 4) УСТРОЙС ЛЯ МОДЕЛИРОВАНИЯ СДАННЫМИ лах сети, Для задачи о кратчайшем путилах выполняются функции дизьюнкции, ддачи о длиннейшем пути - коньюкции.Решать задачи об экстремальных йугяв сетях с огрицательчыми длинами ветвейна известных устройствах невозможно,Из известных устройств наиболее близким по технической сущносги к данномуизобретению являегся устройство 4, содержащее соединенные в соответствии стопологией анализируемой сети отдельныемодели ветви, каждая из которых содержиосновной счетчик импульсов, триггер формирования временного интервала, элементИ блок выделения и индикатор,Управление узлами, входящими в состав модели ветви, производится с помощью импульсных сигналов, формируемых, например, генератором тактовых импульсов, и сигналов, вырабатываемых блоком управления,Однако это устройство не позволяет реть задачу нахождения экстремальных пуй в графе, если хотя бы одна его дуга имеет отрицательную характеристику,рас вид явл Изобретение относится к области вычислительной техники и может быть использс.вано при построении специализированныхвычислительных машин для решения задачо динамических потоках в сетях, возникающих при проектировании сетей связи и транспортных сетей, задач распознавания образов, задачи коммивояжера и г.д,Известны способы и электронные моделидля определения экстремальных путей насетях 11., 2, 33,Известные электронные цифровые моделиди решения задач о путях в сетях основаны на временной аналогии, Такие моделипредставляют собой подобную моделируемойсети цепь из элементов, обеспечивающихзадержку сигнала на время, пропорциональное длине ветви сети. Импульс пуска, поданный в начальный узел, распространяетсяпо сети, задерживаясь на определенное время в отдельных моделях ветвей, Процесспространения импульса и вместе с нимпути, который будет определен при поении импульса в конечном узле, зависитот логической функции, реализуемой в уэС ОТРИЦАТЕЛЬНЫМИБелью изобретения является повышение коэффициента использования оборудования устройства,Поставленная цель достигается тем, что в предложенном устройстве в каждую модель ветви введен блок выравнивания структуры, первый вход которого соединен с выходом индикатора и первым входом модели ветви, второй - с первым выходом блока выделения, второй выход которого соединен со входом индикатора и выходом модели ветви, вход - с выходом основного счетчика импульсов и нулевым входом триггера формирования временного интервала, единичныйвход которого подключен к выходу блока Йвыравнивания структуры, а единичный выходк первому входу элемента И, второй входкоторого соединен с третьим входом блокавыравнивания структуры и вторым входоммодели ветви, выход элемента И подключенко входу основного счетчика импульсов,Каждый блок выравнивания структурысодержит триггер, единичный вход которогосоединен с первым входом блока, а единичный выход - с первым входом элемента И,второй вход которого подключен к третьемувходу блока, а выход соединен со входомсчетчика импульсов, выход которого подключен к первому входу реверсивного счетчикаимпульсов, второй вход которого соединенсо вторым входом блока, а выход подключенк выходу блока.Схема устройства представлена на фиг, 1,где обозначены; элемент И 1, блок 2 выделения, индикатор 4, блок 4 выравниванияЗЬструктуры, триггер 5 формирования временнэгэ интервала, вход 6, выхэд 7 и вход 8устройства и эснэвнэй счетчик импульсэв 9,На фиг, 2 дана схема блока выравнивания структуры, где обозначены вход 10,4 Овыход 1 1, входы 12, 13, реверсивный сче тчик импульсов 14, триггер 15, элемент И16 и счетчик импульсов 17.На фиг. 3, а, 3, б изображена сеть сЯузлами 1 - 1 Ч и указанны ддительностисоответствующих ветвей,Устройство (см. фиг. 2) работает следующим образом,Первоначально путем коммутации между бОсобой модели ветви посредством входа 6 ивыхода 7 формируют топологию сетевоографика, где каждая дуга графа представляет собой одну модель ветви, Триггеры 5 и15 находятся первоначально в нулевом соотоянии. Реверсивный счетчик 14 обнуляется,а счетчик 17 имеет коэффициент пересчета,равный Ч, В счетчик импульсов 9 каждой модели ветви заносится число импуль.сов 60+ (х+) - если ветвь положи(х ) - если ветвь отрица тельная, М = й тельная,где 2 1 Ч емкость основного счетчика импульсов 9;(х ) - длительность положительной ветм (Ф) й+для отрицательных ветвей м =(у,) й- /х /где )О- порядок -го пути, т,е. чис/х ) - длительность отрицательной вет;ви,Первоначально производится структурноевыравнивание сети, Для этого на входы 8всех моделей ветвей выдаются импульсныесигналы и устанавливается в единичное сос)тояние триггер 5 тех моделей ветвей, котооые выходят из начала сетевого графика.При этом импульсы поступают через элемент И 1 в счетчик 9, на выходе которсго сигнал переполнения появляется послепросчета им числа импульсов, равного М =- И + (х+) для ветви с положительнойдлиной, и М = М - (х ) ддя отрицатель.ной ветви, что характеризует задержку импульса пуска на время, пропорциональноедлительности ветвиЭтот импульс поступает на вход блока2 выделения, который запускает моделиветвей, соединенные с выходом данной модели путем установления триггеров 5 соответствующих моделей в единичное состояние и разрешает поступление импульсныхсигналов в счетчик 14 по входу 12 блока4 выравнивания структуры.Поступление импульсов на вход счетчика 14 через блок 2 выделения продолжается до тех пор, пока все модели ветвей,входящие в данный узел, не выдадут импульспереполнения, В дальнейшем импульс, подачный в начальный узел, распространяется по сети и осуществляет запуск моделейветвей аналогично описанному выше. Появление импульса в конечной вершине сетихарактеризует конец выравнивания структуры всего графа, Этот процесс можно отождествить с введением фиктивных ветвейдлины Й в ветви с положительными длинами, что характеризуется введением дополнительной величины задержки, вносимой вблок 4 выравнивания структуры соответствующих моделей ветвей, При этом общаядлительность этих ветвей характеризуетсячислом импульсовддя положительных ветвейпо ветвей, пройденных импульсом пуска по/д ( - порядок 1-го пути, т,е, числоветвей, пройденных импульсом пуска попути.6После этого сигналы управления устанавливают триггеры 5 в нулевое состояние, иначинается процесс определения экстремальНого пути в заданной сети с выравненнымипорядками. Для этого по входу 13 блока 4 1 Овыравнивания структуры моделей ветвей,выходящих из начального узла, триггер 15устанавливается в единичное состояние, Приэтом разрешается поступление импульсовсо входа 10 через элемент И 16 на входсчетчика 17. Счетчик 17 пропускает каждый Й -й импульс в счетчик 14, котсрый с каждым Й -ым импульсом уменьшает порядок данной ветви на единицу, После того, как порядок станет равным нулю,счетчик 14 устанавливает триггер 5 в единичное состояние, что соответствуег дополнительной задержке импульса пуска, введенной при выравнивании структуры, При единичном состоянии триггера 5 разрешается Ипоступление импульсов в счетчик 9 который, отсчитав требуемое число импульсов,выдает сигнал переполнения, Этот сигнал,пройдя блок 2 выделения, запускает моделиветвей, соединенных с данной, путем уста Оновки в единичное состояние триггера 15блоков 4 соответствующих моделей ветвей,Этот процесс повторяется до тех пор, покане будет определен необходимый экстремальный путь. Этот путь определяется с псмс- Мшью блоков 2 выделения соответствующихмоделей ветвей и может быть проиндицироьан с помощью индикаторов 3 (цепц сбросаи установки в единичное состояние триггера 5 не показаны).40Устройство работает следующим образом(фиг, 3), Подразумевается, что каждая дугапредставляет собой модель ветви (фиг. 1).Между узлами 1 Ч и 111 (фиг, 3, а) возможны следующие пути: Н К, Н-а-К, Н-а - 45-б-К, 1 Ч -11 1 Ч -1-1111 Ч-11-1 ц Длинкейшийструктурный путь имеет вцд: 1 Ч - 1 - 11 - 1 И,аструктурная длина его равна трем,Соответственно длины всех путей равны:3,0 и -6. В процессе определения дликней 56шего структурного пути порядки,. которыесформированы блоком 4 и занесены в счетчики 14 (фиг, 2) соответствующих моделейветвей, определяюгсч следующими значения ми 1 Ч - 1=1 - О= 1, Ч- Я З-О=3,561 -=2.-1 = М 1 - 111 = 5 - 1 =о 11 - 11 = 5 - 2 = МПри этом с учетом порядков пугц ь моделях соответствующих ветвей должна быть осуществлена задержка импульса пуска на 6 О длительности, показанные на фиг, 3, б, Эта информация содержится в основном счетчике 9, счетчике 17- и реверсивном счетчике 14 (фиг, 1, 2), Если, например говорить с кратчайшем пути в пресбразс- ванной сети (фиг, 3, б), го он имеет длину равную 24Длиннейший путь будет 1 Чс длиной 33.Формула изобретения1, Устройство для моделирования сетейс отрицательными данными, содержащеемодели ветвей, каждая цз которых включает основной счетчик импульсов, триггерформирования временного интервала,. элмент И, индикатор ц блок выделения, о гл и ч а ю щ е е с я тем, чгс, с цельюповышения коэффициента цспсльзования оборудования, в каждую модель ветви введенблок выравнивания структуры, первый входкоторого соединен с выходом цндцкагорац перьым входом модели вегвц, ьгорой -с первым выходом блока выделения, второйвыход которого соедцнен со входом цкдцкатора и выходом модели ветви, вход - с ььходом основного счегчика импульсоь ц нулевым входом триггера формирования временного интервала, единичный вход которогоподключен к выходу блока выравниванияструктуры и вторым входом модели вегвц,выход элемента И подключен ко входу основногс счегчцка цмпульсоь.2, Усгройсгвс по п, 1, о г л и ч а юш е е с я гем, что блок выраькцьапцяструктуры ссдеожцг триггер, едцкцчкый входкоторого соединен с первым входом блока,.а единичный выход - с первым входом элемента И, второй вход ксгсрсго подключен ктретьему входу блока, а выход - соединенсо входом счетчика импульсов, выход ксгрого подключен к первому входу реверсивного счетчика, импульсов, вгорсй вход когорого соединен сс вторым входом блока, авыход - подключен к выходу блока,Источники информации пошитые вс ькцмание прц экспертизе:1, Авторское свидетельство СССРМ 305484, Гд 067/34 ог 08,12,19692, Ангорское сьцдегельсгьо СССРМ 36743 С 06 Ф 7/48 сг 25,04,19683, Аьгсрсксе свидетельство СССР% 432508, 6 06 г 15/20 ог 21,04 19714 Дсдспсь А, Г, "Решаюшцо элементыццфро-аналоговой мапцпь; дця расчега сетевых графиков", Сбсркцк Спсццализцрованные мсделцрующце машцны и усгройсгва",Киев, 1963 г.Заказ 5562/251 Тираж 864 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий 113035, Москва, Ж 35, Раушская наб., д. 4/5 Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4