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

Изобретение относится к составным частям С11ециализированных математических машин, предназначенных для раскрытия определителей матриц, элементы которых выражаются буквенными символами.

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

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

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

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

элемента первой строки и последних элеме;|тов всех строк.

Потенциальные входы отдельных переключающих ячеек присоединены к выходам соответствующих триггеров искателя сомножителей. Переключающие ячейки, соответствующие элементам одной строки, соединены последовательно таким образом, что импульсный вход последующей ячейки Присоединен к первому выходу .предыдущей ячейки. Имром} элементу первой строки матрицы, присоединен вместе с коммзтацноппым входом псрзого триггера кольцевого коммутатора через блок задерЖКИ к источнику -пускового импульса. К этому источнику непосредственно подключены .вхады устаповки пачального состояния всех триггеров устройства. Вторые выходы переключающих ячеек, соответствующих .всем элементам одного столбца матрицы, за исключением элементов ее первой строки, присоединены к отдельным входам логической схемы «ИЛИ, соответствующей данно.му столбцу, а первые выходы переключающих ячеек, соответствующих аналогичным элементам предпоследнего столбца матрицы, к отдельным входам схемы «ИЛИ, соответствующей последнему столбцу матрицы. Второй выход каждой из переключающих ячеек, .соответствующих элементам первой строки матрицы, присоединен ко входу второй схемы «ИЛИ, соответствующей столбцу матрицы, в которо-м расположен этот же элемент Ко входу второй схемы «ИЛИ, соответствующей последнему столбцу матрицы, присоединен первый выход переключающей ячейки, соответствующей элементу первой строки матрицы, расположенному в ее предпоследнем столбце. Второй вход каждой из вторых логических схем «ИЛИ присоединен к выходу соответствующей первой схемы «Р1ЛИ. К этому же выходу (подключен один «а входов третьей логической схемы «ИЛИ, соответствующей данному столбцу. Второй вход этой схемы П|рисоединен к выходу соответствующего этому же столбцу триггера регистра. Выход каждой из третьих схем «РШИ, соответствующих отдельным столбцам матрицы, за исключением ее последнего столбца, подключен ко входу триггера регистра, который (триггер) принадлежит к последнему столбцу матрицы. Вход лервого триггера регистра соединен с выходом логической схемы «ИЛИ, соответствующей первому столбу матрицы. Выход третьей логической схемы «ИЛИ, соответствующей последнему столбцу матрицы, соединен с- кол1мутационными входами всех триггеров кольцевого коммутатора, за исключением первого триггера этого коммутатора. Выход каждой из вторых логических схем «ИЛИ, соответствующих отдельным столбцам матрицы, присоединен «о входу запоминающего триггера, выход которого подкл очен к потенциальному входу отдельной .(огической схемы «И. Импульсный вход каждой такой схемы включен на выход соответствующего данно.чу столбцу матрицы триггера регистра. Выходы всех логических схем «И, соответствующих отдельным столбцам .матрицы, присоединены к разны.м входам отдельной логической схемы «ИЛИ, сигнал с выхода которой подается на счетный вход триггера, управляющего индикаторами знака.

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

из этих триггеров присоединен дополнительно к потенциальному входу отдельной логической схе.мы «И, на второй импульсный вход которой включен генератор тактовых им;пульсоБ. К выходу этой логической схемы ирнсоединены коммутационные входы всех триггеров регистра.

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

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

Как известно, каждый из членов определителя матрицы ft-ro лорядка Q Цg..1, где , 2, ..., п - номер строки, а , 2, 3, ..., п - помер столбца, в которых расположен элемент gj матрицы, представляет собой произведение элементов матрицы, каждый из которых находится в иной ее стро-кс и в ином столбце, и может быть представ.чен в аиде:

1, ЙЗ k, gjkj -. gnkn,

причем ... / -гКп .

Знак такого члена .может быть определен количеством беспорядков (инверсий) в последовательности вторых индексов

KI, /С2, ..., К, j , .,., KII .

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

Состоит оно из переключающих ячеек 1, блока задерЖ|КИ 2, логических схем «ИЛИ 5 3, 4, 5, 6 н «И 7, 8, запоминаюпщх триггеров 9, триггеров 10 регистра, триггеров 11 кольцевого коммутатора, триггера 12 знака и индИКаторов знака 13.

Переключающие ячейки ставятся в соответствие отдельным элементам матрицы, за исключением первого элемента первой строки ,11 и последних эле.ментов всех строк gjn-. , 2, ..., п. На потенциальные входы переключающих ячеек подаются сигнал ; с выходов соответствующих триггеров искатели со.множителей. Пере ;лючающие ячейки, соответствующие элементам одной и той же строки, на фиг. 1 расположены в одном ряду, а соответствующие элеме; там одного и того же столбца матрицы - в одном столбце расноложения соответствующих строк и столбцов в самой .матрице. Остальп 51.м столбца.м поставлено в соответствие по одной схеме «ИЛИ 3, «Р1ЛИ 4, «ИЛИ 5, «И 7, по одному запо5 триггеру .9 и триггеру И) ptntcrpa.

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

Один из входов каждой схемы «ИЛИ 4 соединен с выходом соответствующей схемы «ИЛИ 3. Второй ВХОД схемы «Р1ЛИ 4 .последнего столбца подключен к первому выходу последней переключающей ячейки, находящейся в первом ряду. У остальных схем «ИЛИ 4 вторые входы соединены со вторыми выходами первых переключающих ячеек соответствующих столбцов.

Выход схемы «ИЛИ 3 первого столбца присоединен ко входу триггера 10 регистра, соответствующего второму столбцу. Выходы остальных схем «ИЛИ 3 подключены дополнительно :ко входам соответствующих схем «ИЛИ 5. Вторые входы этих схем подключены к выходам соответствующих триггеров Уб регистра. Выходы схем «ИЛИ 5, за исключением схемы «ИЛИ 5 последнего столбца, присоединены ко входам триггера 10 регистра последующего столбца.

Выходной сигнал схем «ИЛИ 4 подается на вход соответствующего запоминающего триггера 9. Сигналы с выхода запоминающего триггера 9 и триггера 10 регистра, соответствующих одному и тому же столбцу, подаются на отдельные входы соответствующей этому же столбцу схемы «И 7. Выходы всех схем «И 7 подключены к отдельным входам схемы «ИЛИ 6, выходной сигнал которой подается на счетный вход триггера 12 знака, к отдельным выходам которого подключены индикаторы знака и «- 13.

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

Каждому ряду переключающих я.чеек (строке матрице) соответствует отдельный триггер 11 кольцевого коммутатора. Коммутирующий импульс на первый триггер этого коммутатора поступает через блок задержки 2 от источника иуско,вых импульсов. Коммутирующие импульсы па остальные триггеры .кольцевого коммутатора подаются с 1выхода схемы «ИЛИ 5, соответствующей последнему столбцу матрицы. К выходам триггеров // кольцевого коммутатора, за исключением триггера, соотвстствуюнюпо последнему ряду переключающих ячеек, подключен импульсные входы первых пере.ключаюн1кх ячеек последую1Ц 1Х рядов. К выходу первого из этих Tipnrreров дополнительно подключен один из входов схемы «И 8. На второй вход эгой схемы подаются сигналы от генератора тактовых импульсов. К выходу схемы «И S подключены коммутационные входы триггеров W регистра.

Функциональная схема отдельной переключающей ячейки представлена на фиг. 2. Состоит эта ячейка из логических схем «И 14, 15 и инвертора «НЕ 16. К потенциальному входу ячейки присоединен вход инвертора ,16 и потенциальный вход схемы «И 15. К выходу инвертора «НЕ 16 подключен потенциальный ВХО.Д схемы «И 14. Соединенные вместе импульсные входы схем «И 14 и 15 образуют импульсный вход ячейки. Первый выход переключающей ячейки совмещен с выходом схемы «И 14, а второй - с выходом схемы «И 15.

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

Подгото.вка устройства в целом i: .поиску найдеиного члена определителя заключается в подаче постоянных сигналов на потенциальные входы переключающих ячеек, соответствующих элементам матрицы, являющимся сомножителями члена определителя. Работа устройства начинается с момента подачи единичного пускового импульса, который преждо всего устапавливает все триггеры устройства в исходном состоянии. Через .время т, определяемое блоком за.держ.ки 2, этот же импульс опрокинет один из запоминающих триггеров, вследствие чего иа одном из входов соответствующей схемы «И 7 появится постояииый сигнал. Одновременно опрокинется первый триггер кольцевого коммутатора, вследствие чего опрокинется второй триггер этого коммутатора, а схема «И 8 откроет путь тактовым импульсам на .коммутационные входы триггеров регистра. Вместе с тем при отсутствии сигнала на потенциальном входе первой переключающей ячейки второго ряда произойдет опрокидывание еще одного из запоминающих триггеров, а в случае, когда этот триггер соответствует не последнему столбцу матрицы- опрокидывание триггера регистра, соответствующего ближай.щему по очереди столбцу матрицы. Если из второй строки матрицы в состав сомножителей вощел первый ее элемеит, то есть, когда имеется сигнал на потенциальном входе первой ячейки второго ряда, то вследствие опрокидывания первого триггера кольцевого .коммутатора о.прокинетс5 только первый триггер регистр.а. - , .

регистра, начиная с опрокинутого триггер.и, г, результате чего все триггеры регистра зосстановят свое начальное состояние. Переход последнего триггера регистра в начальное состояние приведет к возни.кновению нлилульса, подаваемого -на коммутационные входы всех, начиная со второго, триггеров кольиезого коммутатора. Такой 1мпульс возни-кнет и в том случае, когда со второй матрицы Б состав сомножителей Бошел последний элемент строки матрицы. В этом случае на одном из потенциалыых входов переключающих ячеек второго ряда не будет сигнала, вследствие чего им.пульс, возникший при оиро кидывании первого триггера кольцевого ко: 1мутатора, иройдет через схе.мь «Р1ЛИ 3 п о нос,1еднего столбца на ком.мутационные входы тр и ггер ОБ ко м му та тор а.

Под влиянием указанного .выше тактового импульса опрокинется вторично (вернется в исходное положение) srOipoA триггер комлптатора, а имп}льс с его выхода нройдет в первую переключающую ячейку третьего ряда. Одновременно опрокинется третий триггер коммутатора. Дааьше процесс будет происходить аналогично, как и после подачи импульса на имшульсиый 1вход переключающей ячейки второго рода.

