Фонд енепертов

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

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

Зависимое от авт. свидетельства ¹.Ч. Кл. G 06f 15f32

Заявлено ОЗ.VI1.1969 (№ 1342748/18-24) с присоединением заявки №

Приоритет

Опубликовано 23.V.1973. Бюллетень ¹ 23

Дата опубликования описания 27ХП1.1973

Комитет ло делам иаооретеиий и открытий ори Совете Мииистров

CGCP

УДК 681.323(088.8) Авторы изобретения

P. П. Базилевич и Е. Ф. Замора

Львовский ордена Ленина политехнический институт

Заявитель

СПЕЦИАЛИЗИРОВАННАЯ ЭЛЕКТРОННАЯ МАШИНА

ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕДАЧИ ГРАФА

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

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

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

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

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

«И» 7, элементы «ИЛИ» 8 и 9, кнопку 10 установки исходного состояния.

Выход генератора 8 одиночных импульсов соединен с одним входом элемента «И» 7 и входом триггера 4, служащим для перевода его в рабочее состояние. Второй вход элемен5 та «И» 7 соединен со статическим выходом триггера 4, на котором имеется единичный сигнал в рабочем состоянии триггера. Выход элемента «И» 7 соединен с одним входом элемента «ИЛИ» 9, второй вход которого соеди10 нен с выходом конца поиска пути блока 1.

Выход элемента «ИЛИ» 9 соединен с запускающим входом блока 2 раскрытия определителей.

15 Динамический выход триггера 4, на котором образуется сигнал при переходе триггера в рабочее состояние, соединен с одним входом элемента «ИЛИ» 8. Второй вход элемента

«ИЛИ» 8 соединен с выходом блока 2. Вы20 ход элемента 8 соединен с запускающим входом блока 1 поиска путей. Входы установки исходного состояния блока 1 и блока 2 соединены через кнопку 10 с источником напряжения Ес. С этим же источником через кноп25 ку 10 соединен вход установки нерабочего состояния триггера 5 и одна клемма первого переключателя б (б — 1), две вторые клеммы которого соединены с разными входами триггера 4. Одна клемма второго переключателя б

30 (б — 2) соединена со входом установки рабо383055

15

25

30 чего состояния триггера 5, две вторые — с выходами блоков 1 и 2 соответственно.

Блок 1 поиска путей (см. фиг. 2) содержит матрицу I, состоящую из п строк по (и — 1) функциональных ячеек 11 (ФЯП, n — наибольший возможный порядок графа), размещенных на пересечениях всех строк и столбцов, кроме соответствующих главной диагонали (слева вниз направо); триггер 12 запуска, и программирующий сдвоенных переключателей 13 задания начальной вершины путей, подчиненных строкам матрицы функциональных ячеек п программирующих сдвоецных переключателей 14 задания конечной вершины путей, подчиненных столбцам матрицы функциональных ячеек, разделительных диодов 15.

Каждая функциональная ячейка 11 содержит триггер 1б с индикатором состояния, управляемый переключатель 17, реализованный двумя логическими элементами «И» и логическим элементом «НЕ», программирующий выключатель ячейки 18, логические элементы

«ИЛИ» 19, «ИЛИ» 20, усилитель 21.

Блок 2 раскрытия определителей (см. фиг.

3) содержит управляемую матрицу II, состоящую из п строк и и столбцов функциональных ячеек 22 (ФЯО 11 — ФЯО пи), триггер

23 запуска, и первых управляемых переключателей строк, реализованных логическими элементами «И» 24 и «И» 25, п вторых управляемых переключателей строк, реализованных логическими элементами «И» 2б и «И» 27, п логических элементов «И» 28 на пвходов,,и логических элементов «НЕ» 29, разделительные диоды 80, логический элемент «ИЛИ» 31 и триггер 82 с индикатором «запись».

Каждая функциональная ячейка 22 содержит триггер 88 с индикатором состояния, управляемый переключатель 84, логические элементы «ИЛИ» 85 и «ИЛИ» 8б.

Знакоискатель III содержит схему параллельного выделения сигналов инверсий 87, параллельный сумматор 88 и индикатор 89 знака. Схема параллельного выделения сигналов инверсий 87 содержит матрицу, образующую сравниваемые сигналы, и (n — 1) матриц выделения сигналов инверсий отдельных элементов найденного слагаемого, Матрица, образующая сравниваемые сигналы, состоит из п строк по (n — 1) элементов «ИЛИ» 40 в каждой строке (см. фиг. 4,а), Матрица выделения сигналов инверсий и-ro элемента слагаемого (см. фиг. 4,б) содержит (и — 1) строк из и элементов «И» 41, подчиненных первым (п — 1) строкам матрицы, образующей сравниваемые сигналы. Матрица выделения сигналов инверсий (n — 1) элемента слагаемого содержит (и — 2) строк из п элементов «И»

41, подчиненных первым (п — 2) строкам матрицы, образующей сравниваемые сигналы и т. д. Матрица выделения сигналов инверсий второго элемента слагаемого содержит одну строку из п элементов «И» 41, подчиненную

65 первой строке матрицы, образующей сравниваемые сигналы.

Один вход каждого элемента «ИЛИ» 40 соединен с выходом Т одной строки и одного столбца функциональной ячейки 22 блока раскрытия определителей. Второй вход этого элемента — с выходом следующего в строке такого же элемента. Один вход каждого элемента «И» 41 одного столбца матрицы выделения сигналов инверсий i-го элемента слагаемого соединен с выходом Т функциональной ячейки 22, находящейся в том же столбце и (i+1) -ой строке. Второй вход каждого элемента «И» 41 соединен с выходом элемента

