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

 

ОП И САНИ Е

ИЗОБРЕТЕНИЯ

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

294!44

Союз Советских

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

Республик

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

Заявлено 25.Х1.1968 (№ 1285785/18-24) с присоединением заявки №

Приоритет

Опубликовано 26,1.1971. Бюллетень ¹ 6

Дата опубликования описания 24Л.1971

МПК G 06f 15/32

Комитет по делам иаобрвтеиий и открытий при Совете й1ииистрав

СССР

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

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

Заявитель

УСТРОЙСТВО ДЛЯ РАСКРЪ|ТИЯ ОПРЕДЕЛИТЕЛЕЙ МАТРИЦ

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

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

«И», «ИЛИ», «НЕ». Для раскрытия полного определителя и-го порядка этими устройствами требуется и" тактов работы.

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

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

«И» соединен с первым выходом переключателя сигналов прямого хода и с сигнальным входом переключателя сигналов прямого хода ячейки i-й строки (A. — 1)-го столбца. Выход первой схемы «И» соединен с первым выходом переключателя сигналов обратного хода и сигнальным входом переключателя сигналов обратного хода ячейки i-й строки (1г + 1)-ro столбца. Второй выход переключателя сигналов обратного хода соединен со вторым входом триггера, второй динамический выход триггера соединен с первым входом второй схемы «ИЛИ», выход которой соединен со вторым входом второй схемы «ИЛИ» ячейки (i + 1) -й строки /;-го столбца. Статический выход триггера соединен с первым входом первой схемы «ИЛИ», второй вход которой соединен с управляющими входами переключателей импульсов прямого и обратного хода, а выход — со вторым входом первой схемы «ИЛИ» ячейки (i -+ 1)-й строки 1г-го столбца. Управляющие входы триггеров всех ячеек г-й строки соединены с управляющей шиной i-й строки матрицы.

Это позволяет раскрывать определитель и-го порядка за и! тактов работы.

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

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

Блок 1 состоит из 12 - ячеек И, образующих квадратную матрицу 22-го порядка. Ячейки каждой строки объединены в кольцевую схему, образу» элементы с 12 устойчивыми соС ОSI НИ» МИ, Ка кдая ячейка (фиг. 2) содержит триггер

14 с двумя устойчивыми состояниями (рабочим и нерабочим), управляемый переключатель импульсов прямого хода 15, реализованный двумя логическими элементами «И» и одним логическим элементом «НЕ», управляемый переключатель импульсов обратного хода

16, реализованный аналогично переключателю

15, логические элементы «И» 17 и 18, «НЕ» 19 и 20, «ИЛИ» 21 и 22, индикатор состояния 28.

Триггер 14 имеет два входа для задания IIBчального состояния — р (для нерабочего состояния) и г (для рабочего состояния). Для всех ячеек в главной диагонали (слева вниз

iia lpaI3o) с истокeilrisi Е, coegsIцены входы r, для всех остальных ячеек с этим источником соединены входы р. Управляющие входы 12 всех ячеек одной строки (кроме первой) соединены с шиной этой строки, служащей дл» подачи управляющих сигналов. Управляющие входы h всех ячеек первой строки не используются.

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

Выход триггера, с которого снимается динамический сдииичный сигнал при переходе из нерабочего состояния в рабочее, соединен с одним из входов элемента «ИЛИ» 22. Выход э leiicii.ra «ИЛИ» 22 чсрез разъем l рассматриваемой ячейки и разъем k, паходящейс» выше в том же столбце ячейки, соединен с одним из ВхОдОВ такого же элемента <<ИЛИ» 22 последней ячейки и входом ее триггсра, служащим для подачи сигналов, перевод»щи э тот т р и г ге р II » e p a o o

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