На последнем цИ1чле работы устройства, который начинается с :по.вторного опрокидывания (возвращения в исходное состояние) предпоследнего триггера ;сольцевого iiOAiMyтатора, опрокинется впервые последний триггер этого коммутатора и одновременно на импульсный вход первой псреключаюихей ячейки подается управляющий сигнал. Если на потенциальном -входе одной из ячеек этого ряда имеется сигнал, то этот имлульс приведет к опрокидыванию триггера регистра, соответствующего ооследующему столбцу, и работа регистра начинается с возвращения этого триггера в исходное состояние. После окончания работы регистра лоследннй триггер кольцевого коммутатора вернется в исходное состояние, а вследствие кольцевого соединения в исходное состояние вернегся и ие.рвый триггер этого ком.утатора. Такой же эффект получится и при отсутствии сигнала иа потенциальных «.ходах всех переключающих ячеак последнего ряда. Только в этом случае возвращение последнего, а зате.м и первого, триггеров кольцевого коммутатора в исходное состояние произойдет под воздействием импу.чьса, ирощедшего через схемы «ИЛИ 3 и 5 последнего столбца.

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

щи.м через схему «ПЛИ 3, появляются па очереди импульсные сигналы, которые по;uuoTCii на входы соответствующих схем «И /. Пр}1 наличии сигналов на -иотенциальиых входах этих схе.м указанные сигналы пройдут через схему «ИЛИ 6 на сход триггера /2 з:-1ака. Общее число импульсов, поступивших ia ВХОД этого триггера за все время работы }стройства, точно равно количеству инверсий в последовательности вторых инде; еов элементов матрицы, являющихся сомножителями члена определители.

