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

1 .1290343

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

Целью изобретения является упрощение устройства, и повьшение надежности.

На фиг. 1 приведена структурная схема устройства; фиг. 2 - сетевой 0 граф G(X, W), где X - множество вер- шин; W - множество дуг графа; на фиг, 3 - таблица, в которой для сетевого графа по фиг, 2 определены W; , Н i д% где i 1 , 2, .,, , п; W, , W - количество соответственно

Реализация такого алгоритма сводится к тому, что предварительно определяются величины W; (,n), а далее вычисляются W,. (,n) с выделением максимального значения W среди этих величин. Полученное значение W равно минимальному множеству путей, покрывающих сетевой граф.

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

10 запуска устройства, вход 11 установки нуля устройства, группу устано- ночных входов 12 устройства, дешифратор 13, группу элементов ИЛИ 14, группы элементов И 15, 16, группу элементов ИЛИ 17, группу реверсивных счетчиков 18, группу элементов 19.задержки, группу триггеров 20, элемент И 21, элементы .И 22-26,элемент ИЛИ

20

М «

ВХОДНЫХ и выходных дуг вершины X;; Wj , Wj - количество соответственно входных и выходных дуг для вершин, принадлежащих i-му рангу.

Если в сетевых графах отсутствуют петли и циклы, то задача определения минимального множества путей, покрывающих сетевой граф, адекватна оптимизационной задаче, в которой опреде- - 2 накапливающий сумматор 28, сумма- ляется максимальное число дуг, при- торы 29 и 30, регистры 31 и 32, линадлежащих разрезу 1-го ранг а среди всех рангов сетевого графа.

Пусть W. W, -w;. ; W. W--W,, Тогда W,IW. ,

Определим понятие разреза i-го ранга, Дпя подмножества вершин А,-, принадлежащих i-му рангу, характеризующегося Xj,€A., разрезом i-ro ранг сетевого графа называется множество Уд. дуг, выходящих из AJ, Количеств У. , дуг обозначим через W , т,е,

I.,Ai

