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

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

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

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

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

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

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

Регистр, соответствующий первой строке, состоит из триггеров I, соответствующих отдельным ненулевым элементам этой строки, а регистры, соответствующие остальным строкам, образуются рабочими ячейками 2, соответствующими отдельным ненулевым элементам этих строк. Кроме того, в состав устройства входят реверсивный коммутатор 3, состоящий из триггера 4, поставленного в соответствие первой строке, и коммутаторных ячеек 5, иоставленных в соответствие остальным строкам матрицы, мультивибратор задержки 6, схема «ИЛИ 7, схема «И 8, блокирующий элементячейка Я кнопка пуска 10, генератор единичных импульсов 11, генератор счетных импульзации 15, триггер конца поиска 16, знакоискатель 17, схем «НЕ 18, схема «ИЛИ 19 и схемы «И 20, соответствующие отдельным строкам матрицы, начиная с третьей.

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

Коммутаторная ячейка 5 (фиг. 3) состоит из триггера 25, логических схем «ИЛИ 26 и 27 и блокирующих элементов-ячеек 28 и 29. Первые и вторые входы схем «ИЛИ и первые и вторые выходы блокирующих элементов совмещены соответственно с первым, третьим, иятым и шестым входами и первым, вторым, третьим и четвертым выходами коммутаторной ячейки. Выход схемы «ИЛИ 26 соединен с первым входом триггера 25, а выход схемы «ИЛИ 2:7 - со вторым его входом. Второй выход триггера 25 соединен со вторым входом блокирующего элемента 28, а первый - с первым входом блокирующего элемента 29. Остальные входы блокирующих элементов совмещены со вторым и четвертым входами коммутаторной ячейки.

Блокирующий элемент 9 (см. фиг. 4) состоит из логических схем «И 30 и 31 и схемы «НЕ 32. Первый вход элемента 9 образуется соединенными вместе первыми входами схем «И 30 и 31, второй его вход совмещен со вторым входом схемы «И 3} и входом схемы «ПЕ 32. Второй вход схемы «И 30 соединен с выходом схемы «НЕ 32. Первый и второй выходы элемента образуются соответственно выходами схем «И 30 и 31.

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

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

Предлагаемое устройство реализует следующий алгоритм:

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

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

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

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

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

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

е)Исключение последнего элемента первой строки свидетельствует об окончании поиска.

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

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

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

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

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

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

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

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

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

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

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

Когда переключатся триггер сигнализации 15 и связанные с ним блоки и будет записан

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

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

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

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

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

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

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

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

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

Bts/fO I

1

iBtaro IiBblM I

Г-ГЦ Г 1