Устройство для определения детерминированных характеристик графа

 

Изобретение относится к области вычислительной техники и может быть использовано в электронных моделирующих установках сетей связи для решения задач, возникающих при перераспределении потоков информации на уз лах коммутации. Целью изобретения является расширение функциональных возможностей за счет определения минимальных сечений графа. Устройство содержит блок 1 перебора сочетаний, триггеры 2, коммутаторы 3, элементы И 4, элемент ИЛИ 5, счетчик 6, регистры 7 и 11, схему сравнения 8, блок 9 управления , блок 10 формирования топологии исследуемого графа. Устройство позволяет определять характеристики сетей связи. 2 ил.. (Л со со to cpuei

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (511 4 С 06 F 15/?О

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3917091/24-24 (22) 24.06.85 (46) 15.04.87. Вюл. № 14 (72) В.С.Тоискин, N.Н.111евчук, B.Е.Царьков и О.Н.Жуков (53) 681.333(088.8) (56) Авторское свидетельство СССР № 304604, кл. G 06 G 7/48, 1969.

Проблемы распределения информации.

Сборник. M. Наука, 1974, с. 27-28. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ДЕТЕРМИНИРОВАННЫХ ХАРАКТЕРИСТИК ГРАФА (57) Изобретение относится к области вычислительной техники и может быть использовано в электронных моделирую„„SU„„1304032 A1 щих установках сетей связи для решения задач, возникающих при -перераспределении потоков информации на узлах коммутации. Целью изобретения является расширение функциональных возможностей за счет определения минимальных сечений графа. Устройство содержит блок 1 перебора сочетаний, триггеры

2, коммутаторы 3, элементы И 4, элемент ИЛИ 5, счетчик 6, регистры 7 и

11, схему сравнения 8, блок 9 управления, блок 10 формирования топологии исследуемого графа. Устройство позволяет определять характеристики сетей связи. 2 ил.

1 13040

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

Целью изобретения является расширение функциональных возможностей устройства за счет определения минимальных сечений графа, На фиг.1 представлена функциональная схема устройства; на фиг.2 — функциональная схема блока управления.

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

ИЛИ 5, счетчик 6 числа разорванных ветвей, первый регистр 7 памяти числа разорванных ветвей, схему 8 сравнения, блок 9 управления, блок 10 формирования топологии исследуемого 25 графа и второй регистр 11 памяти состояния ветвей.

Выходы блока 1 перебора сочетаний соединены с входами триггеров 2 выбо- 3 ра ветвей, выходы которых подключены к управляющим входам коммутаторов 3, выходами подключенных к первым входам блока 10, Выходы элементов И через многовходовый элемент ИЛИ 5

35 подключены к первому входу счетчика

6 числа разорванных ветвей, второй вход которого соединен с первым выходом схемы 8 сравнения. К первым разрядным входам последней подключены первые выходы счетчика 6 числа разорванных ветвей и первые входы регистра 7 памяти числа разорванных ветвей, разрядные выходы которого подключены к вторым разрядным входам схемы 8 сравнения, третий вход которой соединен с вторым выходом блока

9 управления, Второй выход схемы 8 сравнения соединен с вторым входом регистра 7 памяти числа разорванных ветвей и с вторым. входом регистра 11 памяти состояния ветвей,.первые входы которого подключены к прямым выходам триггеров 2 выбора ветвей. Третий выход блока 9 управления подключен к первому входу блока 1 перебора сочетаний ° Четвертый выход блока 9 управления подключен к второму входу блока

10 формирования топологии, выход ко32 2 торого соединен с первым входом блока 9 управления, Блок управления содержит элемент

52 запрета, элементы И 13-15, элемент

16 задержки, триггер 17, генератор

18 одиночных импульсов, элементы

ИЛИ 19 и 20, регистр 21 сдвига, генератор 22 тактовых импульсов.

Устройство рабс тает следующим образом.

В исходном состоянии счетчик 6 числа разорванных ветвей, регистр 11 памяти и регистр 21 сдвига очищены, триггеры 2 выбора ветвей находятся в нулевом состоянии, триггер 17 и все ячейки памяти регистра 7 памяти числа разорванных ветвей — в единичном, В блоке 10 формирования топологии выходы коммутации соединены в соответствии с топологией сети, Четвертый выход блока 9 управления в блоке 10 соединен с парой вершин, для которых определяется минимальное сечение. Генератор 22 тактовых импульсов вырабатывает импульсы с частотой f = 1/Т, причем = t, где t = t + t + р„, время срабатывания схемы 8 сравнения; t,,„ — «ремя срабатывания счетчика 6; t Ä вЂ” время срабатывания регистра 7 памяти, 1

По сигналу запуска, который может вводиться вручную, генератор 18 одиночных импульсов в блоке 9 управления вырабатывает импульс, который проходит через элемент И 14, открытый по второму входу высоким потенциалом с единичного выхода триггера

17, Импульс с выхода элемента И 14 поступает на вход элемента 16 задержки, переводит триггер в нулевое состояние и через третий выход блока 9 управления поступает на вход блока 1 перебора сочетаний, на выходах которого появляется первая комбинация.

Триггеры 2 выбора ветвей при этом устанавливаются в единичное состояние, если данная ветвь присутствует в испытании, и в нулевое — если нет. Вы— сокие потенциалы на прямых выходах триггеров 2 выбора ветвей открывают коммутаторы 3, причем если коммутаторы 3 открыты, т,.е. есть электрическая связь между их выходами. Элемент

l6 задержки задерживает импульс иа время, большее или равное времени установки комбинации и срабатывания I коммутаторов 3. По истечении этого времени на выходе элемента 16 задержки появляется импульс, который через четвертый выход блока 9 управления поступает по второму входу в блок 10 на одну из выбранных вершин.

Если при данном наборе работающих 5 ветвей имеется связность между выбранными вершинами, то посланный из блока 9 управления импульс сразу же появится на входе блока 9 управления, пройдя через блок 10 и открытые коммутаторы 3. Таким образом, будет от- . крыт элемент И 13 и закрыт элемент

12 запрета и импульс с выхода элемента 16 задержки пройдет через открытый элемент И 13. Одновременно импульс, пришедший с входа блока 9 управления через элемент ИЛИ 20, переведет триггер 17 в единичное состояние. Импульс с выхода элемента И 13 через элемент

ИЛИ 19 запустит генератор 18 одиноч- 20 ных импульсов. Последний вырабатывает импульс, который, пройдя через открытый элемент И 14, поступит на вход элемента 16 задержки, переведет триггер 17 в нулевое состояние, при котором элемент И 15 открыт по второму входу высоким потенциалом с инверсного выхода триггера 17, и этот же импульс через третий выход блока 9 управления поступит на вход блока

1 перебора сочетаний, который выдаст очередную комбинацию ветвей. Триггеры 2 выбора ветвей и ключевые схемы

3 срабатывают аналогично описанному.

Допустим, что при этой очередной ком-35 бинации ветвей связность между выбранными вершинами отсутствует. Импульс, вышедший, через определенное время из элемента 16 через четвертый выход блока 9 управления, поступает по второму входу в блок 10 коммутации вершин. Так как связность между выбранными вершинами отсутствует, то на выходе блока 10 и, следовательно, .

45 на входе блока 9 управления сигнал не появится. Поэтому импульс с выхода элемента 16 задержки пройдет через открытый элемент 12 запрета и элемент

ИЛИ 19 и запустит генератор 18 одиноч- ных импульсов, который выработает импульс; Этот импульс с выхода генератора 18 единичных импульсов пройдет через открытый элемент И 15, поступит на вход регистра 21 сдвига и через элемент ИЛИ 20 переведет триггер 17 в исходное положение. Импульс, поступивший на вход регистра 2) сдвига, появляется последовательно на выходах

1304032

4 регистра 21 сдвига с частотой f которую задает генератор 22 тактовых импульсов. Импульсы с выходов регистра 21 сдвига через первые входы блока 9 управления поступают на вторые входы элементов И 4. Через многовходовый элемент ИЛИ 5 импульсы, число которых равно числу разорванных вершин, поступают в счетчик 6 числа разорванных ветвей. По окончании подсчета, т ° е. при появлении импульса на п-м выходе регистра 21 сдвига, импульс с (n+l)го выхода регистра 21 сдвига через второй выход блока 9 управления поступает на схему 8 сравнения. По этому сигналу в схеме 8 сравнения производится поразрядное сравнение содержимого счетчика 6 числа разорванных ветвей и регистра 7 памяти числа разорванных ветвей. Если в счетчике

6 числа разорванных ветвей записано число, равное или большее, чем в регистре 7 памяти числа разорванных ветвей, то со схемы 8 сравнения подается сигнал, который стирает содержимое счетчика 6 числа разорванных ветвей.. В последнем при этом записываются нули. Если же число, записанное в счетчике 6 числа разорванных ветвей, меньше, чем число, записанное в регистре 7 памяти числа разорванных ветвей, то схема 8 сравнения выдает сигнал в регистр 7 памяти числа разорванных ветвей, по которому содержимое счетчика 6 переписывается в регистр 7 памяти. Также схема 8 сравнения выдает сигнал, по которому счетчик 6 устанавливается в исходное состояние. Одновременно по сигналу перезаписи, который подается также на регистр 11 памяти состояния ветвей, в последний записывается состояние триггеров 2 выбора ветвей. После завершения этих операций íà (n+2)-м выходе регистра 21 сдвига появляется импульс, который через элемент ИЛИ

19 запускает генератор 18 одиночных импульсов.

Аналогично описанному импульс с выхода генератора 18 одиночных импульсов через элемент И 14 и третий выход блока 9 управления устанавливает очередную комбинацию в блоке 1 перебора сочетаний. Далее устройство работает аналогично описанному, IIodле перебора всех сочетаний в регистре 7 памяти числа разорванных ветвей оказывается записанным минимальное

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

11 памяти состояния ветвей — номера ветвей минимального сечения. г формулаизобретения

Устройство для определения детерминированных характеристик графа, содержащее блок формирования топологии исследуемого графа, блок перебора сочетаний, группу из п коммутаторов, группу из триггеров, каждый i-й выход (i=1 2, ...,n) блока перебора сочетаний подключен к входу установки в "1" i-го триггера группы, прямой выход которого подключен к управляющему входу i-ro коммутатора,. выход

i-го коммутатора группы подключен к входу i-й вершины группы входом блока20 формирования топологии исследуемого графа, выход i-й вершины группы выходов блока формирования топологии исследуемого графа подключен к информационному входу i-ro коммутатора группы, о т л и ч а ю щ е е с я тем„ что, с целью расширения функциональных возможностей за счет определения минимальных сечений графа, в него введены группа из и элементов И, эле- 0 мент ИЛИ, счетчик, схема сравнения, два регистра памяти и блок управления, который содержит элемент запрета, первый и второй элементы И, элемент задержки, триггер генератор одиночных 35 импульсов„ первый и второй элементы

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

Ф второй вход которого подключен к выходу элемента запрета, третий вход первого элемента ИЛИ блока управления

32

6 подключен к выходу (и+2)-го разряда регистра сдвига, выход каждого -го разряда которого подключен к первому входу.i-го элемента И группы, второй вход которого подключен к инверсному выходу i-го триггера группы, выход (и+1)-го разряда регистра сдвига подключен к входу разрешения сравнения схемы сравнения, вход синхронизации регистров сдвига. блока управления подключен к выходу генератора тактовых импульсов, вход сдвига регистра сдвига объединен с вторым входом второго элемента ИЛИ и подключен к выходу второго элемента И блока управления, выход первого элемента ИЛИ блока управления поцключен к входу запуска генератора одиночных импульсов блока управления, выход которого подключен к первым входам второго и третьего элементов И блока управления, второй вход третьего элемента И блока управления подключен к г:рямому выходу триггера блока упра.вления, инверсный выход которого подключен к второму входу второго элемента И блока управления, выход второго элемента ИЛИ блока управления подключен к входу установки в "1" триггера блока управления, вход установки в "0" которого объединен с входом элемента задержки блока управления, с входом разрешения сравнения cxem сравнения и подключен к выходу третьего элемента И блока управления, выход каждого i-го элемента И группы подключен к i-му входу элемента ИЛИ, Bblxop, которого подключен к счетному входу счетчика, группа разрядных выходов которого годключена к первой группе разрядных входов схемы сравнения и к группе информационных входоз первого регистра памяти, группа разрядных выходов которого подключена х второй группе разрядных входов схемы сравнения, выход "Больше" которой подключен к входу установки в "0" счетчика, а выход Меньше" подключен к входам разрешения перезаписи первого и второго регистров памяти, каждый i-й выход группы разрядных входов которого подключен к прямому выходу i-го триггера группы.

1304032

Составитель Т.Сапунова

Техред В. Кадар Коррек гор Н КоРоль

Редактор А.Лежнина

Заказ 1313/50 Тираж 673 Подписное

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

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

Производственно-полиграфическое предприятие, r, Ужгород, ул. Проектная, 4