Устройство для анализа определителей

Устройство для анализа определителей

Иллюстрации

Показать все

Реферат

 

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

Социалистицеских

Республик

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ " 634284 (61) Дополнительное к авт. свид-ву (22) Заявлено 05.11.75(21) 2187885/18-24 с присоединением заявки №вЂ” (23) Приоритет (43) Опубликовано 25.11.78.Бюллетень № 43 (45) Дата опубликования описания 23 ° 11 .78

С 06 Р 15/32

Государственный комитет

Совета Министров СССР оо делам изооретеннй и открытий (53) УДК 681.351 (088.8) (72} Авторы изобретения

Г. С. 11ирамуа,,К. Н. Камкамидзе, Г. Н. Габашвили и В. А. Богатырев

Грузинский ордена Ленина и ордена Трудового Красного Знамени политехнический институт им. В. И. Ленина (71) Заявитель (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ОПРЕДЕЛИТЕЛЕЙ

Изобретение относится к цифровой вычислительной технике.

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

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

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

Целью изобретения является повышение быстродействия устройства.

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

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

На чертеже представлена блок-схема устройства.

634пп4

Устройство содержит матрицу 1 ячеек памяти, генератор импульсов 2, триггер 3, блок 4 перебора сочетаний, сумматоры 5, выходной сумматор 6 и блок умножения 7.

Вход блока 4 перебора сочетаний соединен с выходом генератора импульсов 2, первые группы входов ячеек памяти столбцов подключены к первой группе в; соответствующих информационных шин, вторые группы входов 8 — к соответствующим выходам блока 4 перебора сочетаний, третьи группы входов ячеек памяти строк подключены к второй группе соответствующих информационных шин а;. Выходы ячеек памяти строк подключены к входам соответствующих сумматоров

5, выходы которых подключены к входам блока умножения 7, выходы которого подключены к первым входам 9 выходного сумматора

6, второй 10 и третий 11 входы выходного сумматора 6 подключены к выходам триггера 3, счетный вход которого подключен к второму вь.х:,ду 12 блока 4 перебора сочетаний, третий выход 13 которого подключен к четвертому входу 14 выходного сумматора 6.

Вычисление плюс-определителей производится по следующему алгоритму: производится выбор всевозможных столбцов из и (i = п, n — 1, ... 1); для каждой выборки производится построчное суммирование выбранных столбцов и перемножения полученных результатов; производится накопление (суммирование) результатов перемножения для всех

Сп (i =- и, и — 1, ...1) выборок, причем знак слагаемых меняется при изменении i (при

i =- и берется положительным, при i = n — 1— отрицательным, при i = и — 2 — положительным и т.д.).

Работа устройства заключается в следующем.

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

n (i = и, и — 1, >1) осуществляется посредством блока 4 перебора сочетаний, производящего перебор всевозможных и-разрядных кодов с i единицами, причем выборке столбца соответствует наличие единицы на соответствующем выходе блока 4 перебора сочетаний. Изменение состояния блока перебора сочетаний происходит при поступлении сигнала с выхода генератора импульсов 2. При завершении перебора всех C„„ и-разрядных кодов с i единицами осуществляется переход к перебору всевозможных п-разрядных кодов с i — 1 единицами, при этом на выходе 12 блока 4 перебора сочетаний вырабатывается сигнал, перебрасывающий счетный триггер 3 в противоположное состояние.

Х С „= 2" — 1

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

14 выходного сумматора 6, с последнего производится выдача результат" вычисления плюс-определителя.

Пример последовательности вычисления плюс-определителя.

Пусть задана матрица

1 2 3

1 0 2

0 1 1

В виде обозначения:

Ci — состояние блока перебора сочетаний 4;

Сг — содержимое сумматоров 5;

С, — содержимое блока умножения 7;

С вЂ” содержимое выходного сумматора 6;

С вЂ” состояние триггера 3.

40

Процесс вычисления плюс-определителя заданной матрицы происходит в следующем

45 по рядке.

Вначале в блоке перебора сочетаний осуществляется перебор всевозможных трехразрядных кодов с тремя единицами

Сг

1 2 3 6

1 0 2 3

С5 = 1, 0 1 1 2, C4 — — 36

Ci 1 1 1 ...Cq =36

55 На этом перебор трехразрядных кодов с тремя единицами заканчивается и блок 4 перебора сочетаний переходит к выработке всевозможных трехразрядных кодов с двумя единицами

Содержимое столбцов матрицы ячеек памяти, выбранных при каждом состоянии блока 4 перебора "î÷åòàíèé,,подается на сумматоры 5, в которых происходит построчное сум5 мирование содержимого выбранных столбцов. С сумматоров 5 информация поступает в блок умножения 7, производящий перемножение результатов построчного суммирования содержимого выбранных столбцов матрицы ячеек памяти. Результат перемно10 жения при каждой выборке поступает в накапливающий выходной сумматор 6 со знаком> зависящим от состояния счетного триггера 3. При единичном состоянии триггера 3 возбуждается вход приема в выходной сумматор 6 без изменения знака 10, а при нулевом состоянии триггера 3 возбуждается вход 11 приема слагаемых в выходной сумматор 6 с отрицательным знаком. Изменение состояния триггера 3 происходит по сигналу с выхода 12 блока 4 перебора сочетаний.

При выработке блоком перебора сочетаний всех

634284

1 2

1 О

О 1

С =0, 3

1, 1

С4 = 36 — 3=33, С 1 1

СЗ

С2

1 2

1 О

О 1

4

3, 1 л (pa3)

2„, C4 = ЗЗ вЂ” 12 =.. 21, Ci 1 О

1 С

= 12

Формула изобретения..з

Сг

3 5

2 2, 1 2

1 2

1 О

О 1

С4 =21 — 20= 1, 15

Сг

О, С4 =1+0=1, 2 3

1 О 2

О 1 1

Cs =1

С1 1 О О,Сг =О

0 1 1 .Сз =20

После выработки всех трех разрядных кодов с двумя единицами блок 4 перебора сочетаний переходит к выработке трехразрядных 2о кодов с одной единицей

Сг

1 2 3 2

1 О 2 О, C4 — — 1+О =1

О 1 1 1

C 0 1 0, С,=О

1 2 3 3

1 О 2 2

О 1 1 1, С4 =1+6=7.

Ci О О, 1 С =6

На этом блок перебора сочетаний завершает перебор всех

k С, =2 1=7

40 трехразрядных кодов и с выходного сумматора 6 выдается его содержимое C 7, которое и является результатом вычисления плюс-определителя для заданной матрицы.

Предложенное устройство для анализа

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

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

Источники информации, принятые во внимание при экспертизе:

1. Авторское свидетельство СССР № 294144, M.Kë2 G 06 F 15/32, 1968.

2. Авторское свидетельство СССР № 300881. M.Êë2 G 06 F 15/32, 1969.

634284

Составитель Ф. Гаврилова

Редактор Е. Гончар Текред О. Луговая Корректор С. Шекмар

Заказ 6763/47 Тираж 784 Подписное

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

1!3035, Москва, Ж-35, Раушская наб. д. 4j5

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4