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

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

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

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

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

Предлагаемое устройство содержит генератор 1 импульсов, блок 2 управления, блок 3 моделей ветвей, блок 4 формирования циклов, блок 5 автоматического формирования топологии, состоящий из логических блоков 6 узловых функций и распределителя 7 импульсов.

Блок 3 моделей ветвей содержит отдельные модели ветвей, выполненные по схеме фиг. 2, где изображены задатчики начального 8 и конечного 9 узлов, счетчик 10 импульсов, триггеры И, 12, элементы «И 13-19, элементы «ИЛИ 20, 21. В модели ветви первые входы задатчиков адресов начального и конечного узлов подключены к первым шинам 22, 23 тактовых импульсов, вторые их входы - к шинам 24, 25 записи номера соответственно начального и конечного узла, а их выходы - к первым входам элементов «И 14, 15 и 16, 17. Выходы элементов «И 15, 16 соединены с первым выходом 26 модели ветви. Вторые входы этих элементов «И, подключены к входам 27, 28 управления модели ветви, а их третьи входы - к нулевому выходу триггера 11, второму выходу 29 модели ветви и первому входу элемента «И 18. Вторые входы элементов «И 17 и 18 связаны с входами 30, 31 формирования цикла модели ветви. Выход элемента «И 17 соединен с единичным входом триггера 12, нулевой вход которого подсоединен к входу 32 сброса модели ветви, а его единичный выход и выход элемента «И

18 через элемент «И 19 и элемент «ИЛИ 20, ххругой вход которого соединен с входом 33 фиксации цикла модели ветви, подключены к единичному входу триггера 11. Нулевой вход триггера И соединен с выходом счетчика 10, вход которого через элемент «И 13 подключен к второй шине 34 тактовых импульсов и выходу элемента «ИЛИ 21. Входы элемента «ИЛИ 21 соединены соответственно с входом 35 управления модели ветви и выходом элемента «И 14, второй вход которого подключен к единичному выходу триггера 11.

Логический блок 6 узловых функций, число которых соответствует числу узлов сети, содержит (фиг. 3) счетчик 36 импульсов, емкость которого равна емкости счетчика 10 импульсов модели ветви, триггеры 37; 38, элементы «И 39-42, элемент «ИЛИ 43.

Вход счетчика 36 импульсов через элемент «ИЛИ 43 подключен к выходам элементов «И 39 и 42, первые входы которых соединены соответственно с единичными выходами триггеров 37, 38, а остальные их входы подключены к входам 44-47 управления логического блока 6 узловой функции. Выход счетчика 36 подключен к нулевому входу триггера 37, выходы которого соединены с выходами 48, 49, и через элемент «И 40, другой вход которого соединен с отдельным входом 50 управления логического блока узловой функции, подключен к выходу 51 логического блока узловой функции. Два других входа 52, 26 логического блока узловой функции подключены через элемент «И 41 к нулевому входу триггера 38, единичный вход которого соединен с единичным входом триггера 37 и подключен к входу 53 сброса логического блока узловой функции. Устройство для исследования сетей работает следующим образом.

Предварительно в счетчики 10 заносятся количества импульсов, пропорциональные пропускным способностям ветвей, а в задатчики адресов начального 8 и конечного 9 узлов, которые могут быть выполнены на базе счетчиков импульсов, заносятся количества импульсов, пропорциональные номерам узлов, из которых данная ветвь выходит и в которые она входит.

Триггеры 11, 37, 38 устанавливаются в единичное состояние. Синтез сети осуществляется в два этапа. На первом этапе проводится определение максимального потока через все узлы синтезируемой сети и формирование топологии сети. Для этого из блока 2 управления на полюса (35, 47) подается сигнал, разрешающий прохождение импульсов ГИ в счетчики 10 и 36.

