Устройство для определения знака членов определителя матрицы
Союз Советскиа
Социалистические
Республик
ОПИСАНИЕ
И ЗОБ РЕ ТЕ Н И Я
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Зависимое от авт. свидетельства №вЂ”
Заявлено 03.Ill.1969 (№ 1318998/18-24) с присоединением заявки ¹â€”
Прнорите к —Опубликовано 21.IV.1972. Ь1оллетень ¹ 14
М.Кл. G 06f 15j32 йомитет по делаю кзооретеиий и открытий ори Совете Мииистров
СССР ДК 681.323 (088.8) Дата опубликования описания 20.Х.1972
Авторы изобретения
Б. И. Блажкевич и Е. Д. Михайлова
Заявитель
Физико-механический институт АН Украинской ССР
УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЗНАКА ЧЛЕНОВ
ОПРЕДЕЛИТЕЛЯ МАТРИЦЪ|
Изобретение относится к составным частям специализированных математических машин, предназначенных для раскрытия определителей матри|ц, элементы которых выражаются буквенными символами.
Известно устройство для определения знака членов определителя матрицы, содержащее коммутатор, селектор, триггеры, индикаторы знака, логические схемы «И», матрицу с закороченнымп вертикальными н горизонтальными шинами одного номера, вертикальные шины которой присоединены соответственно ко входам триггеров селектора и выходам триггеров коммутатора, и ключи, соответствующие отдельным элементам матрицы, определитель которой подлежит раскрытию, управляемые сигналами с выходов триггеров, образующих коммутатор искателя сомножителей.
Основным недостатком известного устройства является то, что согласно алгоритму, реализуемому в этом устройстве и основанному па подсчете количества циклов в подстановке индексов элементов матрицы, являющихся сомножителями члена определителя, каждый из таких циклов отображается в устройстве изолированной группой шип, соединенных между собой через управляемые ключи, соответствующие указанным выше элементам матрицы. Обусловленная этим необходимость электрической изоляции шин матрицы знака искателя в значительной мере затрудняет использование в качестве управляемых ключей полупроводниковых бесконтактных приборов.
Практически приемлемая реализация извест5 ной схемы знакоискателя невозможна без применения контактных управляемых ключей (реле), что значительно снижает быстродействие устройства и уменьшает сроки безотказной его работы.
10 Целью изобретения является по|вышение быстродействия и надежности работы устройсТВВ для поиска знаков членов определитезя.
Предлагаемое устройство для определения знака членов определителя матрицы содер15 жит, как и известное, регистр. кольцевой коммутатор, блок задержки и переключающие ячейки, состоящие из логических схем сИ» и «НЕ» и соответствующие отдельным элементам матрицы, за исключением первого
20 элемента первой строки и последHHx элеме тов всех строк.
Потенциальные входы отдельных переключающих ячеек присоединены к выходам соответствующих триггеров искателя сомножите25 лей. Переключающие ячейки, соответствующие элементам одной строки, соединены последовательно таким образом, что импульсный вход последующей ячейки присоединен к первому выходу предыдущей ячейки. Им30 пульсиыи вход ячейки, соответствующей вто336664 рому элементу первой строки матрицы, присоединен вместе с коммутационным входом псрвого триггера кольцевого коммутатора через блок задержки к источнику пускового импульса, К этому источнику непосредственно подключены входы установки начального состояния всех триггероз устройства. Вторые выходы переключающих ячеек, соответствующих,всем элементам одного столбца матрицы, за исключением элементов ес первой стро<и, присоединены к отдельным входам логической схемы «ИЛИ», соответствующей данному столоцу, а первые выходы пере:<лючающих ячеек, соответствующих аналогичным элементам предпоследнего столбца матрицы, к 01дельным входам схемы «ИЛИ», соответстьующей последнему столбцу матрицы. Второй выход каждой из переключающих ячсек, соответствующих элементам г;ерзой строки матрицы, присоединен ко входу второй схемы
«ИЛИ», соответствующей столбц матзицы, 1 в I
K этому же выходу;подключен один из входов третьей логической схемы «ИЛИ», соответствующей данному столбцу. Второй вход этой схемы присоединен к выходу соответствующеIo этому же столбцу триггера регистра. Выход каждой из третьих схем «ИЛИ», соответствующих отдельным столбцам матрицы, за исключением ее последнего столбца, подключен ко входу триггера регистра, который (триггер) принадлея<ит к последнему столбцу матрицы. Вход, первого триггера регистра соединен с выходом логической схемы «ИЛИ>, соответствующей первому столбу матрицы.
Выход третьей логической схемы «ИЛИ», соответствующей последнему столбцу матрицы, соединен с коммутационными входами всех триггеров кольцевого коммутатора, за исключением первого триггера этого коммугатора.
Выход каждой из вторых логических схем
«ИЛИ», соответствующих отдельным стол бцам матрицы, присоединен 110 входу запоминающего триггера, выход которого подключен к потенциальному входу отдельной логической схемы «И». Импульсный вход каждой такой схемы включен па гыход соответствующего данному столбцу матрицьt триггера рсгистра. Выходы всех логических схем «И», соответстзую1ци:< отдельным столбцам матрицы, ири"оед11н tltl к разным входам огдсльной логической схемы «ИЛИ», сигнал с выхода которой подается па счетный вход триггера, управляющего индикаторами знака.
Кольцевой коммутатор образован триггерами, соотзетстзчо1цимн отдслы1ым стро <11м матрицы. Выход каждого:1з таких триггероз, >
15 0
1О
65 за исключением последнего триггера, присоединен к импульсному входу переключающей ячейки, соответствующей 1первому элементу последующей строки матрицы. Выход первого из этих триггеров присоединен дополнительно к потенциальному входу отдельной логической схемы «И», на второй импульсный вход которой включен генератор тактовых импульсоз. К выходу этой логической схемы присоединены коммутационные входы всех триггеров регистра.
Предлагаемое устройство для поиска знака членов определителя матрицы может быть без каких-либо затруднений выполнено исключительно на полупроводниковых бесконтактных элементах, что обеспечивает возможность значительного повышения его быстродействия и удлинения сроков безотказной работы.
На фиг. 1 изображена функциональная схема устройства в целом, на фиг. 2 — фупкцно",àëüHàÿ схема его переключающих ччеек.
Как известно, каждый из членов определителя матрицы и-ro порядка @=I)g ", где
i=1, 2, ..., и — номер строки, а к=1, 2, 3, ..., и — номер столбца, в которых расположен элемент д,, матрицы, представляет собой произведение элементов матрицы, каждый из которых находится в иной се строке и В ином столбце, и может оыть представ 1ен ь Виде: й1й, Д2 I,, °" аjuj" P 1< причем н,1=,= -к,ф ... =,,-ki =Ь... —;--к„.
Знак такого члена может быть определен количеством беспорядков (инверсий) в последовательности вторых индексов к,, к„ ..., к ;, ..., к„ .
П р и четном числе таких беспорядков э тот знак положительный, при нечетном — отрицательный. Этот спосоо определеш1я знака члена определителя и положен в основу алгоритма, реализуемого в предлагаемом устройстве, функциональная схема которого приведена на фиг. 1.
Состоит оно из переключающих ячеек 1, блока задержки 2, логических схем «ИЛИ»
8, 4, 5, 6 и «И» 7, 8, запоминающих триггеров 9, триггеров 10 регистра, триггеров 11 кольцевого коммутатора, триггера 12 знака и индикаторов знака 1>.
Hepå1<:ï0÷àI0ùèå ячейки ставятся в соответствие отдельным элементам матрицы, за искл1очением первого элемента п<-.рвой строки д» и последних элементов всех с1рок >1„
j=1, 2, ..., и. На потенциальные входы перекл!Оча10щих яческ пода!Отся сиг!Iа.!ы с Вы.",Одов соответствующих триггеров искатели сомно>кителей. Перекл1оча10щие ячейки, сооТI åòñòâóI0ùè= элементам одной It той же строки, на фиг. 1 расположены в одном ряду, а соответствующие элемс1там одного и того же столбца матрицы — в одном cTOлбце расположения соответствующих строк и столбцов г, самой матр1це. Остальным столоцам поставлено в соогзетствис по одной схеме «ИЛИ» 3, «ИЛИ» 4, «ИЛИ» 5, «И» 7, по 0, 336664 б5 Входы схем «ИЛИ» 8, поставленных в соответствие отдельным столбцам матрицы, за исключением последнего ес сголбца, присоединены ко втор||м выходам переключающих ячеек, соответствующих элементам данного столбца, за исключением элемента первой строки. Входы схемы «ИЛ1Л» 8 последнего столбца подключены к первым выходам переключающих я чеек, соответствующих таl изl же элементам предпоследнего столбца. Один из входов каждой схемы «ИЛИ» 4 соединен с выходом соответствующей схемы «ИЛИ» 8. Второй вход схемы «ИЛИ» 4 .последнего столбца подключен к первому выходу последней переключающей я |ейки, находящейся в .первом ряду. У остальных схем «ИЛИ» 4 вторые входы соединены со Вторыми выходами первых переключающих ячеек соответствующих столбцов. Выход схемы «ИЛИ» 8 первого столбца присоединен ко !входу триггера 10 регистра, соответствующего второму столбцу. Выходы остальных схем «ИЛИ» 8 подкл|очены дополнительно ко входам соответствующих схем «ИЛИ» 5. Вторые входы этих схем |подключены к выходам соответствующих триггеров 10 регистра. Выходы схем «ИЛИ» 5, .за исключением схемы «ИЛИ» 5 последнего столбца, присоединены ко входам триггера 10 регистра последу!Ощего столбца. Выходной сигнал схем «ИЛИ» 4 подается на вход соответствующего запоминающего триггера 9. Сигналы с выхода запоминающего трипгсра 9 и триггера 10 регистра, соответствующих одному и тому же столбцу, подаются на отдельные входы соответствующей этому жс столбцу схемы «И» 7. Выходы всех схем «И» 7 подключены к отдельным входам схемы «ИЛИ» 6, выходной сигнал которой подается на счетный вход триггера 12 знака, к отдельным выходам которого подключены индикаторы зпа|ка «+» и « — » И. Переключающие ячейки, находящиеся в одном ряду, соединены последовательно таким образом, что импульсный вход последующей ячейки !1одкл|очен к первому выходу предыдущей ячейки. Импульсный вход первой блокирующей ячейки первого ряда подкл|очен через блок задержки 2 к источнику пускового импульса. Каждому ряду персключающих ячеек (стро.ке матрице) соответствует отдельный! триггер 11 кольцевого коммутатора. Коммутирующий импульс на первый трипер этого коммутатора поступает через блок заде|ржки 2 от источника пусковых импульсов. Коммутирующ!ие пмпуль"ы па остальные триггеры кольцевого коммутатора подаются с выхода схемы «ИЛИ» 5, соответствующей;последнему столбцу матрицы. К выходам триггеров 11 кольцевого коммутатора, за искл|о|снием триггера, соотвсгствующссо последнему ряду переключающих ячеек, подкл!Очены импульсные .входbf псрзых пере!<лI0 1310IIII;." ячес! после.|уlо1LI II < pF1:IO1I. 1(В в|ходу Г1ер ного . -|3 этих Tlpll I гс5 1> 25 зо 40 |5 ,»О 60 ров дополнительно подключен один из входов схемы «И» 8. На второй вход эгой схемы подаются сигналы от генератора тактовых импульсов. К выходу схемы «И» 8 подключены коммутационные входы триггеров 10 регистра. Функциональная схема отдельной переключающей ячейки представлена на фиг. 2. Состоит эта ячейка из логических схем «11» 14, 15 и инвертора «НЕ» 16. К потенциальному Входу ячейки присоединен вход инвертора,16 и |потенциальный вход схемы «И» 15. К выходу инвертэра «НЕ» 16 подключен потенциальный вход схемы «И» 14. Соединенные вместе импульсные входы схем «И» 14 и 15 образуют импульсный вход ячейки. Перв|яй выход переключающей ячейки совмещен с выходом схемы «И» 14, а второй — с выходом схемы «И» 15. При отсутствии сигнала на потенциальном входе переключающей ячейки сигналы, поступающие на ее импульсный вход, направляются на первый выход, так,как в этом случае на общих входах схемы «И» 14 имеется сигнал. При наличии сигнала на потенциальном входе переключающей ячейки сигнал с импульсного входа ячейки поступает на се второй выход. Подготовка устройства в целом к попсы найденного члена определителя закл|очаетс;! в !подаче постоянных сигналов на потенциальные входы переключающих ячеек, соотзетствующих элементам матрицы, являющимся сомножителями члена определителя, Работа устройства начинается с момента подачи единичного пускового импульса, которь|й прежд. всего устанавливает все триггеры устройства в исходном состоянии. Через .время т, определяемое блоком задержки 2, этот же llмпульс опрокинет один из запоминающих триггеров, вследствие чего на одном из входов соответствующей схемы «И» 7 появится, постоянный сигнал. Одповреме||но опрок11нстся первый триггер кольцевого коммутатора, вследствш чего Опрокинется второй триггер этого коммутатора, а схема «И» 8 откроет путь тактовь|м импульсам на .коммутационные входы триггеров регистра. Вместе с тем Tip!I отсутствии сигнала на потенциальном входе первой переключающей ячейки второго ряда произойдет опрокидывание еще одного из запомина!Ощих тригг.рОВ, а в случае, когда этот триггер соответствует не последнему столбцу матрицы — опрокидывание триггера регистра, соответству ощего ближайшему:по очереди столбцу матрицы. Если из второй строки матрицы в состав сомножителей вошел первый се элемент, то есть, когда имеется сигнал на потенциальном входе первой ячейки второго ряда. то вследствие опрокидывания первого триггера кольцевого коммутатора опрокинется толь ко первый триггер регистра. После опрокидывания любого нз трнггероп регнсгра подаваемые через схему «И» <) такго»IIe: импульсы приведут к срабатыванию 336664 регистра, начиная с о!})>о!ИГГеР3 1>СГ icTPii В 112 -Iа.аь!!Ое состояние приведет к возникнове!!и!о импульса, подаваемого на коммутационные входы всех, начиная со второго, триггеров кольцевого коммутатора. Такой импульс воз!!Нкнет и В ТОМ СЛУЧ»Е, КОГД3 СО 13TOPOII CTPOIC}! М3ТРИЦЫ в состав сомножителей .Вошел последний элемент строки матрицы. Б этом случае на одном из потенциальных входов переключающих HI!epic BTopol 0 ряда li б i 33! ciiTна;13, Под ВЛНЯНlгем ) !c»33HIIOI 0 .ВЫше Т iKTOBOI 0 имт!ульса опрокинется вторично (Вер}!ется в исходнос положенис) Второй триГГер коммутатора, а импульс с его выхода пройдет в первую переключающую ячейку третьего ряда. Одновреме!!но опрокинется третий трп! Гер коммутатора. Дальше процесс будет происходить аналогично, как п после подачи импульса на импульсный вход первой переключающей ячейки !Второго рода. На последнем цикле работы устройства, который начинается с повторного опрок!!дыВания (возвращения В исходное состоя|!!!с) 1!редпослед!!ВГО триГГера кд.аьцсьОГО ко «м татора, опрокинется iBI}ppBIIc последний триггер этого коммутатора и одновременно на импульсный вход первой переключающей » Ie}1; Ii;}op»ere>I упр»-вля!ощий сигнал. Если на потенциальном входе одной из ячеек этого ряда имеется сигнал, то этот импульс приведет к опрокидыванию триггера регистра, соответствующего последующему столбцу, и работа регистра начинается с Возвращения этого триггера в исходное состояние. После окончания работы регистра, последний тригГСР КОЛЬЦЕВОГО КОММ>Т»ТОР3 ВЕРНЕТСЯ В ИСходное состояние, а вследствие кольцевого соединения в исходное состояние вернется и первый триггер этого коммутатора. Такой жс эффект получится и при отсутствии сигнала и» потенциальных входах всех переключающ .!х ячеек последнего ряда. Только в этом случае возвращение последнего, а затем и гервого, триггеров кольцевого коммутатора в исходное состояние произойдет под воздействием импульса, прошедшего через схемы «ИЛИ» 8 и 5 последнего столбца. При возВращении первого триггера кольцеВо10 коммутатора в исходное состояние исчезает сигнал на потенциальном входе схемы «И» 8, вследстгис чего прекратится подача тактовых импульсов на коммутационные входы триггеров регистра, и работа устройства будет окончена. Во время каждого из .циклов срабатывания регистра на входах, каждого из его триггеров, начиная с опрокш}утого сигналом, поступающ:!м через схему «11Л1Л» 8 появляются по Очеред:! н.,:1}ульс ые сигналы, котоаые по.,а!Отса 112 Входы соответствучощпх схем «И» ". Пр:! Н»л:!ч}гп снгналов на потенциальных Входах этих схсht указан}!ые с!IГна. !ы 1!ро!Iдут через схему «ИЛИ» 6 на вход триггера 12 з:!ак». Общсе число им пульсов, пост ;пивших а вход этого тр irrepa за все время работы 1стройстВа, точно равно количеству инверсий В ПОСЛЕДОВ»ТСЛЬНОСТИ ВТОРЫХ ИНДЕКСОВ ЭЛ ментов м}!трнцы, я>вляющнхся сомножителям:! дан!}ого члена определителя. Ввиду тогÎ, что,при <подаче на вход т!ри!!.ера знака каждого их!пульса индицнрованный 1> знак пз BIIBBTc}I на противоположный, знак, i СТа!!Ов}!}!ШП!!С>1 IIOC,IC ОКОНЧ»ННЯ P»001Ы YCT(>o!IcTB» lI будет знаком данного члс!i3 onpc;lc;I!ITp., при услош!и, что в исходном состоян:ш !Нд}щировался знак «+». 20 Действительно, непосредственно перед поступле}гнем управля}ощего сигнала ila имН1.лье!!ы!! вхо i первой переключающей ячейки у-го ряда (j: 1) имеются сигналы на нотенциа.!ьных Входах схем «И» 7, соответст>з> Вующих столбцам с порядковыми номерами, к; )1, !=1, 2, ..., (/ — 1), в которых расположены элем llты матрицы — сомно>кители I;IF 2 ог!ределпте !}1, принадлежащие к строкам с порядковы"-.!и номерами . - j. Если элемент 1-й строки, являющийся сомножителем данного члена о!пределителя, расположен в к; -м столоце,то при к,: под воздействием управляющего импульса, снимаемого с выхода (/ — 1) -го триггера кольцевого коммутатора, появится сигнал ещс на потенциальном входе схемы «И» 7, принадле>кащей К, -му столбцу При к, (zz начнется работа регистра с опроКИДЫВ»ПИЯ ТРИГГЕР», !IP}III».(i ежа ЩСГО К (ко+1) -му столбцу, 40 В данном случае на вход триггера з}!ак» поступит столько счетных импульсов, сколько из чисел К„, z=1, 2, ..., (j — 1)1, больше числа к;. Количество таких импульсов будет определяться,количеством чисел в последовательностии вторых индексов, правь!ш а ющих к; н находящихся впереди него. Это и будет число оеспорядков, обусловленных расположением числа к; на /-и месте данной последовательности. Если же к; =а, То реги!стр вообще пе ;,0 сработает и на триггер знака пе поступит ни с.!!ин импульс. Это вполне за!ко!!Омар!Но, так как в последовательности Вторых индексов Впсредп числа к =п нс может находиться превышающее его число. Регистр не работает также до поступления управляющего имнуль,) > са на переключающие ячейки второго ряда. В этом и нет необходимости, так как впереди первого числа в последовательности импульсов нет Вообще других чисел. 6О Изложенный вып}е причцип работы предлагаемого устройства проиллюстрируем на примере поиска знака члена О!пределителя матрицы пятого порядка, сомножителями коTChP0TO ЯВЛЯIОТСЯ Э }ЕМЮНТЬ}:, !5,, 23, с 31 О4з go 336664 10 В последовательности вторых индексов этих -элементов имеется шесть инверсий, а именно одна инверсия числа «3», и по две инверсии чисел «1» и «2», и одна инверсия числа «4». На подготовительном этапе должны быть поданы сигналы на потенциальные входы третьей переключающей ячейки второго ряда, первой — третьего, второй — четвертого и четвертой — пятого ряда. На первом этапе работы устройства сигнал появится на потенциальном входе схемы «И» 7 третьего столбца. На втором этапе по явится сигнал на потенциальном входе схемы «И» 7 третьего столбца и произойдет поочередное опрокидывание триггеров регистра, начиная с триггера, пренадлежащего к четвертому столбцу. При этом на вход триггера знака через схему «И» 7 пятого столбца пройдет один счетный импульс. На третьем этапе опрокинется первый триггер регистра, а во время последующей работы регистра на вход триггера знака пройдет через схемы «И» 7 третьего и пятого столбцов два импульса. На четвертом этапе появится сигнал еще на потенциальном входе схемы «И» 7 второго столбца и произойдет поочередное переключение триггеров регистра, принадлежащих третьему, четвертому и пятому столбцам. Вследствие этого на вход триггера знака поступит дальнейших два счетных импульса через схемы «И» 7 третьего и пятого столбцов. На заключительном этапе опрокинется пятый триггер регистра, а начатая этим работа регистра приведет к подаче на вход триггера знака еще одного счетного импульса через схемы «И» 7 пятого столбца. 3а все время на вход этого триггера поступит б импульсов, в результате чего он вернется в исходное состояние, при котором индикатор указывает знак «+». Зтот знак и будет знаком данного члена определителя. Предмет изобретения I0 Устройство для определения знака членов определителя матрицы, содержащее коммутатор, матрицу переключающих ячеек, регистр, запоминающие триггеры, блок задержки, триггер знака, индикаторы знака и логические схемы «И» и «ИЛИ», отлича>ощееся тем, что, с целью повышения быстродействия и надежности устройства, импульсный вход первой ячейки пер вой спроси соединен со;входом коммутатора и с выходом блока задержки, а 2р импульсные входы первых ячеек остальных строк соединены с соответствующими выходами коммутатора, импульсные входы остальных переключающих ячеек присоединены и первым выходам предыдущих в своих строках 25 переключающих ячеек, первые п,вторые выходы всех переключающих ячеек подключены через соответствующие схемы «ИЛИ» к соответствующим входам запоминающих т риггеров и триггеров регистра, а выходы запоми30 нающих триггеров и соответствующих им триггеров регистра через соответствующие схемы «И» подключены ко входам схемы «ИЛИ», выход которой подключен к счетному входу приггера знака. 6 1Ð
