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

СХ)

1

со со

114

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

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

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

I Устройство содержит (фиг.1) гене- piaTop 1 импульсов, распределитель 2 Импульсов, элемент ИЗ, группу эле- i eHTOB 4 задержки, элемент ИЛИ 5, триггер 6, счетчик 7, группу регист- lioB 8, матрицу 9 счетчиков 10, набор- йое поле 11, состоящее из горизон- Тальных 12 и вертикальных 13 шин и Элементов 14 связи. Устройство работает следующим Образом.

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

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

тенциалом со своего инверсного выхода закрывает элемент И 3 для прохождения следующих импульсов генератора 1. При прохозадении заднего фронта первого импульса в счетчик 7 и во все счетчики 10 записывается единица.

Импульс, появляющийся на выходе элемента 4, задержки, проходит на

горизонтальную шину 12 , и через элементы 14,2 1Э попадает на вертикальные шины 13, 13. С выхода шины 13 он проходит на вход элемента 4 задержки, а с выхода шины 13, - на

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

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

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

графа. Задним фронтом третьего импульса генератора 1 в счетчики 7 и 10 (кроме 10,, , ) записывается еще одна единица и их содержимое равно трем. Импульс, проявляющийся

на выходе элемента 4 задержки, проходит через горизонтальную шину 124 (фиг.1, 12(,-| ) и элемент 14 (фиг.1, . ) вертикальную шину 13

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

25

5(

ну кратчайшего пути из первой в пятую вершину графа После прохоязде- ния импульсов генератора 1 все счетчики 10, кроме Юз, , 1041 ) переполняются, а потому задним фронтом четвертого импульса генератора 1 счетчики 10, кроме 10 3, , 10, , lOji I сбра- 15 сываются в Q, а счетчик 7 переполняется. Сигнал переполнения с его выхода поступает на нулевой вход триггера 6 и перебрасывает его в нулевое состояние, поэтому единичным 20 потенциалом с инверсного в ыхода триггера 6 вновь открывается элемент И 3 для прохождения пятого импульса гене ратора 1, Этим завершается первьй цикл работы устройства по нахождению длин кратчайших путей из первой в третью, четвертую, пятую верпшны. Затем начинается второй цикл по на- хоядению длин кратчайших путей из второй в третью, четвертую и пятую вершины. Пятый импульс генератора 1 проходит через элемент И 3 на вход распределителя 2, который снимает единичньш потенциал с первого выхода и вьщает его по второму выходу на вход записи регистра 8, на вертикальную шину 13j и вход элемента 4 задержки и через элемент ИЛИ 5 на единичный вход триггера 6, который перебрасывается в единичное состояние и вновь закрывает элемент И 3 для прохождения следующих импульсов генератора 1. Далее устройство работает аналогично первому циклу и после прохоящения пятого- восьмого импульсов генератора 1 в счетчики lOjj и 1052 записываются числа 1, 1, 2, указывающие длины кратчайших путей из второй вершины в третью, четвертую и пятую вершины.

30

35

40

45

импульсов генератора 1 45 , lOsj (фиг.1,10п.,„..г

го и десятого в счетчики 10

и Ю.- оказываются записанными числа 1 и 2, указывающие длины кратчайших путей, а нулевой потенциал с инверсного выхода п-го разряда регистра 8j (фиг.1,) поступает так- ;ке на вход останова генератора 1 и прекращает работу устройства.

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

Устройство для исследования пара-« метров сетевых графов, содержащее элемент И, счетчик, группу регистров, матряЬ,у счетчиков, группу элементов задержки, наборное поле, первая и вторая группы входов которого соединены в соответствии с топологией исследуемого графа, генератор импуль- сов, выход которого соединен с первым входом элемента И,отличающее с я тем, что, с целью сокращения аппаратурных затрат, оно содержит распределитель импульсов, элемент ИЛИ, триггер, инверсньй выход которого соединен с вторым входом элемента И, вход установки в О триггера соединен с выходом переполнения счетчика, вход установки в 1 триггера соединен с выходом элемента ИЛИ, входы которого соединены с соответствующими выходами распределителя импульсов , вход которого соединен с выходом элемента И, а выходы соединены с входами записи соответствующих регистров группы, входами соответствующих элементов задержки группы и соответствующими входами первой группы наборного поля, которые соединены в соответствии с топологией исследуемого графа с информационными входами регистров группы, казццый из инверсных информационных выходов К-го регистра группы (где ,.о.,М, а М - размерность матрицы) соединен с входом разрешения соответствующего счетчика К-го столбца счетчика матрицы, инверсный информационный выход стар- шего разряда М-го регистра группы

Девятый импульс генератора 1 вновь 50 соединен с входом останова генератора

,

0

5

5 0

30

35

40

45

импульсов генератора 1 45 , lOsj (фиг.1,10п.,„..г

го и десятого в счетчики 10

и Ю.- оказываются записанными числа 1 и 2, указывающие длины кратчайших путей, а нулевой потенциал с инверсного выхода п-го разряда регистра 8j (фиг.1,) поступает так- ;ке на вход останова генератора 1 и прекращает работу устройства.

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

Устройство для исследования пара-« метров сетевых графов, содержащее элемент И, счетчик, группу регистров, матряЬ,у счетчиков, группу элементов задержки, наборное поле, первая и вторая группы входов которого соединены в соответствии с топологией исследуемого графа, генератор импуль- сов, выход которого соединен с первым входом элемента И,отличающее с я тем, что, с целью сокращения аппаратурных затрат, оно содержит распределитель импульсов, элемент ИЛИ, триггер, инверсньй выход которого соединен с вторым входом элемента И, вход установки в О триггера соединен с выходом переполнения счетчика, вход установки в 1 триггера соединен с выходом элемента ИЛИ, входы которого соединены с соответствующими выходами распределителя импульсов , вход которого соединен с выходом элемента И, а выходы соединены с входами записи соответствующих регистров группы, входами соответствующих элементов задержки группы и соответствующими входами первой группы наборного поля, которые соединены в соответствии с топологией исследуемого графа с информационными входами регистров группы, казццый из инверсных информационных выходов К-го регистра группы (где ,.о.,М, а М - размерность матрицы) соединен с входом разрешения соответствующего счетчика К-го столбца счетчика матрицы, инверсный информационный выход стар- шего разряда М-го регистра группы

0 соединен с входом останова генератора

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

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

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

Фи.1

Фи9.3