Устройство для анализа определителей

 

30088I

E О ПИ

ИЗОБРЕТЕН ИЯ

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

Сова Советских

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

Республик

Зависимое от авт. свидетельства ¹â€”

Заявлено 20.111.1969 (Ле 1315628/18-24) с присоединением заявки №вЂ”

Приоритет—

Опубликовано 07.IV.1971. Бюллетнь № 13

Дата опубликования описания 22Х1.1971

МПК G 06115/32

Комитет по делам изобретений и откры.ий при Совете Министров

СССР

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

P. П. Базилевич

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

Заявитель

УСТРОЙСТВО ДЛЯ АНАЛИЗА ОПРЕДЕЛИТЕЛЕЙ

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

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

Недо, статком известных устройств является относительно большое время проведения анализа из-за осуществления полного перебора.

Предлагаемое устройство отличаегся тем, что оно содержит две гругвпы переключателей функциональных ячевк строк, первые и вторые входы которых соединены с выходами соответствующих программирующих выключателей, а третьи входы переключателей первой гру1лпы соединены с первыми выходами переключателей соседних старших строк и с первыми выходами функциональных ячеек соответствующей строки, вторые выходы переключателей первой группы соединены с первыми входами первых функциональных ячеек в строках, первые выходы переключателей второй группы соединены со вторыми входами функлтиональных ячеек соответствующих cTðoê, а вторые выходы этих переключателей соединены с третьими входами переключателей соседней старшей строки и со вторыми выходами последних функциональных ячеек соответствующих строк, третьи выходы функциональных ячеек соединены с третьими входами всех младших функциональных ячеек в данном столбце, генератор одиночных импульсов соединен с третьим входом переключателя пер:вой строки второй .группы,и с единичным установочным входом триггера, нулевой выход которого соединен с третьим входом переключателя последней строки первой группы.

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

На фиг. 1 изображена блок-схема устройства; на фиг, 2 — схема функциональной ячейки; на фиг. 3 — схема блока знакоиакателей.

У стройство (см. фиг. 1) содержит функциональные ячейки 1, организованные в управ25 ляемую матрицу, состоящую из и строк и и столбцов (и — наибольший возможный, порядок определителя), генератор 2 одиночных импульсов, триггер 3 запуска, и первых управляемых переключателей строк, реализованных логическими элементами «И» 4, 5; и вторых уп300881

65 равляемых переключателей стрск, реализованных логическим и элементами «И» б, 7; пускэвую кно п ку 8; п вьиключателей 9 ячеек строк, п выключателей 10 ячеек столбцов, переключатель П рода ра|бот с положениями «минор» («M») и «алгвб раическое дэполнение» («АД»), триггер 12 конца работы, логический элемент «ИЛИ» 18, блок знако,искателей 14.

Функциональная ячейка содержит триггер

l5, управляемый переключатель импульсов

lб, программирующий выключатель 17, логические элементы «ИЛИ» 18 и 19.

Блок знакоискателей содержит искатель четности подстановок, образованных индексами групп элементов определителя, «минора» или «алгебраического дополнения», и искатель знака «алгебраического дополнения». Искатель четности подстановок содержит матрицу диодов 20, логические элементы «И» 21,подачи на матрицу диодов эпрашивающих им пульсов, логические элементы «И» 22 снятия с матрицы диодов .опра шивающнх им пульсов, триггеры 28 четности числа инверсий отдельных индексов членов определителя, «минора» или «алгебраического дополнения» и конечный тритгер 24 четнэсти с индикаторами знака.

Искатель знака алгебраического допол нения содержит переключатели 25, спаренные с выключателями 9 и 10, подчиненными нечетным строкам и столбцам и григгер 2б с индикаторами знака.

Блэк зна коискателей содержит также жду,щий (2n+ 1) фазный мул ьтивибратор 27 и тритгер 28 с индикатором «член det».

Элементы ма шины соединены следующим образом.

