Устройство для определения детерминированных характеристик графа Советский патент 1987 года по МПК G06F15/173 

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

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

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

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

Выходы блока 1 перебора сочетаний

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

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

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

Блок управления содержит элемент 2 запрета, элементы И 13-15, элемент 16 задержки, триггер 17, генератор 18 одиночных импульсов, элементы ИЛИ 19 и 20, регистр 21 сдвига, генератор 22 тактовых импульсов.

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

5

0

5

0

Чс t. +

время срабатывания схемы 8

разом.

Б исходном состоянии счетчик 6 числа разорванных ветвей, регистр 11 памяти и регистр 21 сдвига очищены, триггеры 2 выбора ветвей находятся в нулевом состоянии, триггер 17 и все ячейки памяти регистра 7 памяти числа разорванных ветвей - в единичном. В блоке 10 формиров 1ния топологии выходы коммутации соединены в соответствии с топологией сети. Четвертый выход блока 9 управления в блоке 10 соединен с Пс1рой 1 ершин, для которых определяется минимальное сечение. Генератор 22 тактовь:х импульсов выра- 5 батывает импульсы с частотой f 1/Т, причем t, где t

tee

сравнения; t. - время срабатывания счетчика 6; tp, - время срабатывания

0 регистра 7 памяти, I

По сигналу запуска, который может вводиться вручную, генератор 18 одиночных импульсов в блоке 9 управления вырабатывает импульс, который проходит через элемент И 14, открытый по второму входу высоким потенциалом с единичного выхода триггера 17. Импульс с выхода элемента И 14 поступает на вход элемента 16 задержки, переводит три.ггер в нулевое состояние и через третий выход блока 9 управления поступает на вход блока 1 перебора сочетаний, на выходах которого появляется первая комбинация. Триггеры 2 выбора ветвей при этом устанавливаются в единичное состояние, если данная ветвь присутствует в испытании, и в нулевое - если нет. Высокие потенциалы на прямых выходах триггеров 2 выбора ветвей открывают коммутаторы 3, причем если коммутаторы 3 открыты, т.е. есть электрическая связь между их выходами. Элемент 16 задержки задерживает импульс на время, большее или равное времени установки комбинации и срабатывания I коммутаторов 3, По истечении этого времени на выходе элемента 16 за5

0

5

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

регистра 21 сдвига с частотой f, которую задает генератор 22 тактовых импульсов. Импульсы с выходов регист ра 21 сдвига через первые входы блока 9 управления поступают на вторые входы злементов И 4. Через многовходовый элемент ИЛИ 5 импульсы, число которы равно числу разорванных вершин, поступают в счетчик 6 числа разорванны

пройдя через блок 10 и открытые ком- О ветвей. По окончании подсчета, т.е. мутаторы 3. Таким образом, будет от- при появлении импульса на п-м выходе крыт элемент И 13 и закрыт элемент регистра 21 сдвига, импульс с (п+1)- 12 запрета и импульс с выхода элемента 16 задержки пройдет через открытый элемент И 13. Одновременно импульс, пришедший с входа блока 9 управления через элемент ИЛИ 20, переведет триггер 17 в единичное состояние. Импульс с выхода элемента И 13 через элемент ИЛИ 19 запустит генератор 18 одиноч- 20 разорванных ветвей. Если в счетчике ных импульсов. Последний вырабатьша- 6 числа разорванных ветвей записано ет импульс, который, пройдя через открытый элемент И 14, поступит на вход элемента 16 задержки, переведет триггер 17 в нулевое состояние, при котором элемент И 15 открыт по второму входу высоким потенциалом с инго выхода регистра 21 сдвига через второй выход блока 9 управления посту пает на схему 8 сравнения. По этому сигналу в схеме 8 сравнения производится поразрядное сравнение содержимого счетчика 6 числа разорванных ветвей и регистра 7 памяти числа

25

число, равное или большее, чем в регистре 7 памяти числа разорванных ветвей, то со схемы 8 сравнения по- дает-ся сигнал, который стирает содержимое счетчика 6 числа разорванных ветвей. В последнем при этом записываются нули. Если же число, записанное в счетчике 6 числа разорванных ветвей, меньше, чем число, записанное в регистре 7 памяти числа разорванных ветвей, то схема 8 сравнения выдает сигнал в регистр 7 памяти числа разорванных ветвей, по которому содер

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

30

число, равное или большее, чем в регистре 7 памяти числа разорванных ветвей, то со схемы 8 сравнения по- дает-ся сигнал, который стирает содержимое счетчика 6 числа разорванных ветвей. В последнем при этом записываются нули. Если же число, записанное в счетчике 6 числа разорванных ветвей, меньше, чем число, записанное в регистре 7 памяти числа разорванных ветвей, то схема 8 сравнения выдает сигнал в регистр 7 памяти числа разорванных ветвей, по которому содер40

45

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

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

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

импульсов. I

Аналогично описанному импульс с

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

