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

Описание патента на изобретение SU218538A1

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

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

и Подключены к источнику литания.

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

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

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

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

входов схемы совнадений 5 согласуется с количеством Шип /г, в системе шин.

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

Количество задейстБоваиных вертикальных шин И входов схемы совпадений 5 зависит от порядка п коикретиой матрицы. Одновременно число задействованных упра1вляемых ключей 2 и управляющих ими триггеров 5 зависит от числа N ненулевых элементов этой матрицы. Способ присоедиления управляемых Ключей 2 в системе шин, соединение триггеров 5 коммутирующего устройства и оодключение К «им триггера конца поиска зависит от способа расположения этих элементов в данной матрице. Итак, в схему устройства включаются ключи 2 и триггеры 3 первых по порядку п групп, причем каждая из групл и ее триггер ставится в соответствие отдельной строке матрицы. Р1з каждой такой группы В:Ключается столько первых по порядку ключей 2 и триггеров 3, сколько имеется в соответствующей строке матрицы Q ненулевых элементов, лрнчем каждый из этих ключей и управляющих Ичми триггеров ставится в соответствие отдельному ненулевому элементу данной строки (первый ключ дажной группы- первому ненулевому элементу, второй ключ - второму элементу и т. д., -независимо от порядкового номера столбца, в котором находится данный элемент).

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

