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

(57) Изотельной ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБРЕ АВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свУ 121754, кл. САвторское свидУ 1387013, кл. С21.10.86. СТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ ИАТРЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВение относится к вычисл ике и может быть исполь зовано для решения систем линейных уравнений и обращения матриц. Целью изобретения является расширение функ" циональных возможностей, Устройствой содержит п операционных блоков и и регистров, где п - количество ур нений системы. Операционный блок (1, где2,п; ) 1,п, содержит три регистра, умножитель, вычитатель, три триггера) два элемента И, элемент НЕ, группу элементов И. Операционный блок (1,1), где 3 1)п, содержит два регистра, узел деления, два триггера, два элемента И, группу элементов И и элемент НЕ. Поставленная цель достигается за счет исполь- ф зованных структурных решений. 2 з.п. ф-лы, 4 ил, 1444820(к)1 с(п + тп Изобретение относится к вычислительной технике.и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных для обращения матриц и решения систем линейных уравнений,Целью изобретения является расширение функциональных воэможностей за счет решения систем линейных урав нений.В основу .работы предлагаемого устройства положен метод ГауссаЖордана, при котором для решения системы из и линейных уравнений 15 АХ=В с ш-правыми частями, расширенная матрица 1 А 1 В ) сводится к пМ(п+ш)-матри .це Е 1 ХЗ,где Е - единичная (пХп)-матрица, по рекуррентным соотношениям(о) 20 для а; = а; ; 1=1,п; т=1,тт+тп; Ь=),пФ Х 1,", - а(,", 1 с 1( и 1 с.ш, 30 ,+) Для обращения плотной (пхп)-матрицы расширенная (пх 2 п)-матрица 1 АЕсводится к (Е)А )-матрице по рекур-.рентным соотношениям (1), в этом случае ш=п и В = Е,На фиг,1 представлена структурнаясхема устройства; на фиг.2 - Функциональная схема 13-го операционного блока (ОБ); на фиг.З - Функциональная схема Ц-го ОБ (т.=2,п;1,п); на фиг.4 - временные диаграммы устройства.Устройство для случая п=З и ш=2(фиг,1) содержит группы 1 т,1 г,1 з 45информационных входов, операционныеблоки 2 ц,2,г 2, регистры 33 , З, синхровход 4 и выходы 55 г, и 5. ОБ 2 Ц=1,п) (фиг.2) содерит перву группу входов бу синхровход 7, регистры 8 и 9 узел деления 10, триггеры 11 и 12, элементыИ 13 и 15, группу элементов И 15,элемент НЕ 16 и группу 17 выходовблока. ОБ 2, (г=2,п; 1=1,п) (Фиг,З)содержит первую группу входов 18,вторую группу входов 19, синхровход20, регистры 21 - 23, умножитель 24,вычитатель 25, триггеры 26 - 28, элементы И 29 и 30, элемент НЕ 31, группу элементов И 32, первую группу выходов 33 и вторую группу выходов 34,Устройство работает следующим образом,В исходном состоянии регистры 33 , 3, 8, 9, 21, 22, 23, триггеры11, 12 , 26, 27 и 28 устройства устанавливаются в нулевое состояние (не.показано).Очередность подачи элементов а,где- номер такта, показана на Фиг,1,Злементы а подаются на 1 входов=1,п) подается дополнительный разряд ф, принимающий значение О дляслучая а;, или 1 для а;, ) )1. Вобщем случае на (1+1)-й вход первойили второй групп входов ОБ 2 устройства подается дополнительный разряд ), равный О, если а;(1-1=1 с),)к)иначе дополнительный разряд Ф равен1 где 1 с - номер рекуррентного шага.оНа нулевом такте элемент аидополнительный разряд О подаются соответственно на 1 входов и (1+1)-йвход первой группы входов 1 ОБ 2 н,При этом на вход элемента НЕ 16 подается нулевой сигнал и на его выходеформируется единичный сигнал, который открывает элемент И 14 и соответственно разрешает запись элементаа в регистр 9 (фиг.2).На первом такте элемент а, и дополнительный разряд 1 подается навход 1), элемент аг, и дополнительный разряд О - на вход 1 г (фиг.1),В ОБ 2 и в регистр 8 записываетсяэлемент а,г, т.к. на вход элементаИ 13 подается дополнительный единичный разряд и на его выходе Формируется единичный сигнал, который разрешает запись в регистр 8 (фиг.2 и4). Триггер 11 устанавливается вединичное состояние. На выходе узладеления 1 О Формируется значениеа = а /а которое через откры 0)а тг о)тые элементы И 15 подается на вход17, В ОБ 2 г, аналогичным образомэлемент аг записывается в регистрг22. На втором такте на вход 1, пода. гются элемент а, и дополнительныиг разряд 1, на вход 1 г - элемент а(1с дополнительным нулевым разрядом. Впятом такте на вход 1 может подас15 ваться элемент а новой матрицы Аяили нулевое значение с дополнительнымнулевым разрядом, на вход 1 г подается элемент ас дополнительным единичным разрядом, в ОБ 2, в случае 20 подачи нулевого значения с дополнительным нулевым разрядом регистр 9и триггер 11 устанавливаются в нулевое состояние (фиг.2 н 4),в ОБ 2 нформируется значение а = аг- ( 25 -- а, а, в ОБ 2 э, - значение21 ва = а - а а в ОБ 2,2 - значеЭ 4 Э 4 14 Э фние а = а 2/а 22, в ОБ 22 - значе(21 (О (О 124ние ад = а - аа "1, в ОБ 2 30 ЭЭ ЭЭ 2 Э Эгфв регистр 22 записывается элемента , в регистр 3, записывается(2112 в0)элемент а с единичным дополнительным разрядом.На последующих тактах ОБ устройства работают аналогичным образом.(Э) ОПервый элемент Х= а,4 формируется на восьмом такте на выходе33 ОБ 2 гэ (на выходе устройства 54).Элемент Х, = а 4 -форМируется надевятом такте на выходе ОБ 5 э, эле(э)мент Х э, = а З 4 - на ДесЯтом такте на выходе регистра 3. (на выходеФ О) 45 устройства 5), Элементы Х 1 , ХЮХ фиксируются соответственно наэ 2девятом, десятом и одиннадцатом тактах (фиг.1). з144 и дополнительный разряд 1, на вход21 - элемент а, и дополнительный разряд О (фиг,1), В ОБ 2 и в регистр 8 записывается элемент а, , триггер 1 находится в единичном состоянии, триггер 12 устанавливается в единичное состояние, на выходе узла деле-.И ния формируется значение а1 эа,Э /а которое подается на выход 17 (фиг,2 и 4), В ОБ 2 2, в регистр 21 записывается элемент а , триггер 26 устанавливается в единичное состояние, в регистр 23 записывается элемент а) , триггер 28 находится в нулевом состоянии, на выходе умножи" теля 24 Формируется значение а 1,2ка г, которое поступает на вход вычи"ьфтателя 25, на второй вход которого подается элемент а , на выходе вычитателя 25 Формируется значениеО) 1)а = аг 2 - а,г а 211 котоРое .чеРез открытые элементы И 32 подается на выход 33 (фиг.З и 4) с дополнительным нулевым разрядом. В ОБ 2 э 1 элемент записывается в регистр 22 (фиг,З).На третьем такте на вход 1 подаэн ются элемент а, и дополнительныиэ разряд 1, на вход 1 г - элемент а . и дополнительный разряд 1, на вход 1 э - а и дополнительный разряд 1. В ОБ 2формируется значение а = а,4/ан, В ОБ 221 в регистр 20)1 зайисывается элемент а , в регистр 23 - элемент а,) , триггеры 26 - 28О)находятся в едйничном состоянии, на выходе вычитателя 25 формируется знаЮч ение а = а 2 - а , а , , которое подается через открытые элементыИ 3 2 на выход 3 3 с дополнительным единичным разрядом (фиг . 3 и 4 ) . В , ОБ 2 , в регистр 2 1 записывается элемент а , в регистр 2 3 - элемент(0атриггер 26 находится в единичг.ном состоянии, а триггеры 27 и 28 - в в нулевом, На выходе вычитателя 25 формируется значение а = аО)- а). а . которое подается на выход1 г э33 с дополнительным нулевым разрядом (фиг,З и 4), В ОБ 22, в регистр 9 записывается элемент а (фиг.2) 55На четвертом такте на вход 1, по 4.о дается элемент а, и дополнительныи единичный разряд, на вход 1 г - элемент аг 4 и дополнительный единичФормула изобретения 1, Устройство для обращения мат.Риц и решения систем линейных уравне= ний, содержащее и операционных блогков, где и - размерность матрицы пкп коэффициентов системы линейных уравнений, причем -я группа информационных входов устройства подк" лючена к первой группе входов 11-гооперационного блока (=1,и) синхравход устройства подключен к синхровходам операционных блоков, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных вазможностей путем решечия систем из и ли - нейных уравнений с т правыми частями, н него введены и регистров, причем синхровход устройства подключен к синхровходам регистров, выходы группы 1-го операционного блока подключены к входам второй группы 21-го операционного блока Ц=1,и), выходы первой группы Ц-го операционного блока подключены к входам первой группы (з.-1,1+1)-го операционного блока (ь=.",и; 1=1,и), выходы второй группы Ц-го операционного блока подключены к входам второй группы 2 О (х+1,1)-го операционного блока(1=2,и;1=1,и), выходы второй группы и 1-го операционного блока подключены к инФормационному входу 1-га регистра Ц=1,и),выход 1-го регистра25 Ц=1,и) подключен к нхадам первой группы (и,1+1)-го операционного блока, выход и-га регистра подклочен к и-му выходу устройства, выход и-го операционного блока подключен к (1-1)-му выходу устройства.2, Устройство по п,1, о т л и -а ю щ е е с я тем, что 11-й операционный блок Ц=1,и) содержит два регистра, узел деления, два триггера, два элемента И, группу элементов И, элемент НЕ, причем 1 входов первой группы блока, где 1 - разрядность чисел, соединены с информациан ными входами первого и второго регистров, (1+1)-й вход первой группы соединен с первым входом первого элемента И, с информационным входом первого триггера и с входом элемента НЕ, выход которого соединен с первым входом второго элемента И, выходы первого и нторого элементов И соединены с синхровхадами соответстненно первого и второго регистров, выходы50 которых соединены соответственно с первым и вторым входами узла деления, выход которого соединен с перными входами элементов И группы, вторые входы которых соединены с выхо,цам первого триггера, который соединен с информационным входом второго триггера, синхравход блока соединен с вторь 1 ми входами первого и второго элементов И, с синхравхадами первого и второго триггерон. выходы элементов И группы и выход второго триггера подключены к группе выходов бло-.ка,3. Устройство по и,1, а т л ич а ю щ е е с я тем, что д-й опе-рационный блок (1=2,и;1=1,и) содержит три регистра, умнажитель, вычита-,тель, три триггера, два элемента И,группу элементов И, элемент НЕ, при.чем 1 входов первой группы блока соединены с информационными входамипервого и второго регистров, (1+1)-йвход первой группы соединен с первымвходом второго элемента И, с информационным входом первого триггера ис входам элемента НЕ, выход которогосоединен с первым входом первогоэлемента И, выходы первого и второго элементов И соединены с синхровходами соответственно первого и второго регистров, выходы которых соединены с первыми входами соответственнонычитателя и умножителя, второй входкоторого соединен с выходом третьегорегистра, а выход - с вторым входомнычитателя, выход которого соединенс первыми выходами элементов И группы, второй вход которых соединенс выходом первого триггера, которыйсоединен с информационным выходомвторого триггера, 1 входов и (1+1)-йвход второй группы блока соединены синформационными нходами соответственно третьего регистра и третьеготриггера, выходы которых подключенык выходам второй группы блока, выходы группы элементов И и второго триггера падкгпочены к выходам первойгруппы выходов блока, синхравход блока соединен с вторыми входами первого и второго элементов И, с синхравходами первого, второго и третьеготриггеров и с синхравходам третьегорегистра.1444820 Составитель М.СиРедактор М;Циткина Техред А.Кравчук орректор Л.Пилиие Тираж 704 Подписно НИИПИ Государственного комитета ССС по делам изобретений и открытий 5, Москва, 11(-35, Ргушская наб., д, Заказ 6508/5 11303 Производственно-полиграфическое предприятие, г. Ужгород,