Ввиду того, что -при лодаче на вход Tipnrreра знака каждого импульса индиц.рованный знак изменяется на противоположный, знак, станов);зщийся после окончания работы устройства и будет знаком данного члена определителя ИрИ условии, что в ИСХОДЮМ СОСТОЯiiiui индицировался знак «-L.

Дейсгвигельно, непосредственно перед ноступ.чением управляющего сигнала на импульсный вход первой переключающей ячейки /-ГО ряда () имеются сигналы на потенциальных входах схем «И 7, еоответствующих столбцам с порядковыми номера.ми, /С; 1, i-l, 2, ..., (j-l), в которых расположены элементы матрицы-сомножители чле;-;а определителя, принадлежащие к строкам с порядковыми номерами . Если элемент /-Й строки, являющийся сомножителем дан0ного члена определителя, расположен в /с/ -м столбце, то при /v иод воздейстВИем у-иравляющего импульса,, снимаемого с 15ыхода (/-1)-го триггера кольцевого коммутатора, появится сигнал еще иа потенц.иальном входе схемы «И 7, принадлежащей /Су --му столбцу. При Kj /г начнется работа регистра с опрокидываиия триггера, принадлежащего к (к / -f 1) -му столбцу.

В данном случае на вход триггера знака

0 поступит столько счетных импульсов, околысо из чисел j , , 2, ..., (/-), больще числа Kj . Количество таких импульсов будет определяться количеством чисел в последовательности вторых индексов, превышающих /с/ н находяпдихся впереди него. Это н будет число беспорядков, обусловленных распо.чожением числа к/ и& /-М месте данной последователь)1ости. ЕслИ же к/ п, то регистр вообще не сработает и на триггер знака не поступит ни

0 OviiBH имцульс. Это влолпе законО|Мйр(ИО, так как в лоследовательности вторых индексов впереди числа KJ я не может на.ходиться превышающее его число. Регистр не работает также до поступления упра вляющего им-иульса на переключающие ячейки второго ряда. В этом и нет необходимости, так как впереди первого числа в последовательности импульсов нет вообще других чисел.

Излолсенный выше принцип работы пред0лагаемого устройства .проиллюстрируем ца примере .поиска знака члена определителя матрицы пятого порядка, сомножителями «отарого являются элементы: gts, gzs, Язь