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

 

Изобретение относится к вычислительной технике и может быть использовано для определения расстояний между вершинами ориентированных графов, являютдихся математическими моделями сетей связи, информационно расчетных систем и т,д. Цель изобретения - расширение функцио нальных возможностей устройства за счет определения длины путей между вершинами ориентированного графа, Устройство содержит группу из п элементов И, группу из п регистров, матрицу из пхп элементов И, вход Начальная установка, элемент ИЛИ-НЕ, дешифратор, генератор тактовых импульсов , счетчик, два,элемент И, вход Запуск, наборное поле, коммутирующие элементы, вертикальные и горизонтальные шины наборного поля . Поставленная цель достигается введением генератора тактовых импульсов , п групп по п индикаторных счетчиков, группы элементов задержки . 4 ил. i IS9 СП со to 00

„„SU„„1259281 А 1

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

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

РЕСПУБЛИК (5946 6 Р 15 20

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

f10 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

H. АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (2I) 3857442/24-24 (22) 20.02,85

,46) 23.09 ° 86 ° Бюл. 9 35 (72) Е. И. Бороденко, В. E. Назаренко и В. В, Рыбка (53) 681. 333(088. 8) (56) Авторское свидетельство СССР

И 943738, кл. G 06 F 15/20, 1982, Авторское свидетельство СССР

Ф 1174937> кл. G 06 F 15/20, 1984. но расчетных систем и т.д. Цель изобретения — расширение функциональных возможностей устройства за счет определения длины путей между вершинами ориентированного графа.

Устройство содержит группу из и элементов И, группу из и регистров, матрицу из п п элементов И, вход "Начальная установка, элемент ИЛИ-НЕ, дешифратор, генератор тактовых импульсов, счетчик. два,элемент И, вход "Запуск", наборное поле, коммутирующие элементы, вертикальные и горизонтальные шины наборного поля. Поставленная цель достигается введением генератора тактовых импульсов, и групп по и индикаторных счетчиков, группы элементов задержки. 4 ил. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПАРАМЕТРОВ ОРИЕНТИРОВАННЫХ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для определения расстояний мекду вершинами ориентированных графов, являюшихся математическими моделями сетей связи, информационОПИСАНИЕ ИЗОБРЕТЕНИЯ / "

1259281

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

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

На фиг. 1 представлена функциональная схема устройства для исследования параметров ориентированных графов, на фиг. 2 — пример графа G(X,A); на фиг. 3 — матрица расстояний графа; на фиг. 4 — временные диаграммы, поясняющие принцип работы устройства, Устройство содержит группу элемен-, тов 1 - 1„задержки, группу H3 Il элементов И 2 (и -максимально возможное количество вершин графа), и групп по и индикаторных счетчиков 3, 3 4 -4 регистров 8,-8„:, матрицу из и х и элементов И 9 9н Щ 10ь !11, 11л

12,-12„, 13, -13„, вход "Начальная установка" 14, элемент ИЛИ-НЕ 15, дешифратор 16, генератор 17 пакетов импульсов, счетчик 18, элемент И 19, элемент И. 20, генератор 21 тактовых импульсов, вход "Запуск" 22, наборное полу 23 и коммутирующие элементы 24.

Наборное поле содержит п вертикальных 25 и п горизонтальных 26 шин, которые через коммутирующие элементы 24 соединены между собой в соответствии с топологией исследуемого графа, один вывод вертикальных шин наборного поля 23 подключены к первым входам группы элементов И

2„-2,„, выходы з.-го элемента И группы 2„ -2„ соединены с первыми входами элемента И 1-й строки .матрицы п.п элементов И 9„-9„, 10, -10„, ll l1 l2 l2 13 13 д

1 элементов И g-ro столбца соединены с одноименными информационными входами J-ro регистра 8, вход начальной установки счетчика 18 соединен с входами начальной установки регистров 8 и является входом "Начальная установка" 14 устройства, счетный вход счетчика. 18 подключен к. выходу первого элемента И 19, первый и

3S второй входы которого соединены соответственно с выходом второго элемента И 20 и выходом элемента ИЛИ-НЕ 15, который подключен .также к вторым входам элементов И 2 -2 а вход эле1 П мента ИЛИ-НЕ 15 соединен с (и+1)-м выходом дешифратора 16, выход счетчика 18 подключен к входу дешифратора 16, первый вход первого элемента И 20 является входом "Запуск" 22 устройства, второй вход второго эле,мента И 20 подключен к выходу генератора 21 тактовых импульсов, а

