УСТРОЙСТВО ДЛЯ РАСКРЫТИЯ ОПРЕДЕЛИТЕЛЕЙ МАТРИЦ Советский патент 1971 года по МПК G06F17/10 G06F17/16 

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

Известны устройства для раскрытия определителей матриц, содержащие триггеры, генераторы импульсов, селектор, логические схемы «И, «ИЛИ, «ПЕ. Для раскрытия полного определителя п-го порядка этими устройствами требуется п тактов работы.

В предлагаемом устройстве с целью сокращения оборудования и повышения быстродействия управляющий вход первой строки управляющего блока соединен с выходом генератора одипочиых импульсов и через схемы «И и пусковую кпопку - с генератором тактовых импульсов. Выход /-и строки управляющего блока соединен с (t4- 1)-й управляющей щиной матрицы. В ячейке г-й строки k-ro столбца матрицы четвертый вход триггера соедипен со вторым входом второй схемы «ИЛИ и через элемент «НЕ - с первым входом второй схемы «И. Первый динамический выход триггера соединен со вторыми входами первой и второй схем «И, выход второй схемы «И соединен с первым выходом переключателя сигналов прямого хода и с сигнальным входом переключателя сигналов прямого хода ячейки i-й строки (k-1)-го столбца. Выход первой схемы «И соединен с первым выходом переключателя сигналов обратного хода и сигнальным входом переключателя сигналов обратного хода ячейки г-й строки (k-1-1}-го столбца. Второй выход переключателя сигналов обратного хода соединен со вторым входом триггера, второй динамический выход триггера соединен с первым входом второй схемы «ИЛИ, выход которой соединен со вторым входом второй схемы «ИЛИ ячейки (1-|-1)-й строки k-ro столбца. Статический

выход триггера соединен с первым входом первой схемы «ИЛИ, второй вход которой соединен с управляющими входами переключателей импульсов прямого 1 обратного хода, а выход - со вторым входом первой схемы «ИЛИ

ячейки (L-}- 1)-й строки k-ro столбца. Управляющие входы триггеров всех ячеек i-й строки соединены с управляющей щиной f-й строки матрицы. Это позволяет раскрывать определитель п-го

порядка за « тактов работы.

На фиг. 1 показана функциональная схема устройства; на фиг. 2 - функциональная схема ячейки. Устройство содержит блок / с п управляеуправляющий блок 3, триггер 4 с индикаторами знака, генератор 5 тактовых импульсов, генератор 6 одиночных импульсов, триггер 7 конца поиска с индикатором «Конец, логические элементы «НЕ 8, «И 9, «PI 10, пусковую кнопку У/ и кнопку 12 продолжения поиска.

Блок I состоит из /г2 ячеек 13, образующих квадратную матрицу д-го порядка. Ячейки каждой строки объединены в кольцевую схему, образуя элементы с п устойчивыми состояниями.

Каждая ячейка (фиг. 2) содержит триггер 14 с двумя устойчивыми состояниями (рабочим и нерабочим), управляемый переключатель импульсов прямого хода 15, реализованный двумя логическими элементами «И и одним логическим элементом «НЕ, управляемый переключатель импульсов обратного хода 16, реализованный аналогично переключателю 15, логические элементы «И 17 и 18, «НЕ 19 и 20, «ИЛИ 21 и 22, индикатор состояния 23.

Триггер 14 имеет два входа для задания начального состояния - р (для нерабочего состояния) и г (для рабочего состояния). Для всех ячеек в главной диагонали (слева вниз направо) с источником нанряження EQ соединены входы г, для всех остальных ячеек с этим источником соединены входы р. Управляющие входы /г всех ячеек одной строки (кроме первой) соединены с шииой этой строки, служащей для подачи управляющих сигналов. Управляющие входы h всех ячеек первой строки не используются.

Вход k каждой ячейки соединен со входом триггера, служащим для подачи импульсов, переводящих триггер в нерабочее состояние, а также через элемент «НЕ 19 - с одним из входов элемента «И 18.

Выход триггера, с которого снимается динамический единичный сигнал при переходе из нерабочего состояпия в рабочее, соединен с одним из входов элемента «ИЛИ 22. Выход элемента «ИЛИ 22 через разъем / рассматриваемой ячейки и разъем k, находящейся выше в том же столбце ячейки, соединен с одним из входов такого же элемента «ИЛИ 22 носледней ячейки и входом ее триггера, служащим для нодачи сигналов, переводящих этот триггер в нерабочее состояние, а также через элемент «НЕ 20 - е элементом «И /7 этой же ячейки.

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

Выход элемента «И П соединен с тем выходом переключателя 15, на котором имеется единичный сигнал при наличии таких же сигналов па сигнальном и управляющем входах этого переключателя, и через разъем b рассматриваемой ячейки и разъем а следу1оп1,ей слева в одной строке ячейки - с сигнальным входом переключателя 15 этой ячейки. Если

ячейка первая в строке, то ее разъем b соединен с разъемом а последней в одной строке ячейки.

