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

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

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

Недостатком известных устройств явотяется относительно большое время проведения анализа из-за осуществления полного перебора.

Предлагаемое устройство отличается тем, что ОНО содержит две npyininbr переключателей функциональных ячеек строк, .первые и вторые входы которых соединены с выxQдaJMи соответствующих программирующ.их выключателей, а третьи входы переключателей первой группы соединены с первыми выходами переключателей соседних старШ;ИХ строк и с первыми выходами функциональных ячеек соответствующей Строки, .вторые выходы переключателей первой группы соединены с первыми входам.и первых функциональных ячеек в строках, первые выходы переключателей второй труппы Соединены со вторыми входами функ Циональных ячеек соответствующих строк, а JBTopbie выходы этих переключателей соединены с третьими входами переключателей сосед:ней старщей строки и со вторыми выходами последних функциональных ячеек соответствующих строк, третьи выходы функциональных ячеек соединены с третьими входами всех младщих функциональных ячеек в данном столбце, генератор одиночных импульсов соединен с третьим входом переключателя первой строки второй группы и с единичным установочным входом триггера, нулевой выход которого соединен с третьим входом переключателя последней строки первой груопы.

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

0

На фиг. 1 изображена блок-схема устройства; на фиг. 2 - схема функциональной ячейки; на фиг. 3 - схема блока знакоИокателейУстройство (см. фиг. 1) содержит функциональные ячейки /, организованные в управ5ляемую матрицу, состоящую из п строк и п столбцов (п - наибольщий возможный порядок определителя), генератор 2 одиночных им-пульсов, триггер 3 запуска, п первых управляемых переключателей строк, реализаваиных логическими элементами «И 4, 5; п |Вторых управляемых переХоГ ючателей строк, реализованных логическим1И элементами «И 6, 7; тгуокавую кнопку 5; п вьиключателей 9 ячеек строк, п выключателей 10 столбцов, переключатель 11 рода работ с положениями «Минор («М) и «алге б|раическое даполнение («АД), триггер 12 конца работы, логи1ческий элемент «ИЛИ 13, блок знакоиокателей 14.

Функциональная ячейка содержит триггер

15,управляемый переклю-чатель импульсов

16,программирующий выключатель 17, логические элементы «ИЛИ 18 и 19.

Блок знакоиСкателей содержит искатель четности подсталовак, образованных индек сами груип элементов определителя, «минора или «алгебраического дополнения, и искатель знака «алгебраического дополнения. Искатель четности подстановок содержит матрицу диодов 20, лагичеакие элементы «И 21 ;подачи на матрицу диодов опрашивающих импульсов, логические элементы «И 22 снятия с матрицы диодов .опрашивающих импульсов, триггеры 23 четности числа инверсий отдельных индексов членов определителя, «минора или «алгебраического дополнения и конечный триггер 24 черност1и с индикаторами знака.

Искатель знака алгебраического дополнения содерншт переключатели 25, спаренные с выключателями 9 и 10, подчиненными нечет«ым строкам и столбцам и триггер 26 с индикаторами знака.

Блок знакоискателей содержит также ждудций (2п+) фазный мультивибратор 27 и триггер 28 с инди:катор.ом «член det.

Элементы ма1щины соединены следующим образом.

Входы 1ФЯ всех функциональных ячеек /, служащие для подачи сигнала, уста.навливающего триггер 15 в нулевое -состояние, соединены в замкнутом положении кнопки 8 с источником такого сигнала о. Сигнальный вход переключателей 16 каждой, кроме первой в ,строке, ячейки соединен Щ1инами 2ФЯ и 5ФЯ предыдущей в строке ячейки с одним из выходов переключателя 16 и тем динамическим выходом триггера этой ячейки, на котором образуется единичный сигнал при переходе его из единичного сост.ояния в пулевое.

Сигнальный вход переключателя 16 каждой первой в строке ф|унк1ц,ио.нальной ячейки соединен щиной 2ФЯ с выходом элемента «И 5 той же строки. Один вход элемента «И 5 соединен шиной 6ФЯ с теми выходами триггеров всех функциональных ячеек следующей старшей строки, на которых образуется единичный сигнал при переходе триггера из нулевого .состояния Б единичное (если рассматриваемая строка не последняя), или же с выходом триггера 3 для последней строки. Вход устаНОВК1И нулевого состояния триггера 3 соединен через кнопку 8 с источником -Бо, а вход установления единичного состояния этого триггера - с генератором 2 единичных импульсов.

Вторые входы элементов «И 4 и 5 каждой строки соединены шина,ми а и б соответственно с выключателем 9 той же строки. Все выключатели Я в свою очередь, соединены с переключателем //, на который подводятся управляющие сигналы, соОТ|ветствуюЩие логическому единичному («1) и нулевому («О) сигналам.

Выходы триггеров 15 всех ячеек первой

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

мультивибратора 27.

Шина 5ФЯ каждой последней в строке ячейки соединена совместно с выходо.м элемента «И 7 рассматриваемой строки с одним из входов элементоВ «И 5 и 7 следующей

старшей строки. Шина 5ФЯ последней ячейки в последней строке соединена с триггером 12 конца работы. Один вход элемента «И 7 первой строки соединен с генератором 2 одиночных нмпульсов. Вторые входы элементов «И

5 и 7 соединены через шины б и а соответственно с вьгключателями 9 той же строк1й. Выход элемента «И 6 каждой строки соединен со входами установки единичного состояния триггеров 15 всех ячеек той же строки.

