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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

s asmemoaav cs ggmasnsv

Сююь Советских

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

Республнк (61) Дополнительное к авт. свид-ву— (22) Заявлено 050б79 (21) 27749б 5/18-24 с присоединением заявки Нов (23) Приоритет—

Опубликовано 15.0581.бюллетень ЙЯ 18

Дата опубликования описания 150581 (51}М, Кд.

G Об F 15/324

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

СССР по дедам изобретений и открытий (53}УД (881.Ç2Ç (088.8) (72) Авторы изобретения

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

Ь

ПЛ"-;-,:;;Д«

Ордена Ленина институт кибернетики A Украина сдй.. GCP ;.е: с ., (71) За яв итель

I (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

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

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

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

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

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

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

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

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

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

20 ко вторым входам соответствующих суммирующих блоков, выход сумматора подключен ко входу блока памяти неизвестных, выход которого соединен с первым входом сумматора, содержит шифраторы приращений неизвестных, коммутатор и выходной дешифратор, выходы суммирующих блоков подключены к входам соответствующих регистров невязок и шифраторов при30 ращений неизвестных, выходы которых

830396

15

20 соединены с соответствующими входами коммутатора, выход которого подсоединен к третьим входам суммирующих блоков и ко входу выходного дешифратора, выход которого подключен ко второму входу сумматора.

На фиг. 1 представлена блок-схема устройства, на фиг. 2 — схема суммирующего блока; на фиг. 3 — схема Шифратора приращений неизвестных.

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

Шифратор приращений неизвестных 3 состоит из (к-2)-х элементов HE 14, (2к-4)-х элементов И 15, шифрирующего узла 16, к-разрядного регистра 17.

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

В i-ый блок 1 памяти коэффициентов заносятся коды коэффициентов а„ i-ой строки решаемой системы и уравнений r. а . - х - = в . В регист1- j3 ры 4 невязок заносятся соответственно коды свободных членов в„, содержимые суммирующих блоков 2 устанавливаются в ноль, и в блок 8 памяти неизвестных заносятся начальные приближения неизвестных. На нулевом такте решения системы уравнений в суммирующие блоки 2 поступают соответственно коды свободных коэффициентов, хранящиеся в регистрах 4 невязок. Далее коды свободных членов из суммирующих блоков 2 поступают на входы регистров 4 невязок, где запоминаются, и на входы шифраторов 3. В этих шифраторах происходит выделение старших разрядов невязок, представляющих собой приращения соответствующих неизвестных, шифрируются в соответствующем шифраторе 3 и через коммутатор 5 поступают на вход дешифратора 6 и на все управляющие входы суммирующих блоков 2, т.е. шифратор 3 выполняет арифметическую операцию: 2 (У„. — невязка). Дешифратор 6 преобразует постуПивший свернутый код приращения неизвестного в полноразрядную величину (старший разряд соответствующей невязки), которая затем суммируется в сумматоре 7 с предыдущим значением соответствующего неизвестного, хранимым в блоке

8, и записывается опять на то же место в блок 8. Код приращения не-. известного, поступивший на управляющие входы суммирующих блоков 2, упрачляе " соответствующем такте сдви3G

55 гом коэффициентов. На следующем первом такте с выходов блоков 1 на первые входы соответствующих суммирующих блоков 2 поступают первые коэффициенты соответствующих строк.

Далее содержимые суммирующих блоков

2 сдвигаются на количество разрядов, определяемое кодом на их управляющем входе. Тем самым осуществляется операция: а„„ь х., (+"), (р — номер итерации). Далее за и тактов в сумматорах образуется величина а" ° х-(Р " . На следующем (nij)-ом такте к полученной сумме добавляется соответственно код свободного члена. Полученный результатневязка уравнения — поступает в регистр 4 невязок, где запоминается на время следующей итерации, и на вход шифратора 3 соответственно.

Таким образом, для решения системы уравнения A х = 8 можно -привести следующий алгоритм работы устройства: х.(Pt<) = х(.Р + x (Р ")

1 1 1

1 — 1, 2, ..., n, ьх (Р+"> = 2en+tjoq

1 1, 1 ) / -1 при начальных условиях: х(= х У = bi.

Работа суммирующего блока 2 заключается в том, что на первые входы всех мультиплексоров 9 поступают соответственно разряды кода коэффициента, причем i-ые входы i-x мультиплексоров 9 объединены, т.е. структурно определяется сдвиг на один разряд. В зависимости от кода на управляющих входах мультиплексоров

9 подключается на выход соответствующий вход. Таким образом, за один такт можно сдвинуть код на к разрядов. Далее код с выходов мультиплексоров 9 поступает на первый вход сумматора 10, где суммируется с другой величиной, поступающей на второй вход сумматора 10 через элементы И 12 и ИЛИ 13 и хранимой в регистре 11. В зависимости от сигналов на управляющих входах элементов

И 12 на второй вход сумматора 10 подключается второй вход суммирующего блока 2, на который подается код невязки из регистра невязки 4.

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

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

830396

Изобретение позволяет значительно сократить оборудование (при и = 100, 20) примерно в 3 раза и повысить быстродействие.

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

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

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

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

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

830396

P иг. )

Составитель Н. Палеева

Техред М. Коштура Корректор М. Демчик

Редактор Л. Повхан

Заказ 3350/55 Тираж 745 Подписное

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

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ППП "Патент", r. Ужгород. ул. Проектная, 4