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

 

243269

О П И С А Н И Е

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Соеетских

Содиалистическик

Республик! ВС 1. НЗЖ А Я

ПАТЕ11ТИОТ1 ХИ11 ЧЕСКАЯ

БИБЛИОТЕКА

Зависимое от авт. свидетельства № 218538

Заявлено 15.Х1!.1967 (№ 1203470/18-24) с присоединением заявки №

Приоритет

Опубликовано 05 V.1969, Бюллетень № 16

Дата опубликования описания 23.IХ.1969

Kë. 42п», 15/32

МПК 6 06f

УДК 681.3:51 (088.8) Комитет по делам изобретений и открытий

IlpH Совете Министров

СССР

Авторы изобретения

Б .И. Блажкевич и Е. Д. Михайлова

Физико-механический институт АН Украинской ССР

Заявитель

УСТРОЙСТВО ДЛЯ РАСКРЫТИЯ ОПРЕДЕЛИТЕЛЯ МАТРИЦ

Известно устройство для раскрытия определителя по авт. св. № 218538.

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

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

Это позволяет ускорить раскрытие опреде5 лителя матриц.

На фиг. 1 изображена функциональная схема устройства; на фиг. 2 — функциональная схема рабочей ячейки; на фиг. 3 — функциональная схема коммутаторной ячейки; на фиг.

10 4 — функциональная схема блокирующего элемента.

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

15 Регистр, соответствующий первой строке, состоит из триггеров 1, соответствующих отдельным ненулевым элементам этой строки, а регистры, соответствующие остальным строкам, образуются рабочими ячейками 2, соответст20 вующими отдельным ненулевым элементам этих строк. Кроме того, в состав устройства входят реверсивный коммутатор 8, состоящий из триггера 4, поставленного в соответствие первой строке, и коммутаторных ячеек 5, по25 ставленных в соответствие остальным строкам матрицы, мультивибратор задержки б, схема

«ИЛИ» 7, схема «И» 8, блокирующий элементячейка 9, кнопка пуска 10, генератор единичных импульсов 11, генератор счетных импуль3р сов 12, схемы «И» 18 и 14, триггер сигнали243269 зации 15, триггер конца поиска 1б, знакоискатель 17, схема «НЕ» 18, схема «ИЛИ» 19 и схемы «И» 20, соответствующие отдельным строкам матрицы, начиная с третьей.

Рабочая ячейка (фиг. 2) состоит из триггера 21, двух логических схем «ИЛИ» 22 и 28, блокирующего элемента-ячейки 24 и разделительных диодов Д, и Д . Первый вход рабочей ячейки совмещен с первым входом блокирующего элемента 24, второй и третий — совмещены соответственно с первым и вторым входом схемы «ИЛИ» 22, четвертый вход через разделительный диод Д> соединен со вторым выходом рабочей ячейки. Второй вход триггера 21 соединен с выходом схемы «ИЛИ»

22, первый вход — со вторым выходом блокирующего элемента 24. Первый выход блокирующего элемента 24 соединен с первым входом схемы «ИЛИ» 28. Второй выход триггера

21 является третьим выходом рабочей ячейки, который через разделительный диод Д соединен со вторым выходом этой ячейки. Первый выход триггера 21 подключен ко второму входу схемы «ИЛИ» 28.

Коммутаторная ячейка 5 (фиг. 3) состоит из триггера 25, логических схем «ИЛИ» 2б и

27 и блокирующих элементов-ячеек 28 и 29.

Первые и вторые входы схем «ИЛИ» и первые и вторые выходы блокирующих элементов совмещены соответственно с первым, третьим, пятым и шестым входами и первым, вторым, третьим и четвертым выходами коммутаторной ячейки. Выход схемы «ИЛИ» 2б соединен с первым входом триггера 25, а выход схемы

«ИЛИ» 27 — со вторым его входом. Второй выход триггера 25 соединен со вторым входом блокирующего элемента 28, а первый — с первым входом блокирующего элемента 29. Остальные входы блокирующих элементов совмещены со вторым и четвертым входами комм ут атор ной я чей ки.

Блокирующий элемент 9 (см. фиг. 4) состоит из логических схем «И» 80 и 81 и схемы

«НЕ» 82. Первый вход элемента 9 образуется соединенными вместе первыми входами схем

«И» 80 и 81, второй его вход совмещен со вторым входом схемы «И» 81 и входом схемы

«НЕ» 82. Второй вход схемы «И» 80 соединен с выходом схемы «НЕ» 82. Первый и второй выходы элемента образуются соответственно выходами схем «И» 80 и 81.

