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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советских Социалистических РеспубликК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Зависимое от авт. свидетельстваЗаявлено 03.711.1969 ( 1342748/18-24) Ч. Кл. С 061 15,РЗ с присоединением заявкиПриоритетОпубликовано 23.7.1973, Бюллетень23Дата опубликования описания 27 Х 1 П.1973 Комитет ло деламобретеиий и открытийи Совете МииистровСССР УДК 681,323(088,8) АвторыизобретенияЗаявитель Р. П. Базилевич и Е. ф. Заморавовский ордена Ленина политехнический институт СПЕЦИАЛИЗИРОВАННАЯ ЭЛЕКТРОННАЯ МАШИ ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕДАЧИ ГРАФА Изобретение относится к области специали. зированной цифровой вычислительной техники и предназначено для автоматического определения в общем виде передачи графа.Известны устройства, предназначенные для автоматического решения указанной задачи.Цель изобретения - увеличение быстродействия специализированной электронной машины. Для этого предлагаемая машина содержит блок поиска путей, обеспечивающий определение путей с каждым тактом; блок раскрытия определителей, обеспечивающий определение слагаемых с каждым тактом; При этом блок раскрытия определителей содержит знакоискатель, состоящий из схемы одновременного выделения всех сигналов инверсий.На фиг. 1 приведена функциональная схема машины; на фиг, 2 - функциональная схема блока поиска путей; на фиг. 3 - функциональная схема блока раскрытия определителей и на фиг. 4 - функциональная схема знакоискателя.Функциональная схема машины (см. фиг. 1) содержит блок 1 поиска путей, блок 2 раскрытия определителей, генератор 8 одиночных импульсов, управляющий триггер 4, триггер б конца поиска с индикатором состояния, сдвоенный переключатель б рода работ, элемент И 7, элементы ИЛИ 8 и 9, кнопку 10 установки исходного состояния. Выход генератора 8 одиночных импульсовсоединен с одним входом элемента И 7 и входом триггера 4, служащим для перевода его в рабочее состояние. Второй вход элемен та И 7 соединен со статическим выходомтриггера 4, на котором имеется единичный сигнал в рабочем состоянии триггера. Выход элемента И 7 соединен с одним входом элемента ИЛИ 9, второй вход которого соеди- О нен с выходом конца поиска пути блока 1,Выход элемента ИЛИ 9 соединен с запускающим входом блока 2 раскрытия определителей. 5 Динамический выход триггера 4, на котором образуется сигнал при переходе триггера в рабочее состояние, соединен с одним входом элемента ИЛИ 8. Второй вход элемента ИЛИ 8 соединен с выходом блока 2. ВыО ход элемента 8 соединен с запускающим входом блока 1 поиска путей. Входы установки исходного состояния блока 1 и блока 2 соединены через кнопку 10 с источником напряжения Ес. С этим же источником через кноп ку 10 соединен вход установки нерабочего состояния триггера б и одна клемма первого переключателя б (б - 1), две вторые клеммы которого соединены с разными входами триггера 4. Одна клемма второго переключателя б О (б - 2) соединена со входом установки рабочего состояния триггера 5, две вторые - с выходами блоков 1 и 2 соответственно.Блок 1 поиска путей (см. фиг. 2) содержит матрицу 1, состоящую из и строк по (и - 1) функциональных ячеек 11 (ФЯП, п - наибольший возможный порядок графа), размещенных на пересечениях всех строк и столбцов, кроме соответствующих главной диагонали (слева вниз направо); триггер 12 запуска, п программирующий сдвоенных переключателей 13 задания начальной вершины путей, подчиненных строкам матрицы функциональных ячеек п программирующих сдвоенных переключателей 14 задания конечной вершины путей, подчиненных столбцам матрицы функциональных ячеек, разделительных диодов 15. 5 10 15 2030 35 40 45 50 55 60 65 Каждая функциональная ячейка 11 содержит триггер 1 б с индикатором состояния, управляемый переключатель 17, реализованный двумя логическими элементами И и логическим элементом НЕ, программирующий выключатель ячейки 18, логические элементы ИЛИ 19, ИЛИ 20, усилитель 21.Блок 2 раскрытия определителей (см. фиг.3) содержит управляемую матрицу П, состоящую из п строк и п столбцов функциональных ячеек 22 (ФЯО 11 - ФЯО пи), триггер 23 запуска, п первых управляемых переключателей строк, реализованных логическими элементами И 24 и И 25, п вторых управляемых переключателей строк, реализованных логическими элементами И 2 б и И 27, и логических элементов И 28 на и входов, и логических элементов НЕ 29, разделительные диоды 30, логический элемент ИЛИ 31 и триггер 32 с индикатором запись.Каждая функциональная ячейка 22 содержит триггер 33 с индикатором состояния, управляемый переключатель 34, логические элементы ИЛИ 35 и ИЛИ 3 б.Знакоискатель П 1 содержит схему параллельного выделения сигналов инверсий 37, параллельный сумматор 38 и индикатор 39 знака. Схема параллельного выделения сигналов инверсий 37 содержит матрицу, образующую сравниваемые сигналы, и (и - 1) матриц выделения сигналов инверсий отдельных элементов найденного слагаемого, Матрица, образующая сравниваемые сигналы, состоит из п строк по (и - 1) элементов ИЛИ 40 в каждой строке (см. фиг. 4,а), Матрица выделения сигналов инверсий и-го элемента слагаемого (см. фиг. 4,б) содержит (и - 1) строк из и элементов И 41, подчиненных первым (и - 1) строкам матрицы, образующей сравниваемые сигналы, Матрица выделения сигналов инверсий (п - 1) элемента слагаемого содержит (и - 2) строк из п элементов И 41, подчиненных первым (и - 2) строкам матрицы, образующей сравниваемые сигналы и т. д. Матрица выделения сигналов инверсий второго элемента слагаемого содержит одну строку из и элементов И 41, подчиненную первой строке матрицы, образующей сравниваемые сигналы.Один вход каждого элемента ИЛИ 40 соединен с выходом Т одной строки и одного столбца функциональной ячейки 22 блока раскрытия определителей. Второй вход этого элемента - с выходом следующего в строке такого же элемента, Один вход каждого элемента И 41 одного столбца матрицы выделения сигналов инверсий -го элемента слагаемого соединен с выходом Т функциональной ячейки 22, находящейся в том же столбце и (+1)-ой строке. Второй вход каждого элемента И 41 соединен с выходом элемента ИЛИ 40 одного столбца и одной строки (через разъем р). Выходы элементов И 41 одной строки соединены вместе и подключены к параллельному сумматору 38. Общее количество входов, подводимых к сумматору 38, равно(и 1) + (и 2)+ 2 + 1 (и 1) и2Сумматор 38 яВляется произвольным суом(и - 1) и матором параллельного действия на2ВХОДОВ.Машина предназначена для автоматического определения в общем виде передачи графа, т. е, раскрытия выраженияТ = - Х Р,ь1Ьгде Рк - передача к-го пути от источника кстоку,Ь - определитель графа,Лд - алгебраическое дополнение к-го пути (т, е. определитель подграфа, не инцидентного к-му пути).Для программирования задачи необходимо переключатель 18 всех ячеек 11 (ФЯП), подчиненных наличным дугам графа, перевести во включенное положение. Дуге графа, выходящей из 1-ой вершины и заходящей в 1-ую вершину, подчинена ячейка ФЯП(где г=1 п, 1=1 и). Сначала осуществляется раскрытие числителя в выражении передачи, следовательно, переключатель б рода работ должен быть в положении ХРЬ, Кроме этого, переводят во включенное положение переключатель 13 строки, подчиненной вершине-источнику, и переключатель 14 столбца, подчиненного вершине-стоку, После этого нажимают кнопку 10 установки исходного состояния. При этом на все триггеры устройства поступает сигнал, устанавливающий их в исходное (нерабочее) состояние. Далее нажимают кнопку генератора 3 одиночных импульсов. Импульс от этого генератора поступит к триггеру 4 и опрокинет его, переводя в рабочее состояние, При этом на выходе триггера образуется импульс, который через элемент ИЛИ 8 и клемму 42 блока 1 поиска путей поступает к триггеру 12. Триггер 12 опрокинется и образующийся на его выходе сигнал20 25 30 35 40 45 пройдет через включенный при программировании переключатель 13 и поступит на матрицу ячеек 11. Матрица этих ячеек осуществит поиск первого пути и фиксирует его переходом триггеров ячеек, подчиненных лхгам пути, в рабочее состояние. На выходах д всех ячеек этой матрицы, находящихся в стооках и столоцах, номера которых совпалают с номерами вершин первого пути, образуется сигнал, который попадает на такой же вхол ячеек 22 блока 2 раскрытия определителей и заблокирует эти ячейки. Это значит, что на блоке 2 будет автоматически запрограммиоовано алгебраическое лополнение к первому найденному пути.После определения первого пути в результате опрокидывания триггера ячейки, полчнненной послелней ветке пути, на выхоле 43 блока 1 ооразуется сигнал. Этот сигнал пройдет через элемент ИЛИ 9 и попалет на вход 44 олока 2 раскрытия определителей. В олоке 2 отт попалет на триггер 23 и опоокинет его. На выходе этого триггера обарзуется сигнал, который пройлет к матрице ячеек 22, гле б- лет осмществлен поиск первого слагаемого алгебраического дополнения, в результате чего загорится индикатор запись триггера 32.Число вьтхолов схемы выделения сигтталотт инверсий 37, на которых образуется елиничный сигнал, булет оавно обтцем числу иттвсосий между инлексами элементов первого найденного слагаемого. Параллельный смматоо 38 определит четность этого числа, что булет зат 1 тиксировано на инликаторе 39 знака.Запись элементов пеового слагаемого осу- ществляют по загоревтнимся инликатооам ячеек 11 (элехтетттьт п.ти) и ячеек 22 (элечеттттт алгеораического лополнеттият. После записи первого найленпого слагаемого нажимают кнопку генератора 3. Образовавтпийся пои этом втооой импльс генератора через элементы И 7 и ИЛИ 9 поступает непососзственпо на блок 2 раскрытия опрелелителеть гле осуществляется поиск следующего слагае. мого и т, д. После опрелеления всех слагаемых числителя на выходе 4 а блока 1 образуется сигнал, который пройдет через переключатель 6 опрокинет триггер 5, в результате чего загорится индикатор конца поиска.Для раскрытия знаметтателя выоажения передачи необхолимо пепеключатель б перевести в положение Л. После нажатия кнопки 10 триггер 4 установится соазу в рабочее состояние. при котором с этого триггеоа на элемент И 7 подается елиничнын сигнал. Пои нажатии кнопки генератора 3 пеовьтй и все последующие импульсы булут поступать чеоез элементы И 7 и ИЛИ 9 к блоку 2 раскрытия опрелелнтелей. Слеловательно, булет осуществлено раскрытие полного опоелелптеля графа,Прелмет изобоетени я 1. Спеттиализироваттная электроттттая хтантина лля определения перелачи гоафа, солержащая блок поиска путей, блок раскрытия опосделитслей, триггеры, генератор олиночттых импульсов, логические элементы и переключатели, отличатощаяся тем, что, с целью увеличения быстроленствия, в ней генератор олиночных импульсов соелиттетт через правлятотций триггер и пеОвьттт логттческий элеметтт ИЛИ с запускающим входом блока поиска путей, выхол которого соелинен чеоез втооой логический элемент ИЛИ с запускатоптттхт входом блока раскрытия определителей, выход котооого через первый, логический элемент ИЛИ полключен и запускаютцему вход блока поиска птетт. 2. Машина по п. 1, отличаюатаяся тет. что выхол каждой функциональной ячейки блока поиска путей соелинен через пеоеключатель задания конечной верптиньт олного столбца со входом первой ячейки строки, помеР которой совпалает с номером столбца рассматриваемой ячейки,383055 оставптель Н. ГузеиковаТекред Е. Борисова Корректор В. Жолудева Редактор Е. Типография, пр. Сапунова,аказ 23385 Изд. М 617 Тираж 647 ПодписноеЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР Москва, Ж.35, Раугнская иаб., д, 4/5