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

1

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

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

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

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

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

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

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

0 ко вторым входам соответствующих суммирующих блоков, выход сумматора подключен ко входу блока памяти неизвестных, выход которого соединек с первым входом сумматора, содержит шифраторы приращений неизвестных, коммутатор и выходной дешифратор, выходы суммирующих блоков подключены к входам соответствующих регистров невязок и шифраторов приращений неизвестных, выходы которых соединены с со.ответствующими входами коммутатора, выход которого подсоединен к третьим входам суммирующих блоков и ко входу выходного дешифратора, выход которого подключен ко второму входу сумматора. . На фиг. 1 представлена блок-схема устройства; на фиг. 2 - схема суммирующего .блока; на фиг. 3 - схе ма Шифратора приращений неизвестных Устройство состоит из блоков 1 памяти коэффициентов, суммирующих блоков 2, шифраторов 3 приращений неизвестных, регистров 4 невязок, коммутатора 5, выходного дешифратора б, сумматора 7 и блока 8 памяти неизвестных. Суммирующий блок 2 сос тоит из к мультиплексоров 9, где к - разрядность кодов,, к-разрядных сумматора 10 и регистра 11, двух элементов И 12 и элемента ИЛИ 13. Шифратор приращений неизвестных 3 состоит из {к-2)-х элементов НЕ 14 (2к-4)-х элементов И 15, шифрирующего узла 16, к-разрядного регистра 17. Устройство работает следующим образом. В i-ый блок 1 памяти коэффициентов заносятся коды коэффициентов i-ой строки решаемой системы L -iV х;-,- . В регис уравнений я 4 невязок заносятся соответствен ры но коды свободных членов в, содержимые суммирующих блоков 2 устанавливаются в ноль, и в блок 8 памяти неизвестных заносятся начальные приближения неизвестных. На нулевом такте решения системы уравнений в суммирующие блоки 2 поступают соответственно коды свободных коэффициентов, хранящиеся в регистрах 4 невязок. Далее коды свободных членов из суммирующих блоков 2 поступают на входы регистров 4 невязок, где запоминаются, и на входы шифраторов 3. В этих шифраторах происходит выделение старших разрядов невязок, представляющих собой приращения соответствующих неизвестных, шифрируются в соответствующем шифра торе 3 и через коммутатор 5 поступают на вход дешифратора б и на все управляющие входы суммирующих блоков 2, т.е. шифратор 3 выполняет арифметическую операцию: ( - невязка) . Дешифратор б преоб разует поступивший свернутый код приращения неизвестного в полнораз рядную величину (старший разряд соответствующей невязки), которая затем суммируется в сумматоре 7 с предыдущим значением соответствующего неизвестного, хранимым в блоке 8, и записывается опять на то же место в блок 8. Код приращения неизвестного, поступивший на управляю щие входы суммирующих блоков 2, Р соответствующем такте сдв гом коэффициентов. На следующем первом такте с выходов блоков 1 на первые входы соответствующих суммирующих блоков 2 поступают первые коэффициенты соответствующих строк. Далее содержимые суммирующих блоков 2 сдвигаются на количество разрядов , определяемое кодом на их управляющем входе. Тем car«jM осуществляется операция: а дх( , (р - номер итерации). Далее за п тактов в сумматорах образуется величина а . . На следующем (п+1)-ом такте к полученной сумме добавляется соответственно код свободного члена. Полученный результат-, невязка уравнения поступает в регистр 4 невязок, где запоминается на время следующей итерации, и на вход шифратора 3 соответственно. Таким образом, для решения системы уравнения А - можно привести следующий алгоритм работы устройства:x.(pti; х .Р + , i 1, 2, ,,., п, .(р+) . уДР) у (Р) - S дх,(Р-Ь гпри начальных условиях: „ (о .. . у .(р) . 1 -10 --01. Работа суммирующего блока 2 заключается в том, что на первые входы всех мультиплексоров 9 поступают соответственно разряды кода коэффициента, причем i-ые входы i-х мультиплексоров 9 объединены, т.е. структурно определяется сдвиг на один разряд. В зависимости от кода на управляющих входах мультиплексоров 9 подключается на выход соответствующий вход. Таким образом, за один такт можно сдвинуть код на к разрядов. Далее код с выходов мультиплексоров 9 поступает на первый вход сумматора 10, где суммируется с другой величиной, поступающей на второй вход сумматора 10 через элементы И 12 и ИЛИ 13 и хранимой в регистре 11. В зависимости от сигналов на управляющих входах элементов И 12 на второй вход сумматора 10 Подключается второй вход суммирующего блока 2, на который подается код невязки из регистра невязки 4, Работа шифратора 3 заключается в следующем. С помощью элементов НЕ 14 и 15 собрана схема, которая работает как приоритетная цепочка, т.е. при появлении старшей (левой) значащей единицы прохождение остальных разрядов на вход узла 16 запрещено. Преобразованный с помощью узла 16 код записывается в регистр 17, где хранится в течение итерации.

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

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

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

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

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

5

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

2.Евреинов Э.В. и Прангишви-..

ли И,В. Цифровые автоматы с настраи0ваемой структурой. М,, Энергия, 1974, с. 195 (прототип).