Блокирующий элемент работает следующим образом.

При наличии сигнала на втором входе импульсный сигнал с первого входа передается на второй выход. При отсутствии сигнала на втором входе импульсный сигнал, подаваемый на первый вход, появляется на первом выходе.

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

25 зо

4

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

r) Если выбору нового элемента какой-то, не являющейся последней, строки не сопутствует появление строк со всеми заблокированными элементами, то следующим выбирается первый слева незаблокированный элемент в последующей строке. д) Выбор любого из элементов последней строки свидетельствует о том, что этот элемент вместе с остальными выбранными элементами является сомножителем члена определителя. е) Исключение последнего элемента первой строки свидетельствует об окончании поиска.

До начала работы устройство с помощью кнопки сброса (на схеме не показана) устанавливают в исходное состояние, характеризующееся тем, что первые выходы всех триггеров (1, 15, 1б, 21, 25), за исключением триггера и коммутатора, замкнуты на землю; у этого триггера на земле находится второй вых од. После отпускания кнопки сброса первый им. пульс от генератора счетных импульсов 12 проходит через нормально замкнутые контак

243269

65 ты кнопки пуска 10, первый выход блокирующего элемента 9 и схему 14 на второй вход триггера 4 коммутатора 3 и переключает последний на один шаг в прямом направлении (вниз). При этом сигналом с первого выхода коммутатора 4 переключается первый триггер

1 в первом регистре. Это вызывает появление на четвертых входах рабочих ячеек и соответственно на вторых входах блокирующих элементов 24 всех рабочих ячеек, стоящих с этим триггером в одном столбце, сигнала, блокирующего прохождение сигналов на первый вход триггеров 21 указанных ячеек. Этим же сигналом с первого выхода триггера 4 коммутатора переключается по пятому входу триггер 25 первой коммутаторной ячейки.

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

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

В случае появления регистра со всеми заблокированными ячейками вследствие срабатывания соответствующей этому регистру схемы «И» 20 и схемы «ИЛИ» 19 следующий счетный импульс от генератора 12 поступает через второй выход блокирующего элемента 9 на второй вход последней коммутаторной ячейки, через ее второй выход — на второй вход предыдущей ячейки и т. д. до тех пор, пока не попадет на второй вход той коммутаторной ячейки, триггер 25 которой переключился предыдущим импульсом генератора 12. При этом сигнал, снимаемый со второго плеча триггера

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

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

Обратное движение реверсивного коммутатора осуществляется благодаря сигналу от мультивибратора задержки б, поступающему

10 на четвертые входы коммутаторных ячеек и соответственно на вторые входы блокирующих элементов 29 этих ячеек.

Сигнал с выхода мультивибратора задержки б поступает также на вход схемы «И» 8, в

15 результате чего шунтируется выход генератора 12. Время существования сигнала на выходе мультивибратора задержки обеспечивает обратное самопереключение рабочих и коммутаторных ячеек.

20 Следующий импульс от генератора 12 поступает на третьи входы коммутатора 3 и переключает его в прямом направлении.

Когда переключатся триггер сигнализации

15 и связанные с ним блоки и будет записан

25 результат, нажимают кнопку пуска 10, и на второй вход триггера 15 поступает единичный импульс от генератора 11.

Об окончании выбора членов определителя свидетельствует переключение последнего

З0 триггера 1 в первом регистре при обратном ходе реверсивного коммутатора 3. При этом сигнал с первого выхода первой коммутаторной ячейки возвращает в исходное состояние триггер 4 коммутатора, а сигнал с его второго вы35 хода переключает триггер конца поиска 1б, в результате чего исчезает сигнал на дтором входе схемы «И» 14, что препятствует дальнейшим переключениям в схеме.

Работа машины возобновляется после уста40 новления ее в исходное состояние.

Все блоки устройства (логические схемы, триггеры, генераторы и т. д.) выполнены на полупроводниковых элементах.

Принцип работы предлагаемого устройства

45 проверен на изготовленном в институте-заявителе макете, предназначенном для раскрытия определителя не более шестого порядка.

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

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

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

243269 З,го.7 В

&сЫ,, ЬЫ,Г

егоo

Фиг 2

&ос7

8podZ

Фиг у

Составитель А. А, Плащин

Редактор Б. Б. Федотов Техред А. А. Камышникова Корректоры: Л. Голованова и Т. И. Горбанова

Заказ 228I/4 Тираж 480 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Центр, пр, Серова, д, 4

Типография, пр. Сапунова, 2