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

ОП САНИЕ ИЗОБРЕТЕНИЯ 1 ц 798862 К АВТОУСКОММ СВИ ВТВЛЬСТВУ(22) Заявлено 05. 12. 78 (21) 2691586/18-24 Р 1) М ИЛ с присоединением заявки Нов(23) Приоритет О 06 Г 15/324 Государственный коинтет СССР по дедаи нзобретеннй н открытнй(72) Авторыизобретения В.П,Боюн, Л.Г.Козлов, Б.Н.Малиновский и С,И.Третьяков Ордена Ленина институт кибернетики АН Украинской ССР(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ Изобретение относится к вычислительной технике и может быть применено при построении устройств для решения систем линейных алгебраических уравнений.Известно цифровое устройство для решения систем уравнений, построенное на базе интегратора, содержащее интеграторы коэффициентов, интеграторы свободных членов и интеграторы неизвестных, причем выходы интеграторов коэффициентов каждого столбца соединены с выходами интеграторов свободного члена тога же столбца, выходы которых подключены ко входам 15 интеграторов неизвестных того же столбца и входам интеграторов коэффициентов соответствующих строк (,1).Недостатками данного устройства являются большое количество сбору" 20 дования, низкое быстродействие, трудность определения конца решения.Наиболее близким по технической сущности к предлагаемому, является устройство для решения систем линейных алгебраических уравнений, которое содержит регистры свободных членов, запоминающий блок коэффициентов, сумматоры, множительные блоки, регистры неизвестных схемы при- Ж ема, выходы регистров свободных членов соединены с первыми входами первых сумматоров соответствующих строк из сумматоров, к вторым входам которых подключены выходы множитель" ных блоков соответственно, сумматоры соединены последовательно, причем выходы последних и-ых сумматоров подсоединены к входам схем приема соответственно, выходы которых подключены к соответствующим входам регистров неизвестных, выходы которых соединены с общей точкой объединенных первых входов соответствующих множительных блоков каждой строки из множительных блоков, выходы запоминающих блоков коэффициентов подсоединены к, общей точке объединенных вторых входов множительных блоков соответствующих строк 2)Работа устройства заключается в следующем. С выходов запоминающих блоков на входы множительных блоков соответствующих строк поступают значения коэффициентов параллельным кодом, а с выходов регистров неизвестных в соответствующем такте и на входы соответствующих множительных блоков каждой строки подаются последовательно (начиная с младших)разряды неизвестных. полученные разряды произведений коэффициентов на неизвестные в соответствующем такте суммируются между собой и с кодом свободного члена на последовательном сумматоре, состоящем из и сумматоров. Результаты выполненных операций (код невязки) передаются в схему приема, которая преобразует поступивший код невязки в код неизвестного (например, выделяется часть величины невязки). Полученное таким образом новое приближение неизвестного будет использовано в следующей итерации,Данное устройство имеет существенный недостаток - низкое быстродействие, Это объясняется тем, что код невязки проходит столбец из и одноразрядных сумматоров, а при достаточно большом порядке и решаемой системй уравнени время решения может быть недопустимо большим.Цель изобретения - повышение быстродействия устройства. Поставленная цель достигаетсятем, что в устройство для решениясистем линейных уравнений, содержащее запоминающие блоки коэффициентов,регистры невязок, регистры неизвестных, одноразрядные сумматоры, введены сдвиговые регистры, сумматоры иприоритетный блок, управляющий входкоторого является управляющим входомустройства, первый вход кажпого сумматора соединен с выходом соответствующего запоминающего блока коэфФициентов, второй вход - подключенк выходу соответствующего сдвиговогорегистра, вход которого соединен спервым выходом регистра невязок,выход каждого сумматора соединен свходом соответствующего регистра невязок и с одним из входов приоритетного блока, первый выход которогоподключен к управляющим входам сдвиговых регистров, второй выход приоритетного блока соедйнен с первымивходами одноразрядных сумматоров,управляющий вход каждого из которыхсоединен с вторым выходом соответствующего регистра невязок, выходкаждого одноразрядного сумматорачерез соответствующий регистр неизвестных соединен с своим вторымвходом,На Фиг.1 схематически представлено предлагаемое устройство; наФиг.2 - схема приоритетного блока;на фиг.3 - схема сдвигового регистра.Устройство содержит запоминающиеблоки 1 коэффициентов, сумматоры 2регистры 3 невязок, приоритетныйблок 4, одноразрядные сумматоры 5,регистры б неизвестных, сдвиговыерегистры 7, управляющий вход 8устройства, элемент ИЛИ 9, сдвиговыйрегистр 10, элементы И 11, регистр 12, шифратор 13, триггеры, 14, элементы И 15.Устройство работает следующим образом.В запоминающий блок 1 коэффициентов заносятся коды коэффициентовсоответствующих строк, в регистры бнеизвестных - нулевые начальные приближения неизвестных, а в регистры3 невязок - коды соответствующихсвободных членов решаемой системыуравнений. Содержимые всех сумматоров устанавливаются в нуль. На, выходах блока 4 образуются соответственно 1 офК, где К - разрядные коды111 и 000 (с - основание сис темы счисления).На нулевой итерации код соответствующего свободного члена с выходарегистра 3 невязки через сдвиговыйрегистр 7 без задержки (на его управ ляющий вход подан нулевой сигнал)поступает на вход сумматора 2 соответственно, на второй вход которогоничего не подается. В результатекоды свободных членов проходят через д сумматоры 2 без изменений, затем поступают в регистры невязок 3 соответственно и в блок 4. В этом блокепроисходит выделение старшего разряда наибольшего (по модулю) свободного члена. Код адреса полученногостаршего разряда устанавливается напервом выходе блока 4, а на второмвыходе - К-разрядный код этого старшего разряда. Полуненный таким образом код старшего разряда представляет собой величину приращения неизвестных, которая изменяется в зависимости от сигнала на управляющемвходе 8. Код адреса старшего разрядауправляет длительностью задержки с 40 помощью сдвиговых регистров 7 подачи кодов свободных членов из регистров 3 невязок в сумматоры 2.В первой интерации из запоминающих блоков 1 коэффициентов в сумма торы 2 поступают последовательно разряды (начиная с младших) кодов коэффициентов соответствующих строк.Через определенное количество тактов,определяемое кодом адреса значащейединицы величины, приращения неизвестных, в сумматоры 2 добавляются соответс(твенно разряды (начиная с младших) свободных членов. После проведения укаэанных операций на выходахсумматоров 2 появляются результаты, Б представляющие собой коды соответствующих невязок, которые поступают всоответствующий регистр 3 для хранения на время итерации и в приоритетный)блок 4, где из полученных кодов неб вязок выделяется самый старший раэряд, который представляет собой величину приращения неизвестных на следующей итерации. В этой же, первой, итерации одновременно с получением кодов невязок происходит вычислениеФормула изобретения 40 новых приближений неизвестных.Этовычисление заключается в следующем.На сумматоры 5 поступают коды предыдущего значения соответствующего неизвестного из регистров б неизвестных и приращение неизвестного иэблока 4, режимом работы сумматоров 5 (сложение или вычитание) управляюткоды, полученные с вторых входовсоответствующих регистров 3 (выходызнаковых разрядов),Все последующие итерации идентичны первой.Приоритетный блок 4 работает следующим образом. На входы элементаИЛИ 9 поступают разряды (начиная смладших) кодов соответствующих невязок, Элемент ИЛИ 9 определяет наличие соответствующей значащей единицы в одноименных разрядах кодов всехневязок, а сдвиговый регистр 10 Фильтрует эту информацию, Содержимоесдвигового регистра 10 сдвигается вкаждом такте на один разряд вправо(в сторону старших разрядов).За К тактов в сдвиговом регистре10 получается К - разрядное слово,значащий каждый разряд которого свидетельствует о наличии его в одноименном разряде хотя бы одной невяэки. Далее с помощью элементов И 11выделяется старший значащий разрядслова, хранимого в сдвиговом регистре 10. Элементы И 11 соединены так,что инверсный выход каждого, последующего за старшим, разряда разрешает прохождение единицы с прямоговыхода, например, )-го разряда сдвигового регистра 10 на вход регистра12, а все последующие за 1-ым элементом И 11 остаются закрытыми. Выделенный код старшей единицы, установленный в регистре 12, может быть из-менен в пределах - 9 "в зависимости от сигнала, поступающего на управляющий вход регистра 12 с входа 8.Код, установленный в регистре 12,представляет собой код приращениянеизвестных и подается через шифра"тор 13 на первый выход и без преобразований на второй выход блока 4.Код, поступивший на второй вход первого (Фиг.3) элемента-И 15 и вход триггера 14, задерживается в зависи-мости от кода на управляющем входесдвигового регистра 7, т,е. на пер.вых входах элементов И 15. Например,при коде на элементах И 15 101 (старший, правый, разряд подается на верхний элемент И 15) код, прошедшийчерез регистр 7,. задерживается надва разряда. Устройство для решения систем линейных уравнений, содержащее запоми,нающие блоки коэйфициентов, регист ры невязок, регистры неизвестных,одноразрядные сумматоры, о т л и ч а ю щ е е с я тем, что, с целью ,повышения быстродействия, в него введены сдвиговые регистры,сумматооы 2 О и приоритетный блок, управляющийвход которого является управляющим входом .устройства, первый вход каждого сумматора соединен с выходом соответствующего запоминающего блока коэффициентов, второй вход - подключен к выходусоответствующего сдвигового регистра, вход которого соединен с первым выходом регистра невязок, выход каждого сумматора соединен с входом соответствующего регистра невязок и с одним из входов приоритетного блока, первый выход которого подключен к управляющим входам сдвиговых регистров, второй выход приоритетного блока соединен с первыми вхоЗ 5 дами одноразрядных сумматоров, управляющий вход каждого из которых соеди,нен с вторым выходом соответствующего регистра невязок, выход каждого одноразрядного сумматора через соответствующий регистр неизвестных соединен; с своим вторым входом,Источники информации,принятые во внимание при экспертизе1. Майоров Ф. М. Электронные цифр ровые интегрирующие машины, М., Машгиз, 1962, с.86,2. Евреинов Е.В. и Прангишвили И.В.Цифровые автоматы с настраиваемойструктурой. М., "Энергия", 1974,с,195, Фиг.б. 7 (прототип).798862 ель А,Кер Ковале Состави едактор Л.Кеви Техреднова К С Некмар е Тираж. 756 ПодписиГосударственного комитета СССРделам изобретений и открытийосква, Ж, Раушская наб., д.4 акаг 10057/6 ВНИИП