j-й ()=1,2,...,n) выход дешифратора 16 соединен с первыми входами элементов И J-ro столбца матрицы и и элементов И 9.„-9„, 10, -10„, 11„-11Ä 2 -12, 13, -13, выходы элементов 1, -1„ задержки соединены с горизонтальными шинами 25 наборного поля 23, а входы соединены с выходами соответствующих элементов И, группы 2„ -2„, вход запуска генератора 17 пакетов импульсов соединен с выходом второго элемента И

19, а выход соединен с информационными входами соответствукяцих индикаторных счетчиков 3 -3, 4„-4„, 5„.-5;, 6, -6>, 7 -7, входы сброса которых соединены с соответствующими выходами регистров 8„-8„.

Генератор 17 пакетов импульсов вырабатывает пакеты из п импульсов и запускается задним фронтом тактового импульса с генератора 21. Период следования импульсов в пакете равен с В.1

ch2 П где,„ „ — период следования тактовых импульсов генератора 21, Элементы — 1„ задержки обеспечивают время. задержки, равное +

ch2

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

Предварительно на наборном поле 23.набирается структура исследуемого графа при помощи коммутирующих элементов 241 Если между вершинами х,; и х„" есть ребро, то между j.-й горизонтальной и g-й вертикальной пинами устанавливается элемент 24 в проводящем направлении. По входу 14

5 подается импульс, который устанавливает в нулевое состояние счетчик 18 регистры 8, -8„. Индикаторные счетчи125928! 4 торые находятся не в нулевом состоянии, сбрасываются в нулевое состояние при переходе соответствующего разряда регистров 8,-8„ из "1" в "О".

На вход элемента ИЛИ-НЕ 15 коммутируется (К+1)-й выход дешифратора, где К вЂ” количество вершин в исследуемом графе. Максимальное количество вершин равно числу и, После этого устройство готово к работе. 1О

При. подаче на вход 22 единичного .потенциала через второй элемент И 20 начинают проходить тактовые импульсы с.генератора 21, Тактовые импульсы с выхода элемента И 20 поступают на один вход элемента И 19, на другой вход которого подается единичный потенциал с выхода элемента ИЛИ-НЕ 15. .Тактовые импульсы с выхода элемента И 19 поступарт на счетный вход 20 счетчика 18. В зависимости от состояния счетчика 18 на соответствующем выходе дешифратора появляется единичный потенциал, который открывает элементы И соответствующего 25 столбца матрицы nVn элементов И

9,, -96, 10! -10„, 11 -11„, !2 -12„, 13, -13 соответствующего регистра

8,,-8„, а также подается на вход соответствующей вертикальной шины наборного поля 23 ° Выходы вертикальных шин наборного поля 23 подключены к первым входам элементов И 2„ -2„, на вторые входы которых подается единичный потенциал с выхода инвер35 тора 15. Тактовые импульсы с выхода элемента И 19 поступают на управля-. ющий вход генератора 17 пакетов импульсов,и задним входом запускают генератэр после чего тот выдает паЭ

40 кет из и импульсов, задержанных относительно начала тактового импульI са на величину 1,,>1 =,;, (фиг. 4 г и д), Счетчики 3,-3„, 4, -4„, 5 -5,„, 6 -61„7 -7, рассчитаны на подсчет и 45 (n-1)-ro импульса, так как максимальиый путь в графе между двумя вершинами равен п-1, где n — количество вершин в графе. С приходом п-го импульса счетчики сбрасываютt 50 ся в нулевое состояние.

Пример работы устройства. Исследуемый граф изображен на фиг. 2, временные диаграммы работы устройства — на фиг. 4.

