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

 

) ) я, .; т ° « с к Вй

° °

4 ос 4 -.: + А

Союз Сеюетских

Социалистических

Респубаик

ОП САНИЕ

ИЗОБРЕТЕНИЯ

oi)798862

К АВТОУСКОММ СВИ ВТВЛЬСТВУ (61) Дополыительиое к авт. свид-ву— (22) Заявлено 05. 12. 78 (21) 2691586/18-24 с присоединением заявки М— (23) Приоритет

Опубликовано230181. Б оллетеиь 3

Дата опубликования описания 2301.81 (5!)М. Кл.з

G 06 F 15/324

Государственный комнтет

СССР по делам нзобретеннй н открытнй

М) УДК 681. 325. 5 (088.8) (72) Авторы изобретения

В.П.Боюн, Л.Г.Козлов, Б.Н.Малиновский и С.И.Третьяков

Ордена Ленина институт кибернетики AH Украинской CCP (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

ЛИНЕЙНЫХ УРАВНЕНИЙ

Изобретение относится к вычислительной технике и может быть применено при построении устройств для решения систем линейных алгебраических уравнений.

Известно цифровое устройство для решения систем уравнений, построенное на базе интегратора, содержащее интеграторы коэффициентов, интеграторы свободных членов и интеграторы неизвестных, причем выходы интеграторов коэффициентов каждого столбца соединены с выходами интеграторов свободного члена тога же столбца, выходы которых подключены ко входам интеграторов неизвестных того же столбца и входам интеграторов коэффициентов соответствующих строк f1).

Недостатками данного устройства являются большое количество оборудования, низкое быстродействие, трудность определения конца решения.

Наиболее близким по технической сущности к предлагаемому .является устройство для решения систем линейных алгебраических уравнений, которое содержит регистры свободных членов, запоминающий блок коэффициентов, сумматоры, множительные блоки, регистры неизвестных схемы при- Ж ема, выходы регистров свободных членов соединены с первыми входами первых сумматоров соответствующих строк из сумматоров, к вторым входам которых подключены выходы множительных блоков соответственно, сумматоры соединены последовательно, причем выходы последних и-ых сумматоров подсоединены к входам схем приема соответственно, выходы которых подключены к соответствующим входам регистров неизвестных, выходы которых соединены с общей точкой объединенных первых входов соответствующих множительных блоков каждой строки из множительных блоков, выходы запоминающих блоков коэффициентов подсоединены к, общей точке объединенных вторых входов множительных блоков соответствующих строк $2j.

Работа устройства заключается в следующем. С выходов запоминающих блоков на входы множительных блоков соответствующих строк поступают значения коэффициентов параллельным кодом, а с выходов регистров неизвестных в соответствующем такте и на входы соответствующих множительных блоков каждой строки подаются последовательно (начиная с младших) 798862 разряды неизвестных. полученные разряды произведений коэффициентов на неизвестные в соответствующем такте суммируются между собой и с кодом свободного члена на последонательном сумматоре, состоящем из и сумматоров.

Результаты выполненных операций (код невязки) передаются в схему приема, которая преобразует поступивший код ненязки в код неизвестного (например, ныделяется часть величины невязки). Полученное таким образом новое приближение неизвестного будет использовано н следующей итерации.

Данное устройство имеет существенный недостаток — низкое быстродействие. Это объясняется тем, что код невязки проходит столбец из и одноразрядных сумматоров, а при достаточно большом порядке п решаемой системй уравнений. время решения может быть недопустимо большим.

Цель изобретения — повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство для решения систем линейных уравнений, содержащее запоминающие блоки коэффициентов, регистры невязок, регистры неизвестных, одноразрядные сумматоры, введены сдниговые регистры, сумматоры и приоритетный блок, управляющий вход которого является управляющим входом устройства, первый вход кажпого сумматора соединен с выходом соответствующего запоминающего блока коэфФициентов, второй вход — подключен к выходу соответствующего сдвигоного регистра, вход которого соединен с первым выходом регистра невязок, выход каждого сумматора соединен с входом соответствующего регистра невязок и с одним из входов приоритетного блока, первый выход которого подключен к управляющим входам сдвиговых регистров, второй выход приоритетного блока соедйнен с первыми входами одноразрядных сумматоров, управляющий вход каждого из которых соединен с вторым выходом соответствующего регистра невязок, выход каждого одноразрядного сумматора через соответствующий регистр неизвестных соединен с своим нторым входом

На фиг.1 схематически представлено предлагаемое устройство; на фиг.2 — схема приоритетного блока; на фиг.3 — схема сдвигового регистра.

Устройство содержит запоминающие блоки 1 коэффициентов, сумматоры 2 регистры 3 невязок, приоритетный блок 4, одноразрядные сумматоры 5, регистры 6 неизвестных, сдвигоные регистры 7, управляющий вход 8 устройства, элемент ИЛИ 9, сдвиговый регистр 10, элементы И 11, регистр

12, шифратор 13, триггеры, 14, элементы И 15.

Устройство работает следующим образом.

В запоминающий блок 1 коэффициентов заносятся коды коэффициентов соответствующих строк, в регистры 6 неизвестных — нуленые начальные приближения неизвестных, а в регистры

3 невязок — коды соответствующих свободных членов решаемой системы уравнений. Содержимые всех сумматоров устананливаются в нуль. На, выходах блока 4 образуются соответственно 1оф К, где К - разрядные коды

11...1 и 00...0 (q — основание сис15 темы счисления).