Входы 1ФЯ всех функциональных ячеек 1, служащие для подачи сигнала, устанавливающего триггер 15 в нулевое, состояние, соединены в замкнутом положении кнопки 8 с источником такого сигнала Е,. Сигнальный вход переключателей lб каждой, кроме первой в ,строке, ячейки соединен шинами 2ФЯ и 5ФЯ предыдущей в с роке ячейки с одним из выходов переключателя lб и тем динамическим выходом триггера этой ячейки, на котором об разуется единичный сигнал при переходе его из единичного состояния в нулевое.

Сигнальный вход переключателя lб каждой первой в строке функциональной ячейки соединен шиной 2ФЯ с выходом элемента «И» 5 той же строки. Один вход элемента «И» 5 соединен шиной бФЯ с теми выходами триггеров всех функциональных ячеек следующей старшей строки, на которых образуется единичный сигнал при переходе триггера из нулевого состояния в единичное (если рассматриваемая строка не последняя), или же с выходом триггера 8 для последней строки. Вход установии нулевого состояния триггера 8 соединен через кнопку 8 с источником F<, а вход установления единичного состояния этого триггера — с генератором 2 единичных импульсов.

l5

Я

3О

Вторые входы элементов «И» 4 и 5 каждой строки соединены шинами а и б соответственно с выключателем 9 той же строки. Все выключатели 9, в свою очередь, соединены с переключателем 11, на который подводятся управляющие сигналы, cOOTIBBTcòâóþùèå логическому единичному («1») и нулевому («О») сигналам.

Выходы триггеров 15 всех ячеек первой строки, на которых образуется единичный сигнал,при переходе триггеров из нулевого сос1ояния в единичное, соединены через шины бФЯ совместно с выходом элемента «И» 4 первой стро|ки с за пускающим входом ждущего мультивибратора 27.

Шина 5ФЯ каждой последней в строке ячейки соединена совместно с выходом элемента «И» 7 рассма-риваемой строки с одним из входов элементов «И» б и 7 следующей старшей строки. Шина 5ФЯ по|следней ячейки в последней строке соединена с триггером 12 конца работы. Один вход элемента «И» 7 первой строки соединен с генератором 2 одиночных импульсов. Вторые, входы элеме|нтов «И» б и 7 соединены через шины б и а соответственно с вьгключателя ми 9 TOH æå стрэки. Выход элемента «И» б каждой строки соединен ico входами установки единичного состояния триггеров 15 всех ячеек той же cTpolKB.

Один из входов элементов «ИЛИ» 18 и 19 всех, кроме последней строки, ячеек соединен через шину 8ФЯ рассматриваемой и шину

7ФЯ находящейся в одном столбце следующей старшей строки ячейки с выходом элемента «ИЛИ» 19 этой ячейки. Для ячеек последней строки указанные входы элементов «ИЛИ»

18 и 19 соединены с выключателями 10 соответствующих столбцов. К выключателям 10 подводятся сигналы с переключателя 11.

Второй вход элемента «ИЛИ» 18 соединен с программирующим выключателем 17, íà который подводятся управляющие сигналы, соответствующие логическим единице и нулю.

Второй вход элемента «ИЛИ» 19 соединен со статическим единичным выходом триггера 15.

Этот же статический выход триггера соединен через шину T ячейки с одним из входов элементов «И» 21 и 22 соответствующих строки и сгол б ца искателя четности подстановок блока знакоискателей 14.

Вторые входы всех элементов «И» 21 одной строки соединены с. одним выходом мультивиэратора 27. Вторые входы элементов «И»22 подключены .к матрице диодов 20, к которой также подключены выходы элементов «И» 21.

Выходы элементов «И» 22 одной строки подключены к триггерам четности 28 той же строки. Вторые входы этих триггеров подключены к выходам ждущего мульти вибратора 27. Входы установления нера|бочего состояния тригге ров 28 подключены к первому выходу мультивибратора 27. Динамические выходы триггеров 28 подключены к конечному Tipmrrepy 24 четности. Вход установления нерабочего состояния триггера 24, coOTBBTcòâóþùåãо фиксации

300881 знака «плюс», соединен с (n+1)-ым выходом мультивибратора 27.