w;, /УЛ,( .

Таким образом, формализованная

постановка задачи имеет следующий

+ вид: найти W niax W ,

i i

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

w;

-, . , i 0,n, причем W.i 0 для .

5

0

Реализация такого алгоритма сводится к тому, что предварительно определяются величины W; (,n), а далее вычисляются W,. (,n) с выделением максимального значения W среди этих величин. Полученное значение W равно минимальному множеству путей, покрывающих сетевой граф.

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

10 запуска устройства, вход 11 установки нуля устройства, группу устано- ночных входов 12 устройства, дешифратор 13, группу элементов ИЛИ 14, группы элементов И 15, 16, группу элементов ИЛИ 17, группу реверсивных счетчиков 18, группу элементов 19.задержки, группу триггеров 20, элемент И 21, элементы .И 22-26,элемент ИЛИ

0

- 2 накапливающий сумматор 28, сумма- торы 29 и 30, регистры 31 и 32, линию 33 задержки. Элементы И 3- , элемент ИЛИ 14; и реверсивный счетчик 18; определяют число выходных дуг

- для Х.-й вершины графа.

Триггер 6 совместно с элементами И 7, 8 и генератором 5 импульсов обеспечивают предварительный и основной режимы работы устройства, Б

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

вершины графа с помощью группы ре- версив1 ых счетчиков 18 получить результирующую величину W;,. между числом вьпсодных и входных дуг, в основном работы устройства импульсы через первый элемент И 7 поступают на управляющие входы элементов И третьей группы 15j (, п) и вход линии 33 задержки, что позволяет определить минимальное множество путей,

покрывающих сетевой граф.

Входы 12;. устройства предназначены для занесения информации о топологии моделируемого графа.

55 Элементы И 4j. совместно с элементом ИЛИ 17j и вычитающим входом счетчика 18 группы реверсивных счетчиков определяют число входных , дуг WJ для Х;-й вершины граф.

Группа элементов И 15 совместно с элементом И 21 определяет момент окончания .работы устройства (нулевое состояние всех триггеров 2-. формирователей дуг).

Группа элементов И 16 совместно с группой элементов 19 задержки, группой триггеров 20 и элементом ИЛИ 27 передают содержимое группы счетчиков 18 на вход первого сумма- тора 28.

Группа реверсивных счетчиков 18 предназначена для определения результирующего соотношения между выходными и входными дугами W для каждой вершины графа,

Группа элементов 19; задержки- реализована таким образом, что выполняется соотношение , , гдet; - задержка i-ro элемента. Выполнение такого соотношения позволяет после- овательно передавать на вход сумма- ора 28 содержимое реверсивных счетчиков 18 для вершин, принадлежащих одному и тому же рангу сетевого гра- фа.

Группа триггеров 20 обеспечивает однократную передачу содержимого реверсивных счетчиков 18j на вход первого сумматора 28 при появлении управляющего сигнала на выходе соответствующего элемента задержки, входящего в состав группы элементов 19 задержки.

Элемент И 2 определяет момент окончания работы устройства (нулевое состояние всех триггеров 2ц ) мат- ,рицы 1 формирователей дуг.

Сумматор 28 является сумматором накапливающего типа, В нем вычисля- ется результирующая величина входны и выходных дуг для вершин, принадлежащих i-му рангу.

Сумматор 29 является сумматором комбинационного типа, В нем опреде- ляется количество дуг Уд. , выходящи из подмножества верщин А|, принадлежащих разрезу i-ro ранга графа.

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

Сигналы на выходах линии 33 заде жки появляются последовательно на первом, втором и третьем выходах, причем длительность задержки на первом выходе превьщ1ает задержку последнего элемента 19„ группы элементов 19jзадержки.

Устройство для вычисления характеристик сетевых графов работает следующим образом.

Первоначально в матрицу 1 заносится информация о топологии моделируемого графа сети. При этом триггеры 2 j формирователей дуг, моделирующие ветви графа, устанавливаются в единичное состояние с помощью установочных входов устройства 12- , Соответствующие триггеры формирователей дуг определяются пересечением строки с номером, равным номеру начальной вершины моделируемой ветви и столбца с номером, равным номеру конечной верщины. После занесения исходной информации на входах элементов И группы 15, соответствующих начальным вершинам моделируемого графа, устанавливаются высокие потенциалы, так как в однонаправленном графе без циклов и петель на - чальные вершины не содержат входящих ветвей и триггеры формирователей дуг, находящиеся в этом столбце, находятся в нулевом состоянии. Триггер 6, группа триггеров 20, накапливающий сумматор 28, регистры 31 и 32 установлены в кулевое состояние с помощью сигнала на входе 11 устройства,

С появлением пускового сигнала на входе 10 устройства появляются импульсы на выходе генератора 5 импульсов. Поскольку триггер 6 находится в нулевом состоянии, то импульсы с выхода генератора 5 импульсов через элемент И 8 поступают на вход счетчика 9, что приводит к последовательному возбуждению выходных шин дешифратора 13 и поступлению уп- равлянщих сигналов на входы элементов И 3 и 4, Это позволяет подавать на суммирующие входы группы ревер-- сивных счетчиков 18с помощью элементов И и элементов ИЛИ 14 группы число импульсов, соответствующих числу выходных дуг для X,- -и верщины графа (числу единичных состояний триггеров фop в poвaтeлёй дуг 2- , расположенных в i-й строке). Аналогично на вычитающие входы группы реверсивных счетчиков 18 с помощью элементов И 4 и элементов НИИ 17 поступает число импульсов, соответ- ствуищих числу входных дуг для вершины графа (числу единичных соетояний триггеров 2- формирователей дуг, расположенных в j-м столбце), В результате на выходе реверсивных счетчиков группы 18 получается число W. , равное разности между числом выходных и входных дуг для Xj-й вершины графа.

Выходной сигнал с последней тины дешифратора устанавливает триггер 6 в единичное состояние. Это позволяет привести устройство в режим вычисле- ния минимального множества путей, покрывающих сетевой граф, В этом режиме работы импульсы через первый элемент И 7 поступают на входы элементов И группы 15 и вход линии 33 задержки. Сигнал появляется на выходе тех элементов И 15 группы, которые соответствуют вершинам, принадлежащим i-му рангу сетевого графа. Сформированные выходные сигналы сбрасывают триггеры формирователей дуг строки с номером, равным номеру столбца, и через соответствующий элемент задержки передают содержимое- реверсивного счетчика в накапливающий сумматор 28. Выполнение соотношения t- tj+, для группы элементов 19 задержки позволяет на первом суммаФормула изобретения

1, Устройство для вычисления характеристик сетевых графов, содержа щее матрицу формирователей дуг; первую группу элементов ИЛИ по числу строк матрицы форкмрователей дуг, вторую группу элементов ИЛИ по числу столбцов матрицы формирователей дуг,

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

20 информационный выход каждого j-ro

формирователя дуги каждой i-ой. строки матрицы подключен к j-му входу i-ro элемента ИЛИ первой группы (где i, j l ,2|,, , . ,п), рторой информационный

25 выход каждого j-ro формирователя дуги каяздого j-ro столбца матрицы подключены к i-му входу j-ro элемента ИЛИ второй группы, первый информационный вход каждого j-ro формировате- торе получить результирующую величину 30 ля-дуги каждой i-ой строки матрицы Wj выходных дуг для ве{)шин, принад-подключен к выходу i-ro элемента И

лежащих i-му рангу. Далее на первомпервой группы, выход каждого триггевыходе линии 33 задержки появляетсяра группы подключен к первому входу

.управляющий сигнал, позволяющий с по- одноименного элемента И второй груп- мощью элементов И 22 и 25, сумматора эг пы, отличающееся тем.

29 получить на регистре 31 число дуг W , выходящих из подмножества вер- шиЬ А., принадлежащих разрезу i-ro ранга графа (для нулевого ранга величины W и W совпадают). Сигнал с 0 триггер, элемент ИЛИ, линия задержки, восемь элементов И, накапливаючто, с целью упрощения устройства и повьгаения надежности, в устройство введены группа реверсивных счетчиков, группа элементов задержки.

второго выхода линии 33 задержки поступает на входы элементов И 23 и 24, которые совместно с сумматором 30 позволяют проанализировать соотношение величин W, и W-.. тах W ,

1 .1

с-1

причем если W .W. , то величина wr. с помощью элемента И 26 из реI

гистра 31 переписывается в регистр 32.

Вычислительный процесс продолжается до тех пор, пока все вершины графа не будут распределены по рангам. Этой ситуации соответствует сброс всех триггеров 2- формирователей дуг матрицы 1 в нулевое состояние, появление на выходе элемента И 2 высокого потенциала и прекращение работы генератора 5 импульсов.;

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

50 подключены к j-му выходу первой группы выходов дешифратора, третьи информационные входы формирователей дуг каждой i-й строки матрицы объединены и подключены к i-му выходу

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

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

1, Устройство для вычисления характеристик сетевых графов, содержащее матрицу формирователей дуг; первую группу элементов ИЛИ по числу строк матрицы форкмрователей дуг, вторую группу элементов ИЛИ по числу столбцов матрицы формирователей дуг,

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

информационный выход каждого j-ro

формирователя дуги каждой i-ой. строки матрицы подключен к j-му входу i-ro элемента ИЛИ первой группы (где i, j l ,2|,, , . ,п), рторой информационный

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

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

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

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

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

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

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

O/POHS

J/fCTMff 2/ycr ff Jjoarffff t/ff.2

ffCfffg

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

Редактор И. Рыбченко Техред Л. Сердюкова Корректор А. Обручар

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

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

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

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

cpue.3