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

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

Иллюстрации

Показать все

Реферат

 

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (63) Дополнительное к авт. свил-ву (22} Заявлено 080277 (21) 2449773/18-24 с присоединением заявки № (23) Приоритет (5() М. Кл.

G Об F 15/32

Госупарствеиный конисе сссР ио лелин изобретений и открытий (53) УДК 681 . 14 (088. 8) Опубликовано 250279 Бюллетень ¹ 7

Дата опубликования описания 250279 (72) Авторы изобретения О.В. Викторов, Л.Ф. Карачун и A.М. Романкевич

Киевский ордена Ленина политехническчй институт имени 50-лЕтия Великой Октябрьской социалистической революции (54) УСТРОЙСТВО ДЛЯ РАСКРЫТИЯ И ВЫЧИСЛЕНИЯ

ОПРЕДЕЛИТЕЛЕЙ МАТРИЦ

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

Известны устройства для раскрытия определителей матриц, содержащие генератор, элементы И, ИЛИ, счетчики, дешифраторы, матрицу из и ячеек (1) .

Однако такие устройства работают Ю относительно медленно, так как для раскрытия одного члена определителя должны сработать и счетчиков. Для раскрытия определителя и-го порядка нужно n"Tàêòoâ работы. 15

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

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

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

Достигается это тем, что в устройство введены элементы И, ИЛИ, распределитель сигналов, блок памяти и арифметический блок, причем выход генератора соединен с первыми входами блока управления, первого и второго элементов И, первых ячеек первой и второй строк матрицы и с первым входом блока определения знака, второй вход которого соединен с первым выходом блока управления, а второй выход блока определения знака — с первым входом арифметического блока, второй вход .которого подключен к первому выходу блока памяти, второй выход блока памяти соединен с первыми входами первого элемента ИЛИ и третьего элемента И, выход которого подключен к первым входам генератора и второго элемента ИЛИ, выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами распределителя сигналов, выход которого соединен с вторыми входами второго элемента ИЛИ и генератора; выход второго элемента И соединен через элемент задержки с вторым входом первого элемента ИЛИ и непосредственно с третьим входом второго элемента ИЛИ; и ячеек каждой строки.матрицы первыми-. входами и выходами соединены в кольцо, вторые входы последних ячеек каждой строки матрицы соединены с первыми входами соответствующих первых входных элементов ИЛИ каждой строки матрицы1 второй, третий, четвертый и пятый выходы блока управления соединены соответственно с первыми входами вторых входных элементов ИЛИ третьей, четвертой, пятой и шестой строк матрицы, вторые входы которых соединены соответственно с 1О вьиодом первого элемента И, а выхоцы вторых входных элементов ИЛИ третьей, четвертой, пятой и шестой строк матрицы соединены соответственно с вторыми входами первых ячеек этих же, 1я строк матрицы; выходы первых входных элементов ИЛИ каждой строки подключены к третьим входам первых ячеек каждой строки матрицы группа выходов распределителя сигналов соединейа с первой группой входов блока памяти, причем каждый выход иэ этой группы выходов подключен к первому входу соответствующего элемента И в -ом столбце матрицЫ выходы соответствующих элементов И i-ой строки матрицы объединены и соединены с соответствующими входами блока памяти и блока определения нулевого члена, выход которого соединен с вторым входом третьего элемента И; ячейки мат0 рицы соединены между собой вторыми и третьими входами и выходами последовательно по строкам и четвертымй и йятыми входами — выходами параллельнопо столбцам; второй вход соответствукщего элемента И соединен с шестыа выходом k"-ой ячейки, пятые выходы первой ячейки первой строки, второй ячейки второй строки,. °, и-ой ячейки и-ой строки подключены к од- 40 ному входу выхоцного элемента И каждой строки, другой вход которого соединен с выходом выходного элемента И каждой строки, расположенной в соседней нижней строке; выходы выходного элемента И первой строки и выход арифметического блока являются выходами устройства; третий вход генератора, вторые входы первого и второго элементов И, вторые входы первых . 50 входных элементов ИЛИ каждой строки являются управляющими входами устройства, а также тем, что в каждой k< -ой ячейке первый вход ячейки соединен с первымн входами триггера H первого элемента И, выход которого соединен с первым: входом первого элемента ИЛИ, выход первого элемента ИЛИ соединен с первым выходом ячейки, второй вход ячейки соединен с вторым входом триггера, третий вход ячейки соединен с .60 третьим и четвертым входами триггера и с третьим выходом ячейки, четвертый и пятый входы ячейки соединены с первым и вторым входами второго элемента ИЛИ, выход которого подключен 68 к пятому входу триггера, ко второму входу первого элемента И и к четвертому выходу ячейки; нулевой выход триггера соединен с вторым выходом ячейки, единичный выход триггера соединен с вторым входом первого элемента ИЛИ, с пятым и шестым выходами ячейки.

На фиг. l показана структурная схема устройства для п-б, где и — по» рядок определителя; на фиг. 2 — структурная схема ячейки.

Устройство содержит генератор 1, блок 2 определения знака, блок 3 управления, блок 4 определения нулевого члена, распределитель 5 сигналов, блок б памяти, арифметический блок 7, матрицу из n идентичных ячеек 8, элементы И 9, 10, 11, элементы ИЛИ 12, 13, первые входные элементы И 14, вторые входные элементы ИЛИ 15, элементы И 16., выходные элементы Й 17 каждой строки, элемент задержки 18 °

Каждая из ячеек состоит из триггера 19, элемента И 20, элементов ИЛИ

21, 22, ключа 23.

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

Для этого замыкаются ключи 23 всех ячеек 8, соответствующих ненулевым элементам матрицы определителя. Элементу а; матрицы определителя, находящемуся в i-ой строке и j-ом столбце матрицы, соответствует ячейка 8, находящаяся в i-ой строке и

j-ом столбце. На управляющие входы из генератора 1 и из блока 3 подаются сдвинутые относительно друг друга на время Г последовательности им- . пульсов. На вход, связанный с первой строкой матрицы, подается последовательность импульсов, имеющих период следования Т, на вход связан- ный с второй строкой — запаздывающая относительно предыдущей последовательность с периодом Т, на вход третьей строки — с периодом 2Т, на вход четвертой строки — c периодом

6Т на вход пятой строки — с периодом 24Т и т.д. В общем случае период следования импульсов равен T(i-I).

Блок 3 выступает в качестве делителя частоты импульсов, поступающих на ее вход с генератора 1 с периодом Т.

В первсм такте работы устройства по входу устройства выдается сигнал длительностью Т„ = (n-1) Т + C„, где C<— цлительность импульса управляющей последовательности. Этот сигнал поступает через элементы ИЛИ 14 на входы первых в строке ячеек 8, через элементы И 10 и ИЛИ 13 — на вход записи единицы распределителя сигналов 5 и на вход генератора 1. Генератор 1 вырабатывает управляющий сигнал первого такта, который поступает на входы ячеек первого столбца, а также на вход блока 3 и через элемент задержки 18 на синхровход рас648987 пределителя 5. При этом происходит запись единицы в первый разряд распределителя 5. Кроме того в первом такте в течение действия входного сигнала в ячейки 8 строк матрицы записываются единицы в следующем порядке: в первую ячейку первой снизу строки, во вторую ячейку следующей строки, в третью ячейку третьей снизу строки и т.д. и, наконец, в последнюю ячейку верхней строки. Реализуется базовая перестановка (1,2,3...д) 1О т.е. в соответствии с заданной перестановкой сигналы с выходов распределителя 5 через элементы И 16 проходят иа входы блоков 5 и 6. Каждое состояние матричной, схемы соответствует одному члену раскрытого опреде)5 лителя п-го порядка, так как, если расположить первые индексы элементов определителя матрицы,который равен сумме произведений вида

