Устройство для решения матричного уравнения вида ах=в

,тельных машинах ботки данных для нейных уравнений зированных вычисли- устройствах обрарешения систем лии обращения плотныхматриц. ель изо ения - упрощение устогоса-Жорсисте енная ррент=1,п ш ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБР К АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Седухин С.Г. Параллельная интерпретация прямых методов линейнь алгебры, - Программирование, 1984, Р 4, с, 57-68.Авторское свидетельство СССР У 1444820, кл, С 06 Р 1.5/347, 1987(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ МАТРИЧНОГО УРАВНЕНИЯ ВИДА АХ=В(57) Изобретение относится к вычистельной технике и может быть испол Изобретение относится к вычислительной технике и может быть исполь роиства,В основу работы предлагаемустройства положен метод Гаусдана, при котором для решениялинейных уравнений АХ=В расшии .(и+ш) матрица .А/В 3 сводитсп-(п+ш) матрице ГЕ/Х 1, где Еничная (пи) матрица, по рекуаным соотношениям для а; =а;1,1=1,п+ш (при обращении матриц.801509932 А 1 зовано для решения систем линейных уравнений и обращения матриц. Целью изобретения является упрощение устройства. Устройство содержит п(и+)/ /2+пш операционных блоков; (1,1)-й операционный блок (=1,п) содержит регистр, узел вычисления обратной величины числа, две группы элементов И, группу элементов ИЛИ и триггер; И,1)-й операционный блок (1=2,п+ш, 1=1,п, .-11) содержит четыре триггера, три регистра, умножитель, вычитатель, четыре группы элементов И, группу элементов ИЛИ и элемент ИЛИНЕ, Поставленная цель достигается за счет реализованных структурныхе решений, 2 з,п. ф-лы, 4 ил 2 табл расширенная и 2 п матрица А/одится к и 2 п матрице Е/А 1(а (и1 =а;,а.е(1 си, 1 (1 (ш На фиг. 1 представлена структур= ная схема устройства для решения матричных задач для случая п=3 и ш=2; на фиг. 2 - функциональная схемаЗь11-го операционного блока (ОБ) (1,3= =1,п; д=); на фиг, 3 - функциональная схема ц-го ОБ (х=2,п+ш, 1=1,п; х.Ъ 1)3 на фиг, 4 - временные диаграммы устройства1509932 3Табл, 1 и 2 показывают логику работы ОБ.Устройство для случая и 3 и ш 2 (фиг, 1) содержит группы информационных входов 1,-1, синхровход 2, операционные блоки 3 ,3 ,Зр выходы 4и 4 , Размерности структуры устройства ш и и показаны пунктирными линиями (фиг. 1). 10Операционный блок 3; (1=Д) (фиг. 2) содержит группу входов 5, синхровход 6, регистр 7, узел 8 вычисления обратной величины числа, группы элементов И 9 и 10, группу 15 элементов ИЛИ 11, триггер 12, выход 13.Операционный блок 3; (=2,п+ш;1=1,п; -1 ъ,) (фиг, 3) содержит первую группу входов 14, второй 20 вход 15, синхровход 16, регистры 17- 19,.умножитель 20, вычитатель 21, триггеры 22-25, группы элементов И 26-29, группы элементов ИЛИ 30 и 31, элемент ИЛИ-НЕ 32, первую группу выходов 33 и второй выход 34.Рассмотрим работу ОБ 3; (1=1=1,п), логика работы которого показана в табл. 1, При подаче на 1 входов первой группы входов 5 значения эле мента а , а на(1+1)-й вход 5 - нулевого сигнала, в регистр 7 записывается значение элемента а , триггер 12 устанавливается в нулевое состояние. С инверсного выхода триг гера 12 единичный сигнал открывает группу элементов И 10, через которую значение 1/ас выхода узла 8 вычисления обратной величины числа подается на вход группы элементов ИЛИ 40 11. С выхода группы элементов ИЛИ 11 значение 1/а подается на выход 13 ОБ. Если триггер 12 устанавливается в единичное состояние, то открывается группа элементов И 9 и на выход 45 13 ОБ через группу элементов ИЛИ 11 подается значение элемента ав, .Рассмотрим работу ОБ 3; (х=2,п+ш; ,1=1,п; 1-1 Ъ д) (фиг. 3), Логика работы этого ОБ задается табл. 2,На нулевом такте при подаче на 1 входово первой группы входов значения Сви нулевых сигналов на (1+1)-й и (1+ +3)-й входы 1 в регистр 17 записывается значение С , триггеры 22 и 24 устанавливаются в нулевое состояние С выходов триггеров 22 и 24 нулевые сигналы подаются на входы элемента ИЛИ-НЕ 32, на выходе которого формируется единичный сигнал, разрешающий запись в регистр 19 и открывающий группу элементов И 26. Черезгруппу элементов И 26 и группу элементов ИЛИ 30 значение подается напервый вход умножителя 20, На второйвход 15 ОБ подается значение Вкоторое записывается в регистр 13.С выхода регистра 18 значение В подается на второй вход умножителя 20,на выходе которого формируется произо оведение С,В , которое записывается в регистр 19, На первом такте подаются значение С на 1 входов 1,ехнулевой сигнал на (1+1)-й вход 1 иединичный сигнал на (1+2)-й вход 1,на второй вход 15 подается В . ВЬхрегистры 17 и 18 записываются соответственно значения С и В . Триггерьх ьх е24 устанавливается в единичное состояние, единичный сигнал открываетгруппы элементов И 27 и 29. На первый вход умножителя 20 подается черезгруппу элементов И 27 и группу элементов ИЛИ 30 произведение г=В 8 хСвх,на второй вход - значение В с выхоЬхда регистра 18. На выходе умножителя20 формируется значение гВ , которое подается на вход вычитателя 21,на второй вход которого подаетсязначение С, с выхода регистра 17, Навыходе вычитателя 21 формируетсязначение Со -гВ , которое через открытую группу элементов И 29 и группу элементов ИЛИ 31 подается на 1выходов, первой группы выходов 33,На (1+1)-м и (1+2)-м выходах 33 имеются нулевые сигналы, так как триггеры 23 и 25 находятся в нулевомсостоянии,На втором такте ОБ работает аналогично. Триггер 25 устанавливается в единичное состояние, На (1+1)-й выход 33 подается нулевой сигнал, а на, (1+2)-й выход 33 - единичный сигнал, На третьем такте на (1+1)-й вход 14 подается единичный сигнал, а на (1+2)-й вход 14 -нулевой сигнал.Триггер 22 устанавливается в единичное состояние, триггер 24 - в нулевое состояние. Открывается группа элементов И 28, через которую с выхода регистра 19 подается значениеог"ВьСна вход группы элементов ИЛИ 31 и соответственно на 1 выходов 33. На (1+1)"й и (1+2)"й выходы 33 пода-ются соответственно нулевой и единич 5 150993 ный сигналы. На последующих тактах ОБ работает аналогичным образом.Устройство работает следующим образом.В исходном состоянии регистры 7, 17-19, триггеры 12, 22-25 устройства устанавливаются в нулевое состояние (фиг 2 и 3, не показано).1 ООчередность подачи элементова. и нулевого значения О , где й -эномер такта (фиг, 1). Элементы ах=1,п подаются на 1 входов первойгруппы входов 1 Одновременно с элементами а на (1+1)-й вход первой)1группы входов 1, подается на нулевомтакте дополнительный разряд О, на1,2 .птактах - дополнительныйразряд 1, на и такте - дополнительный 20разряд О, Элементы а; (1=1,п 1 5=2и+и подаются на 1 входов первойгруппы входов 1; (1=2,п+щ). Одновремеино с элементами а иа (1 е 1)-й и(1+2)-й входы 1. (1=2,п+тп) подаютсяна (1-1)-м такте соответственно дополнительные разряды О и О, на 1,1+11+итактах - соответственно дополнительные разряды О и 1, на(1+и)-м такте - соответственно до 30полнительные разряды 1 и О.ээНа нулевом такте элемент а идополнительный разряд О.подаются навход ОБ 3, (фиг. 1), .В. регистр 7 ОБ3 записывается элемент а,35На первом такте элемент а, и дополнительный разряд 1 подаются соответственно на 1-й и (1+1)-й. входы1 элемент а и дополнительно раз 112ряды О и О подаются соответственнона 1-й, (1+1)-й и (1+2)-й входы 1(Фиг, 1), В ОБ 3, в регистр 7 записывается элемент а 2. В ОБ 32, В регис тр 1 7 з аписыв ается элемент а 22 врегистр 18 - значение 1/а, в регистр 19 " значение а" ,=а, /а, .(фиг4).1На втором. такте элемент а и доЗполнительныи разряд 1 подаются соответственно на 1-й и (1+1)-й входы501 , элемент а и дополнительные раз 9ряды О и 1 подаются соответственнона 1-й (1+1)-й и (1+2)-й входы 1 е,элемент а н дополнительные разряды0 и .О подаются соответственно на1-й, (1+1)-й и (1+2)-й входы 1 . В55ОБ 3 в регистр 7 залисывается аВ ОБ 3 ,на. выходе вычитателя 21 фор- .мируется а=а, -аДа В ОБ З,в ре 2 6гистр 17 записывается а, , в регистр18 - значение 1/а , в регистр 19значение а=а, /а(Фиг. 4).На третьем такте нулевое значениеО и дополнительный разряд О подаются соответственно на 1-й и (1+1)-йвход 1, элемент а,и дополнительныеразряды О и 1 подаются соответственно на 1-й, (1+1)-й и (1+2)-й входы12, элемент а и дополнительные разз2 аряды О и 1 подаются соответственнона 1-й, (1+1)-й и (1+2)-й входы 1ээлемент а и дополнительные разрядыО и О подаются соответственно на1-й, (1+1)-й и (1+2)-й входы 1 а ВОБ З в регистр 7 записывается нулевое значение. В ОБ З,на выходевычитателя 21 Формируется значениеа" =а -а, а, . В ОБ Зана выходе32 эг 12 3)вычитателя 21 формируется значениеа =а. -а а , В ОБ 32 в регистр 7ззаписывается значение а т22На четвертом такте на вход 1), может подаваться элемент а новой системы линейных уравнений или нулевоезначение с дополнительным разрядомО, на 1-й, (1+1)-й и (1+2)-й входы1 подаются соответственно нулевоеозначение О и дополнительные разряды 1 и О, на 1 - й, (1+1)-й и (1+2)-йвходы 1 - соответственно элементэа и дополнительные разряды О и 1,на 1-й, (1+1)-й и (1+2)-й входы 1,соответственно элемент а и дополни).цтельные разряды О и 1, на 1-й, (11)-й и (1+2)-й входы 1 - соответ 5ственно элемент а,и дополнительныеразряды О и О. В ОБ З,в регистры17 и 18 записываются нулевые значения, В ОБ 3 в регистр 7 записывается элемент а , В ОБ 3 формируетсярегистр 1: ". аписывается значениеат =1 /а , В ОБ 3, формируется знарегистр 19 записывается значение а=а,/а ,На пятом такте на 1-й, (1+1)-й и(1+2)-й входы 1 з подаются соответственно нулевое значение О и дополнительные разряды 1 и О, на 1-й, (1++)-й, (1+2)-й входы 1 соответственна элемент а и дополнительные разряды О и 1 на 1-й, (1+1)-й, (1+2)-йвходы 1 подаются соответственноэлемент и дополнительные разряды Ои 1, В ОБ 3,2 в регистр 7 записывается значение аДа В ОБ З в регистры(1а 5:а с зтя 5 25 15 гНа последующих тактах ОБ устройства работают аналогичным образом,Первый элемент Х=а, формируетсяХна восьмом такте на выходе 4 . Навыходе 4, на девятом такте форрруется элемент Х,=а,4 а элеме т З =Юз)=а на,песятом такте. Элементы ХзФХ и Х формируются на выходе 4ы зсоответственно на девятом, десятом иодиннадцатом тактах (фиг. 1),10 Формула изобретения 1,Устройство для решения матричного уравнения вида АХ=В, где А - матрица регулярности и п, Х и В - матрицы размерности и щ (п,щ - разряд ность расширеной матрицы А/В 3) содержащее п(п+1)/2+пщ операционных блоков, причем д-й информационный вход (=1 п+щ) устройства подключен к входам первой группы х 1-го операци онного блока, синхровход устройства подключен к синхровходам операционных блоков, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, выход первой группы Ц-го операционного блока (1=3 п; 1=1 п; дЪ 1) подключен к входам первой группы ( 1+1)-го операционного блока, 1 входов и (1+1)-й вход первой группы (1 - разрядность элементов матрицы) -го операционного блока (=2 п) подключены соответственно к 1 выходам и (1+2)-му выходу первой группы (х)-го операционного блока, где 1 - разрядность элементов 45 матрицы, выходы первой группы Ц-го операционного блока (д=п+1 и+щ; =1 п) подключены к входам первой группы ( +1)-го операционного блока, второй выход Ц-го операционного блока (ь.=1 п+щ1=1 Т 1 х ) 1) соединен с вторым входом (х+1 )-го операционного блока, выход Ип)-го операционного блока подключен к (-и)-му выходу устройства55 (=п+1, и+щ),2Устройство по п. 1, о т л ич а ю щ е е с я тем, что Ц-операционный блок (=1=1 п) содержит регистр, узел вычисления обратной величины числа, две группы элементов И, группу элементов ИЛИ и триггер причем 1 входов первой группы блока соединены с информационным входом регистра, выход которого соединен с входом узла вычисления обратной величины числа и с первыми входами элементов И первой группы, второй вход которых соединен с прямым выходом триггера, а выход - с первыми входами элементов ИЛИ группы, вторые входы которых соединены с выходами элементов И второй группы, вторые входы которых соединены с инверсным выходом триггера, информационный в 1 од которого соединен с (1+1)-м входом первой группы блока, синхровход которого соединен с входом разрешения записи регистра и с синхровходом триггера, выход группы элементов ИЛИ является выходом блока.3, Устройство по и. 1, о т л ич а ю щ е е с я тем, что Ц-й операционный блок (д=2 и+щ; 1=1 п -1 Ъ 1) содержит три регистра, умножитель вычитатель четыре триггера, четыре группы элементов И, группу элементов ИЛИ и элемент ИЛИНЕ, причем 1 входов первой группы блока соединены с информационным входом первого регистра, выход которого соединен с первым входом вычитателя и с первыми входами элементов И первой группы, выходы которых соединены с первыми входами элементов ИЛИ первой группы, вторые входы которых4соединены с выходами элементов И второй группы, а выходы - с первым входом умножителя, второй вход которого соединен с вторым выходом блока и с выходом второго регистра, выход умножителя подключен к информационному входу третьего регистра и второму входу вычитателя, информаци-онный вход второго регистра соединен с второй группой входов блока, выход вычитателя соединен с первыми входами элементов И четвертой группы, выход. которых соединен с первыми входами элементов ИЛИ второй группы, выход которых соединен с 1 выходами первой группы выходов блока, вторые входы элементов ИЛИ второй группы соединены с выходами элементов И третьей группы, первые входы которых соединены с выходом третьего регист- .ра и с первыми входами элементов И9 1509932 10 второй группы, вход разрешения запи- ционным входом второго триггера, выси третьего регистра соединен с объ- ход которого является (1+2)-м выходом единенными выходами элемента ИЛИ-НЕ первой группы выходов блока, синхрои с вторыми входами элементов И пер- вход блока соединен с входами раэреше"5вой группы, (1+1)-й вход первой груп- ния эаписи первого и второго репы входов блока соединен с инФорма- гистров, с синхровходами первого, ционным входом первого триггера, . второго, третьего и четвертого тригвыход которого соединен с первым вхо- геров.дом элемента ИЛИ-НЕ, с вторыми входа- О Таблицами элементов И третьей группы и синФормационным входом второго триг- Входыгера, выход которого является (1+1)-мвыходом первой группы выходов бло-1 1+ка, (1+2)-й вход первой группы блока 15соединен с информационным входом тре тьего триггера, выход которого. соединен с вторым входом элемента ИЛИНЕ, с вторыми входами элементов И а 1 а ааех Внх бх второй и четвертой групп и с инФорма Выход а бц а ЬхТираж 668 КНТ ССС Производственно-издательский комбинат "Патент",Ужгород, ул. Гагарина, 10 Заказ 5815/48 ВНИИПИ Госуда твенного комитета по 113035, Москва, ЖПодписноеобретениям и открытиям прРаушская наб., д. 4/5