Сигнал переполнения одного из счетчиков 10 устанавливает триггер 11 модели ветви в нулевое состояние. Сигнал, появившийся на нулевом выходе триггера 11, поступает через выход 29 в устройство управления, запрещая поступление импульсов ГИ в счетчики 10, 36, и разрешает поступление импульсов ГИ на вход распределителя 7 импульсов и входы задатчиков начальных (22) и конечных (23) узлов. Сигнал о переполнении одного из задатчиков адресов узлов подается через выход 26 в блок 5 автоматического формирования топологии и в блок 2 управления, запрещая поступление нмпульсов ГИ на полюса (22, 23) в распределитель импульсов, и разрешает поступление импульсов ГИ. Совпадение этого сигнала с сигналом на одном из элементов (41) логического блока узловой функции (вход 52) устанавливает соответствующий триггер 38 в нулевое состояние. Тем самым запрещается поступление импульсов ГИ в соответствующий счетчик 36 до окончания первого этапа. Процесс повторяется до тех пор, пока не появится сигнал на выходе распределителя импульсов, сигнализирующий блоку управления об окончании первого этапа. После окончания первого этапа в счетчиках 36 импульсов записаны количества импульсов, равные Ломаке -JuiKc 1 где Ломаке - емкость счетчика; накс - количество импульсов, пропорциональное максимальному потоку /-ГО узла. На втором этапе проводится определение ветвей, принадлежащих гамильтонову циклу, и определение минимальных пропускных способностей ветвей, лежащих на этом цикле. Для этого по сигналу из блока 2 управления разрещается поступление импульсов ГИ в задатчики начальных 8 и конечных 9 узлов и формирователь гамильтоновых циклов, который, формируя цикл, устанавливает триггеры 11 в единичное состояние в тех моделях ветвей, у которых триггеры 37 находятся в единичном состоянии. При этом в счетчики 10 моделей ветвей, принадлежащих гамильтоно ву циклу, заносится количество импульсов, пропорциональное минимальным пропускным способностям этих ветвей. Далее на полученном множестве вновь формируется гамильтонов цикл и весь процесс повторяется. Второй этап закончится только тогда, когда все триггеры 37 окажутся установленными в нулевое состояние. При этом количество импульсов, записанных в счетчиках 10 моделей ветвей, характеризуют пропускную способность синтезируемой сети. Предмет изобретения 1. Устройство для исследования сетей, содержащее блок моделей ветвей, соединенный с блоком формирования циклов, генератор импульсов, подключенные к блоку управления, отличающееся тем, что, с целью увеличения быстродействия процессов подготовки и решения задач на сетях, оно содержит блок автоматического формирования топологии, состоящей из распределителя импульсов, вход и первый выход которого подключены к блоку управления, а каждый из остальных выходов распределителя импульсов соединен с входом логического блока узловой функции, другие входы которого соединены с блоками управления, моделей ветвей, формирования циклов; выходы логических блоков узловой функции подключены к входу блока управления; первые входы задатчиков адресов начального и конечного узлов моделей ветвей подключены к первым шинам тактовых и.мпульсов, вторые их входы соединены с щинами записи номера соответственно начального и конечного узлов, а выходы - с первыми входами соответственно первого, второго, третьего и четвертого элементов «И, выходы которых соединены с первым выходом модели ветви, подключены к входам управления модели ветви, а их третьи входы соединены с нулевым выходом первого триггера, вторым выходом модели ветви и первым входом пятого элемента «И, второй вход которого и второй вход четвертого элемента «И соединены с входами формирования цикла модели ветви; выход четве/.того элемента «И соединен с единичным входом второго триггера, нулевой вход которого подключен к входу сброса модели ветви, а его единичный вход и выход пятого элемента «И через шестой элемент «И и первый элемент «ИЛИ, соединенный другим ВХСГ.ОМ с входом фиксации цикла модели ветви, подключены к единичному входу первого триггера, нулевой вход которого соединен с пыходом счетчика, вход которого через седьмой элемент «И соединен с второй шиной тактовых импульсов и выходом второго элемента «ИЛИ, входы которого соединены с входом управления модели ветви и выходом второго элемента «И, второй вход которого подключен к единичному выходу первого триггера. 2. Устройство по п. I, отличающееся тем, что логический блок узловой функции содержит счетчик, вход которого через первый элемент «ИЛИ подключен к выходам первого и второго элементов «И, первые входы которых соединены с единичными выходами соответственно первого и второго триггеров, а остальные их входы подключены к входам управления логического блока узловой функции; ВЫХОД счетчика соединен с кулевым входом первого триггера, выходы которого соединены с выходами формирования цикла логического блока узловой функции, и через третий элемент «И, другой вход которого соединен с отдельным входом управления логического блока узловой функции, подключен к выходу логического блока узловой функции, два других входа которого через четвертый элемент «И подключены к нулевому входу второго триггера, единичный вход которого соединен с единичным входом первого триггера и подключен к входу сброса логического блока узловой функции.

р«г. /

IJ

Л

2ffO21

о0d

2629 30

JJ

J

23

/

/f

/J

2S

12

T.

625

J/

Ф«г. 2

Фиа.З