Устройство для обращения плотных ( х ) матриц

. Авгуль тельство СССР 1 15/347, 1984, У. Н. Ч 1.1 согп агре - эсае 1 пе Ргос. 1 п 1. Соп 1.У., 1980, р. 217 рц(пд аз зузРага 1- - 227. ЕНИЯ(54) УСТ ПЛОТНЬ (57) Изо числитель пользован и выть ис- вычисГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНИЕ ИЗО К АВТОРСКОМУ СВ(56) Авторское свиде1211754, кл. б 06Нъапд.К., СЬепрз 1 гцс 1 цгез 1 ог зо 1 чпд 11 егп о 1 емца(опз. -1 е 1 Ргос. Х 1 еч УогК Н РОЙСТВО ДЛЯ ОБРА Х (1 х 1 х 1 х 1) МАТРИЦбретение относится к обланой техники и может бо в специализированных 801387013 А 1 устройствах обраизобретения явстродействия. Устоперационных бло- )К) содержит умри регистра, четыре И и группу элемен) содержит умножиобратной величие триггера, два элеементов И, элемент ментов ИЛИ. РК-й ножитель, сумматор.,триггеров, грчппч ента И. Поставленсчет алгоритмичесений, реализованных ы,5 ил. лительных машинах и ботки данных. Целью ляется повышение бь ройство содержит п ков (ОБ). РК-й ОБ (Р ножитель, сумматор, т триггера, два элемента тов И. РК-й ОБ (Р=К тель, узел вычисления ны, два регистра, четыр мента И, две группы эл ИЛИ - НЕ, группу эле ОБ (Р(К) содержит ум пять регистров, восемь элементов И, два элем ная цель достигается за ких и структурных реш в устройстве. 3 з.п. ф-лИзобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных.Цель изобретения - повышение быстродействия,На фиг. 1 представлена функциональная схема устройства для обращения (п)(п) плотных матриц для случая и=4; на фиг. 2 - функциональная схема соединения четырех операционных блоков; на фиг. 3 и 4 временные диаграммы устройства; на фиг. 5 - таблицы, описывающие логику работы операционных блоков.Устройство для п=4 содержит информационные входы 1) 14 группы, операционнь)е блоки (ОБ) 2, , 244, выходы 3) 34, синхровход 4.ОБ 2;,(1=1) содержит первую группу входов 5, синхровход 6, умножитель 7, узел 8 вычисления обратной величины числа, регистры 9 и 10, триггеры 11 - 14, элементы И 15 и 16, группы элементов И 17 и 18, элемент ИЛИ - НЕ 19, группу элементов ИЛИ 20, первую группу выходов 21, вторую группу выходов 22, третью группу выходов 23 (фиг 2).ОБ 2 = - 2,и; 1=1, и - 1; )1) содержит синхровход 6, первую группу входов 24, вторую группу входов 25, умножитель 26, сумматор 27, регистры 28 - 30, триггеры 3 -34, элементы И 35 и 36, группу элементов И 37, первую группу выходов 38, вторую группу выходов 39 фиг, 2).ОБ 2 ц (1=1, п - 1; )=2, и; (1) содержит синхровход 6, первую группу входов 40, вторую группу входов 41, умножитель 42, сумматор 43, регистры 44 - 48, триггеры 49 - 56, группу элементов И 57, элементы И 58 и 59, первую группу выходов 60, вторую группу выходов 61.В основу работы устройства обращения (п)4,п матрицы А=(а, положен метод, при котором расширенная (п)(2 п) матрица А, Е 1 сводится к (п)(2 п) матрицеЕ/Апо рекуррентным соотношениям(о)для а;,=ап, 1, )=1,п и к=1, п 1 Х) (К) Х)Логика работы ОБ 2;Я=1) задаетсятабл. 1, ОБ 2 ц (1=2,; =1,и - 1; ),) )табл. 2, ОБ 21(1=1,п - 1; )=2,и;(1)табл. 3 (фиг. 5).Устройство работает следующим образом,В исходном состоянии регистры 9, 10, 28,29, 30, 44 - 48 и триггеры 11 в 14, 31 - 34,49 - 56 (фиг. 2) ОБ 21(1, 1= 1,и) устанавливаются в нулевое состояние цепи установки(не показано),Очередность подачи элементов а; матрицы А, где- номер такта, показана нафиг. 1. Элементы а подаются на гп входовпервой группы входов ОБ. Одновременно сэлементами а на и)+ 1-й и гп+2-й входы 5 О 5 20 25 30 35 40 45 50 55 первой группы входов подаются два дополнительных разряда, принимающие значения 0 или 1.На нулевом такте элемент аи дополнительные разряды 1 и 0 подаются соответственно на гп входов, гп+ 1-й вход и и)+2-й вход первой группы входов 1 ОБ 2) . При этом на вход элемента И 16 подается единичный дополнительный разряд, а на его выходе формируется единичный сигнал, который разрешает запись элемента аи в регистр 10 по заднему фронту тактового импульса. Кроме того, дополнительный единичный разряд устанавливает и триггер1 в единичное состояние (фиг. 2 - 4).На первом такте на вход 1) подаются элемент а) г и дополнительные разряды 0 и 1, на вход 1 г - элемент аг и дополнительные разряды 1 и 0 (фиг. 1). В ОБ 2) ) триггер 11 устанавливается в нулевое состояние, триггеры 12 и 13 - в единичное состояние, в регистр 9 записывается элемент а)г, так как на вход элемента И 15 подается единичный дополнительный разряд и на его выходе формируется единичный сигнал, который разрешает запись элемента а)г в регистр 9 по заднему фронту тактового импульса (фиг. 2 - 4), На входе узла 8 вычисления обратной величины числа формируется значение 1/а) ), которое поступает на вход умно- жителя 7, на второй вход которого подается элемент а)г. На выходе умножителя 7 формии)руется значение а)г=аг /аи которое через открытые элементы И 17, ИЛИ 20 подается на выходы 21 - 23. В ОБ 2 г) триггер 31 устанавливается в единичное состояние, на входе элемента И 35 формируется единицный сигнал, с помощью которого по заднему фронту тактового импульса в регистр 29 записывается элемент аг) (фиг. 2 - 4).На втором такте на вход 1) подаются соответственные элементы а)з и дополнительные разряды 0 и 1, на вход 1 г - элемент агг и дополнительные разряды 0 и 1, на вход 1 з - элемент аз) и дополнительные разрядыг1 и 0 (фиг. 1). В ОБ 2 в регистр 9 записывается элемент а)з, триггер 13 устанавливается в нулевое состояние, триггер 14 - в единичное состояние. На выходе умножи(1)теля формируется значение а)з=а)з/а). В ОБ 2 г) в регистр 28 записывается элемент а)г, в регистр 30 - элемент агг, триггер (1)31 устанавливается в нулевое состояние, триггеры 32 и 33 - в единичное состояние. На входе умножителя 26 формируется значение а)гаг), которое поступает на вход сумматора 27. На второй вход сумматора 27 через открытые элементы И 37 подается элемент агг. На выходе сумматора 27 форми 1) 41)руется значение агг=агг - а)г аг). В ОБ 2)г в11)регистр 44 записывается аг, триггер 49 устанавливается в единичное состояние (фиг. 2 - 4).На третьем такте на вход 1 подаютсяээлемент а 4 и дополнительные разряды 0 и 1, 138703(О15 Ь 11 Ьг( Ьз( Ь 1,Ь. Ь з Ь 24 Ьзг Ьзз Ьз 4 Ь 4 г ")4 з 20 25 формула изобретения 30 35 40 45 50 55 на вход 1 г - элемент агз и дополнительные разряды 0 и 1, на вход 1 з - элемент азг и дополнительные разряды 0 и 1, на вход 14 - элемент а 41 и дополнительные разряды31 и 0 фиг. 1). В ОБ 211 в регистр 9 записывается а(4, на выходе умножителя фор)мируется значение а(4=а(4/а 11, которое через элементы И 17 и ИЛИ 20 подается на выходы 21 - 23. В ОБ 2 г( в регистр 28 записывается а(з, в регистр ЗО - агз, на)выходе умножителя 27 формируется зна(1) )чение агз=агз - а 13 аг 1, КотороЕ ПОСтуидЕТ на выход 38, В ОБ 21 г в регистр 44 записывается а(з, в регистр 45 - а(г, триггер 49 устанав- И )ливается в нулевое состояние, триггеры 53 и 50 - в единичное состояние. В ОБ 2 гг в регистр 10 записывается агг, триггер 11 ус(2)танавливается в единичное состояние фиг, 2 - 4).На четвертом такте на вход 11 подаются произвольное ги-разрядное число признак+) и дополнительные разряды 0 и О, на вход 1 г - элемент аг 4 и дополнительные разряды 0 и 1 на вход 1 з - элементразз и дополнительные разряды 0 и 1, на вход 14 - элемент а 4 г и дополнительные разряды 0 и 1 фиг. 1).В ОБ 211 триггер 12 устанавливается в нулевое состояние, при этом на выходе элемента ИЛИ - НЕ 19 формируется единичный сигнал, который открывает группу из элементов И 18 и через элементы ИЛИ ЯО значение ь1=1/а 11 поступает на входы 21 - 23. В ОБ 2 г 1 в регистр 28 записывается аЯ, в регистр 30 - аг 4. На выходе сумматора(1) И) 27 формируется значение аг 4=аг 4 - ,а(4 аг 1, которое поступает на вход 38. В ОБ 21 г в регистр 44 Записывается а 1"4, в регистр 45 - а(з, в регистр 46 - а(, триггер 50 устанав- И (1)ливается в нулевое состояние, триггеры 51 и 54 - в единичное состояние. В ОБ 2 гг в регистр 9 записывается агз, триггер 11 устанав(1)ли вается в нулевое состояние, триггеры 1 2 и 1 3 - в единичное состояние . Н а выходе умножителя 7 формируется значение агз=(2) =агз/агг, которое поступает на выходы 21 -(1)23 фиг. 2 - 4).На пятом такте на вход 11 может подаваться элемент ановой матрицы А или нулевое значение с дополнительными разрядами 1 и О, на вход 1 г - признак ( и дополнительный разряды 0 и О, на вход 1 з - аз 4 и дополнительные разряды 0 и 1, на вход 14 - а 4 з и дополнительные разряды 0 и 1 фиг. ), В ОБ 211 в регистр 10 записывается элемент а 11 новой матрицы или нулевое значение, триггер 11 устанавливается в единичное состояние, В ОБ 2 г 1 в регистр 28 записывается Ь, триггер ЗЗ устанавливается в нулевое состояние, на выходе сумматора 27 формируется значение Ьг(=(1) (1) (2) а 1 г, в регистр 47 - а(з, в регистр 48 - агз, триггер 51 устанавливается в нулевое состояние, триггеры 55 и 52 - в единичное состояние, на выходе сумматора 43 форми(2) ) 1 (2)руется а(з=а(з - а(гагз. В ОБ 222 в регистр 9 записывается элемент а(г 4, триггер13 уста (1)навливается в нулевое состояние, а триггер 14 - в единичное состояние, на выходе умножителя 7 и соответственно элементов ИЛИ 20 формируется аг 4)=а 4)/аФ (фиг. 2 - 4),На последующих тактах работы в ОБ 2 формируются значения элементов обратной матрицы аналогично согласно табл.1 - 3 нефиг. 5). Первый элемент Ь 41 обратной матрицы формируется на выходе ОБ 214 на такте с номером 1 О, а последний элемент Ь 14 - в ОБ 214 на такте с номером 16 фиг. 1) . Полученные элементы образуют обратную матрицу вида Таким образом, в предлагаемом устройстве для выполнения обращения (и)4,и) плотной матрицы требуется иг операционных блоков и 5 и - 4) тактов работы. 1. Устройство для обращения плотных (и (и) матриц, содержащее иг опера ционных блоков, отличающееся тем, что, с целью повышения быстродействия, 1-й информационный вход устройства соединен с первой группой входов 11-го операционного блока (1= 1, и), первая группа выходов 11-го операционного блока = 1, и, (= ( ивсоединена с первой группой входов 1 1 + + 1)-го операционного блока, вторая группа выходов 11-го операционного блока ц=1, п - 1, г)1) соединена с второй группой входов 1+1)1-го операционного блока, третья группа выходов 11-го операционного блока (ц=2 и, 11=1) соединена с второй группой входов- 1, 1) -го операционного блока, вторая группа выходов 11-го операционного блока(11(1, 1=2,и - 1, 1=3,и) соединена с второй группой входов в 1,1)-го операционного блока, первая группа выходов (,и-го операционного блока (1= 1,и) соединена с 1-м выходом устройства, управляющий вход которого соединен с синхровходами ц-х операционных блоков 1,)= и).2. Устройство по и. 1, отличающееся тем, что 11-й операционный блок (1,1=1 и, 1=1) содержит умножитель, узел вычисления обратной величины числа, два регистра, четыре триггера, две группы элементов И, два элемента И, группу элементов ИЛИ, элемент ИЛИ в , причем из входов первой группы операционного блока соединены с информационными входами первого и второго регистров, где и) - разрядность элементов матрицы, (и)+ 1)-й вход первой группы опе 1387013тем, что 11-й операционный блок (1=2,п, ) =1, и - 1, 1)1 ) содержит умножитель, сумматор, три регистра, четыре триггера, два элемента И, и группу элементов И, при чем гп входов первой группы операционного блока соединены с информационными входами второго и третьего регистров, (в+1) -й вход первой группы операционного блока соединен с первым входом первого элемента И и с информационным вхо дом первого триггера, в (гп+2)-й вход первой группы операционного блока соединен с первым входом второго элемента И и с информационным входом третьего триггера, вторая группа входов операционного блока соединена с информационным входом первого регистра, выходы которого соединены с второй группой выходов операционного блока и с первым входом умножителя, второй вход которого соединен с выходом второго регистра, а выход - с первым входом сумматора, второй вход которого соединен с выходом элементов И группы, выход сумматора подключен к гп-выходам рационного блока соединен с первым входом второго элемента И и с информационным входом первого триггера, а (в+2)-й вход первой группы операционного блока соединен с первым входом первого элемента И и с информационным входом второго триггера, выход второго элемента И соединен с входом разрешения записи второго регистра, выход которого соединен с входом узла вычисления обратной величины числа, выход которого соединен с первыми входами элементов И второй группы и с входом первого сомножителя умножителя, вход второго сомножителя которого соединен с выходом первого регистра, вход разрешения записи которого соединен с выходом первого элемента И, выход умножителя соединен с первыми входами элементов И первой группы, выходы которых соединены с первыми входами элементов ИЛИ группы, вторые входы которых соединены с выходами элементов И второй группы, вторые входы элементов И второй группы соединены с выходом элемента ИЛИ - НЕ, первый вход которого соединен с выходом первого триггера и с информационным входом третьего триггера, второй вход элемента ИЛИ всоединен с выходом второго триггера, с вторыми входами элементов И первой группы и с информационным входом четвертого триггера, выходы элементов ИЛИ группы подключены к выходам первой, второй и третьей группы выходов операционного блока, выходы третьего и четвертого триггера являются соответственно (гп+1)-м и (гп+2)-м выходами первой группы операционного блока, синхровход которого соединен с вторыми входами первого и второго элементов И, с синхровходами первого, второго, третьего и четвертого триггеров.3. Устройство по п. 1, отличающееся 5 10 15 20 25 30 35 первой группы операционного блока, выходы первого и второго элементов И соединены с входами разрешения записи соответственно второго и третьего регистров, выход третьего регистра соединен с первыми входами элементов И группы, вторые входы которых соединены с выходом третьего триггера и с информационным входом четвертого триггера, выход четвертого триггера подключен к (гп+2)-му выходу первой группы операционного блока, (гп+1)-й выхрд которого соединен с выходом второго триггера, информационный вход которого соединен с выходом первого триггера, синхровход операционного блока соединен с входом разрешения записи первого регистра, вторым входом первого и второго элементов И и с синхровходами первого, второго, третьего и четвертого триггеров.4. Устройство по п. 1, отличающееся тем, что ц-й операционный блок (1=1, й 1, 1=2, и, 1(1) содержит умножитель, сумматор, пять регистров, восемь триггеров, два элемента И и группу элементов И, причем гп входов первой группы операционного блока соединены с информационным входом первого регистра, выход которого соединен с информационным входом второго регистра, выход которого соединен с информационными входами третьего и четвертого регистров, выходы которых соединены соответственно с первым входом умножителя и с первыми входами элементов И группы, (т+1) -й вход первой группы операционного блока соединен с информационным входом первого триггера, выход которого соединен с информационным входом второго триггера, выход которого соединен с первым входом первого элемента И и с информационным входом третьего триггера, выход которого соединен с информационным входом четвертого триггера, выход которого подключен к (гп+1)-му выходу первой группы операционного блока, (гп+2)-й вход первой группы которого соединен с информационным входом пятого триггера, выход которого соединен с информационным входом шестого триггера, выход которого соединен с первым входом второго элемента И и с информационным входом седьмого триггера, выход которого соединен с вторыми входами элементов И группы и с информационным входом восьмого триггера, выход которого подключен к (в+2) -му выходу первой группы операционного блока, вторая группа входов которого соединена с информационным входом пятого регистра, выход которого соединен с второй группой выходов операционного блока и с вторым входом умножителя, выход которого соединен с первым входом сумматора, второй вход которого соединен с выходами элементов И группы, выход сумматора подключен к т выходам первой группы операционного блока, синхровход которого соединен с вторыми вхо1387013 дами первого и второго элемента И и с входами разрешения записи первого, второго и 924 пятого регистров, с синхровходами с первого по восьмой триггеров. 14 р 1 12 11387013 1 аЮЛаиа 1 Та даик Редактор И. ШуллаЗаказ 1223/48НИИПИ Государственног113035, МоскПроизводственно-полиграф Составитель М. СилинТехред И. Верес Корректор И. МускаТираж 704 Подписноекомитета СССР по делам изобретений и открытна, Ж - 35, Раугиская наб., д. 45веское предприятие, г. Ужгород, ул. Проектная, 4