Второй выход нереключателя 15, на котором имеется нулевой сигнал (отсутствует единичный сигнал) при паличии единичных сигналов па сигнальном и управляющем входах ЭТ01-0 нереключателя, соедннен со входом триггера, служащим для нодачи сигналов, переводящпх триггер в рабочее состояние.

Выход элемента «И 18 соединен с тем выходом нереключателя 16, на котором пмеется единичный сигнал при наличии таких же сигпалов иа сигпальпом и управляющем входах

переключателя, и через разъем d рассматриваемой ячейки и разъем а следующей справа в одной строке ячейки - с сигнальным входом нереключателя 16 этой ячейки. Если же ячейка последняя в строке, то ее разъем d соединеп с разъемом с нервой в одной строке ячейки.

Второй выход нереключателя 16, па котором имеется нулевой сигнал при наличии единичных сигналов на сигнальном и управляющем

входах этого нереключателя, соединен со входом триггера, служащим для подачи сигналов, переводящих триггер в нерабочее состояние. Выход триггера, с которого снимается статический единичный сигнал, когда триггер находится в рабочем состоянии, соединен с одним нз входов элемента «Р1ЛИ 21 и через программирующий ключ 24 - е индикатором состояния 23. Выход элемента «ИЛ1-1 2/ соединен через разъем п рассматриваемой ячейки и разъем т находящейся выще в одном столбце ячейки с одним из входов элемента «Р1ЛИ 22 и управляющими входами переключателей 15 и 16 этой ячейки. Разъемы / п я первых (верхпих) и fe и /л

последних (нижних) во всех столбцах ячеек не нснользуются.

Селектор 2 содержит п элементов «ИЛИ 25, каждый на п входов, элeJмeнт «И 26 на п входов и индикатор 27 «член del. Каждый

элемент «ИЛИ 25 подчинен одному столбцу ячеек блока /. Входы этого элемента соединены через выходы / ячеек одного столбца блока / с программирующими ключами 24 этих ячеек. Выходы эле.ментов «ИЛИ 25 соедипе1 Ь с элементом «PI 26. Выход элемента «И 26 соедннен с индикатором 27 и через элемент «НЕ 8 - с одним из входов элемента «И 9. Второй вход элемента «И .9 соединен с выходом элелюнта «И 10, один вход которого соединен через пусковую кнопку 11 в непажатом состоянии с генератором 5 тактовых импульсов, а другой - со статическим выходом триггера 7 конца поиска.

Выходы элемента «И 9 и генератора 6 одиночных импульсов нодсоедннены к; симметричному входу триггера 4 и входу установления нерабочего состояния триггеров первой строки управляюн;его блока 3. Управляющий блок содержит п - 1 строк триггеров. Первая строi-тая - (i-г 1) триггер, (п- 1)-ая - п триггеров. Триггеры каждой строки замкнуты в кольцо, а входы установления нерабочего состояния триггеров одной строки соединены вместе и подключены к выходу последнего триггера предыдущей строки, т. е. блок 3 представляет собой (п-1)-разрядный счетчик, причем первый разряд содержит два элемента, второй - три и т. д.

Выход первого триггера первой строки блока 3 соединен с управляющей щиной УШ-2 второй строки блока ). Выходы первого и второго триггеров второй строки блока 3 через элемент «ИЛИ 12 соединены с управляющей шиной УШ-3 третьей строки блока / и т. д., т. е. выходы i триггеров г-й строки через элемент «ИЛИ соединены с управляющей щиной (г + 1)-й строки УШ-(/ + I) блока /.

Выход последнего га-го триггера последней (п- 1)-й строки соединен со входом установления нерабочего состояния триггера 7 конца поиска. Входы установления рабочих состояний всех первых триггеров во всех строках и входы установления нерабочего состояния всех остальных триггеров блока 3 соединены через пусковую кнопку НЕ нажатом состоянии с источником ЕО установления начального состояния.

Перед включением устройства необходимо запрограммировать на нем раскрываемый определитель. Для этого необходимо замкнуть ключ 24 всех ячеек блока /, соответствующих ненулевым элементам определителя. Отметим, что элементу «jj определителя, находящемуся в г-й строке и /-м столбце матрицы, подчинена ячейка блока ), находящаяся в той же строке и том же столбце.

После этого необходимо нажать пусковую кнопку //. При этом с источника ЕО на все триггеры устройства подается напряжение, устанавливающее их в необходимое ттчальное состояние. Все первые триггеры всех строк блока 3 устанавливаЕотся в рабочее состояние. а остальные - в нерабочее. В блоке / рабочее состояние принимают только триггеры ячеек, находящихся в диагонали, что соответствует первому члену полного определителя. При этом триггер 4 принимает такое состояние, что загорается индикатор знака «Плюс.