регистра 21 сдвига с частотой f, которую задает генератор 22 тактовых импульсов. Импульсы с выходов регистра 21 сдвига через первые входы блока 9 управления поступают на вторые входы злементов И 4. Через многовходовый элемент ИЛИ 5 импульсы, число которых равно числу разорванных вершин, поступают в счетчик 6 числа разорванных

ветвей. По окончании подсчета, т.е. при появлении импульса на п-м выходе регистра 21 сдвига, импульс с (п+1)- разорванных ветвей. Если в счетчике 6 числа разорванных ветвей записано

го выхода регистра 21 сдвига через второй выход блока 9 управления постпает на схему 8 сравнения. По этому сигналу в схеме 8 сравнения производится поразрядное сравнение содержимого счетчика 6 числа разорванных ветвей и регистра 7 памяти числа

ветвей. По окончании подсчета, т.е. при появлении импульса на п-м выходе регистра 21 сдвига, импульс с (п+1)- разорванных ветвей. Если в счетчике 6 числа разорванных ветвей записано

число, равное или большее, чем в регистре 7 памяти числа разорванных ветвей, то со схемы 8 сравнения по- дает-ся сигнал, который стирает содержимое счетчика 6 числа разорванных ветвей. В последнем при этом записываются нули. Если же число, записанное в счетчике 6 числа разорванных ветвей, меньше, чем число, записанное в регистре 7 памяти числа разорванных ветвей, то схема 8 сравнения выдает сигнал в регистр 7 памяти числа разорванных ветвей, по которому содер

жимое счетчика 6 переписывается в ре-

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

импульсов. I

Аналогично описанному импульс с

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

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

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

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

15

подключен к выходу (n-i-2)-ro разряда регистра сдвига, выход каждого i-ro разряда которого подключен к первом входу.i-ro элемента И группы, второ вход которого подключен к инверсном выходу i-ro триггера группы, выход (п+1)-го разряда регистра сдвига по ключен к входу разрешения- сравнения схемы сравнения, вход синхронизации регистров сдвига.блока управления подключен к выходу генератора такто вых импульсов, вход сдвига регистра сдвига объединен с вторым входом- вт рого элемента ИЛИ.и подключен к вых ду второго элемента И блока управле ния, выход первого элемента ИЛИ бло управления подключен к входу запуск генератора одиночных импульсов блок управления, выход которого подключе

входу i-й вершины группы входом блока-20 к первым входам второго и третьего

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

25

элементов И блока управления, второй- вход третьего элемента И блока управления подключен к прям.ому выходу триггера блока упра.вления, инверсный выход которого подключен к второму входу второго элемЁ .нта И блока управления, выход второг о элемента ИЛИ блока управления подключен к входу установки в 1 триггера блока управвведены группа из п элементов И, эле--30 ления, вход установки в О которого

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

объединен с входом элемента задержки блока управления, с входом разрешения сравнения схемы сравнения и подключен к вь1ходу тре.тьего элемента И блока управления, выход каждого i-ro элемента И группы подключен к i-му входу элемента ИЛИ, выход которого подключен к счетному входу счетчика, группа разрядных выходов которого подключена к nepBoii группе разрядных входов схемы сравнения и к группе информационных входов первого регистра памяти, группа разрядных выходов которого подключена :. второй группе

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

ду установки в О счетчика, а выход Меньше подключен к входам разрешения перезаписи первого и второго репервого элемеН1 а ИЛИ блока управления - О гистров памяти, каждый i-й выход

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

подключен к выходу (n-i-2)-ro разряда регистра сдвига, выход каждого i-ro разряда которого подключен к первому входу.i-ro элемента И группы, второй вход которого подключен к инверсному выходу i-ro триггера группы, выход (п+1)-го разряда регистра сдвига подключен к входу разрешения- сравнения схемы сравнения, вход синхронизации регистров сдвига.блока управления подключен к выходу генератора тактовых импульсов, вход сдвига регистра сдвига объединен с вторым входом- второго элемента ИЛИ.и подключен к выходу второго элемента И блока управления, выход первого элемента ИЛИ блока управления подключен к входу запуска генератора одиночных импульсов блока управления, выход которого подключен

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

объединен с входом элемента задержки блока управления, с входом разрешения сравнения схемы сравнения и подключен к вь1ходу тре.тьего элемента И блока управления, выход каждого i-ro элемента И группы подключен к i-му входу элемента ИЛИ, выход которого подключен к счетному входу счетчика, группа разрядных выходов которого подключена к nepBoii группе разрядных входов схемы сравнения и к группе информационных входов первого регистра памяти, группа разрядных выходов которого подключена :. второй группе

разрядных входов схемы сравнения, вы- ход Больше которой подключен к вхо-

ду установки в О счетчика, а выход Меньше подключен к входам разрешения перезаписи первого и второго регруппы разрядных входов которого подключен к прямому выходу i-ro триггера группы.

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

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

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

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

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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