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

 

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

Социалистических

Республик (») 534765 (61) Дополнительное к авт. свид-ву(22) Заявлено 21.03.75 (21) 2115634/24 с присоединением заявки №вЂ” (23) Приоритет— (51) М, Кл.-

Ci 06 F 15/20

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

Совете Министров СССР по делам изооретений и открытий (43) Опубликовано05,11.76. Бюллетень № 41 (53) УДК 681.333 (088,8) (45) Дата опубликования описания

В. В. Васильев, А. Г. Додонов, В. В. Федоров, Н. В. Федотов и

B. B. Хаджинов (72) Авторы изобретения (71) Заявитель

Институт электродинамики АН Украинской ССР (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕЙ С ОТРИЦАТЕЛЬНЫМИ

ДАННЫМИ

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

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

Решать задачи об экстремальных йугях

B сетях с отрицательными длинами ветвей на известных устройствах невозможно.

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

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

Белью изобретения является повышение коэффициента использования оборудования устройства, Поставленная цель достигается тем, что в предложенном устройстве в каждую модель ветви введен блок выравнивания структуры, первый вход которого соединен с выходом индикатора и первым входом модели ветви, второй - с первым выходом блока выделения, второй выход которого соединен со входом индикатора и выходом модели ветви, вход — с выходом основного счетчика импульсов и нулевым входом триггера формирования временного интервала, единичный вход которого подключен к выходу блока и выравнивания структуры, а единичный выходк первому входу элемента И, второй вход которого соединен с третьим входом блока выравнивания структуры и вторым входом модели ветви, выход элемента И подключен ко входу основного счетчика импульсов, Каждый блок выравнивания структуры содержит триггер, единичный вход которого соединен с первым входом блока, а единичный выход — с первым входом элемента И, @ второй вход которого подключен к третьему входу блока, а выход соединен со входом счетчика импульсов, выход которого подключен к первому входу реверсивного счетчика импульсов, второй вход которого соединен со в "îðûì входом блока, а выход подключен к выходу блока, Схема устройства представлена на фиг,1, где обозначены: элемент И 1, блок 2 выделения, индикатор 4, блок 4 выравнивания

35 структуры, триггер 5 формирования временнэгэ интервала, вход 6, выхэд 7 и вход 8 устройства и эснэвнэй счетчик импульсэв 9.

На фиг. 2 дана схема блока выравнивания структуры, где обозначены вход 10, 4О выход 11, входы 12, 13, реверсивный счетчик импульсов 14, триггер 15, элемент И

16 и счетчик импульсов 17.

На фиг. 3, а, 3, б изображена сеть с

Я узлами I — IV и указанны длительности соответствующих ветвей, Устройство (см. фиг. 2) работает следующим образом, Первоначально путем коммутации между собой модели ветви посредством входа 6 и выхода 7 формируют топологию сетевого графика, где каждая дуга графа представляет собой одну модель ветви, Триггеры 5 и

15 находятся первоначально в нулевом соо- 55 тоянии. Реверсивный счетчик 14 обнуляется, а счетчик 17 имеет коэффициент пересчета, равный N В счетчик импульсов 9 каждой модели ветви заносится число импул .сов 60

М = N

+ (х+) - если ветвь положи(х ) - если ветвь отрицательная, М = N тельная, где 2 N емкость основного счетчика импульсов 9;

+Ъ (x ) - длительность положительной вет м=(у -р,.)и+(х .) для отрицательных ветвей м =(р р,)н- /х / где ) — порядок g-го пути, r,e, чиви, / ! х ) - длительность отрицательной вет; ви, Первоначально производится структурное выравнивание сети, Для этого на входы 8 всех моделей ветвей выдаются импульсные сигналы и устанавливается в единичное сос> тояние триггер 5 тех моделей ветвей, которые выходят из начала сетевого графика.

При этом импульсы поступают через элемент И 1 в счетчик 9, на выходе которс го сигнал переполнения появляется после просчета им числа импульсов, равного М = — И + (х+) для ветви с положительной длиной, и М = N - (х ) для отрицатель ной ветви, что характеризует задержку импульса пуска на время, пропорциональное длительности ветви.

Этот импульс поступает на вход блока

2 выделения, который запускает модели ветвей, соединенные с выходом данной модели путем установления триггеров 5 соответствующих моделей в единичное состояние и разрешает поступление импульсных сигналов в счетчик 14 по входу 12 блока

4 выравнивания структуры.

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

-му пути; р — порядок б-го пути, т.е, число ветвей, пройденных импульсом пуска по пути.

После этого сигналы управления устанавливают триггеры 5 в нулевое состояние, и начинается процесс определения экстремаль