При.поступлении первого тактового импульса на первом выходе дешифрато- . ра появляется напряжение логической единицы ("фиг. 4б). Генератор пакетов импульсов запускается и выдает. пакет из и импульсов (фиг, 4г}. Напряжение логической "1" с первого выхода дешифратора 16 поступает на первые входы элементов И 9, -91, и открывает их. Кроме того,;это же напряжение поступает на один вывод первой вертикальной шины 25, наборного поля 23, на котором набрана топология исследуемого графа (фиг. 1). С другого вывода шины 25, это напряжение поступает на элемент И 2,„, который открыт напряжением логической "1" с выхода элемента ИЛИ-НЕ 15, С выхода элемента И 2 (фиг. 4д) напряжение логической " 1" поступает на схему И 9 и записывает в первый

1 разряд регистра 8 "1". Кроме того, это напряжение поступает на линию 1„» задержки и через нее задержанное время -t, „ — на горизонтальную шину 26, наборного поля 23. Напряжение логической "1" с инверсного выхода первого разряда регистра 8, при его переходе в единичное состояние пропадает (фиг. 4е), запрещая тем самым запись в индикаторный счетчик 3, импульсов с генератора 17 так как первый импульс пакета saдержки на величину Т 3 1 =t (фиг. 4д и а). Первый импульс пакета записыается ao ace счетчики 3,-3, 4 -4

5,-5„, 6, -6„, 7, -7„, кроме счетчика 3i.

Напряжение логической "1" с горизонтальной шины 26 наборного по"

1 ля 23 через элемент 24,, попадает на вертикальную шину 25, через элемен" ты И 2 и 9 записывает "1". в третий разряд регистра 81 и запрещает дальнейшую запись импульсов в счетчик 33 (фиг. 4з). Поэтому второй импульс запишется только в счетчике 3,3„

Напряжение логической "1" с выхода элемента И 23 поступает на вход линии 1 задержки и через нее — на

3 горизонтальную шину 26 наборного поля 23, а затем через коммутирующий элемент 24>, элемент И 2, записывает в четвертый разряд регистра 8„

"1", запрещая тем самым дальнейшую запись импульсов в счетчик 34 (фиг. 4к). После этого во все счетчики, кроме счетчиков Зу, 3 и 34,, запишутся и-1 импульсов, а затем и-й импульс, сбросив их содержимое в "0"

S 1

Таким образом, в первой строке матрицы расстояний после первого такта. работы (счетчики 3, -3 ) будет

1 записано 0012 (фиг. 3), а во всех остальных счетчиках будут записаны нули. Аналогично будет работать устройство и во втором, третьем и четвертом тактах, С приходом пятого тактового импульса на пятом выходе дешифратора 16, который скоммутирован на вход элемента ИЛИ-НЕ 15, по,является напряжение логической I" которое через элемент ИЗИ-НЕ 15 запрещает дальнейшую работу устройства.

В первых четырех разрядов регистров

8,, 82, 8 . и 8„ записывается матрица достижимостей графа (фиг. 2), а в индикаторных счетчиках 3, -3„, 4,-4,, 5,-5, б, -6,записывается

Ф . матрица расстояний (фиг, 3) исследуемого графа (фиг, 2). Во всех остальнь х разрядах регистров и счетчиках будут записаны нули.

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

Устройство для исследования параметров ориентированных графов, содержащее генератор тактовых импульсов, группу из и элементов И (rpe n — максимально возможное количество исследуемого графа), два эле-. мента И, матрицу пвп элементов И, элемент ИЛИ-НЕ, дешифратор, счетчик, п регистров, коммутирующие элементы, наборное поле, содержащее вертикальные и горизонтальные шины, горизонтальные шины. наборного поля через коммутирующие элементы соединены с соответствующими вертикальными шинами в соответствии с монологией графа, один выход каждой вертикальной шины наборного поля подключен к первому входу одноименного элемента И группы, выход которого подключен к первым входам элемента И одноименной строки матрицы из ns n элементов И, вторые входы всех элемен259281 Ь тов И группы объединены и подключены к выходу элемента ИЛИ-HE выхщт каждого i-ro элемента И каждого дго столбца матрицы из п п элемен5 тов И подключен к i-му информационному входу группы входов 1-го регистра (где i, J=-1, 2, 3,...; п) входы начальной установки всех регистров и счетчика объединенй и являются

10 входом начальной установки устройст- ва, счетный вход счетчика. соединен с выходом первого элемента И, первый вход которого подключен к выходу второго элемента И, а второй выход—

1s к выходу элемента ИЛИ-НЕ, группа входов которого подкл1очена к выходам дешифратора, выход счетчика подклю чен к входу дешифратора, первый вход второго элемента И.является входом

20 запуска устройства, а второй вход подключен к выходу генератора тактовых импульсов, вторые входы всех элементов И каждого )-ro столбца матрицы из n"n элементов И объединен ны и подключены к j-му выходу дешифратора, другой выход каждой вертикальной шины наборного поля подключен к одноименному выходу дешифратора, о т л и ч а ю щ е е с я тем, ЗО что, с целью расширения функциональных воэможностей за счет определения длины пути между вершинами, в него введены генератор пакетов импульсов, и групп индикаторных счетчиков по и счетчиков в каждой, группа из п эле35 ментов задержки, выходы которых соединены с горизонтальными шинами наборного поля, а.вход каждого эле мента задержки группы подключен к

4О выходу одноименного элемента И группы, вход запуска генератора запуска пакетов импульсов подключен к выходу первого элемента И, а выход подключен к счетным входам всех индикатор4S ных счетчиков группы, вход сброса каждого i-го индикаторного счетчика

Ф каждой i-й группы подключен к --му выходу группы выходов j-го регистра.!

259281

1259281

1 2

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

Редактор Н, Яцола Техред И.Попович Корректор И. Муска

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

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

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

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