Устройсгво для раскрытия определителей матриц

 

ОПИСАНИЕ

И ЗОБ РЕ Т Е Н ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ:

2I8538

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

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

Республик р ро»° «3

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

Кл. 42m:, 15,!32

Заявлено 15.111.1967 (№ 1139268/26-24) с присоединением заявки №

Приоритет

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

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

МПК G 06f

УДК 681.3:51(088.8) Комитет по делам изобретений н открытий прн Совете Министров

СССР

Авторы изобретения

Ь. И. Влажкевич, Р. П, Ьазилевич и E. Д. Михайлова

Физико-механический институт AH Украинской ССР

ЗаявитеЛь

УСТРОЙСТВО ДЛЯ РАСКРЬ1ТИЯ 011РЕДЕЛИТЕЛЕИ МАТРИЦ

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

Предлагаемое устройство отличается тем, что оно содержит матрицу искателя сомножителей и матрицу знакоискателя (с закороченными вертикальными .и горизонтальными шинами одного номера) вертикальные шины которой подсоединены, соответственно, ко входам триггеров селектора и выходам триггеров коммутатора, Вертикальные шины матрицы искателя сомножителей соединены со входами схемы «И», выход которой через вентиль подкл1очен к управляющему входу коммутатора и через схему «НЕ» — ко входу второй схемы «И». Управляющий вход вентиля подключен к генератору импульсов, а управляющие входы ключей матрицьг искателя сомножителей подсоеди неньг соответственно ко входам триггеров второго коммутатора, выход которого соединен через триггер конца поиска со вторым входом схемы «И». Управляющий вход второй схемы «И» подсоединен к генератору импульсов, выход — к управляющему входу второго коммутатора. Горизонтальньге шины матрицы искателя сомножителей объединены и подключены к источнику питания.

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

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

10 и принципиальные схемы узлов.

Искатель сомножителей членов определителя состоит из системы вертикальных шин управляемых ключей 2 с индикаторами включения, триггеров 8 коммутирующего устрой15 ства, триггера 4 конца поиска, схемы совпадений 5, логической схемы 6 «НЕ», схемы совпадений 7, источника 8 периодических управляющих сигналов, источника 9 единичных управляющих сигналов, ключа 10 установки

20 нуля, пускового переключателя 11 и источника 12 рабочего сигнала (блока питания).

Число шин в системе шин принимается равным предполагаемому максимальному порядку п„,„матрицы Q, определитель которой мо25 жет быть еще раскрыт с помощью описываемого устройства. Количество ключей 2 выбирается равным предполагаемому максимальному числу ненулевых элементов m„„,. в одной строке, умноженному на максимальный

30 порядок матрицы ил„, Точно таким же при218аЗс нимается число триггеров 3 коммутирующего устройства, причем цепь управлония каждого из ключей 2 соединена с рабочим выходом отдельного триггера 8. В искателе сомножителей принято, что m,„„. = — и „,„,.а. Количество 5 входов схемы совпадений б согласуется с количеством шии и,„„, в системе шин.

Управляемые ключи 2 и соответствующие им триггеры 3 коммугирующего устройства разбиты на и,„„,. групп по и„„,. ключей и 10 триггеров. На сриг. 1 ключи и триггеры, образующие такие группы, расположены в отдельHbIY горизонтальных строках.

Количество задействованных вертикальных шин и входов схемы совпадений 5 зависит от 15 порядка п конкретной матрицы. Одновременно число задействованных управляемых ключей 2 и управляющих ими триггеров 8 зависит от числа Й ненулевых элементов этой матрицы. Способ присоединения управляемых 20 ключей 2 в системе шин, соединение триггеров 8 коммутирующего устройства и подключение к ним триггера конца поиска зависит от способа расположения этих элементов в данной матрице. Итак, в схему устройства 25 включаются ключи 2 и триггеры 8 первых по порядку и групп, причв» .каждая из групп и ее триггер ставится в соответствие отдельной стро ке матрицы. Из .каждой такой группы включается столько, первых по порядку клю- 30 чей 2 и триггеров 8, сколько имеется в соответствующей строке матрицы Q ненулевых элементов, причем каждый из этих ключей и управляющих ими триггеров ставится в соответствие отдельному нвнулевому элементу 35 данной строки (первый ключ данной группы— первому ненулевому элементу, второй ключ— второму элементу и т. д., независимо от порядкового номера столбца, в котором находится данный элемент). 40