Один контакт iBcex ключей 2 присоединен на постоянно -к источнику 12 рабочего сигнала. Вторые контакты задействованных в схеме управляемых ключей 2, соответствующие ненулевым элементам матрицы Q (например, элементу q , расположенному на пересечении ее J-ой строки и к-го столбца), присоединены к соответствующей шине (к-ой) системы вертикальных шин. Задействованные. в схе.ме триггеры 3 коммутирующего устройства, соответствующие ненулевым элементам матрицы Q, расположенным в одной ее строке, соединены между собой по кольцевой схеме (выход

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

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

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

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

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

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

Число горизонтальных и число вертикальных шин системы щин 13 равны числу шин 1 искателя сомножителей п.. Такое же количество триггеров 15 .коммутатора и триггеров 16 селектора. Горизонталвная и вертикальная шины с одинаковым порядковым номером соединены накоротко. Каждая пара таких щин подключена к цепи управления отдельного триггера 16 селектора. Первые п пар шин системы щин 13 дополнительно присоединены по порядку к отдель1ным выходам первых п триггеров 15 коммутатора (- - триггеров 15 коммутатора соединены последовательно (выход первого подключен ко входу второго, выход второго - ко входу третьего и т. д., а выход предпоследнего - ко входу последнего). Цепи управления всех этих триггеров присоединены ко входу схемы совпадений 19, один из входов которой подключен к входу источника 8 периодических управляющих сигналов, а второй - к выходу схемы совпадений 5 с п входами. Выходы установки начального состояния этих же триггеров через ключ 20 установки начального состояния подключены к источнику 12 рабочего сигнала таким образом, чтобы в состоянии готовности к однократной передаче сигнала от источника управляющих сигналов на свой выход находился только первый триггер. Выходы установки состояния триггеров 16 селектора присоединены через этот же ключ 20 к источнику 12 рабочего сигнала таким образом, чтобы в аналогичном состоянии готовности находились все эти триггеры. Выходы всех триггеров 16 селектора подключены .1К соединенным накоротко входу в цепь улра;зл€ н.ия триггера 18, к одному из выходов

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

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

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

Итак, из ненулевых элементов определеной строки (t-ой) матрицы Q ставится в соответствие один из управляемых ключей 14 группы ключей (t-ой), соответствующей данной строке (первому ненулевому элементу -

первый по порядку ключ, второму - второй и т. д.). Второй контакт ключа, соответствующий элементу 7;j, , присоединяется к к-ой вертикальной шине, соответствующей к-ому столбцу матрицы Q.

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

До начала работы знакоискателя все входящие в его состав триггеры 15 и 16 путел кратковременного замыкания ключа 20 установки

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

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

Работа злакоискателя иачинается с момента появления на выходе схемы совпадений 5 сигнала; который, воздействуя на схему coiBпадений 19, открывает путь управляющим импульса 1К триггерам /5 ком1мутатора, вследствие чего «а всех подключенных к выходам этих триггеров вертикальных шинах системы шин 13 появляются по очереди управляющие сигналы. На объединеином выходе триггеров J6 селектора появляется лишь столько управляющих импульсов, сколько групп соединенных вместе пар шии, т, е. сколько замкнутых циклов V у графа, соответствующего найденному члену определителя.

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

После записи сомножителей и знака найденного члена определителя работа устройства возобновляется путем подачи от переключателя П единичного управляющего импульса на триггеры 3. Если включенная новая группа п ключей 2 соответствует сомножителям нового члена определителя, то состояние схемы совпадений 5 останется без изменений, а периодическая работа искателя сомножителя «е будет восстановлена. В противном же случае, вслед за единичным управляющим импульсом, когда открыт путь периодическим управляющим сигналам через схему совпадений 7, начинается автоматический поиск сомножителей следующего члена определителя. Принципиальные схемы узлов устройства приведены на фиг. 3 (за исключением источника 72 рабочего сигнала, показанного в виде блока). Система вертикальных шин / искателя сомножителей и система скрещивающихся вертикальных и горизонтальных шин 13 объединены в коммутационное поле 1 и 13, к которому /подведены и свободные контакты управляемых ключей 2 искателя сомножителей и управляемых ключей 14 знакоискателя. Контакты присоединяются к соответствующим вертикальным шинам с помощью гибких двойных шнуров и штепсельных разъемов. Схема совпадений 5 с п входами и логическая схема 6 «НЕ объединены для упрощения в схему 5 н 6 (выполняющую логическую операцию «PI - НЕ). Входы этой схемы с помощью переключателей KI, К.2, Кз, - К,1-1, К„ присоединяются к вертикальным шинам системы шин 1, или непосредственно к источнику рабочего сигнала (нулевой зажим источника 12 питания). Индикация «задействованных входов схемы «И - НЕ, т. е. входов, присоединенных к шинам, осуществляется с помощью сигнальных лампочек Л, Л, Л,,,, ...,Лп-1, Л„. Схема совпадения 7 образуется усилительным каскадом на триоде TI, питаемом непосредственно с выхода источника 8 периодических сигналов, и шунтирующими выход этого каскада двумя ключами на триодах Т, и Гз, первый из которых управляется сигналом с выхода схемы 5 и 6, а второй - с выхода триггера 4 конца поиска. Блок знакоискателя, осуществляющий логическую операцию «НЕ, выполнен в виде усилителя на триоде Т, питаемого от источпика периодических сигналов, выход которого зашунтирован выходом схемы «И-НЕ. Роль источника единичных управляющих сигналов выполняет в данной схеме зажим - 9 е источника питания, к которому через резистор

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

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

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

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

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

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

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

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

матриц, содержащее коммутаторы, селектор, лителя матрицы, оно содержит матрицу пс;,а теля сомножителей и матрицу зна-коискателя с закороченными вертикальными и горизонтальными шинами одного номера, вертикальные шинь которой подсоединены соответственно ко входам триггеров селектора и выходам триггеров коммутатора, вертикальные шииы матрицы искателя сомножителей соединены со входами схемы «И, выход которой через 1вентиль подключен к управляющему входу коммутатора и через схему «НЕ подсоединен ко входу второй схемы «И, управляющий вход вентиля подключен к гшератору импульсов, а управляющие входы ключей матрицы искателя сомножителей подсоединены соответственно ко входам триггеров второго коммутатора, выход которого соединен через триггер конца поиска со вторым входом второй схемы «И, управляющий вход второй схемы «И подсоединен к генератору импульсов, а выход - к управляющему входу второго коммутатора, горизонтальные щины матрицы искателя сомножителей объединены и подключены к ИСТОЧНИКУ литания.

Похожие патенты SU218538A1

название год авторы номер документа
УСТРОЙСТВО для ОПРЕДЕЛЕНИЯ ЗНАКА ЧЛЕНОВ ОПРЕДЕЛИТЕЛЯ МАТРИЦЫ 1972
  • Б. И. Б.Пажкевич Е. Д. Михайлова
  • Физико Механический Институт Украинской Сср
SU336664A1
Устройство для раскрытия определителей матриц и поиска прадеревьев направленного графа 1971
  • Блажкевич Богдан Иванович
  • Михайлова Евгения Дмитриевна
  • Спиридонов Юрий Алексеевич
SU474809A1
УСТРОЙСТВО ДЛЯ АНАЛИЗА ОПРЕДЕЛИТЕЛЕЙ 1971
SU300881A1
УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ПЕРЕДАЧИ ГРАФА 1970
SU259495A1
УСТРОЙСТВО ДЛЯ РАСКРЫТИЯ ОПРЕДЕЛИТЕЛЕЙ МАТРИЦ 1971
SU294144A1
УСТРОЙСТВО ДЛЯ РАСКРЫТИЯ ОПРЕДЕЛИТЕЛЯ МАТРИЦ 1969
SU243269A1
Специализированная электронная машина для анализа определителей 1969
  • Базилевич Роман Петрович
SU481037A1
Устройство для вычисления спектра Фурье 1983
  • Зенцов Владимир Александрович
  • Чупик Радослав
SU1121678A1
УСТРОЙСТВО для РАСКРЫТИЯ и ВЫЧИСЛЕНИЯ ОПРЕДЕЛИТЕЛЕЙ МАТРИЦ 1973
  • Г. Левин, Г. Е. Барсуков Г. И.
SU404090A1
УСТРОЙСТВО для ПЕРЕВОРА СОМНОЖИТЕЛЕЙ ДЕТЕРМИНАНТА МАТРИЦЫ 1969
SU255647A1

Иллюстрации к изобретению SU 218 538 A1

Реферат патента 1968 года УСТРОЙСГВО для РАСКРЫТИЯ ОПРЕДЕЛИТЕЛЕЙ МАТРИЦ

Формула изобретения SU 218 538 A1

-Р ЕЗ-МЗЗЕЙ-EZvT -f.

г .

SU 218 538 A1

Даты

1968-01-01Публикация