Ного пути в заданной сети с выравненными порядками. Для этого по входу 13 блока 4 О выравнивания структуры моделей ветвей, выходящих из начального узла, триггер 15 устанавливается в единичное состояние, При этом разрешается поступление импульсов ео входа 10 через элемент И 16 на вход счет ика 17. Счетчик 17 пропускает каждый N -й импульс в счетчик 14, котс рый с каждым N -ым импульсом уменьшает порядок данной ветви на единицу, Пос» ле того, как порядок станет равным нулю, счетчик 14 устанавливает триггер 5 в единичное состояние, что соответствуег дополнительной задержке импульса пуска, введенной при выравнивании структуры, При единичном состоянии триггера 5 разрешается И поступление импульсов в счетчик 9, который, отсчитав требуемое число импульсов, выдает сигнал переполнения, Этот сигнал, пройдя блок 2 выделения, запускает модели ветвей, соединенных с данной, путем уста- Ю новки в единичное состояние триггера 15 блоков 4 соответствующих моделей ветвей, Этот процесс IIOBroðÿåòñÿ до тех пор, пока не будет определен необходимый экстремаль ный путь. Этот путь определяется с помс 4 щью блоков 2 выделения соответствующих моделей ветвей и может быть проиндицироьан с помощью индикаторов 3 (цепи сброса и установки в единичное состояние триггера 5 не показаны).

Устройство работает следующим образом (фиг, 3), Подразу-меваегся, что каждая дуга представляет собой модель ветви (фиг. 1).

Между узлами IV и Ill (фиг, 3, a) возможны следующие пути: Н К, Н-а-К, Н-г,—

-б-К, IV-lll IV- I-ill > I U- l-II 11! Длинкейший структурный путь имеет вид: IU — I — II — lll,а структурная длина его равна трем, Соответственно длины всех путей равны:

3,0 и -6, В процессе определения длинней56 шего структурного пути порядки,. которые сформированы блоком 4 и занесены в счетчики 14 (фиг, 2) соответствующих моделей ветвей, определяюгсч следующими значения-ми: 1 / I = 3 — О= f, 1 - !11 5-О=3, 55

)-II=2.- = I-Il! =>- =, ц-ц =

При этом с учетом порядков пути B моделях соответствующих ветвей должна быть осуществлена задержка импульса пуска на 6О длительности, показанные на фиг, 3, б, Эта информация содержится в основном счетчике 9, счетчике 17-и реверсивном счетчике 14 (фиг. 1, 2), Если, например, говорить с кратчайшем пути в преобразс ванной сети (фиг 3, б), го он имеет длину равную 24

Длиннейший путь будет IU-Ill с длиной

33.

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

1, Устройство для моделирования сетей с отрицательными данными, содержащее модели ветвей, каждая из которых ьключаdT основной счетчик I:ìãóëüñoB, триггер формирования временного интервала, элемент И, индикатор и блок выделения, о гличающееся тем,чго, сцелью повышения коэффициента использования оборудования, в каждую модель ветви введен блок выравнивания структуры, первый вход которого соединен с выходом индикатора и перьым входом модели ветви, ьгорой— с первым выходом блока выделения, второй выход KoropoI coepiiBBE со входом индикатора и выходом модели ветви, вход — с вь— ходом основного счегчика импульсоь и нулевым входом триггера формирования временного интервала, единичный вход которого подключен к выходу блока выравнивания структуры и ьгорым входом к одели вегви, выход элемента И подключен ко входу основного счетчика импульсоь.

2, Устройсгво по п. 1, о г л и ч а юL1 е е с я гем, что блок выраькпьапия структуры содержиг триггер, единичный вход которого соединен с первым входом блока,. а единичный выход — с первым входом элемента И, второй вход которого подключен к третьему входу блока, а выход — соединен со входом счетчика импульсов, выход xoroрого подключен к первому входу реверсивного счег,"ика, импульсов, вгорой вход когорого соединен со вторым входом блока, а выход — подключен к выходy блока.

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

1, Авторское свидетельство СССР

М 305484, Гд 06 $ 7/34 or 08,12,1969

2, Ангорское свидетельство СССР

М 367433, Cq 06 t,7/48 ог 25,04.1968

3, Авторское свидетельство СССР

¹ 432508, 5 Обг 15/ 0 or 21,041971

4„Додонов А. Г. "Решаюшпе элементы цифро-аналогo мапш ь; д.:я расчега сетевых графиков", Сборник "Специализированные моделирующие машкны li "сгройсгва", Киев, 1963 г.

IV

Составитель А. Жеренов

Редактор Л. Утехина ТехредА. Демьянова Корректор Н. Бугакова

Заказ 5562/251 Тираж 864 Подлисное

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

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

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