Из всех n „. вертикальных шин 1 в схеме непосредственно используются только, первые по порядку п шин, каждая из,которых подключается к отдельному входу схемы совпадений 5. Остальные и,„„— п ее входы присое 45 диня отся непосредственно к источнику 12 рабочего сигнала. Выход схемы совпадений б через логическую схему б «НЕ» присоединен к одному из трех входов схемы совпадений 7, второй ее вход подключен к выходу источни- 50 ка 8 периодических управляющих сигналов, а третий — к выходу триггера 4 конца поиска.

Один контакт всех:ключей 2 присоединен на постоянно к источнику 12 рабочего cviiiaла. Вторые KoiHTBKTbi задействованных в схеме 55 управляемых ключей 2, соответствующие»енулевым элементам матрицы Q (например, элементу q«, расположенному .на пересече нии ее -ой строки и к-ro столбца), присоединены к соответствующей шине (к-ой) системы 60 вертикальных шин. Задействованные в схеме триггеры 8 коммутирующего устройства, соответствующие .ненулевым элементам матрицы

Q, расположенным в одной ее строке, соединены между собой по кольцевой схеме (выход первого, присоединен ко входу второго, выход второго — ко входу третьего и т. д., а выход последнего — ко входу первого). Цепи управления всех триггеров, соответствующих ненулевым элементам первой .строки матрицы, присоединены через пусковой .переключатель 11 к выходу схемы совпадений 7 или к выходу источника 9 единичных управляющих сигналов. Цепи управлвния задействованных триггеров 8 каждой последующей группы подключены к выходу последнего задействованного триггера 3 предыдущей группы. Цвпь управления триггера 4 конца поиска, присоединяется к выходу послед него задействован ного триггера 8 в группе триггеров, соответствующей последней строке матрицы.

Выходы установки начального состояния всех триггеров 8 коммутирующего устройства присоединены через ключ 10 установки нуля к источнику 12 рабочего сигнала таким образом, что при замкнутом ключе 10 в рабочем состоянии, характеризующимся замыканивм управляемого да иным триггером ключа, нахо. дятся только первые триггеры 3 в каждой группе триггеров. Вход установки начального состоя ния триггера 4 конца поиска присоединен через этот же ключ 10 установки нуля K источнику 12 рабочего сигнала таким образом, что при замкнутом ключе 10 на выходе триггера 4 появляется сигнал.

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

Замыкание ключа iiK приводит к присоединению к-го входа схемы совпадений к источнику сигнала. Если при включении какой-то группы и ключей на чыходе схемы совпадений появляется сигнал, то элементы матрицы, соответствующие включенным ключам 2, являются сомножителями члена определителя

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

218538

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

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

Для прекращения работы коммутирующего устройства используется сигнал схемы совпадений 5, при появлении которого схема совпадений 7 не пропускает в коммутирующее устройство управляющих импульсов от источника 8 периодических управляющих сигналов.

Знакоискатель состоит из системы скрещивающихся вертикальных и горизонтальных шин 18, управляемых ключей 14, триггеров 15 коммутатора, триггеров lб селектора, индикаторов 17 знака, управляющего индикаторами знака триггера 18, схемы совпадений 19, ключа 20 установки начального состояния и переключателя 21 начальной установки знака.

Число горизонтальных и число вертикальных шин системы шин 18 равны числу шин 1 искателя сомножителей n„.. Такое же количество триггеров 15,коммутатора и триггеров

lб селектора. Горизонтальная и вертикальная шины с одинаковым порядковым номером соединены накоротко. Каждая пара таких шин подключена к цепи управления отдельного триггера lб селектора. Первые и пар шин системы шин 18 дополнительно присоединены ло порядку к отдельным выходам первых и триггера в 15 коммутатора (n=-п,„, ).

