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

Союз Советскиз Социалистические РеспубликОПИСАНИЕИ ЗОБРЕТЕ Н ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Фl"-".". Зависимое от авт. Свидетельства-Заявлено 03.11,1969 ( 1318998/18-24)с присоединением заявки-Прчоритет - - Опубликовано 21.1 Ъ.1972. Ь Оллетень14 М.Кл, 6 061 15(32 Комитет по делаю кзооретений и открытий ори Совете Министров СССРУДК 681.323 (088.8) Дата опубликования описания 20,Х.1972 1 вторы1 зобретени И. Блажкевич и михайлов; 3 ая Вител Физико-механический институт АН Украинской ССР УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЗНАКА ЧЛЕ ОПРЕДЕЛИТЕЛЯ 1 т 1 АТРИ ЦЪ Изобретение Относится к составным частям специализированных математических машин, предназначенных для раскрытия определи- гелей матриц, элементы которых выражаются буквенными символами.Известно устройство для определения знака членов определителя матрицы, содержащее коммутатор, селектор, триггеры, индикаторы знака, логические схемы И, матрицу с закороченными вертикальными н горизонтальными шинами одного номера, вертикальные шины которой присоединены соответственно ко входам триггеров селектора и выходам триггеров коммутатора, и ключи, соответствующие отдельным элементам матрицы, определитель которой подлежит раскрытию, управляемые сигналами с выходов триггеров, образующих коммутатор искателя сомножителей.Основным недостатком известного устройства является то, что согласно ачгоритму, реализуемому в этом устройстве и основанному па подсчете количества циклов в подстановке индексов элементов матрицы, являющихся сомножителями члена определителя, каждый из таких циклов отображается в устройстве изолированной группой шип, соединенных между собой через управляемые ключи, соотВетствующие указанным выше элементам матрицы. Обусловленная этим необходимость электрической изоляции шин матрицы знака искателя в значительнои мере затрудняет использование в качестве управляемых ключейполупроводниковых бесконтактных приборов,Практически приемлемая реализация извест 5 ной схемы знакоискателя невозможна безприменения контактных управляемых ключей(реле), что значительно снижает быстродействие устройства и уменьшает сроки безотказной его работы.10 Целью изобретения является повышениебыстродействия и надежности работы устройстВа для поиска знакОВ членоВ определителя.Предлагаемое устройство для определениязнака членов определителя матрицы содер.15 жит, как и известное, регистр. кольцевойкоммутатор, блок задержки и переключаю.шие ячейки, состоящие из логических схемИ и НЕ и соответствующие отдельнымэлементам матрицы, за исключением первого20 элемента первой строки и последних элеме тов всех строк,Потенциальные входы отдельных переключающих ячеек присоединены к выходам соотВетствующих триггеров искателя сомножите 25 лей. Переключающие ячейки, соответствующие элементам одной строки, соединены последовательно таким образом, что импульсный вход последующеи ячейки присоединен кпервому выходу предыдущей ячейки. Им 30 пульсиый вход ячейки, соответствующей вто 336664я 10 15 20 25 30 35 го 45 50 55 60 65 рому элементу первой строк матрицы, присоединен вместе с коммутационным входом первого триггера кольцевого коммутатора через блок задержки к источнику пускового импульса, К этому источнику непосредственно подключены входы установки пачалы 1 ого состояния всех триггеров устройства. Вторые выходы переключающих ячеек, соответствующих,всем элементам одного столбца матрицы, за исключечием элементов ес первой строк 1, присоединены к отдельным входам логической схемы ИЛИ, соответствующей данномугстолоцу, а первые выходы переключающих ячеек, соответствующих аналогичным элементам предпоследнего столбца матрицы, к о- дельным входам схемы ИЛИ, соответстьующей последнему столбцу матрицы. Второй выход каждой из переключающих ячсек, соответствующих элементам г;ервой строки матрицы, присоединен ко входу второй схемы ИЛИ, соответствующей стол бц мято ицы, в которог расположен этот ке элех 1 ент, Ко входу второй схемы ИЛИ, соответствующей последнему столбцу матрицы, прпсоеди 1:ен первый выход переключающей ячейки, соответствующей элементу первой строки матрицы, расположенному в ее предпоследнем столбце. Второй вход каждой из вторых логических схем ИЛИ присоединен к выходу соотвстствуюьцей пеовой схемы ИЛИ. К этому же выходу;подключен один из входов третьей логической схемы ИЛИ, соответствующей данному столбцу. Второй вход этой схемы присоединен и выходу состветствующего этому же столбцу триггера регистра. Выход каждой из треты 1 х схем ИЛИ, соответствующих отдельным столбцам матрицы, за исключеппем ее последнего столбца, подключен ко входу триггера регистра, который (триггер) принадлежит к последнему столбцу матрицы. Вход, первого триггера регистра соединен с выходом логической схемы ИЛИ, соответствующей первому столбу матрицы. Выход третьей логической схемы ИЛИ, соОтветствующеи последнему столбцу матрицы, соединен с коммутационными входами всех триггеров кольцевого коммутатора, за исключением первого триггера этого коммутатора. Выход каждой из вторых логически схем ИЛИ, соответствугощих отдельным столбцам матрицы, присоединен по входу запоминающего триггера, выход которого подключен к потенциальному входу отдельной логической схемы И. Импульсньй вход каждой такой схемы включен па гыход соответствуощего данному столбцу матриць триггера регистра. Выходы всех логических схем И, соответствую 1 цих отдельным столбцам матрицы, присоед."сны к разным входам огдсльной логической схемы ИЛИ, сигнал с выхода которой подается па счетный вход триггера, управляОщего индикаторами знака.Кольцевой коммутатор образован триггера- МИ, СООТВЕТСТВ 101 ЦПМ 11 ОТДСЛЫЫМ СТРОКЯМ мятр 1 ц 1. Вьход кяждо 0:3 таких трнгерон,за исключением последнего триггера, присоединен к импульсному входу переключающей ячейки, соответствующей первому элементу последующей строки матрицы, Выход первого из этих триггеров присоединен дополнительно к потенциальному входу отдельной логической схемы И, на второй импульсный вход которой включен генератор тактовых импульсов. К выходу этой логической схемы присоединены коммутационные входы всех триггеров регистра,Предлагаемое устройство для поиска знака членов определителя матрицы может быть без каких-либо затруднений выполнено исключительно на полупроводниковых бесконтактных элементах, что обеспечивает возможность значительного повышения его быстродействия и удлинения сроков безотказной работы.На фиг. 1 изображена функциональная схема устройства в целом, на фиг. 2 - фупкц 1 опальная схема его переключающих ччеек.Как известно, каждый из членов определителя матрицы и-го порядка 9 = д. "(, где =1, 2, , и - номер строки, а к=1, 2, 3, , гг - номер столбца, в которых расположен элемент др, матрицы, представляет собой произведение элементов матрицы, каждый из которых находится в иной се строке и в ином столбце, и может оыть представ, Ои ь зи е:Йй,Д 2 г, " Я/Фг" Дл,л,причем и,1=,-к,+тк, 7= . - ,.-кл .Знак такого члена может быть определен количеством беспорядков (инверсий) в последовательности вторых индексовкь к, к;,., кл,При четном числе таких беспорядков этот знак положительный, при нечетном - отрицательный. Этот спосоо определешя знака члена определителя и положен в основу алгоритма, реализуемого в предлагаемом устройстве, функциональная схема которого приведена на фиг. 1.Состоит оно из переключающих ячеек 1, блока задержки 2, логических схем ИЛИ ,3, 4, 5, 6 и И 7, 8, запоминаОцих триггеров 9, триггеров 1 О регистра, триггеров 11 кольцевого коммутатора, триггера 12 знака и индикаторов знака 13,Перек;почающие ячейки ставятся в соответствие отдельным элементам матрицы, за искл 1 очением первого элемента псрвой строки д И ПОСЛЕДНИХ ЭЛЕМЕНТОВ ВСЕХ СЛрОК ргл 1=1, 2 гг, На потенциальные входы перекл 1 очягощих я 1 еск гпода 1 отся сиг 1 ал с выходов соответствующих триггеров искатели сомнокителей. Перекл 1 оча 1 ощие ячейки, соотпетствующи. элементам одной и той же строки, на фиг. 1 расположены в олпом ряду, я соответству 1 О 1 цпе элемс 1 там ОдОго и того же столбца матрицы - в одном столбце расположения соответствующих строк и столбцов г, самой матр 1 це. Остальным столоцам поставлено в соогветствис по одной схем- ИЛИ 3, ИЛИ 4, ИЛИ 5, И 7, по о,. Оъу запо. мчияюцему трпггеру 9 и триггеру Й 1 рсг 1 Сгрг.б 5 5Входы схем ИЛИ 3, поставленных в соответствие отдельным столбцам матрицы, за исключением пос;сднего ес сголбца, присоед."111 ены ко вторым выходам переключающих ячеек, соответствующих элементам данного столбца, за исключением элемента первой строки. Входы схемы ИЛ 1 Л 3 последнего столбца подключены к первым выходам переключающих ячеек, соответствующих такиз же элементам предпоследнего столбца.Один из входов каждой схемы ИЛИ 4 соединен с выходом соответствующей схемы ИЛИ 3, Второй вход схемы ИЛИ 4 последнего столбца подключен к первому выходу последней переключающей ячейки, находящейся в первом ряду. У остальных схем ИЛИ 4 вторые входы соединены со Вторыми выходами первых переключающих ячеек соответствующих столбцов.Выход схемы ИЛИ 3 первого столбца присоединен ко входу триггера 10 регистра, соответствующего второму столбцу. Выходы Остальных схем ИЛИ 3 подклочены дополнительно ко входам соответствуощих схем ИЛИ 5. Вторые входы этих схем подключены к выходам соответствующих триггеров 10 регистра. Выходы схем ИЛИ 5, за исключением схемы ИЛИ 5 последнего столбца, присоединены ко входам триггера 10 регистра последующего столбца.Выходной сигнал схем ИЛИ 4 подается на вход соответствующего запоминающего триггера 9. Сигналы с выхода запоминающего триггера 9 и триггера 10 регистра, соответствующих одному и тому же столбцу, подаются ца отдельные входы соответствующей этому жс столбцу схемы И 7. Выходы всех схем И Т цодклочены к отдельным входам схемы ИЛИ 6, вьходцой сигнал которой подается на счетный вход триггера 12 знака, к Отдельным выходам которого подключены индикаторы зпака + и-И,Переключающие ячейки, цаходяц;неся в одном ряду, соединены последовательно таким образом, что импульсный вход последующей ячейки подклочен к пеовому выходу предыдущей ячейки. Импульсный вход первой блокирующей ячейки первого ряда подклочец через блок задержки 2 к источ ику пускового импульса.Каждому ряду персключающцх ячеек (стро.ке матрице) соответствует отдельный триггер 11 кольцевого коммутатора. Коммутирующий импульс ца первый трипер этого коммутатора поступает через блок задержки 2 от источника пусковых импульсов, Коммутирующие цмпуль"ы ца остальные триггеры кольцевого коммутатора подаются с выхода схемы ИЛИ 5, соответствующей,последнему столбцу матрицы. К выходам триггеров 11 кольцеВого коммутатора, за исклоснием триггера, соотвсгствуюц 1:со последнему ряду переключающих ячеек, подклОчецы импульсные входы псрвых пере 1 лОаОпих 51 чсек после;1 х 10- 1 ццх р 51 доц. 1, Вьходу первого 3 этх трцгс 5 10 5 20 25 30 35 40 5 ,О 60 ров дополнительно подключен один из входов схемы И 8. На второй вход эгой схемы подаются сигналы от генератора тактовых импульсов. К выходу схемы И 8 подключены коммутационные входы триггеров 10 регистра.Функциональная схема отдельной переклочающей ячейки представлена на фиг. 2, Состоит эта ячейка из логических схем И 14, 15 и инвертора НЕ 16. К потенциальному Входу ячейки присоединен вход инвертора,16 и потенциальный вход схемы И 15. К выходу инвертэра НЕ 16 подключен потенциальный вход схемы И 14. Соединенные вместе импульсные входы схем И 14 и 15 образуют импульсный вход ячейки. Первый выход переключающей ячейки совмещен с выходом схемы И 14, а второй - с выходом схемы 1 Л 15.При отсутствии сигнала на потенциальном входе переключающей ячейки сигналы, поступающие ца ее импульсный вход, направляются на первый выход, так,как в этом случае ца общих входах схемы И 14 имеется сигнал. При наличии сигнала на потенциальном входе переключающей ячейки сигнал с импульсного входа ячейки поступает ца се второй выход.Подготовка устройства в целом к попсы найденного члена определителя заключается в подаче постоянных сигналов ца потецциаль. ные входы переключающих ячеек, соотзетствующих элементам матрицы, являющимся сомножителями члена определителя, Работа устройства начинается с момента подачи единичного пускового импульса, которьп прежд. всего устанавливает все триггеры устройства в исходном состоянии. Через время т, опреде. ляемое блоком задержки 2, этот же импульс опрокинет один цз запоминающих триггеров, вследствие чего ца одном из входов соответствующей схемы И 7 появится, постоянный сигнал. Одновременно опрокинется первый триггер кольцевого коммутатора, вследствц чего Опрокинется второй триггер этого коммутатора, а схема И Я откроет путь тактовьи 1 импульсам ца .коммутационные моды триггеров регистра, Вместе с тем прц отсутствип сигнала на потенциальном входе первой переключающей ячейки второго ряда произойдет опрокидывание еще одного цз запоминаощцх триггеров, а в случае, когда этот триггер соответствует не последнемч столбц матрицы - опрокидывание триггера регистра, соответству ощего ближайшему по очереди столбцу матрицы, Если из второй строки матрицы в состав сомножителей вошел первый се элемент, то есть, когда имеется сигнал на потенциальном входе первой ячейки второго ряда. то вследствие опрокидывания первого трцп ера кольцевого коммутатора опрокинется только первый триггер регистра. После опрокидывания любого цз трцггероц регцсгра подаваемые через схему И с) так. товые импульсы приведут к срабатываниюрегистра, начиная с о 1 р 3.1 Путого трцггер, ц результате чего все трпггсры реги ".ра Восст- новят свое начальное состо 51 нис. Переход по- следнеГО триггера 13 СГистр В начальное состояние приведет к воз:11 гкновенио цм 1 ульс 1, подаваемого на коммутционные входы всех, начиняя со дорого, т 13 НГ 1 еповкоммутатора. Такой цмпульс возникнет и В том слУч 2 е, КОГда со 13 тОР 01 сГ."30 ки хЯт 13 ццы в состав сомножителей Вошел последний элемент строки матрицы. Б этом случае ца одном из потенциальных входов переключающих ячеек второ о ряда цс бдег с 1 Гц,12, вслед. ствие чего цмпгльс, возн 1 гкшцй прц опрокидывании пе 13 вого тРиггеРЯ К 0,1 ьцевого коз 31 Ут- тора, пройдет через кемь ИЛИ д ц 2 по- С,1 ЕДНЕГО СТОЛОЦЯ 112 К 031 МУТЯЦИО;11 ЬЕ ВХОДЫ триггеров коммутатора.Под В:1 иянцем ук 2 зяннОГО .Выше тактОВОГО 1 мт 1 улься опрокинется вторично (Ве 13 пется в исходное положение) ВторОЙ триГГВ 13 коммутатора, а импульс с его выхода пройдет в первую переключающую ячейку третьего ряда. Одновреме.Но опрокинется третий триггер коммутатора. Дальше процесс будет пропсходить аналогич 10, как и после подачи импульса ца цжсульсцы 1 вход первой переключающейей ячейки Второго рода.На последнем ццкле работы устройства, который начинается с повторного опрокидывания (возвращения В исходное состоя 1 цс) Н 13 ед 30 след 1 геГО триггера кольцсього 1 гоммутатора, опрокинется впервые последний триггер этого коммутатора ц одновременно ца импульсный вход первой переключающей ячецк 1 11 Одяется упр .Вляющий сиГ 1 ал. Если ца потенциальном Входе одной из ячеек этого ряда имеется сигнал, то этот импульс приведет к опрокидыванию триггера регистра, соответствующего последующему столбцу, и работа регистра начинается с возвращения этого тритгера в исходное состояпис. После окончания работы регистра ,последний триггер кольцевого коммутатора Вернется В исходное состояние, а вследствие кольцевого соединения в исходное состояние вернется и Цгрвый триггер этого коммутатора. Такой же эффект получится и при отсутствии сигнала ц потенциальных входах всех переключающ:х ячеек последнего ряда. Только в этом случае возвращение последнего, а затем ц первого, триггеров кольцевого коммутатора в цсходцое состояние произойдет под воздействием импульса, прошедшего через схемы ИЛИ 8 и О последнего столбца.Прц возВращении первого триггера кольцеВого коммутатора в исходное состояние исчезает сигнал на потенциальном входе схемы И 8, вследствие чего прекратится подача тактовых юьпульсов ца коммутационные входы триггеров регистра, и работа устройства будет окончена.Во время каждого из.циклов срабатывания регистра па входах, каждого из его триггеров, цачпцая с опрокинутого сигналом, поступаюц:.1 х Через схсг;у 11 Л 1 Л 8, появляются по ОЧСРЕДЦ ЦМ.1 У:ЬСЦЫЕ СИГПЯЛЫ, КОТОРЫЕ ПОдОтс 51 ц я Вход:соот 13 етству 10 цпх схем И ". Прц цл:1 чцп сцгналов на потенциальных ВходЯК этих схез указанные с 11 Г 5 а.ы Н 13011 дут через схему ИЛИ 3 на вход триггера 12 з:1 Як. Общее число импульсов, пост;пившихна вход этого тр 1 ггера за все время работы 1 стройств, точно равно количеству инверсий13 последовательности Вторых индексов элсментов матрицы, являющихся созногкцтелям:1 дац Гого члена определителя,Ввиду того, что,при подаче на Вход приНера знака каждого ихпульса индцццрованный15 знак Изменяется ня протцв 010 ложцый, зняк,устаповпвшцйс 51 пос,с Окончания 13200 ы устройств и будет зцаком данного члена опрс;1 слцтсля при услоши, что в исходном состояши 1 ндццировался знак +,20 Действ:Тельно, непосредственно пс 13 сд ПОступлецием управля 1 ощего сигнала ца имп 3 льсны 111 вхо;1 первой переключающей ячейки у-Го ряда (у,=-1) имеются сигналы ца потенциальных входах схем И 7, соответст 2 Вующих столбцам с порядковыми номерами,к; )1, 1=1, 2, , (у - 1), в которых расположены элс 3 ецты матрицы - сомноясител 11 чле 2051 ределпте 51, пр 5 Надлежащие к строкам сцорядковы.".и номерами ". Если элементЗО 1-1 строки, являющийся сомножителем данного члсца определителя, расположен в к; -хстолоце,то при к,1 ад воздействием управляющего импульса, снпмасмого с выхода1 - 1) -го триггера кольцевого коммутатора,З- появитс 5 сигнал ещс на потенциальном входесхемы И 7, принадлежащей К, -му столбцу.При к, (г начнется работа регистра с опрокидывания т 13 НГГе 132, п 13 ч 1 Ня: ежщего1 к г +1) -му столбцу,40 В данном случае на вход триггера закяпоступит столько счетных ИМГ 1 ульсо 13, сколькоиз чисел К, 1=1, 2, , (у - 1), больше числак;. Количество таких импульсов будет определяться,количеством чисел В последовательности вторых индексов, правьшающих к; цнаходящихся впереди него. Это и будет числобеспорядков, обусловленных расположениемчисла к; ца у-и месте данной последовательности. Если же к; =г, во рег 1 Ст 13 вообще пе;,О сработает ц на триггер знака не поступит ниО;ниц импульс, Это вполне закономарНо, таккяк В последоВательности Вторых пцдсксОВВпс 13 едп числя к =гг нс МОжет цяходчтьс 51превышающее его число. Регистр це работаеттакже до поступления управляющего имцульса на переключающие ячейки второго ряда.В этом и нет необходимости, так как впередипервого числа в последовательности цмпульсов нет вообще друтих чисел.6 О Изложенный вьипе принцип работы предлагаемого устройства проиллюстрируем напримере поиска знака члена определителяматрицы пятого порядка, сомножителями котОрОГО являОтея элОмюцты: 5 р 723 731 т04 Я 5В последовательности вторых индексов этих элементов имеется шесть инверсий, а именно одна инверсия числа 3, и по две инверсии чисел 1 и 2, и одна инверсия числа 4.На подготовительном этапе должны быть поданы сигналы на потенциальные входы третьей переключающей ячейки второго ряда, .первой - третьего, второй - четвертого и четвертой - пятого ряда, На первом этапе работы устройства сигнал появится на потенциальном входе схемы И 7 третьего столбца. На втором этапе появится сигнал на потенциальном входе схемы И 7 третьего столбца и произойдет поочередное опрокидывание триггеров регистра, начиная с триггера, пренадлежащего к четвертому столбцу. При этом на вход триггера знака через схему И 7 пятого столбца пройдет один счетный импульс. На третьем этапе опрокинется первый триггер регистра, а во время последующей работы регистра на вход триггера знака пройдет через схемы И 7 третьего и пятого столбцов два импульса, На четвертом этапе появится сигнал еще на потенциальном входе схемы И 7 второго столбца и произойдет поочередное переключение триггеров регистра, принадлежащих третьему, четвертому и пятому столбцам. Вследствие этого на вход триггера знака поступит дальнейших два счетных импульса через схемы И 7 третьего и пятого столбцов, На заключительном этапе опрокинется пятый триггер регистра, а начатая этим работа регистра приведет к подаче на вход триггера знака еще одного счетного импульса черезсхемы И 7 пятого столбца, За все время на вход этого триггера поступит б импульсов, в результате чего он вернется в исходное состояние, при котором ин указывает знак + Зтот знак и буд зна ом данного члена определителя,Предмет изобретения 0Устройство для определения знака членов определителя матрицы, содержащее коммутатор, матрицу переключающих ячеек, регистр, запоминающие триггеры, блок задержки, триггер знака, индикаторы знака и логиче ские схемы И и ИЛИ, отличаощееся тем, что, с целью повышения быстродействия и надежности устройства, импульсный вход первой ячейки первой спроси соединен со,входом коммутатора и с выходом блока задержки, а 20 импульсные входы первых ячеек остальных строк соединены с соответствующими выходами коммутатора, импульсные входы остальных переключающих ячеек присоединены и первым выходам предыдущих в своих строках 25 переключающих ячеек, первые п,вторые выходы всех переключающих ячеек подключены через соответствующие схемы ИЛИ к соответствующим входам запоминающих триггеров и триггеров регистра, а выходы запоми нающих триггеров и соответствующих им триггеров регистра через соответствующие схемы И подключены ко входам схемы ИЛИ, выход которой подключен к счетному входу приггера знака.Б 6