Один из входов элементов «ИЛИ 18 и 19 всех, кроме последней строки, ячеек соединен через щину ЗФЯ рассматриваемой и шину 7ФЯ находящейся в одном столбце следующей старшей строки 5:чейки с выходом элемента «ИЛИ 19 этой Ячейки. Для ячеек последней строки указанные входы элементов «ИЛИ 18 и 19 соединены с выключателями 10 соответствующих столбцов. К выключ1ателям 10 подводятся сигналы с переключателя //.

Второй вход элемента «ИЛИ 18 соединен с программирующим выключателем 17, «а который подводятся управляющие сигналы, соответствующие логическим единице и нулю. Второй вход элемента «ИЛИ 19 соединен со

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

блока знакоискателей 14.

Вторые входы элементов «И 21 одной строки соединены с. одним выходом мультивибратора 27. Вторые входы элементов «И 22 подключены ,к матрице диодов 20, к которой

также подключены выходы элементов «И 21. Выходы элементов «И 22 одной строки подключены к триггерам четности 23 той же строки. Вторые входы этих триггеров подключены к выходам лсдушего мультивибратора 27. Еходы установления нерабочего состояния триггеров 23 (Подключены к первому выходу мультивибратора 27. Динамические выходы триггеров 23 подключены к конечному триггеру 24 четности. Вход установления .нерабочего состояния триггера 24, соответствующего фиксации

знака «плюс, соединен с (л+1)-ым выходом мультивибратора 27.

Одна .клемма «аждого (переключателя 25 подключена к одному Быхлду мультивибратора 27, вторая - к триггеру 26 знака «алгебраического дополнения. Входы устаяавкй нулевого состояния триггера 26 и триггера 23 подключены к выходу элемента «ИЛИ 75. Один вход элемента «ИЛИ 13 соединен с генерато1ром одиночных импульсов 2, второй через кнопку 8 - с источником EQ . Вход установки единичнаго состояния триггера 28 соединен с (2п+1)-ым выходом мультивибратора 27.

Предлагаемое устройство ра-ботает следующим образоаМ.

Для раскрытия определителя необходимо включить программирующие переключатели 17 Всех ячеек, подчиненных наличным ненулевым элементам. Выклю-чатели 9 и 10 всех строк и столбцов с полностью нулевыми элементаМи необходимо перевести в сьключелное положение (на фиг. 1 они представлены во включенном положении). Переключатель 11 рода работ должен быть в положении М. После программирования нажимают пусковую кнопку 8.

При этом на триггеры 15 всех ячеек, а также триггеры 3, 12, 26 и 28 поступает напряжение о, устанавливающее их в нулевое состояние. После этого нажимают кнопку генератора 2. Импульсом этого генератора опрх)кидывается триггер 3. О|бразовавшийся на выходе этого триггера динамический сигнал поступает к последней строке и переводит в единичное состояние триггер первой В ключен1ной ячейки этой строки. Статическим сигналом с выхода 7ФЯ этой ячейки блокируются все находящиеся выше в одном столбце ячейки. Динамический сигнал с выхода 6ФЯ поступает через элемент «И 5 следующей младшей строки на вход 2ФЯ первой ячейки этой строки и опраюидывает триггер первой включенной при программИровании и незаблокированиой ячейки и т. д. В результате в каждой строке в единичное состояние переходит триггер только одной ячейки, причем все эти ячейки кз разных столбцов, т. е. найден первый искомый член раскрытого определителя.

Динамический сигнал с выхода опрокинутого триггера ячейки первой строки поступает на ждущий мультивибратор 27 и запускает его. На выходах последнего образуется последовательность разделенных во времени импульсов. Импульсом с первого выхода мультивибратора устанавливаются в нерабочее состояние триггеры четности 23. Импульсами со следующих п-1 выходов опрашиваются состояния триггеров ячеек на наличие инверсий со старщими ячейками. В результате такого опроса триггеры 23 фиксируют четность количества Инверсий отдельных элементов найденного члена определителя, (я+1)-й импульс мультивибратора устанавливает в ед.ини;ч.ное состояние конечный триггер четности 24. Следующие

п-1 импульсов опращивают состояние триггеров 23, и триггер 24 фиксирует четность суммарного числа инверсий между всеми элементами члена р1пределителя. (2п + 1)-й импульс

переводит в единичное состояние триггер 23, что свидетельствует о конце поиска первого члена определ:ителя.

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

5 на входы 4ФЯ всех ячеек первой строки. Триггер, находящийся в единичном состоянии в этой строке, возвращается в нулевое состояние. Образовавщийся при этом на выходе 5ФЯ динамический сигнал попадает через элемент

0 «И 6 второй строки на входы 4ФЯ всех ячеек этой строки. Паходящийся в рабочем состоянии триггер второй строки опрокидывается, и динамическим сигналом с выхода 5ФЯ ячейки переводится в единичное состояние триггер

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

сируется второй искомый член определителя.

Для поиска следующего члена снова необходимо нажать кнопку генератора 5 и т. д.

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

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

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

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

щих строк, а вторые выходы этих переключателей соединены с третьими входами переключателей соседней старшей страки и со вторыми выходами последних функциональных ячеек соответствующих строк, третьи выходы функциональных ячеек соединены с третьими входами всех младших функциональных ячеек

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