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

294 44 Союз Советских Социалистических Республиктва18 МПК 6 061 15 оединением заявкириоритет Комитет по делам иаобрвтеиий и открыти при Совете Министров СССРДК 681,142(088,8) летень Л публикования описания 24 Л.1971 Автор зобретения Р. П. Ба лев Заявитель УСТРОЙСТВО ДЛ СКРБ 1 ТИЯ ИТЕЛЕЙ МАТРИ блок 1 с гг управляе ояниями, селектор 2 ависимое от авт. свидетель аявлено 25,Х 1.1968 ( 128 публиковано 26,1.1971. Бю Устройство является специализированной математической машиной для автоматического раскрытия определителей матриц, записанных в общем (символическом) виде. Может применяться для анализа различных физических систем, которые описываются линейными уравнениями, в частности для анализа линейных электрических цепей.Известны устройства для раскрытия определителей матриц, содержащие триггеры, генераторы импульсов, селектор, логические схемы И, ИЛИ, НЕ, Для раскрытия полного определителя п-го порядка этими устройствами требуется и" тактов работы.В предлагаемом устройстве с целью сокращения оборудования и повышения быстродействия управляющий вход первой строки управляющего блока соединен с выходом генератора одиночных импульсов и через схемы И и пусковую кнопку - с генератором тактовых импульсов. Выход г-й строки управляющего блока соединен с (г + 1) -й управляющей шиной матрицы. В ячейке г-й строки й-го столбца матрицы четвертый вход триггера соединен со вторым входом второй схемы ИЛИ и через элемент НЕ - с первым входом второй схемы И. Первый динамический выход триггера соединен со вторыми входами первой и второй схем И, выход второй схемы И соединен с первым выходом переключате 10 15 20 25 ля сигналов прямого хода и с сигнальным входом переключателя сигналов прямого хода ячейки г-й строки (й - 1)-го столбца. Выход первой схемы И соединен с первым выходом переключателя сигналов обратного хода и сигнальным входом переключателя сигналов обратного хода ячейки г-й строки (й + 1) -го столбца. Второй выход переключателя сигналов обратного хода соединен со вторым входом триггера, второй динамический выход триггера соединен с первым входом второй схемы ИЛИ, выход которой соединен со вторым входом второй схемы ИЛИ ячейки (г + 1) -й строки /;-го столбца. Статический выход триггера соединен с первым входом первой схемы ИЛИ, второй вход которой соединен с управляющими входами переключателей импульсов прямого и обратного хода, а выход - со вторым входом первой схемы ИЛИ ячейки (г+ 1)-й строки й-го столбца. Управляющие входы триггеров всех ячеек г-й строки соединены с управляющей шиной г-й строки матрицы.Это позволяет раскрывать определитель и-го порядка за ггпу тактов работы.На фиг. 1 показана функциональная схема устройства; на фиг. 2 - функциональная схема ячейки,Устройство содержитмыми устойчивыми гоступравляющий блок 3, триггер 4 с индикаторами знака, генератор 5 тактовых импульсов, генератор 6 одиночных импульсов, триггер 7 конца поиска с индикатором Конец, логические элементы НЕ 8, И 9, И 10, пусковую кнопку 11 и кнопку 12 продолжения поиса.Блок 1 состоит из г- ячеек И, образующих квадратную матрицу г-го порядка. Ячейки каждой строки объединены в кольцевую схему, образу элементы с г устойчивыми со- СОЯНИ 51 МИ,Ка 5 кдая ячейка (фиг. 2) содержит триггер 14 с двумя устойчивыми состояниями (рабочим и нерабочим), управляемый переключатель импульсов прямого хода 15, реализованный двумя логическими элементами И и одним логическим элементом НЕ, управляемый переключатель импульсов обратного хода 16, реализованный аналогично переключателю 15, логические элементы И 17 и 18, НЕ 19 и 20, ИЛИ 21 и 22, индикатор состояния 23.Триггер 14 имеет два входа для задания начального состояния - р (для нерабочего состояния) и г (для рабочего состояния). Для всех ячеек в главной диагонали (слева вниз папраВО) с истО 1 ни 1(ом напрРени 51 Ео соединены входы г, для всех остальных ячеек с этим источником соединены входы р. Управляющие входы 1 г всех ячеек одной строки (кроме первой) соединены с шиной этой строки, служащей дл подачи управляющих сигналов. Управляющие входы 1 г всех ячеек первой строки не используются.Вход и каждой ячейки соединен со входом триггера, служащим для подачи импульсов, переводящих триггер в нерабочее состояние, а также через элемент НЕ 19 - с одним из входов элемента И 18.Выход триггера, с которого снимается динамический сдиничный сигнал при переходе из нерабочего состояния в рабочее, соединен с одним из входов элемента ИЛИ 22. Вь 1 ход элемента ИЛИ 22 через разъем / рассматриваемой 5 гчейки и разъем 1 г, паходящейс выше В том же столбце ячейки, соединен с одним из ВхОдОВ такоО же элемента ИЛИ 22 последней ячейки и входом ее триггера, служащим для подачи сигналов, переводящих этот трР 1 ггер В нераоочее состояне, а такс через элемент 11 Е 20 - с элементом И 17 этой жс ячейки,Выход триггера, с которого снимается динамический едини шый сигнал при персходе триггера с рабочего состояния в нерабочее, соединен с одним из входов элементов И 17 и 8.Выход элемента И 17 соединен с тем Выходом переключателя 15, на котором имсетс едипичпыи сигнал прп наличии таких же сигналов на сигнальном и управляющем входа:( этого переключателя, и через разъем Ь рассматриваемойчейки и разъем а слсдуннцсй слева в однои строке ячеики - с сигнальным Входом переклОател 51 15 этой ячейки. Если5 10 15 20 25 30 35 40 45 50 55 60 65 5 чейа псрВа 51 В сроке то се разьем Ь соединен с разъемом а послсдпей в одной строке 51 СЙКИ,Второй выход переключателя 15, на котором имеется нулевой сигнал (отсутствует едипишьш сигнал) при наличии единичных сигналов на сигнальном и управляющем входах этого переключателя, соединен со входом триггера, служащим для подачи сигналов, переводящих три гер в рабочее состояние.Выход элемента И 18 соединен с тем выходом переключателя 16, на котором имеется единичный сигнал при наличии таких же сигналов па сипалыОм и управляющем входах переключателя, и через разъем д рассматриваемой ячейки и разъем а следующей справа в одной строке ячейки - с сигнальным входом переключателя 16 этой ячейки. Если же ячейка последняя в строке, то ее разьем д соединен с разъемом с первой в одной строке ячейки.Второй выход переклОчателя 16, на котором имеется пулевой сигнал при наличии единичных сигналов па сигнальном и управл 5 пощем Входах этого переключателя, соединен со входом триггера, служащим для подачи сигналов, переводящих триггер в нерабочее состояние,Выход триггера, с которого снимается статический единичный сигнал, когда триггер находится в рабочем состоянии, соединен с одним из входов элемента ИЛИ 21 и через программирующий ключ 24 - с индикатором состояния 23. Выход элемента ИЛИ 21 соединен через разъем п рассматриваемой ячейки и разъем пг находящейся выше в одном столбце ячейки с одних из входов элемента ИЛИ 22 и управл 1 ощими входами переклю 1 ателей 15 и 16 этой 5 ей 1(и.Разьемы 1 и г первых (всрхних) и 1 г и пг последих (пигкпих) во всех столбцах ячеек не используются.Селектор 2 содержит п элементов ИЛИ 25, каждый па г Входов, элемент И 26 на п входов и индикатор 27 члсп (1 е 1. Каждый элемент ИЛИ 25 подчинен одному столбцу Ргчеек блока . Входы этого элемента соединены через выходы 1 ячеек одного столбца блока 1 с программирующими ключами 24 этих 5 се. Выходы элементов ИЛИ 25 соединены с элементом И 26. Выход элемента И 26 соединен с индикатором 27 и через элемент НЕ 8 - с одним из в.(одов элемента И 9. Второй вход элемента И 9 соединен с выходом элемента И О, один вход которого соединен через пусковую кнопку 11 в ненажатом состоянии с генсратором 5 тактоьых импульсов, а другой - со статическим выходом триг-ра 7 коца поиска,Выходы элемента И 9 и генератора б одипочньх импульсов подсоединены к симметричному входу триггера 4 и входу установления нерабочего состояния триперов первой стро,и управляющего блока 3. Управл 1 ощий блок содср 5 Ит п - 1 строк триггеров. Первая строка содержит два твиггера, втопая - три, 29444Таблица б 0100 в 0010 01 1000 10 1 СОО 100 0010 010 0100 1000 00011000 0001 а 1000 40 10 0100100 0010 1000 0001 г 1000 д 0100 01 0010 10 0010 е 0010 01 0100 001 1000 1000 0001 к 0100 10 1000 010 00010100 0010 н 0001 01 1000 001 0100 0100 0010 л 1000 м 1000 01 0100 10 0001 010 0001 001 0100 0100 00100100 0010 о 0001 и 1000 10 1000 01 0001 100 0010 100 0010 0010 01000010 0100 р 0010 10 0001 010 1000 0010 0100 55 с 0001 01 0010 бО 010 10000010 0100 х 0100 01 0010 100 0001 0001 1000 ф 0010 10 0100 100 0001 б 5 0001 1000 ц 0100 10 0001 010 0010 0001 1000 Е-тая - (К + 1) триггер, (и - 1)-ая - п триггеров. Триггеры каждой строки замкнуты в кольцо, а входы установления нерабочего состояния триггеров одной строки соединены вместе и подключены к выходу последнего триггера предыдущей строки, т. е. блок 3 представляет собой (и - 1) -разрядный счетчик, причем первый разряд содержит два элемента, второй - три и т. д.Выход первого триггера первой строки блока 3 соединен с управляющей шиной УШвторой строки блока 1. Выходы первого и второго триггеров второй строки блока 3 через элемент ИЛИ 12 соединены с управляющей шиной УШтретьей строки блока 1 и т. д., т. е, выходытриггеров -й строки через элемент ИЛИ соединены с управляющей шиной (с + 1) -й строки УШ- (1 -1) блока 1,Выход последнего и-го триггера последней (и - 1)-й строки соединен со входом установления нерабочего состояния триггера 7 конца поиска. Входы установления рабочих состояний всех первых триггеров во всех строках и входы установления нерабочего состояния всех остальных триггеров блока 8 соединены через пусковую кнопку 11 в нажатом состоянии с источником Еп установления начального состояния.Перед включением устройства необходимо запрограммировать на нем раскрываемый определитель. Для этого необходимо замкнуть ключ 24 всех ячеек блока 1, соответствующих ненулевым элементам определителя. Отметим, что элементу ац определителя, находящемуся в с-й строке и 1-м столбце матрицы, подчинена ячейка блока 1, находящаяся в той же строке и том же столбце.После этого необходимо нажать пусковую кнопку 11. При этом с источника Е, на все триггеры устройства подается напряжение, устанавливающее их в необходимое начальное состояние, Все первые триггеры всех строк блока 3 устанавливаются в рабочее состояние, а остальные - в нерабочее. В блоке 1 рабочее состояние принимают только триггеры ячеек, находящихся в диагонали, что соответствует первому члену полного определителя. При этом триггер 4 принимает такое состояние, что загорается индикатор знака Плюс.После отпускания кнопки 11 через элементы И 9 и 10 с генератора 5 к блоку Л поступают тактовые импульсы. После первого импульса триггеры первой строки блока Л переходят из состояния 10 (единицей обозцачим рабочее состояние триггера, в данном случае - первого, нулевым - нерабочее) в состояние 01. При этом с выхода первого триггера на шину УШпроходит сигнал, который попадает на входы й всех ячеек второй строки блока 1. В этой строке в рабочем состоянии находится только триггер второй ячейки, следовательно, только он может изменить свое состояние, При переходе этого а риггера в нерабочее состояние на его правом динамическом выходе образуется сигнал, который, пройдя через элемент И 9, выход о и вход а ячейки, попадает на сигнальный вход переключателя последней ячейки. На управляющем входе этого переключателя сигнал отсутствует, ибо в первом 5 столбце блока 1 ниже второй строки нет триггеров, которые находятся в рабочем состоянии, а такой сигнал может появится на входе т ячейки только в том случае, если ниже этой ячейки имеется триггер какой-либо ячейки в 10 рабочем состоянии. Следовательно, ца выходепереключателя, связанном с триггером ячейки, образуется сигнал, который переводит этот триггер в рабочее состояние, Это, в свою очередь, приводит и появлению сигнала на левом 15 динамическом выходе этого триггера, которыйчерез элемент ИЛИ 10, выход е первой ячейки второй строки и вход Й первой ячейки первой строки попадает к триггеру последней ячейки и переводит его в нерабочее состояние.20 Образовавшийся вследствие этого на его правом динамическом выходе сигнал проходит через элемент И 6, выход И первой ячейки первой строки, вход с второй ячейки первой строки и попадает ца сигнальный вход пере ключателя 4 второй ячейки первой строки, Науправляющем входе этого переключателя сигнала уже нет (триггер второй ячейки второй строки принял нерабочее состояние). Следовательно, сигнал с выхода переключателя 4 про- чО ходит к триггеру ячейки и переводит его в рабочее состояние. На этом цикл заканчивается,Состояние триггеров ячеек блока 1 и триггеров блока 3 после первого тактового импульса представлено ца фиг, З,б. Фиг. З,а - З,и 55 представляют все состояния устройства, т. е.полный цикл его работы для определителя четвертого порядка. 45 010 0100 001 1000 1000 00011000 0001 ж 0001 и 0100 10 0100 01 0001 100 1000 100 1000 0100 0010 0100 0010 50 т 1000 у 0010 10 0010 01 1000 001 0001 001 0001 0010 01000010 0100ч 0001 01 0100 010 0010 0001 1000 ш 0001 ) щ 0010 10 0010 1 01 0001 001 0100001 0100 0001 1000 / 0001 1000 Как видим полный цикл включает 4 = 1.2.3.4 = 24 состояния. Каждое состояние блока 1 соответствует одному члену раскрытого полного определения четвертого порядка. Поскольку переход от одного состояния к другому сопровождается только одной перестановкой индексов элементов членов определителя, т. е. только одной инверсией, знаки, с которыми найденные члены должны входить в выражение раскрытого полного опреде.лителя, должны последовательно чередоваться: плюс - минус и т. д., начиная с плюса для первого члена - ааа а. Эти знаки указываются индикаторами триггера 4, которыи с каждым тактовым импульсом меняет свое состояние на противоположное.При раскрывании определителей более высоких порядков устройство работает аналогичным образом - сначала перебираются все возможные перестановки элементов низкого порядка, после чего порядок увеличивается на единицу и опять осуществляется полный перебор всех возможных перестановок, Каждая образовавшаяся при этом перестановка является членом раскрытого полного определителя,Обычно приходится раскрывать неполные определители, значительная часть элементов которых равна нулю. Для фиксирования и выделения из всех членов полного раскрытого определителя только тех, которые содержат исключительно ненулевые элементы, применяется селектор 2. Если после определенного тактового импульса ячейки блока 1 принимают состояние, соответствующее члену определителя, включающему все ненулевые элементы, на каждый элемент И 26 селектора поступает с соответствующих ячеек сигнал, и, следовательно, такой сигнал оказывается на каждом входе элемента И 26, а также на его выходе. Загорается индикатор 27 член де, а на входе элемента И 9 сигнал отсутствует (он соединен с элементом И 26 через элемент НЕ 8). Следовательно, с генератора 5 на блок 3 подача тактовых импульсов прекращается, и устройство фиксирует свое состояние, После записи результата - элементов найденного члена определителя (по загоревшимся индикаторам 23 ячеек блока 1) и знака (по индикатору триггера 4) - необходимо нажать кнопку 12 продолжения поиска. При этом с генератора 6 к блоку 3 проходит один тактовый импульс, и устройство принимаеточередное состояние. Если это состояние несоответствует новому члену раскрываемогонеполного определителя, на выходе элемента.1 И 26 сигнал не появляется, и устройствопродолжает работать, как описано выше.После полного перебора всех возможных перестановок па выходе последнего триггерапоследнего ряда блока 3 образуется сигнал,10 который переводит триггер 7 в нерабочее состояние,П р е д м е т изобретения1. Устройство для раскрытия определителейматриц, содержащее триггеры, селектор, генераторы, управляющую схему и матрицу, пгличаючееся тем, что, с целью увеличения быстро действия и упрощения схемы, в нем управляющий вход первой строки управляющего блока соединен с выходом генератора одиночных импульсов и через схемы И и пусковую кнопку - с генератором тактовых импульсов, выход -и строки управляющего блока соединен с ( + 1) -й управляющей шиной матрицы.2. Устройство по п. 1, отличающееся тем,что в нем в ячейке -й строки Й-го столбца матрицы четвертый вход триггера соединен со вторым входом второй схемы ИЛИ и через элемент НЕ - с первым входом второй схемы И, первый динамический выход триггера соединен со вторыми входами первой и второй схем И, выход второй схемы И соединен ч 5 с первым выходом переключателя сигналовпрямого хода и с сигнальным входом переключателя сигналов прямого хода ячейки г-й строки (я + 1) -го столбца, выход первой схемы И соединен с первым выходом переключате ля сигналов обратного хода и сигнальным входом переключателя сигналов обратного хода ячейки -й строки (я + 1)-го столбца, второй выход переключателя сигналов обратного хода соединен со вторым входом триггера, второй 4 динамический выход триггера соединен с первым входом второй схемы ИЛИ, выход которой соединен со вторым входом второй схемы ИЛИ ячейки (+1)-й строки й-го столбца, статический выход триггера соединен с первым входом первой схемы ИЛИ, второй вход которой соединен с управляющими входами переключателей импульсов прямого и обратного хода, а выход - со вторым входом первой схемы ИЛИ ячейки (+1)-й строки Й-го столбца, управляющие входы триггеров всех ячеек -й строки соединены с управляющей шиной -й строки матрицы.294144 г Редактор Б, Б. федото Т. А. Джаманкулов и Л. А. Царьков ипография, пр. Сапунова, 2 Фгг, 2оставитель Е, И. Иванеевахред Л. В. Куклина Коррект Заказ 1257/14 Изд,561 Тираж 473ЦНИИПИ Комитета по делам изобретений и открытий при Совете МпнисМосква, Ж, Раушская наб., д, 4/5 Подписноеов СССР