" a1

1 2 о, Z 2и

<и>и -" и

2 и в порядке их возрастания, то совокупность вторых индексов образует

НЕКОТОРУЮ ПЕРЕСтаНОВКУ (d.1, d 2 -, -и .множества чисел от 1 до и. В течение каждого такта работы устройства 1 пробегает1 все разряды распределителя 5, а затем по цепи обратной связи через элемент ИЛИ 13 записывается в первый разряд распределителя 5.

После выдачи каждого синхроимпульса осуществляется выборка одного элемента определителя. Сигнал с единичного выхода распределителя 5 поступа- ®5 ет одновременно на первый горизонтальный вход выборки ячейки блока 6 и на вход 0(„ вертикальной выборки. При этом происходит выборка и считывание из ячейки, в которой хранится эле- 4Q мент О1,,так как предварительно запись элементов определителя в ячейки блока 6 осуществляется таким образом, чтобы эти ячейки образовали матрицу, аналогичную матрице определителя. 45После считывания очередного элемента определителя в блоке 6 вырабатывается сигнал, определяющий конец считывания, который .поступает в качестве сикхроимпульса на сикхровход распределителя 5. Сигнал с второго выхода распределителя 5 поступает на второй горизонтальный вход блока 6 и на d.2 -ой вертикальный вход блока

6. При этом происходит выборка и считывание из ячейки, в которой хранится элемент О2,2.Аналогично происходит выборка остальных элементов, входящих в данное произведение вида а1 „ о2,, à, ...а„„„и . Вычисление этого произведения производится в арифме- 60 тическом блоке 7, ка вход которого поступают считываемые из блока б элементы определителя.

Сигнал с последнего выхода распределителя 5 определяет начало нового такта работы устройства. Этот сигнал поступает на вход генератора 1, который вырабатывает управляющий сигнал нового такта.

Рассмотрим работу устройства после того, как на нем в первом такте была установлена базовая перестановка (1,2,3,4,5,6) для случая, когда n=á. Во втором такте единица, записанная в триггер 19 второй справа ячейки 8 второй сверху строки матрицы под действием управляющего сигна-! ла, поступающего на вход данной ячейки, сдвигается в последнюю ячейку 8 этой строки. Единица, записанная в триггер 19 последней ячейки первой сверху строки, под действием управляющего сигнала, сдвинутого на по отношению к сигналу, действующему на ячейки соседней снизу строки, проходит через элементы 21 последней ячейки, ИЛИ 14 пeðâoé строки и далее через элемент И 20 первой ячейки второй строки, открытую сигналом с выхода элемента ИЛИ 22. На выходе элемента ИЛИ 22 присутствует единичкый сигнал, так как в триггере 19 первой ячейки нижней строки записана единица. Единица, поступающая с выхода элемента ИЛИ 22 не записывается в триггер 19 первой ячейки 8 первой строки, так как его единичный вход закрыт сигналом с выхода элемента ИЛИ 22, заведенным на второй единичный вход триггера 19.

За A) тактов устройство генерирует все и! перестановок.

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

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

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

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

1. устройство для раскрытия и вычисления определителей матриц, содержащее генератор, блок управления, блок определения знака, блок определения нулевого члена и матрицу из и идентичных ячеек, о т л и ч а ющ е е с я тем, что, с целью упрощения устройства, в него введены элементы И, ИЛИ, распределитель сигна648987 лов, блок памяти и арифметический блок, причем выход генератора соединен с первыми входами блока управления, первого и второго элементов И, первых ячеек первой и второй строк матрицы и с первым входом блока определения знака, второй вход кото- 5 рого соединен с первым выходом блока управления, а второй выход блока определения знака — с первым входом арифметического блока, второй вход которого подключен к первому выходу И1 блока памяти, второй выход блока памяти соединен с первыми входами первого элемента ИЛИ и третьего элемента И, выход которого подключен к первым входам генератора и второго элемента ИЛИ, выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами распределителя сигналов, выход которого соединен со вторыми входами второго элемента ИЛИ и генератора; выход второго элемента И соединен через. элемент задержки C вт- оры-м входом первого элемента ИЛИ и непосредственно с третьим входом второго элемента ИЛИ; и ячеек каждой строки мат- 26 рицы первыми входами и выходами соединены в кольцо, вторые выхоцы последних ячеек каждой строки матрицы соединены с первыми входами соответствующих первых входных элемен- î.â ИЛИ 30 каждой строки матрицы; второй, третий,- четвертый и пятый выходы блока управления соединены соответственно с первыми входами вторых входных элементов ИЛИ третьей, четвертой, пятой и шестой строк матрицы, вторые входы которых соединены соответственно с выходом первого элемента И, а выходы вторых входных элементов ИЛИ третьеи, четвертой, пятой и шес-ой строк матрицы соединены соответственно с вторыми входами первых ячеек этих же строк матрицы; выходы первых входных элементов ИЛИ каждой строки подключены к третьим входам первых ячеек каждой строки матрицы; группа выходов 45 распределителя cBI"íàëoâ соединена с первой группой входов блока памяти, причем каждый выход из этой группы выходов подключен к первому входу соответствующего элемента И в 3-ом 5О столбце матрицы; выходы соответствующих элементов И i-ой строки матрицы объединены и соединены с соответствующими входами блока памяти и блока определения нулевого члена, выход которого соединен со вторым входом третьего элемента И; ячейки матрицы соединены между собой вторыми и третьими входами и выходами последовательно по строкам и четвертыми и пятыми входами — выходами параллельно по столбцам; второй вход соответствующего элемента И соединен с шестым выходом k"-ой ячейки, пятые выходы первой ячейки первой строки, второй ячейки второй строки,..., п-ой ячейки и-ой строки подключены к одному входу выходного элемента И каждой строки, другой вход которого соединен с выходом выходного элемента И каждой строки, расположенной в соседней нижней строке; выходы выходного элемента И первой строки и выход арифметического блока являются выходами устройства; третий вход генератора, вторые входы первого и второго элементов И, вторые входы первых входных элементов ИЛИ каждой строки являются управляющими входами устройства.

2. Устройство по п.1, о т л ич а ю щ е е с я тем, что в каждой

k; — oé ячейке первый вход ячейки coej динен с первыми входами триггера и первого элемента И, выход которого соединен с первым входом первого элемента ИЛИ, выход первого элемента ИЛИ соединен с первым выходом ячейки, второй вход. ячейки соединен с вторым входом триггера, третий вход ячейки соединен с третьим и четвертым входами триггера и с третьим выходом ячейки, четвертый и пятый входы ячейки соединены с первым и вторым входами второго .элемента ИЛИ., выход которого подключен к пятому входу триггера,- ко второму входу первого элемента И и к четвертому выходу ячейки; нулевой выход триггера соединен с вторым выходом ячейки, единичный выход триггера соединен с вторым входом первого элемента ИЛИ с пятым и шестым выходами ячейки.

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

1. Авторское свидетельство СССР

9 255647, М.Кл G 06 F 15/32, 1967.

2. Авторско свидетельство СССР

9. 294144, М.Кл. G 06 F 15/32, 1968.