«ИЛИ» 40 одного столбца и одной строки (через разъем р). Выходы элементов «И» 41 одной строки соединены вместе и подключены к параллельному сумматору 88. Общее количество входов, подводимых к сумматору 38, равно (и — 1) + (и — 2) +... + 2 + 1 = " г

Сумматор 38 является произвольным (и — 1) и матором параллельного действия на г входов.

Машина предназначена для автоматического определения в общем виде передачи графа, т. е. раскрытия выражения

Х

Л где P< — передача к-го пути от источника к стоку, Л вЂ” определитель графа, Лд — алгебраическое дополнение к-го пути (т. е. определитель подграфа, не инцидентного к-му пути).

Для программирования задачи необходимо переключатель 18 всех ячеек 11 (ФЯП), подчиненных наличным дугам графа, перевести во включенное положение. Дуге графа, выходящей из i-ой вершины и заходящей в /-ую вершину, подчинена ячейка ФЯП-ij (где

i=1...n, j=l...n). Сначала осуществляется раскрытие числителя в выражении передачи, следовательно, переключатель б рода работ должен быть в положении «ХР Л ». Кроме этого, переводят во включенное положение переключатель 13 строки, подчиненной вершине-источнику, и переключатель 14 столбца, подчиненного вершине-стоку. После этого нажимают кнопку 10 установки исходного состояния. При этом на все триггеры устройства поступает сигнал, устанавливающий их в исходное (нерабочее) состояние. Далее нажимают кнопку генератора 3 одиночных импульсов.

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

«ИЛИ» 8 и клемму 42 блока 1 поиска путей поступает к триггеру 12. Триггер 12 опрокинется и образующийся на его выходе сигнал

383055

15

45 пройдет через включенный при программировании переключатель 18 и поступит на матрицу ячеек 11. Матрица этих ячеек осуществит поиск первого пути и фиксирует его переходом триггеров ячеек, подчиненных лугам п ти, в рабочее состояние. На выходах д всех ячеек этой MBTpHIIbl, находящихся в стпоках и столбцах, номера которых совпалают с номерами вершин первого пути, образуется сигнал. который попадает на такой же вхол ячеек 22 блока 2 раскрытия определителей и заблокирует эти ячейки. Это значит, что па блоке 2 будет автоматически запрограммиповано алгебраическое лополнение к первому найденному пути.

После определения первого пути в результате опрокидывания триггера ячейки, подач пенной послелней ветке пути, на выходе 48 блока 1 ооразуется сигнал. Этот сигнал пройдет через элемент «ИЛИ» 9 и попялет на вход

44 олока 2 раскрытия определителей. В олоке

2 он попалет на триггер 28 и оппокинет его.

На выходе этого триггера обарзуется сигнал, которьш пройлет к матрице ячеек 22, гле б .— лет осуществлен поиск первого слагаемого алгебраического дополнения, в результате чего загорится индикатор «запись» триггера 82.

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

88 определит четность этого числа, что булет зафиксировано на инликаторе 89 знака.

Запись элементов пепвого слагаемого ociществляют по загоревшимся индикатопам ячеек 11 (элементы п ти) и ячеек 22 (элементы алгеораического дополнения). После записи первого найденного слагаемого нажимают кнопку генератора 8. Образовавшийся пп этом втопой имп льс генератора через элементы «И» 7 и «ИЛИ» 9 поступает непоспсзственпо на блок 2 раскрытия опрелелителег", гле осуществляется поиск следующего Г.лягаемого и т, д.

После опрелеления всех слагаемых числителя на выходе 45 блока 1 образуется сигнал, который пройдет через переключатель 6 опрокинет триггер 5, в результате чего загорится индикатор конца поиска.

Для раскрытия знаменателя выпяжения передачи необходимо пепеключатель б перевести в положение «Л». После нажатия кнопки

10 триггер 4 установится спазу в рабочее состояние. при котором с этого триггепа на элемент «И» 7 подается единичный сигнал. Ппи нажатии кнопки генератора 8 пепвый и все последующие импульсы будут поступать чепез элементы «И» 7 и «ИЛИ» 9 к блоку 2 раскрытия определителей. Следовательно, булет осуществлено раскрытие полного оппелелптеля графа.

Предмет изобпетения

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

«ИЛИ» с запускающим входом блока поиска путей, выхол которого cop÷÷íåí чепез втопой логический элемент «ИЛИ» с запускающим входом блока раскрытия определителей, выход котопого через первый,логический элемент «ИЛИ» полключен и запускаю.нему вход блока поиска п тей.

2. Машина по п. 1, отличаю цаяся тем. что выхол каждой функциональной ячейки блока поиска путей соелинен через пепеключятель задания конечной вершины î lllol о столбца со

Bxo IoM первой ячейки строки, помоp которой совпалает с номером столбца рассматриваемой ячейки.

383055

)777

1(n -0 р(п-1) ) pal-1)Г pfll-f){r ) p(i2 1)п

Г 7 7) 7 Т(п-1)2 ТРЯ(П 7) 1 Т(п-1)л рпп

Составитель Н. Гузеикова

Текред Е. Борисова

Корректор В. Жолудева

Редактор Е. Гончар

3 ак аз 2338 5 Изд. М 617 Тираж 647 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, )К-35, Раугнская иаб., д. 475

Типография, пр. Сапунова, 2