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

 

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

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

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

РЕСПУБЛИК

9 А1

09) (11) 151) 4 С 06 F 15 20

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4193258/24-24 (22) 09.02.87 (46) 23.08.88. Бюл, В 31 (72) П.П.Лебедев и Е.Д.Бобраков (53) 681 ° 333 (088 ° 8) (56) Авторское свидетельство СССР

)) 1174937 кл. G U6 F 15/20, 1984.

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

)) 1259281, кл. G 06 F 15/20, 1985. (54) УСТРОИСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПАРАМЕТРОВ СЕТЕВЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике и предназначено для решения задач исследования сетевых структур на графах. Цель изобретения — сокращение аппаратурных затрат. Для этого в устройство, содержащее генератор импульсов, элемент И, группу элементов задержки, счетчик, группу регистров, матрицу счетчиков и наборное поле, введены распределитель импульсов, элемент ИЛИ-и триггер..3 ил.

1418739

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

Цель изобретения — сокращение ап5 паратурных затрат.

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

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

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

В исходном статическом состоянии 25 обнуляются распределитель 2, триггер

6, регистры 8, счетчики 10 (которые выполняются таким образом, что их переполнение происходит при прохождении и-2 импульсов). В счетчик 7 заносится число, дополняющее число п-1 до его полной емкости. Если между i-й и 3-й (i < j) вершинами графа есть дуга, то между шиной 12, и ши( ной 13 устанавливается элемент 14;„

35 в проводящем направлении. Устройство определяет длины кратчайших путей от i-й, начиная с i-1 и кончая i-n-2 вершинами, до всех последующих вершин, при этом длины путей из первой во вторую вершину и из (и-1)-й в и-ю вершину не находятся, поскольку априори.известно, что длина каждого из этих путей равна единице (длины путей находятся в виде числа дуг пуф5 тей) .

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

Импульс, появляющийся на выходе элемента 4 задержки, проходит на горизонтальную шину 12 < и через элементы 14,< 14,> попадает на вертикальные шины 13, 13 . С выхода шины

13 он проходит на вход элемента 4 задержки, а с выхода шины 13 — на вход элемента 41 задержки и на информацирнный вход третьего разряда регистра 8,, в котором записывается единица . Вследствие этого нулевой потенциал с инверсного выхода указанного разряда, поступив на управляющий вход счетчика 10,, запрещает ему дальнейший счет импульсов. Содержимое (1) этого счетчика указывает длину кратчайшего пути из первой в третью. вершину графа-примера. Отметим, что нумерацию разрядов регистров 8 удобно .производить соответственно номерам вертикальных шин 13. Задним фронтом второго импульса генератора 1 в счетчик 7 и во все счетчики 10, кроме

10,, записывается еще одна единица, так что их содержимое равно двум.

Импульс, появляющийся на выходе элемента 42 задержки и элемента 43 задержки, проходит через горизонтальные шины 12, 12, элементы 14, 14<<, 14>< на вертикальные шины 13

13 и с них — на входы элементов 4, 4 задержки (на фиг.1 элемент соответствует элементу 4 „, ) и на информационные входы третьего и четвертого разрядов регистра 8,, после чего и в четвертом его разряде записывается единица, а нулевой потенциал с инверсного выхода четвертого разряда, пос-. тупив на управляющий вход счетчика

104,, запрещает ему дальнейший счет импульсов. Содержимое (2) счетчика

10, указывает длину кратчайшего пути из первой в четвертую вершину графа. Задним фронтом третьего импульса генератора 1 в счетчики 7 и

10 (кроме 10,, 10, ) записывается еще одна единица и их содержимое равно трем. Импульс, проявляющийся на выходе элемента 4 задержки, проходит через горизонтальную шину 12 (фиг.1, 12 „, ) и элемент 14 (фиг,1, 14 „,, п) на вертикальную шину 135

3 14187 (фиг ° 1, 13„) и с нее — на информационный вход пятого разряда 8,, записывая в нем единицу и обуславливая выдачу ноля на управляющий вход счет- 5 чика 10,(фиг.1-10„,), запрещая ему дальнейший счет импульсов. Содержимое (3) счетчика 10, указывает длину кратчайшего пути из первой в пятую вершину графа. После прохожде- 10 ния импульсов генератора 1 все счетчики 10, кроме 10,, 10 1, переполняются, а потому задним фронтом четвертого импульса генератора 1 счетчики 10, кроме 10,, 10,, 10, сбрасываются в " ", а счетчик 7 переполняется. Сигнал переполнения с его выхода поступает на нулевой вход триггера 6 и перебрасывает его в нулевое состояние, поэтому единичным потенциалом с инверсного выхода триггера 6 вновь открывается элемент И 3 для прохождения пятого импульса генератора 1. Этим завершается первый цикл работы устройства по нахождению 25 длин кратчайших путей из первой в третью, четвертую, пятую вершины.

Затем начинается второй цикл по нахождению длин кратчайших путей из второй в третью, четвертую и пятую вершины. Пятый импульс генератора 1 проходит через элемент И 3 на вход распределителя 2, который снимает единичный потенциал с первого выхода и выдает его по второму выходу на вход записи регистра 8, на вертикальную шину 13 и вход элемента 4 задержки и через элемент ИЛИ 5 на единичный вход триггера 6, который перебрасывается в единичное состояние и вновь закрывает элемент И 3 для прохождения следующих импульсов генератора 1. Далее устройство работает аналогично первому циклу и после прохождения пятого-восьмого импульсов генератора 1 в счетчики 10 °

104 и 10> записываются числа 1, 1, 2, указывающие длины кратчайших путей из второй вершины в третью, четвертую и пятую вершины.

Девятый импульс генератора 1 вновь 50 проходит через элемент И 3 на вход распределителя 2, который снимает единичный потенциал со второго выхода и выдает его на третий выход. Далее устройство работает аналогично 55 по нахождению длин кратчайших путей из третьей в четвертую и пятую вершины графа. После прохождения девято39

4 го и десятого импульсов генератора 1 в счетчики 10 » 10, (фиг.1,10„, „< и 10 „,„ ) оказываются записанными и,л- числа 1 и 2, указывающие длины кратчайших путей, а нулевой потенциал с инверсного выхода и-го разряда регистра 8 (фиг.1,8 „ ) поступает также на вход останова генератора 1 и прекращает работу устройства.

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

НЕ! триггер, инверсный выход которого соединен с вторым входом элемента И, вход установки в "0" триггера соединен с выходом переполнения счетчика, вход установки в "1" триггера соединен с выходом элемента ИЛИ, входы которого соединены с соответствующими выходами распределителя импульсов, вход которого соединен с выходом элемента И, а выходы соединены с входами записи соответствующих регистров группы, входами соответствующих элементов задержки группы и соответствукицими входами первой группы наборного поля, которые соединены в соответствии с топологией исследуемого графа с информационными входами регистров группы, каждый из инверсных информационных выходов К-го регистра группы (где К=1,...,М, а Мразмерность матрицы) соединен с входом разрешения соответствующего счетчика К-го столбца счетчика матрицы, инверсный информационный выход стар-. шего разряда М-го регистра группы соединен с входом останова генератора импульсов, вход запуска которого является входом запуска устройства, счетные входы счетчиков матрицы объединены и соединены с выходом генератора импульсов, выход каждого из элементов задержки группы соединен с соответствующим входом второй группы наборного поля. 1418739

Составитель О.Гречухина

Техред А.Кравчук Корректор И.Эрдейи

Редактор Г.Волкова

Заказ 4155/47 Тираж 704 Подписное

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

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

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