ФОНД енепЕРТОВ Советский патент 1973 года по МПК G06F15/173 

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

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

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

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

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

Выход генератора 3 одиночных импульсов соединен с одним входом элемента «И 7 и входом триггера 4, служащим для перевода его в рабочее состояние. Второй вход элемента «И 7 соединен со статическим выходом триггера 4, на котором имеется единичный сигнал в рабочем состоянии триггера. Выход элемента «И 7 соединен с одним входом элемента «ИЛИ 9, второй вход которого соедивен с выходом конца поиска пути блока /. Выход элемента «ИЛИ 9 соединен с запускающим входом блока 2 раскрытия определителей.

Динамический выход триггера 4, на котором образуется сигнал при переходе триггера в рабочее состояние, соединен с одним входом элемента «ИЛИ 8. Второй вход элемента «ИЛИ 8 соединен с выходом блока 2. Выход элемента 8 соединен с запускающим входом блока / поиска путей. Входы установки исходного состояния блока / и блока 2 соединены через кнопку 10 с источником напряжения EQ. С этим же источником через кнопку W соединен вход установки нерабочего состояния триггера 5 и одна клемма первого переключателя 6 (6-/), две вторые клеммы которого соединены с разными входами триггера 4. Одна клемма второго переключателя 6

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

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

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

Блок 2 раскрытия определителей (см. фиг. 3) содержит управляемую матрицу II, состоящую из п строк и п столбцов функциональных ячеек 22 (ФЯО У/ -ФЯО пп), триггер 23 запуска, п первых управляемых переключателей строк, реализованных логическими элементами «И 24 и «И 25, п вторых управляемых переключателей строк, реализованных логически.ми элементами «И 26 и «И 27, п логических элементов «И 28 на п входов, п логических элементов «НЕ 29, разделительные диоды 30, логический элемент «ИЛИ 31 и триггер 32 с индикатором «запись.

Каждая функциональная ячейка 22 содержит триггер 33 с индикатором состояния, управляемый переключатель 34, логические элементы «ИЛИ 35 и «ИЛИ 36.

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

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

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

сигналов инверсий г-го элемента слагаемого соединен с выходом Г функциональной ячейки 22, находящейся в том же столбце и (1+1)-ой строке. Второй вход каждого элемента «И 41 соединен с выходом элемента

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

равно

(n-l) + (n-2) + ... + 2-i-l -.

Сумматор 38 является произвольным сум(л - l)-z

матором параллельного действия на -

входов.

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

7 - 2П-Дь

где Ph - передача к-го пути от источника к

стоку,

Д - определитель графа. Aft - алгебраическое дополнение к-то пути (т. е. определитель подграфа, не инцидентного /с-му пути).

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

вершину, подчинена ячейка (где ...п, ...п). Сначала осуществляется раскрытие числителя в выражении передачи, следовательно, переключатель 6 рода работ должен быть в положении «ЕР/гЛй. Кроме

этого, переводят во включенное положение переключатель 13 строки, подчиненной вершине-источнику, и переключатель 14 столбца, подчиненного вершине-стоку. После этого нажимают кнопку 10 установки исходного состояния. При этом на все триггеры устройства поступает сигнал, устанавливающий их в исходное (нерабочее) состояние. Далее нажимают кнопку генератора 3 одиночных импульсов. Импульс от этого генератора поступит к триггеру 4 и опрокинет его, переводя в рабочее состоя.ние. При этом на выходе триггера образуется импульс, который через элемент «ИЛИ 8 и клемму 42 блока / поиска путей поступает к триггеру 12. Триггер 12 опрокипется и образующийся на его выходе сигнал

лройдет через включенный при программировании переключатель 13 и поступит на матрицу ячеек //. Матрица этих ячеек осуществит поиск первого пути и фиксирует его переходом триггеров ячеек, подчиненных дугам nvти, в рабочее состояние. На выходах д всех ячеек этой матрицы, находящихся в CTDOKHX и столбцах, номера которых совпадают с номерами верщин первого пути, образуется сигнал, который попадает на такой же вход ячеек 22 блока 2 раскрытия определителей и заблокирует эти ячейки. Это значит, что на блоке 2 будет автоматически запрограммиповя1го алгебраическое дополнение к перволту найденному пути.

После определения первого пути в результате опрокидывания триггера ячейки, подчиненной последней ветке пути, на выходе 43 блока / образуется сигнал. Этот сигнал пройдет через элемент «ИЛИ 9 и попадет на вход 4 блока 2 раскрытия определителей. В блоке 2 01Г попадет на триггер 23 и опрокинет его. На выходе этого триггера обарзуется сигнал, который пройдет к матрице ячеек 22, где будет осуществлен поиск первого слагаемого алгебраического дополнения, в результате чего загорится индикатор «запись триггера 32.

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

Запись элементов первого слагаемого осуществляют по загоревшимся индикаторам ячеек // (элементы ПУТИ) и ячеек 22 (элементы алгебраического дополнения). После записи первого найденного слагаемого нажимают кнопку генератора 3. Образовавшийся при этом ВТОРОЙ ИМПУЛЬС генератора через элементы «И 7 и «ИЛИ 9 поступает непосрелственно на блок 2 раскрытия определителей, где осуществляется поиск следующего слагаемого и т. д.

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

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

изобретения

1. Специализированная электронная мангина для определения передачи графа, содержащая блок поиска путей, блок раскрытия определителей, триггеры, генератор одиночных импульсов, логические элементы и переключатели, отличающаяся тем, что, с целью увеличения быстродействия, в ней генератор одиночных импульсов соединен через управляющий триггер и первый логический элемент «ИЛИ с запускающим входом блока поиска путей, выход которого соетинен через второй логический элемент «ИЛИ с запускающим входом блока раскрытия опре.делителей. выход КОТОРОГО через первый логический элемент «ИЛИ подключен к запускающему входу блока поиска путей.

2. .Машина по п. 1, отличающаяся тем. что

„X

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

,J , .,

6Х. 9ЯП

был

1 d

4

.Р

,.р flt

т TUn-1)

т

, b 2kp2fn-)

TlJfl

Т221T /n iiJ

П Т22

ip( ipfn-m kpfn- JM

Т(П1)Л j(f,.j,2 ) J(n-3jn /7я kpaZ

41

Л /

ip1fn-1)

pifi

Tin

p2n

ftJ

Ш/г-7Я T

J3{n-3 in

pnn

л

д

Фиг.