На нулевой итерации код соответствующего свободного члена с ныхода регистра 3 невязки через сдвиговый регистр 7 без задержки {на его управЩ ляющий вход подан нулевой сигнал) поступает на вход сумматора 2 соответственно, на второй вход которого ничего не подается. В результате коды свободных членов проходят через д сУмматоры 2 без изменений, затем поступают в регистры невязок 3 соответственно и в блок 4. В этом блоке происходит выделение старшего разряда наибольшего (по модулю) свободного члена. Код адреса полученного старшего разряда устанавлИвается на первом выходе блока 4, а на втором выходе — К-разрядный код этого старшего разряда. Полуненный таким образом код старшего разряда представляет собой величину приращения неизвестных, которая изменяется н зависимости от сигнала на управляющем входе 8. Код адреса старшего разряда управляет длительностью задержки с

40 помощью сдвиговых регистров 7 подачи кодов свободных членов из регистров 3 ненязок в сумматоры 2.

В первой интерации из запоминающих блоков 1 коэффициентов в сумма4 торы 2 поступают последовательно разряды (начиная с младших) кодов коэффициентов соответствующих строк.

Через определенное количество тактов, определяемое кодом адреса значащей единицы величины. приращения неизвестных, в сумматоры 2 добавляются соответг(твенно разряды (начиная с младших) свободных членов. После проведения укаэанных операций на выходах сумматоров 2 появляются результаты, представляющие собой коды соответствующих невязок, которые поступают в соответствующий регистр 3 для хранения на время итерации и в приоритетный) блок 4, где из полученных кодов невязок выделяется самый старший pasряд, который представляет собой величину приращения неизвестных на следующей итерации. В этой же, первой, итерации одновременно с получением кодов ненязок происходит вычисление

798862 новых приближений неизвестных.Это вычисление заключается в следующем.

На сумматоры 5 поступают коды преды дущего значения соответствующего неизвестного из регистров б неизвестных и приращение неизвестного иэ

1 .-блока 4. режимом работы сумматоров5 (сложение или вычитание) управляют коды, полученные с вторых входов соответствующих регистров 3 (выходы знаковых разрядов).

Все последующие итерации идентичны первой.

Приоритетный блок 4 работает следующим образом. На входы элемента

ИЛИ 9 поступают разряды (начиная с младших) кодов соответствующих невязок. Элемент ИЛИ 9 определяет наличие соответствующей значащей единицы в одноименных разрядах кодов всех невязок, а сдвигоный регистр 10 фильтрует эту информацию, Содержимое сдвигового регистра 10 сдвигается н каждом такте на один разряд вправо (в сторону старших разрядов).

За К тактов н сдвигоном регистре

10 получается К вЂ” разрядное слово, значащий каждый разряд которого свидетельствует о наличии его в одноименном разряде хотя бы одной невяэки. Далее с помощью элементов И 11 выделяется старший значащий разряд слова, хранимого в сдниговом регистре 10. Элементы И 11 соединены так, что инверсный выход каждого, последующего за старшим, разряда разрешает прохождение единицы с прямого выхода, например, i-го разряда сдвигового регистра 10 на вход регистра

12, а все последующие за 1-ым элементом И 11 остаются закрытыми. Выделенный код старшей единицы, установленный в регистре 12, может быть из- менен в пределах 0 - 9 "н зависимости от сигнала, поступающего на управляющий вход регистра 12 с входа 8.

Код, установленный в регистре 12, представляет собой код приращения неизвестных и подается через шифратор 13 на первый выход и без преобразований на второй выход блока 4.

Код, поступивший на второй нход первого (фиг.3) элемента-И 15 и вход триггера 14, задерживается в заниси- мости от кода на управляющем входе сднигового регистра 7, т.е. на пер.вых входах элементов И 15. Например, при коде на элементах И 15 101 (старший, правый, разряд подается íà верхний элемент И 15) код, прошедший через регистр 7,. задерживается на дна разряда.

Формула изобретения регистра невязок, выход каждого одноразрядного сумматора через соотнетст40 вующий регистр неизвестных соединен; с своим вторым входом.

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

1. Майоров Ф. N. Электронные цифр роные интегрирующие машины. М., Машгиз, 1962, с.86.

2. Евреинов E.Â. и Прангишвили И.В.

1Цифровые автоматы с настраиваемой структурой. М., "Энергия", 1974, с.195, фиг.б. 7 (прототип).

Устройство для решения систем линейных уравнений, содержащее запоми.нающие блоки коэффициентов, регист15 ры невязок, регистры неизвестных, одноразрядные сумматоры, о т л и ч а ю щ е е с я тем, что, с целью, повышения быстродействия, в него введены сднигоные регистры,сумматооы

2О и приоритетный блок, управляющий вход которого является управляющим входом .устройства, первый вход каждого сумматора соединен с выходом соответствующего запоминающего блока коэффициентов, второй вход - подключен к выходу соответствующего сдвигового регистра, нход которого соединен с первым выходом регистра невязок, выход каждого сумматора соединен с входом соответствующего регистра ненязок и с одним из входов приоритетного блока, первый выход которого подключен к управляющим входам сдвиговых регистров, второй выход приоритетного блока соединен с первыми Вхо35 дами одноразрядных сумматоров, управляющий вход каждого из которых соеди;нен с вторым выходом соответствующего

798862

Составитель A. .Êåðåíîâ

Редактор Л.Кеви Техред Н. Ковалева Корректор . С.Некмар

Зака" 10057/68 Тираж 756 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5 .Филиал ППП "Патент", r.Óæãîðîä, ул.Проектная,4