Устройство для решения системлиНЕйНыХ уРАВНЕНий Советский патент 1981 года по МПК G06F17/12 

1

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

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

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

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

ема, выходы регистров свободных членов соединены с первыми входами первых сумматоров соответствующих строк из сумматоров, к вторым входам которых подключены выходы множительных блоков соответственно, сумматоры соединены последовательно, причем :выходы последних п-ых сумматоров подсоединены к входам схем приема

0 соответственно, выходы которых подключены к соответствующим входам регистров неизвестных, выходы которых соединены с общей точкой объединенных первых входов соответствующих

5 множительных блоков каждой строки из множительных блоков, выходы запоминающих блоков коэффициентов подсоединены к, общей точке объединенных вторых входов множительных блоков

соответствукядих строк 2 .

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

Q последовательно (начиная с младших)

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

(код невязки) передаются в схему приема,которая преобразует поступивший код невязки в код неизвестного

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

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

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

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

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

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

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

В запоминающий блок 1 коэффициентов заносятся коды коэффициентов соответствующих строк, в регистры 6 неизвестных - нулевые начальные приближения неизвестных, а в регистры 3 невязок - коды соответствующих свободных членов решаемой системы уравнений. Содержимые всех сумматоров устанавливаются в нуль. На, выходах блока 4 образуются соответственно 609-q. К , где К - разрядные коды 11...1 и 00...О (q - основание системы счисления).

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

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

ОВЫХ приближений неизвестных. Это

ычисление заключается в следующем. а сумматоры 5 поступают коды предыущего значения соответствующего незвестного из регистров 6 неизвестых и приращение неизвестного из

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

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

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

За К тактов в сдвиговом регистре 10 получается К - разрядное слово, значащий каждый разряд которого свидетельствует о наличии его в одноименном разряде хотя бы одной невязки. Далее с помощью элементов И 11 выделяется старший значащий разряд слова, хранимого в сдвиговом регистре 10. Элементы И 11 соединены так, что инверсный выход каждого, последующего за старшим, разряда разрешает прохождение единицы с прямого выхода, например, i-го разряда сдвигового регистра 10 на вход регистра 12, а все последующие за I-ьш элементом И 11 остаются закрытыми. Вьщеленный код старшей единицы, ус;тановленный в регистре 12, может быть из-менен в пределах зависимости от сигнала, поступающего на управляющий вход регистра 12 с входа 8. Код, установленный в регистре 12, представляет собой код приращения. неизвестных и подается через шифратор 13 на первый выход и без преобразований на второй выход блока 4. Код, поступивший на второй вход первого (фиг.З) элемента-И 15 и вход

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

Формула изобретения

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

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

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

I 2. Евреинов Е.В. и Прангишвили И.В. {Цифровые автоматы с настраиваемой структурой. М., Энергия, 1974, с.195, фиг.6. 7 (прототип).

J

«.1

фи&Ъ