Выход элемента «И» 17 соединен с тем выходом переключателя 15, иа котором имсетс» едипичпыи сигнал прп наличии таких же сигналов на сигнальном и управляющем входа:( этого переключателя, и через разъем b рассматриваемой»чейки и разъем а следу«»цсй слева в одной строке ячейки — с сигнальным

Dxo!roke! llepei(vIo 1aTeisI 15 этой ячейки. Ec. III

s; icIII(a перва!! v, с!рокe, ro ce раз.ьем b coegIIпсн с разъемом а послсдпей в одной строке

S1" С11«И.

Второй выход переключателя 15, иа котором имеется пулевой сигнал (отсутствует едипи шьш сигнал) при наличии единичных сигналов lla сигнальном и управляющем входах этого переключателя, соединен со входом триггера, служащим для подачи сигналов, переводян;их триггер в рабочее состояние.

Выход элемента «И» 18 соединен с тем выходом переключателя 16, иа котором имеется единичный сигнал при наличии таких же сигналов па сипгальном и управляющем входах переключателя, и через разъем d рассматриBBeiIoI 5Iчсйки и разъем а следующей справа в одной строке ячейки — с сигнальным входом переключателя 16 этой ячейки. Если же ячейка последняя в строке, то ее разьем d соединен с разъемом с первой в одной строке ячейки.

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

Выход триггера, с которого снимается статический единичный сигнал, когда триггер находится в рабочем состоянии, соединен с одним из входов элемента «ИЛИ» 21 и через программирующий ключ 24 — с индикатором состояния 28. Выход элемента «ИЛИ» 21 соединен через разъем а рассматриваемой ячейки и разъем пг находящейся выше в одном столбце ячейки с одних! из входов элемента

«ИЛИ» 22 и управля ощими входами переключателей 15 и 16 этой ячейки.

Раз.ьемы l и и первых (верхиих) и k u m послед!!их (IIII»(них) во всех столбцах ячеек не используются.

Селектор 2 содержит 22 элементов «ИЛИ»

25, каждый па 12 входов, элемент «И» 26 Hà 12 входов и индикатор 27 «члсп det». Каждый элемент «ИЛИ» 25 подчинен одному столбцу

si»eei(блока !. Входы этого элемента соединены через выходы l ячеек одного столбца блока 1 с программирующими ключами 24 этих !! !сек. Выходы элементов «ИЛИ» 25 соединены с элементом «И» 26. Выход элемента «И»

26 соединен с индикатором 27 и через элемент

«1-1Е» 8 — с одним из в.(одов элемента «И» 9.

Второй вход элемента «И» 9 соединен с выходом -;Ie»cilra «И» !О, один вход которого соединен через пусковую кнопку 11 в иеиажатом состоянии с ieiicparopoii 5 тактоьых импульсов, а другой — со статическим выходом тригi " pB 7 !(О!1цa ilolic«B.

Вы Оды элемента «И» 9 и генератора б одино иь1х импульсов подсоединены к симметричному входу триггера 4 и входу установления нерабочего состояния трип.еров первой строi,è управл»ющего блока 3. Ъ правля!ощий блок содср «ит а — 1 строк триггеров. Первая строка содержит два тпиггера, вто11ая — три, 294!44

i-тая — (i + 1) триггер, (n — 1)-ая — n триггеров. Триггеры каждой строки замкнуты в кольцо, а входы установления нерабочего состояния триггеров одной строки соединены вместе и подключены к выходу последнего триггера предыдущей строки, т. е. блок 8 представляет собой (и — 1) -разрядный счетчик, причем первый разряд содержит два элемента, второй — три и т. д.

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

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

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

После этого необходимо нажать пусковую кнопку 11. При этом с источника Е, на все триггеры устройства подается напряжение. устанавливающее их в необходимое начальное состояние. Все первые триггеры всех строк блока 8 устанавливаются в рабочее состояние, а остальные — в нерабочее. B блоке 1 рабочее состояние принимают только триггеры ячеек, находящихся в диагонали, что соответствует первому члену полного определителя. При этом триггер 4 принимает такое состояние, что загорается индикатор знака «Плюс».

После отпускания кнопки 11 через элементы «И» 9 и 10 с генератора 5 к блоку 8 поступают тактовые импульсы. После первого импульса триггеры первой строки блока 8 переходят из состояния 10 (единицей обозначим рабочее состояние триггера, в данном случае— первого, нулевым — нерабочее) в состояние

01. При этом с выхода первого триггера на шину УШ-2 проходит сигнал, который попадает на входы h всех ячеек второй строки блока 1. В этой строке в рабочем состоянии находится только триггер второй ячейки, следовательно, только он может изменить свое состояние. При переходе этого триггера в нерабочее состояние на его правом динамическом выходе образуется сигнал, который, пройдя через элеТаблица а 1000

40 10 0100

100 0010

1000 0001 б 0100 в 0010

01 1000 10 1С00

100 0010 010 0100

1000 0001 1000 0001 г 1000 д 0100

01 0010 10 0010 е 0010

01 0100

001 1000

1000 0001

45 010 0100 ; 001 1000

1000 ООО1 I 1000 ООО1 ж 0001 ц О 100

10 0100 01 0001

100 1000, 100 1000

0100 0010 0100 0010

50 к 0100

10 1000

010 0001

0100 0010 л 1000 м 1000

01 0100 10 0001

010 0001 001 0100

0100 0010 | 0100 0010 н 0001

01 1000

001 0100

0100 0010 о 0001 п 1000

10 1000 01 0001

100 0010 100 0010

0010 0100 0010 0100 р 0010

10 0001

010 1000

0010 0100

55 т 1000 у 0010

10 0010 01 1000

001 0001 001 0001

0010 0100 0010 0100 с 0001

01 0010 бО 010 1000

0010 0100 х 0100

01 0010

100 0001

0001 1000 ц 0100

10 0001

010 0010

0001 1000 ф 0010

10 0100

100 0001 б5 0001 1000 мент «И» 9, выход b и вход а ячейки, попадает на сигнальный вход переключателя последней я .ейки. На управляющем входе этого переключателя сигнал отсутствует, ибо в первом столбце блока 1 ниже второй строки нет триггеров, которые находятся в рабочем состоянии, а такой сигнал может появится на входе т ячейки только в том случае, если ниже этой ячейки имеется триггер какой-либо ячейки в

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

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

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

Состояние триггеров ячеек блока 1 и триггеров блока 8 после первого тактового импульса представлено на фиг. З,б. Фиг. З,а — З,и представляют все состояния устройства, т. е. полный цикл его работы для определителя четвертого порядка.

294144 ч 0001

01 0100

010 0010

0001 1000 ш 0001 щ 0010

10 0010 | 01 0001

001 0100 001 0100

ООО1 1OOO (OOO1 1ООО

Как видим полный цикл включает

4! = 1.2.3.4 = 24 состояния. Каждое состояние блока 1 соответствует одному члену раскрытого полного определения четвертого порядка. Поскольку переход от одного состояния к другому сопровождается только одной перестановкой индексов элементов членов определителя, т. е. только одной инверсией, знаки, с которыми найденные члены должны входить в выражение раскрытого полного определителя, должны последовательно чередоваться: «плюс» — «минус» и т. д., начиная с «плюса» для первого члена — а,а22аз,,..., а„„. Эти знаки указываются индикаторами триггера 4, которыи с каждым тактовым импульсом меняет свое состояние на противоположное.

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

Обычно приходится раскрывать неполные определители, значительная часть элементов которых равна нулю. Для фиксирования и выделения из всех членов полного раскрытого оггределителя только тех, которые содержат исключительно ненулевые элементы, применяется селектор 2. Если после определенного тактового импульса ячейки блока 1 принимают состояние, соответствующее члену определителя, включающему все ненулевые элементы, на каждый элемент «И» 26 селектора поступает с соответствующих ячеек сигнал, и, следовательно, такой сигнал оказывается на каждом входе элемента «И» 26, а также на его выходе. Загорается индикатор 27 «член det», а на входе элемента «И» 9 сигнал отсутствует (он соединен с элементом «И» 26 через элемент

«НЕ» 8). Следовательно, с генератора 5 на блок 3 подача тактовых импульсов прекращается, и устройство фиксирует свое состояние. После записи результата — элементов найденного члена определителя (по загоревшимся индикаторам 23 ячеек блока 1) и знака (по индикатору триггера 4) — необходимо нажать кнопку 12 продолжения поиска. При этом с генератора 6 к блоку 3 проходит один тактовый импульс, и устройство принимает очередное состояние. Если это состояние не соответствует новому члену раскрываемого неполного определителя, на выходе элемента

«И» 26 сигнал не появляется, и устройство продолжает работать, как описано выше.

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

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

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

2. Устройство по п. 1, отличающееся тем, что в нем в ячейке i-й строки k-ro столбца матрицы четвертый вход триггера соединен со вторым входом второй схемы «ИЛИ» и через элемент «НЕ» — с первым входом второй схемы «И», первый динамический выход триггера соединен со вторыми входами первой и второй схем «И», выход второй схемы «И» соединен у с первым выходом переключателя сигналов прямого хода и с сигнальным входом переключателя сигналов прямого хода ячейки i-й строки (k + 1) -го столбца, выход первой схемы

«И» соединен с первым выходом переключате40 ля сигналов обратного хода и сигнальным входом переключателя сигналов обратного хода ячейки i-й строки (k + 1)-го столбца, второй выход переключателя сигналов обратного хода соединен со вторым входом триггера, второй

45 динамический выход триггера соединен с первым входом второй схемы «ИЛИ», выход которой соединен со вторым входом второй схемы «ИЛИ» ячейки (i+-1)-й строки k-го столбца, статический выход триггера соединен с первым входом первой схемы «ИЛИ», второй вход которой соединен с управляющими входами переключателей импульсов прямого и обратного хода, а выход — со вторым входом первой схемы «ИЛИ» ячейки (i+1)-й строки

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

294144

Фиг )

Епе а

Нп7РЬГ д

Фиг. 2

Составитель Е. И. Иванеева

Редактор Б, Б. Федотов Техред Л. В. Куклина Корректоры: Т. А. Джаманкулова и Л. А. Царькова

Заказ 1257/14 Изд. № 561 Тираж 473 Подписное

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

Москва, Ж-35, Раушская наб., д, 4/5

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