После отпускания кнопки 11 через элементы «И 9 и 10 с генератора 5 к блоку 3 поступают тактовые импульсы. После первого нмпульса триггеры первой строки блока 3 переходят из состояния 10 (единицей обозначим рабочее состояние триггера, в данном случае- первого, нулевым - нерабочее) в состояние 01. При этом с выхода первого триггера на щину УШ-2 проходит сигнал, который попадает на входы h всех ячеек второй строки блока /. В этой строке в рабочем состоянии находится только триггер второй ячейки, следовательно, только он может изменить свое состояние. При переходе этого триггера в нерабочее состояние на его правом динамическом выходе образуется сигнал, который, пройдя через элемент «П 9. выход b и вход а ячейки, попадает на сигнальный вход переключателя последней ячейки. На управляющем входе этого переключателя сигнал отсутствует, ибо в первом столбце блока / ниже второй строки нет триггеров, которые находятся в рабочем состоянии, а такой сигнал появится на входе т ячейки только в том случае, если ниже этой ячейки имеется триггер какой-либо ячейки в

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

динамическом выходе этого триггера, который через элемент «Р1ЛИ 10, выход е первой ячейки второй строки и вход k первой ячейки первой строки попадает к триггеру последней ячейки н переводит его в нерабочее состояние.

Образовавщийся вследствие этого на его правом динамическом выходе сигнал проходит через элемент «И 6, выход d первой ячейки первой строки, вход с второй ячейки первой строки и попадает па сигнальный вход переключателя 4 второй ячейки первой строки. На управляющем входе этого переключателя сигпала нет (триггер второй ячейки второй строки принял нерабочее состояние). Следовательно, сигнал с выхода переключателя 4 проходит к триггеру ячейки и переводит его в рабочее состояние. На этом цикл заканчивается. Состояние триггеров ячеек блока / и триггеров блока 3 после первого тактового импульса представлепо на фиг. 3,6. Фиг. 3,а - 3,Щ

представляют все состояния устройства, т. е. полный цикл его работы для определителя четвертого порядка.

Таблица

40

45

50

55

60

65

Как видим полный цикл включает 4 1.2.3.4 24 состояния. Каждое состояние блока 1 соответствует одному члену раскрытого полного определения четвертого порядка. Поскольку переход от одного состояния к другому сопровождается только одной перестановкой индексов элементов членов определителя, т. е. только одной инверсией, знаки, с которыми найденные члены должны входить в вырал ение раскрытого полного определителя, доллшы последовательно чередоваться: «плюс - «минус и т. д., начиная с «плюса для первого члена - 0110221233, ., «пп- Эти знаки указываются индикаторами триггера 4, который с каждым тактовым импульсом меняет свое состояние на противоположное.

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

Обычпо приходится раскрывать неполпые определители, значительная часть элементов которых равна нулю. Для фиксирования и выделения из всех членов полного раскрытого определителя только тех, которые содержат исключительно ненулевые элементы, применяется селектор 2. Если после определенного тактового импульса ячейки блока 1 принимают состояние, соответствующее члену определителя, включающему все непулевые элементы, па каждый элемент «И 26 селектора поступает с соответствующих ячеек сигнал, и, следовательпо, такой сигпал оказывается на каждом входе элемента «И 26, а также па его выходе. Загорается индикатор 27 «член del, а на входе элемента «И 9 сигнал отсутствует (он соединен с элементом «И 26 через элемент «ПЕ 8. Следовательно, с генератора 5 па блок 3 подача тактовых импульсов прекращается, и устройство фиксирует свое состояние. После записи результата - элементов найденного члена определителя (по загоревщимся индикаторам 23 ячеек блока /) и знака (по индикатору триггера 4) - необходимо HaHvaTb кнопку 12 продолжения поиска. При этом с генератора 6 к блоку 3 проходит один

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

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

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

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

-и строки управляющего блока соединен с (i-j- 1)-й управляющей щиной матрицы.

2.Устройство по п. 1, отличающееся тем, что в нем в ячейке i-й строки fe-ro столбца матрицы четвертый вход триггера соединен со

вторым входом второй схемы «ПЛИ и через элемент «НЕ - с первым входом второй схемы «П, первый динамический выход триггера соединен со вторыми входами первой и второй схем «П, выход второй схемы «И соединен

с первым выходом переключателя сигналов прямого хода и с сигнальным входом переключателя сигналов прямого хода ячейки г-й строки (fe-f 1)-го столбца, выход первой схемы «И соединен с первым выходом переключателя сигналов обратного хода и сигнальным входом нереключателя сигналов обратного хода ячейки г-й строки ()-YO столбца, второй выход переключателя сигналов обратного хода соединен со вторым входом триггера, второй

динамический выход триггера соединен с первым входом второй схемы «ИЛП, выход которой соединен со вторым входом второй схемы «ПЛИ ячейки ()-й строки /г-го столбца, статический выход триггера соединен с

первым входом первой схемы «ПЛИ, второй вход которой соединен с управляющими входами переключателей импульсов прямого и обратного хода, а выход - со вторым входом первой схемы «ПЛИ ячейки ()-й строки

столбца, управляющие входы триггеров всех ячеек г-й строки соединены с управляюндей щиной 1-й строки матрицы. шм :.4.. ,ГI I-. I

I П e

LL-t

I

-

IT

H mphr