Все и, триггеров 15 коммутатора соединены последовательно (выход первого подключен ко входу второго, выход второго — ко входу третьего и т. д., а выход предпоследнего — ко входу последнего). Цепи управления всех этих триггеров присоединены ко входу схемы совпадений 19, один из входов которой подключен к входу источника 8 периодических управляющих сигналов, а второй — к выходу схемы совпадений 5 с и входами. Выходы установки начального состояния этих же триггеров через ключ 20 установки начального состояния подключены к источнику 12 рабочего сигнала таким образом, чтобы в состоянии готовности к однократной передаче сигнала от источника управляющих сигналоз на свой выход находился только первый триггер. Выходы установки состояния триггеров

lб селектора присоединены через этот же ключ 20 к источнику 12 рабочего сигнала таким образом, чтобы в аналогичном состоянии готовности находились все эти триггеры. Выходы всех триггеро в lб селектора подключены ж соединенным накоротко входу в цепь управления триггера 18, к одному из выходов

65 которого присоединен индикатор 17 знака

«+», ко второму — индикатор знака « — ».

Один из входов установки начального состоя ния триггера 18 через перекл.ачатель 21 начальной установки знака и ключ 20 установки начального состояния, прпсоедпнен к источнику 12 рабочего сигнала.

Количество управляемых ключей 14 знакоискателя равно количеству управляемых ключе.i 2 искателя сомножителей. Как и последние, ключи 14 разбиты на группы по nt„,„,ключей, каждая из которых ставится в соот1ветствие отдельной строке матрицы Q. Цепи управления кл.очей 14, входящих в одн групп . -эответствующую некоторой строке матрицы Q, присоединены ко входам отдельных триггеров 8, входящих в группу этих триггеров, соответствующую этой же строке матрицы Q.

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

Итак, каждому из ненулевых элементов определеной строки (i-ой) матрицы Q ставится в соответствие один из управляемых ключей 14 группы ключей (i-ой), соответствующей данной строке (первому ненулевому элементу— первый по порядку ключ, второму — второй и т. д.). Второй контакт ключа, соответствующий элементу д,, присоединяется к к-ой вертикальной шине, соответствующей к-ому столбцу матрицы Q.

Порядок и принцип работы знакоискателя следующий.

До начала работы знакоискателя все входяшие в его состав триггеры 15 и lб путем кратковременного замыкания ключа 20 установки начального состояния ставятся в исходное положение. При этом переключатель 21 началь..ой установки знака ставится в такое же положение, чтобы в случае четного и при замкнутом ключе 20 индикатор 17 знака показывал знак «+», а при нечетном — знак « — ». По=ле определения сомножителей члена определителяспомощью искателя сомножителей взамкнутом состоянии находятся ключи 14 знакоискателя, соответствующие элементам матрицы Q, являющимся этими сомножителями.

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

218538

Работа знакоискателя;начинается с момента появления на выходе схемы совпадений 5 сигнала, который, воздействуя на схему совпадений 19, открывает путь управляющим импульсам к триггерам 15 ком мутатора, вследствие чего на всех подключенных к выходам этих триггеров вертикальных шинах системы шин 18 появляются по очереди управляющие сигналы. На объединенном выходе триггеров

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

Каждый из восьми управляющих импульсов, попадая с выхода триггеров 1б селектора на счетный вход триггера 18 индикатора з нака, переводит эгот триггер из одного состояния равновесия в другое, вследствие чего раз меняется установленный первоначальный знак, указываемый индикатором 17 знака. Окончательно устанавли ваегся знак, соответствующий знаку выражения (— 1) (— 1), являющийся знаком данного члена определителя.

После записи сомножителей и знака найденного члена определителя работа устройства возобновляется .путем подачи от переключателя 11 единичного управляющего импульса на триггеры 8. Если включенная ноевая группа и ключей 2 соответствует сомножителям но во го члена определителя, то состояние схемы совпадений 5 останется без изменений, а периодическая работа искателя сомножителя не будет восстановлена. В противном же случае, вслед за единичным управляющим импульсом, когда открыт путь периодическим управляющим сигналам через схему совпадений 7, начинается автоматический поиск сомножителей следующего члена определителя. Принципиальные схемы узлов устройства приведены на фиг.3 (за исключением источника 12рабочего сигнала, показанного в виде блока). Система вертикальных шин 1 искателя сомножителей и система скрещивающихся вертикальных и горизонтальных шин 18 объединены в коммутацио нное поле 1 и 18, .к которому подведены и свободные контакты управляемых ключей 2 искателя сомножителей и управляемых ключей 14 знакоискателя. Контакты присоеди няются к соответствующим вертикальным шинам с помощью гибких двойных шнуров и штепсельных разъемов. Схема совпадений 5 с и входами и логическая схема б «НЕ» объединены для упрощения в схему 5 и б (выполняющую логическую операцию «И — HE») .

