Устройство для раскрытия и вычисления определителей матриц Советский патент 1979 года по МПК G06F17/16 

рицЫ первыми- входами и выходами соединены в кольцо, вторые входы последних ячеек каждой строки матрицы соединены с первыми входами соответствую 1ДИХ первых входных элементов ИЛИ каждой строки матрицы второй, третий, четвертый и пятый выходы блока управЛенин соединены соответственно с первыми входами вторых входных элементов ИЛИ третьей, четвертой, пятой и Шестой строк матрицЕЗ, втопые входы которых соединены соответственно .с выходом первого элемента И, а выходы вторых входных элементов ИЛИ третьей, четвертой, пятой и аестой строк мат рицы соединены соответственно с вторыми входами первых, ячеек этих , строк матрицы; выходы первых вхсэдных элементов ИЛИ каждой строки подключены к третьим входам первых ячеек каждой строки матрицы} группа выхоKOS распределителя сигналов соединена с перзой группой входов блока памяти, причем каждый выход из этой группы выходов подключен к первому Входу соответствующего элемента И в J-OM столбце матрицы; выходы соответ етв-ующих элементов и i-ой строки мат рицы объединены и соединены с соответствувзщими входами блока памяти и блока определения нулевого члена, выход которого соединен с вторым вхо дом третьего элемента И,- ячейки матрищз соединены между собой вторыми и третьими входами, и выходами п.оследовательно по строкам и четвертыми и.Пятыми входами - выходами параллел HQ.tjo столбцам; второй вкод соответСТвующего элемента И соединен с шестым выходом k j-ofl ячейки, пятые выходы первой ячейки первой строки, вт рой ячейки второй строки,.«., п-ой ячейки п-ой строки подключены к одному входу выходного элемента И каждой строки, другой, вход.которого сое динен с выходом выходного элемента И каждой строки, расположенной в сосед ней нижней строке; выходы выходного элемента И первой строки и выход арифметического блока являются выходами устройства; третий вход генератора, вторые входы первого и второго элементов И, вторые входы первык . входных элементов ИЛИ каждой строки являются управляющими входами устрой ств.а, .а также тем, что в каждой k.|ячейке первый вход ячейки соединен .с первыми входами триггера и первог элемента И, выход которого соединен с первым :. входом первого элемента И выход первого элемента ИДИ соединен с первым, выходом ячейки, второй вхо ячейки соединен с вторым входом три гера, третий вход ячейки соединен с третьим и четвертым входами триггер и с третьим выходом ячейки, четверт и пятый входы ячейки соединены с пе вым и вторым входами второго элемента ИЛИ, выход которого подключен пятому входу триггера, ко второму ходу первого элемента И и к четверому выходу ячейки; нулевой выход риггера соединен с вторым выходом чейки, единичный выход триггера оединен с вторым входом первого элеента ИЛИ, с пятым и шестым выходаи ячейки. На фиг. 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, соответствующих .ненулевым элементам матрицы определителя. ЭлеMBFiTy матрицы определителя, находящемуся в i-ой строке и j-ом столбце матрицы, соответствует ячейка 8, находящаяся в i-ой строке и J-OM столбце. На управляющие входы из генератора 1 и из блока 3 подаются сдвинутые относительно друг друга на время тг последовательности им- . пульсов. На вход, связанный с первой строкой матрицы, подается последовательность импульсов, имеющих период следования Т, на вход связанный с второй строкой - запаздывающая относительно предыдущей последовательность с периодом Т, на вход третьей строки - с периодом 2Т, на вход четвертой строки - с периодом 6Т, на вход пятой строки - с периодом 24Т и т.д. В общем случае период следования импульсов равен T(i-I). Блок 3 выступает в качестве делителя частоты импульсов, поступающих на ее вход с генератора 1 с периодом Т. В первом такте работы устройства по входу устройства выдается сигнал длительностью Т (п-1) т + Т , где Су .длительность импульса управляющей последовательности. Этот сигнал поступает через элементы ИЛИ 14 на входы первых в строке ячеек 8, через элементы И 10 и ИЛИ 13 - на вход записи единицы распределителя сигналов 5 и на вход генератора 1. Генератор 1 вырабатывает управляющий сигнал первого такта, который поступает на входы ячеек первого столбца, а также на вход блока 3 и через элемент задержки 18 на синхровход распределителя 5. При этом происходит запись единицы в первый разряд распределителя 5. Кроме того в первом такте в течение действия входного сигнала в ячейки 8 строк матрицы за писываются единицы в следующем по-рядке; в первую ячейку первой снизу строки, во вторую ячейку следующей строки, в третью ячейку третьей сни строки и т.д. и, наконец, в последнюю ячейку верхней строки. Реализуется базовая перестановка (1,2,3...п т.е. -В соответствии с заданной пере тановкой сигналы с выходов распреде лителя 5 через элементы И 16 проходят на входы блоков 5 и б. Каждое состояние матричной.схемы соответст вует одному члену раскрытого опреде лителя п-го порядка, так как, если расположить первые индексы элементов определителя матрицы ...а .JKoтopый равен сум ме произведений вида «п,«п, ,,„ 1Ы.-1 2Л2 ОпЛП «. В порядке их возрастания, то совокупность вторых индексов образует некоторую перестановку (оС, d, ..-, п ) множества чисел от 1 до п. В течени каждого такта работы устройства i пробегает/Bce разряды распределителя 5, а затем по цепи обратной связи через элемент ИЛИ 13 записывается в первый разряд распределителя 5. После вьвдачи каждого синхроимпул са осуществляется выборка одного эле мента определителя. Сигнал с единич ного выхода распределителя 5 поступа ет одновременно,на первый горизонтал ный вход выборки ячейки блока б и на вход eiи вертикальной выборки. При этом происходит выборка и считывание из ячейки, в которой хранится элемент а,так как предварительно запись элементов определителя в ячейки блока б осуществляется таким образом чтобы эти ячейки образовали матрицу аналогичную матрице определителя. После считывания очередного элемента определителя в блоке 6 вырабатывается сигнал, ;определяющий конец считывания,.Который Поступает в качестве синхроимпульса на,синхровход распределителя 5. Сигнал с второго выхода распределителя 5 поступает на второй горизонтальный вход блока б и на Ой вертикальный ,вход блока 6. При этом происходит выборка и считывание из ячейки, в которой хранится элемент 02(2-Аналогично происходит выборка остальных элементов, входящих в данное произведение вида °-io4«z L2« 3 ta-- tv in Вычисление этог произведения производится в арифметическом блоке 7, на вход которого поступают считываемые из блока 6 эле менты определителя. Сигнал с последнего выхода распределителя 5 определяет начало ново го такта работы устройства. Этот сигнал поступает на вход генератора 1, который вырабатывает управляющий сигнал нового.такта Рассмотрим работу устройства после того, как на нем в первом такте была установлена базовая перестановка (1,2,3,4,5,6) для случая когда . Во втором такте единица, записанная в триггер 19 второй справа ячейки 8 второй сверху строки матриЦК под действием управляющего сигнала, поступающего на вход данной ячейки, сдвигается в последнюю ячейку 8 этой строки. Единица, записанная в триггер 19 последней ячейки первой сверху строки, под действием управляющего сигнала, сдвинутого на отношению к сигналу, действующему на ячейки соседней снизу строки, про ходит через элементы 21 последней ячейки, ИЛИ 14 первой строки и далее через элемент И 20 первой ячейки второй строки, открытую сигналом с выхода элемента ИЛИ 22. На выходе элемента ИЛИ 22 присутствует единичный сигнал, так как в триггере 19 первой ячейки нижней строки записана единица. Единица, поступающая с выхода элемента ИЛИ 22 не записывается 3 триггер 19 первой ячейки 8 первой строки, так как его единичный вход закрыт сигналом с выхода элемента ИЛИ 22, заведенным на второй единичный вход триггера 19. За п тактов устройство генерирует все п перестанов,ок. Для того, чтобы не производить выборку элементов определителя, равных нулю, используется блок 4, представляющий собой схему ИЛИ. После полного перебора всех возможных перестановок на входах каждого элемента И 17 появляются сигна- , лЫг проходящие на выход верхнего элемента И 17 как сигнал, определяющий окончание вычксленкя определителя. В данном устройстве по сравнению с прототипом HciMHoro уменьшены аппаратурные затраты, а также возможно вычисление значения определителя и его отдельных членов. Устройство может быть использовано автономно как специализированная машина,, а также в качестве дополнительного оборудования для универсальной ЦВМ. изобретения Формула 1. Устройство для раскрытия и вычисления определителей матриц, содержащее генератор, блок управления, блок определения знака, блок определения нулевого члена и матрицу из п идентичных ячеек, о т л и ч а ющ е е с я тем, что, с ,целью упрощения устройства, в него введены элементы И, ИЛИ, распре,делитель сиеналов, блок памяти и арифметический блок, причем выход генератора соединен с первыми входами блока управления, первого и второго элементов И, - первых ячеек первой и второй строк матрицы и с первым входом блока определения знака, второй вход которого соединен с первым выходом блока управления, а второй выход блока определения знака - с первым входом арифметического блока, второй вход которого подключен к первому выходу блока памяти, второй выход блока памяти соединен с первыми входами первого элемента ИЛИ и третьего элемента И, выход которого подключен к первым входам генератора и второго элемента ИЛИ, выходы первого и второго элементов ИЛИ соединены соответственно с первым и вторым входами распределителя сигналов, выход которого соединен со вторыми входами второго элемента ИЛИ и генератора; выход второго элемента И соединен через,элемент задержки с вторым входом первого элемента ИЛИ и непосредственно с третьим входом второго элемента ИЛИ; п ячеек каждой строки матрицы первыми входами и выходами соединены Ь кольцо, вторые выходы последних ячеек каждой строки матрицы соединены с первыми входами соответствующих первых входных элементов ИЛ каждой строки матрицы; второй, третий, четвертый и пятый выходы блока управления соединены соответственно с первыми входами вторых входных элементов ИЛИ третьей, четвертой, пятой и шестой строк матрицы, вторые входы которых соединены соответстБвнно с выходом первого элемента И, а выходы вторых входных элементов ИЛИ третьей четвертой, пятой и шестой строк матрицы соединены соответственно с вторыми входами первых ячеек этих же строк матрицы выходы первых входных элементов ИЛИ каждой строки подключены К третьим входам первых ячеек каждой строки матрицы; группа выходов распределителя сигналов соединена с первой группой.входов блока памяти, причем каждый выход из этой, группы выходов подключен к первому входу соответствующего элемента И в j-ом столбце матрицы; выходы соответствующих элементов И i-ой строки матрицы объединены и соединены с соответствующими входами блока памяти и блока определения нулевого члена, выход которого соединен со вторым входом третьего элемента И; ячейки матрицы соединены между собой вторыми и третими входами и выходами последовательно по строкам и четвертыми и пятыми входами - выходами параллельно по столбцам; второй вход соответствующего элемента И соединен с шестым выходом К -:-ой ячейки, пятые выходы первой ячейки первой строки, второй ячейки второй строки,..., п-ой ячейки п-ой строки подключены к одному входу выходного элемента И каждой строки, другой вход которого соединен с выходом выходного элемента И каждой строки, расположенной в соседней нижней строке; выходы выходного элемента И первой строки и выход арифметического блока являются выходами устройства; третий вход генератора, вторые входы первого и второго элементов И, вторые входы первых входных элементов ИЛИ каждой строки являются управляющими входами устройства.

2. Устройство по п,.1, о т л ичающееся тем, что в каждой 1с„;;-ой ячейке первый вход ячейки соединен с первыми входами триггера и первого элемента И, выход которого соединен с первым входом первого элемента ИЛИ, выход первого элемента ИЛИ соединен с первым выходом ячейки, второй вход.ячейки соединен с вторым входом триггера, третий вхо ячейки соединён с третьим и.четвертым входами триггера и,с третьим-выходом ячейки, четвертый и пятый входы ячейки соединены с первым и вторы входами второго элемента ИЛИ-, в-ыход которогоподключен к пятому входу триггера,- ко второму входу первого элемента И и к четвертому выходу ячейки; нулевой выход триггеча соединен с вторым выходом ячейки, единичный выход триггера соединен с вторым входом первого элемента ИЛИ с пятым шестым выходами ячейки.

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

1,Авторское свидетельство СССР 255647, МЛСл.2 G 06 F 15/32, 1967.

2,Авторское свидетельство СССР №.294144, М.КлГ G Об F 15/32, 1968.

5FliTi W н н п

Ьг4

« Tj Фиг