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

сударственный комин сссР о и изобретений открытий(72) Авторы ИЗОбрЕтЕНИя О.В. ВикторОв, Л.Ф, Карачун и А манкеви Киевский имени 50 рдена Ленина политехническчй институтЕтия Великой Октябрьской социалистическореволюции(54) УСТРОЙСТВО ДЛЯ РАСКРЫТИЯ И ВЫЧИСЛЕНИ ОПРЕДЕЛИТЕЛЕЙ МАТРИЦами к ройство им Кроме того крытие опр пределител другим с о зобретенияойства. ым в хоосредго ле ки,матИзобретение относится к вычислительной технике, в частности к устройствам, предназначенным для решения задач методом матричной алгебры.Известны устройства для раскрытия определителей матриц, содержащие генератор, элементы И, ИЛИ, счетчики, дешифраторы, матрицу из и ячеек 1 .Однако такие устройства работают относительно медленно, так как для раскрытия одного члена определителя должны сработать и счетчиков. Для раскрытия определителя и-го порядка нужно и"тактов работы.Наиболее близким по технияеской сущности к изобретению является устройство для раскрытия определителей матриц, содержащее генератор, блок управления, блок определения знака, блок определения нулевого члена и матрицу из и идентичных яче 2ек 21,Это уст еет сложную конструкцию, оно выполняеттолько рас еделителя, а вычисление о ей должно быть выполнено собом.Целью и является упро. щение устр Достигается это тем, что в устройство введены элементы И, ИЛИ, распределитель сигналов, блок памяти и арифметический блок, причем выход генератора соединен с первыми вход блока управления, первого и второго элементов И, первых ячеек первой и второй строк матрицы и с первым входом блока определения знака, второй вход которого соединен с первым выходом блока управления, а второй выход блока определения знака - с первым входом арифметического бло а, второй вход которого подключен к первому выходу блока памяти, второй выход блока памяти соединен с первыми входами первого элемента ИЛИ и третьего элемента И, выход которого подключен к первым входам генератора и второго элемента ИЛИ, выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами распределителя сигналов, выход которого соединен с вторыми входами второго элемента ИЛИ и генератора;выход второго элемента И соединен через элемент задержки с втордом первого элемента ИЛИ и непственно с третьим. входом второмента ИЛИ; и ячеек каждой строрицц первыми входами и выходами соединеиц в кольцо, вторые входы последних ячеек каждой строки матрицы соединены с первыми входами соответствующих первых входных элементов ИЛИ каждой строки матрицы; второй, третий, четвертый и пятый выходы блока управ ления соединены соответственно с первыми входами вторых входных элементов ИЛИ третьей, четвертой, пятой и шестой строк матрицй, вторые входы которых соединены соответственно ,с 1 О вьиодом первого элемента И, а выхоцы вторых входных элементов ИЛИ третьей, четвертой, пятой и шестой строк матрицы соединены соответственно с вто" рцми входами первых ячеек этих же, 1 я строк матрицы; выходы первых входных элементов ИЛИ каждой строки подключены к третьим входам первых ячеек каждой строки матрицы группа выходов распределителя сигналов соединейа с первой группой входов блока памяти, причем каждый выход иэ этой группы выходов подключен к первому входу соответствующего элемента И в -ом столбце матрицы; выходы соответствующих элементов И 1-ой строки матрицы объединены и соединены с соответствующими входами блока памяти и блока определения нулевого члена, выход которого соединен с вторьм входом третьего элемента И; ячейки мат 30 рицы соединены между собой вторымии третьими входами и выходами последовательно по строкам и четвертымй и йятыми входами - выходами параллельно по столбцам; второй вход соответсТвукщего элемента И соединен с шестыа выходом к-ой ячейки, пятые выходы первой ячейки первой строки, второй ячейки второй строки,., и-ойячейки и-ой строки подключены к одному входу выхоцного элемента И каждой строки, другой вход которого соединен с выходом выходного элемента Икаждой строки, расположенной в соседней нижней строке; выходы выходногоэлемента И первой строки и выходарифметического блока являются выходами устройства; третий вход генератора, вторые входы первого и второгоэлементов И, вторые входы первыхвходных элементов ИЛИ каждой строкиявляются управляющими входами устройства, а также тем, что в каждой К -ойячейке первый вход ячейки соединенс первыми входами триггера и первогоэлемента И, выход которого соединенс первым входом первого элемента ИЛИ,выход первого элемента ИЛИ соединенс первым выходом ячейки, второй входячейки соединен с вторым входом триггера, третий вход ячейки соединен с .60третьим и четвертым входами триггераи с третьим выходом ячейки, четвертыйи пятый входы ячейки соединены с первым и вторым входами второго элемента ИЛИ, выход которого подключен 85 к пятому входу триггера, ко второмувходу первого элемента И и к четвертому выходу ячейки; нулевой выходтриггера соединен с вторым выходомячейки, единичный выход триггерасоединен с вторым входом первого элемента ИЛИ, с пятым и шестым выходами ячейки.На фиг. 1 показана структурнаясхема устройства для п-б, где и - порядок определителя; на фиг. 2 - структурная схема ячейки,Устройство содержит генератор 1,блок 2 определения знака, блок 3 управления, блок 4 определения нулевогочлена, распределитель 5 сигналов,блок б памяти, арифметический блок 7,матрицу из и идентичных ячеек 8, элементы И 9, 10, 11, элементы ИЛИ 12,13, первые входные элементы И 14,вторые входные элементы ИЛИ 15, элементы И 16., выходные элементы Й 17каждой строки, элемент задержки 18Каждая из ячеек состоит из триггера 19, элемента И 20, элементов ИЛИ21, 22, ключа 23.Перед началом работы устройствапроисходит настройка матричной схемы,,Цля этого замыкаются ключи 23 всехячеек 8, соответствующих ненулевымэлементам матрицы определителя. Элементу а; матрицы определителя, находящемуся в 1-ой строке и 3-омстолбце матрицы, соответствует ячейка 8, находящаяся в 1-ой строке и3-ом столбце. На управляющие входыиз генератора 1 и из блока 3 подаются сдвинутые относительно друг другана время Г последовательности им- .пульсов, На вход, связанный с первой строкой матрицы, подается последовательность импульсов, имеющихпериод следования Т, на вход связан-ный с второй строкой - запаздывающаяотносительно предыдущей последовательность с периодом Т, на входтретьей строки - с периодом 2 Т, навход четвертой строки - с периодом6 Т, на вход пятой строки - с периодом 24 Т и т.д. В общем случае периодследования импульсов равен Т(1-1),Блок 3 выступает в качестве делителячастоты импульсов, поступающих наее вход с генератора 1 с периодом Т.В первом такте работы устройства повходу устройства выдается сигнал длительностью Т= (и)+ Г где Т -цлительность импульса управляющейпоследовательности, Этот сигнал поступает через элементы ИЛИ 14 на входы первых в строке ячеек 8, черезэлементы И 10 и ИЛИ 13 - на вход записи единицы распределителя сигналов 5 и на вход генератора 1. Генератор 1 вырабатывает управляющий сигнал первого такта, который поступаетна входы ячеек первого столбца, атакже на вход блока 3 и через элемент задержки 18 на синхровход рас 648987,который равен сумме произведенийвида г и2 О 2г с и с и " д2 и в порядке их возрастания, то совокупность вторых индексов образует НЕКОтОруЮ ПЕрЕСтаНОВКу (С 1,сз,д-п) множества чисел от 1 до и, В течение каждого такта работы устройства ф 1 пробегаетвсе разряды распределителя 5, а затем по цепи обратной связи через элемент ИЛИ 13 записывается в первый разряд распределителя 5.После выдачи каждого синхроимпульса осуществляется выборка одного элемента определителя. Сигнал с единичного выхода распределителя 5 поступа-ет одновременно на первый горизонтальный вход выборки ячейки блока б и на вход о( вертикальной выборки. При этом происходит выборка и считывание из ячейки, в которой хранится эле О мент Отак как предварительно запись элементов определителя в ячейки блока б осуществляется таким образом, чтобы эти ячейки образовали матрицу, аналогичную матрице определителя.После считывания очередного элемента определителя в блоке б вырабатывается сигнал, Определяющий конец считывания, который поступает в качестве синхроимпульса на синхровход распределителя 5. Сигнал с второго выхода распределителя 5 поступает на второй горизонтальный вход блока б и на Ы,2 -ой вертикальный вход блока б. При этом происходит выборка и считывание из ячейки, в которой хранится элемент 02 .Аналогично происходит выборка остальных элементов, входящих в данное произведение вида 01о 2, О ап . Вычисление этого произведения производится в арифме тическом блоке 7, на вход которого поступают считываемые из блока б элементы определителя.Сигнал с последнего выхода распределителя 5 определяет начало новопределителя 5. При этом происходит запись единицы в первый разряд распределителя 5. Кроме того в первом такте в течение действия входного сигнала в ячейки 8 строк матрицы записываются единицы в следующем порядке: в первую ячейку первой снизу 5 строки, во вторую ячейку следующей строки, в третью ячейку третьей снизу строки и т.д. и, наконец, в последнюю ячейку верхней строки. Реализуется базовая перестановка (1,2,3 л) 1 О т.е. в соответствии с заданной перестановкой сигналы с выходов распределителя 5 через элементы И 16 проходят иа входы блоков 5 и 6. Каждое состояние матричной. схемы соответствует одному члену раскрытого опреде 15 лителя п-го порядка, так как, если расположить первые индексы элементов определителя матрицы го такта работы устройства. Этот сигнал поступает на вход генератора 1, который вырабатывает управляющий сигнал нового такта.Рассмотрим работу устройства после того, как на нем в первом такте была установлена базовая перестановка (1,2,3,4,5,6) для случая, когда п=б. Во втором такте единица, записанная в триггер 19 второй справа ячейки 8 второй сверху строки матрицы под действием управляющего сигнала, поступающего на вход данной ячейки, сдвигается в последнюю ячейку 8 этой строки. Единица, записанная в триггер 19 последней ячейки первой сверху строки, под действием управляющего сигнала, сдвинутого напо отношению к сигналу, действующему на ячейки соседней снизу строки, проходит через элементы 21 последней ячейки, ИЛИ 14 первой строки и далее через элемент И 20 первой ячейки вто"рой строки, открытую сигналом с выхода элемента ИЛИ 22. На выходе элемента ИЛИ 22 присутствует единичный сигнал, так как в триггере 19 первой ячейки нижней строки записана единица. Единица, поступающая с выхопа элемента ИЛИ 22 не записывается в триггер 19 первой ячейки 8 первой строки, так как его единичный вход закрыт сигналом с выхода элемента ИЛИ 22, заведенным на второй единичный вход триггера 19,За и) тактов устройство генерирует все и перестановок.Для того, чтобы не производить выборку элементов определителя, равных нулю, испОльзуется блОк 4 представляющий собой схему ИЛИ.После полного перебора всех возможных перестановок на входах каждого элемента И 17 появляются сигналы, проходящие на выход верхнего элемента И 17 как сигнал, Определяющий окончание вычисления определителя.В данном устройстве НО сравнению с прототипом намного уменьшены аппаратурные затраты, а также возможно вычисление значения определителя и его отдельных членов.устройство может быть использовано автономно как специализированная машина, а также в качестве дополнительного оборудования для универсальной ЦВМ.Формула изобретения1. устройство для раскрытия и вычисления определителей матриц, содержащее генератор, блок управления, блок определения знака, блок определения нулевого члена и матрицу из и идентичных ячеек, о т л и ч а ющ е е с я тем, что, с целью упрощения устройства, в него введены элементы И, ИЛИ, распределитель сигналон, блок памяти к арифметическийблок, причем выход генератора соединенс первыми входами блока управления, первого и второго элементов И,первых ячеек первой и второй строкматрицы и с первым входом блока определения знака, втооой вход которого соединен с первым выходом блокауправления, а второй выход блока определения знака - с первым входомарифметического блока, второй входкоторого подключен к первому выходу рблока памяти, второй выход блокапамяти соединен с первыми входамипервого элемента ИЛИ и третьего элемента И, выход которого подключен кпервым входам генератора и второгоэлемента ИЛИ, выходы первого к второго элементов ИЛИ соединены соответственно с перным и вторым входамираспределителя сигналов, выход которого соединен со вторымк входамивторого элемента ИЛИ и генератора;выход второго элемента И соединенчерез, элемент задержки с вторым входом первого элемента ИЛИ и непосредственно с третьим входом второго элемента ИЛИ; и ячеек каждой строки матрицы первыми входами и выходамк соединены н кольцо, вторые выхоцы последних ячеек каждой строки матрицысоединены с первыми входами соответствующих первых входных элементов ИЛИ 3 Окаждой строки матрицы; второй, третий,- четвертый и пятый выходы блокауправления соединены соответственнос первыми входами вторых входных элементов ИЛИ третьей, четвертой, пятойи шестой строк матрицы, вторые входыкоторых соединены соответственно свыходом первого элемента И, а выходывторых входных элементов ИЛИ третьек,четвертой, пятой и шестой строк матрицы соединены соответственно с нторымк входами первых ячеек этих жестрок матрицы; выходы первых входныхэлементов ИЛИ каждой строки подключены к третьим входам первых ячеек каждой строки матрицы," группа выходов 45распределителя сигналов соединена спервой группой входов блока памяти,причем каждый выход из этой группывыходов подключен к первому входусоответствующего элемента И в 3-ом 5 Остолбце матрицы; выходы соответствующих элементов И 1-ой строки матрицыобъединены к соединены с соответствующимк входами блока памяти и блока определения нулевого члена, выход которого соединен со вторым входом третьего элемента И; ячейки матрицы соединены между собой вторыми и третьими входами и выходами последовательно по строкам и четвертыми и пятыми входами - выходами параллельно по столбцам; второй вход соответствующего элемента И соединен с шестым выходом К -ой ячейки, пятые выходы первой ячейки первой строки, второй ячейки второй строки и-ой ячейки и-ой строки подключены к одному входу выходного элемента И каждой строки, другой вход которого соединен с выходом выходного элемента И каждой строки, расположенной в соседней нижней строке; выходы выходного элемента И первой строки к выход арифметического блока являются выходами устройства; третий вход генератора, вторые входы первого и второго элементов И, вторые входы первых входных элементов ИЛИ каждой строки являются управляющими нходами устройства,2. Устройство по п.1, о т л ич а ю щ е е с я тем, что н каждой )с; -ой ячейке первый вход ячейки соединен с первыми входами триггера и первого элемента И, выход которого соединен с первым входом первого элемента ИЛИ, выход первого элемента ИЛИ соединен с первым выходом ячейки, второй вход. ячейки соединен с вторым входом триггера, третий вход ячейки соединен с третьим и четвертым входами триггера и с третьим выходом ячейки, четвертый и пятый входы ячейки соединены с первым и вторым входами второго .элемента ИЛИ., выход которого подключен к пятому входу триггера,. ко второму входу первого элемента И и к четвертому выходу ячейки; нулевой выход триггера соединен с вторым выходом ячейки, единичный выход триггера соединен с вторым входом первого элемента ИЛИ с пятым и шестым выходами ячейки. Источники информации, принятые вовнимание при экспертизе.1, Авторское свидетельство СССРР 255647, М.Кл6 06 Р 15/32, 1967.2, Анторско свидетельство СССРР. 294144, М.Кл. 6 06 Р 15/32, 1968.