Входы этой схемы с помощью,переключателей К, К, К», ... К„, К„присоединяются к вертикальным шинам системы шин 1, или непосредственно к источнику рабочего сигнала (нулевой зажим источника 12 питания). Индикация «задействованных» входов схемы

«И — НЕ», т. е. входов, присоединенных к шинам, осуществляется с помощью сигнальных лампочек .Ть Л, 7, ...,J7„>, Л „. Схема совпадения 7 образуется усилительным каскадом на триоде Т,, питаемом непосредственно

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

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

60 б5 с выхода источника 8 периодических сигналов, и шунтирующими выход этого каскада двумя ключами на триодах Т, и Т», первый из кото5 рых управляется сигналом с выхода схемы г и б, а второй — с выхода триггера 4 конца поиска. Блок знакоискателя, осуществляющий логическую операцию «НЕ», выполнен в виде усилителя на триоде Т4, питаемого от источ10 ника периодических сигналов,,выход которого зашунтирован выходом схемы «И — НЕ». Роль источника единичных управляющих сигналов выполняет в данной схеме зажим — 9 в источника питания, к которому через резистор

15 22 и пусковой переключатель 11 в его нижнем положении присоединяются цепи управления всех задействованных триггеров первой группы триггеров коммутирующего устройства (в этом случае заряжаются конденсаторы). Раз20 ряд этих конденсаторов при возврате переключателя 11 в исходное положение создает едияичный управляющий сигнал для данной группы триггеров.

Подготовка устройства к раскрытию кон25 кретного определителя, т. е. программирование задачи, осуществляется следующим образом.

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

35 схемы совпадвний 5 и б, сколько столбцов (строк) содержит заданная матрица;,в схеме знакоискателя замыкается такое же число первых по,порядку ключей; на коммутацио нном поле выходы управляемых ключей 2 и 14„

40 соответствующих отдельным ненулевым элементам, присоединяются к соответствующим вертикальным шинам систем шин 1 и 18; переключатель 21 начальной установки знака устанавливается в положение «+» в случае

45 четного порядка заданной матрицы, и B положение « — » в случае нечетного; нажимом кнопки «пуск», посредством которой замыкается ключ 20 установки начального состояния, схема знакоискателя .приводится в состояние

50 готовности к работе и нажимом кнопки «установка нуля», .посредством которой замыкается ключ 10 установки нуля, в состояние готовности,приводится схема искателя сомножителей.

Работа устройства начинается сразу же пос55 ле отпускания кнопки «установка нуля» и приостанавливается, после нахождения сомножителей члена определителя и знака этого чле наа.

218538

13

10 лителя матрицы, оно содержит матрицу гс,.а теля сомножителей и матрицу знакоискателя с закороченными вертикальными и горизонтальными шинами од ного номера, вертикальные шины которой подсоединены соответственно ко входам триггеров селектора и выходам триггеров коммутатора,:вертикальные шины матрицы искателя сомножителей соединены со входами схемы «И», выход которой через вентиль подключен к упра вляющему входу коммутатора и через, схему «НЕ» подсоединен ко входу второй схемы «И», управ; яющий вход вентиля подключен к генератору импульсов, а управляющие входы ключей матрицы искателя сомножителей подсоединены соответственно ко входам триггеров второго

5 коммутатора, выход которого соединен через .триггер конца поиска со вторым входом второй схемы «И», управляющий вход второй схе мы «И» подсоединен к генератору импульсов, а выход — к управляющему входу второго

10 коммутатора, горизонтальные шины матрицы искателя сом ножптечси объединены и подк,.почены к источнику питания.

218538

Фоа. 3

Составитель А. А. Субботин

Редактор Е. В. Семанова Текред А. А. Камышникова Корректоры: С. А. Башлыкова и В. В. Крылова

Заказ 2112/12 Тираж 530 Подписное

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

Москва, Центр, пр. Серова, д. 4

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