Одна, клемма ка ждого переключателя 25 подключена к одному выходу мультивибратора 27, вторая — к триггер у 2б знака «алгебраического дополнения». Входы установки нулевого состояния григгера 2б и триггера 28 подключены к выходу элемента «ИЛИ» 13.

Один вход элемента «ИЛИ» 13 соединен с генератаром одиночных импульсов 2, второй через кнопку 8 — с источником Ео. Вход установки единичного состояния триггера 28 соединен с (2n+1)-ым выходом мультивибратора 27.

Предлагаемое устройство работает следующим о бразом.

Для ра скрытия апределителя необходимо включить программирующие переключатели

17 всех ячеек, подчиненных наличным ненулевым элементам. Выключатели 9 и 10 всех строк и стол бцов с полностью нулевыми элементами необходимо перевести в выключенное положение (на фиг. 1 они представлены во включенном положении) . Переключатель 11 рода работ должен быть в положении М. После программирования нажимают .пусковую кнопку 8.

При этом ча триггеры 15 всех ячеек, а также триггеры 3, 12, 26 и 28 поступает на пряжение Ео, устанавливающее их в нулевое состояние. После этого нажимают кнопку генератара 2. Импульсом этого генератора опрокидываепся триггер 3. Образовавшийся на выходе этого триггера динамический ситнал поступает к:последней страке и переводит в единичное состояние триггер первой включен ной ячейки этой строки. Статическим сигналом с выхода 7ФЯ этой ячейки бло кируювся все находящиеся выше в одном столбце ячейки. Динамический сигнал с выхода бФЯ поступает через элемент «И» 5 следующей младшей строки на вход 2ФЯ первой ячейки этой строки и апржидывает триггер первой включенной при программиравании и незаблокированной ячейки и т. д, В результате в каждой строке в единичное состояние переходит триггер только одной ячейки, причем все эти ячейки из разных столбцов, т. е. найден первый, искомый член раскрытого определителя.

Динамический сигнал с выхода опрокинутого тригтера ячейки первой сгроки поступает на ждущий мультивибратор 27 и запускает его.

На выходах последнего образуется последавательность разделенных Во времени импульсов.

Импульсом с первого выхода мультивибратора устанавливаются в нерабочее состояние триггеры четнасти 23. Импульсами со следующих n — 1 выходов олрашиваются состояния триггеров ячеек на наличие инверсий со старшими ячейками. В результате такого опроса триггеры 28 фиксируют четность количества инверсии отдельных элементов найденного члена определителя, (n+1)-й импульс мультивибратора устанавливает .в единичное состояние конечный триггер четности 24. Следующие

n — 1 импульсов опрашивают состояние триггерав 23, и триггер 24 фиксирует четность суммарного числа инверсий между всеми элементами члена апределителя. (2п+1) -й импульс переводит в единичное состояние триггер 23, что свидетельствует о конце поиска первого члена определителя.

После за писи его по загоревшимся,индикаторам ячеек и индикаторам знака нажимают кнопку генератора 2. Образовавшийся второй импульс от генератора 2 уже не может по)пасть на самую нижнюю сгроку, так как ра бочее состояние триггера 3 не может быть изменено этим имлульсом, и проходит только яа входы 4ФЯ всех ячеек пер вой строки. Триггер, находящийся в единичном состоянии в эгой строке, возвращается в,нулевое состояние.

Образовавшийся при этом на выходе 5ФЯ динамический сигнал пападает через элемент

20 «И» б второй строки на входы 4ФЯ всех ячеек этой строки, Находящийся в рабочем состоянии триггер второй строки опрокидывается, и динамическим сигналом с выхада 5ФЯ ячейки переводится в единичное состояние триггер следующей свободной (неза блокированной и включенной при программировании) ячейки второй строки. Если такой ячейки по второй строке не окажется, то сигнал попадает на третью строку и т. д. В результате этого фиксируется второй, искомый член определителя.

Для поиска следующего члена снова необходимо нажать кнапку генератора 2 и т. д.

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

60 б5

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

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