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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Опубликовано 15.0 3.8 1.6 оллвтеиь 14х 10

Дата опубликования описания 15.03,81

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

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

Республик

<1 813446 (53)М. Кл з

G 06 F 15/324

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

СССР по делам изобретений и открытий (53) УД (681 325.5 (088.8) !

В.П.Боюн, Л.Г.Козлов, Б.Н.Малиновский и С.И (72) Авторы изобретения ретвн бэв.".; „:

ЕЛ „:; 1: "..; ".(й r ; кой Р 0;,д. 4

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

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

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

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

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

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

20 точке объединенных вторых входов множительных блоков соответствующих строк (2).

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

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

Цель изобретения — сокращение оборудования. 25

Поставленная цель достигается тем, что устройство для решения систем линейных уравнений, содержащее сумматор, запоминающий блок неизвестных, регистры, накапливающие суммато- о ры и запоминающие блоки коэффициентов, выход каждого из которых подключен к первому входу соответствующего накапливающего сумматора, второй вход которого соединен с первым 35 выходом соответствующего регистра, содержит блок выделения приращения неизвестных, блок управления сдвигом, коммутатор и блок формирования тактовых сигналов, выходы которого подключены соответственно к первому 4О и второму управляющим входам блоков выделения приращения неизвестных, блока управления сдвигом и к управляющему входу коммутатора, выход каждого накапливающего сумматора 45 подключен к входу соответствующего регистра и к соответствующему информационному входу блока выделения приращения неизвестных, Выход которого подключен к первому входу сум- 5О матора и к входу блока управления сдвигом, первый выход которого соединен с входом блока формирования тактовых сигналов, второй выход блока фправления сдВиГОм пОдключен к 55 первым управляющим входам накапливающих сумматоров, вторые управляющИе входы которых соединены с выходом коммутатора, второй выход каждого регистра соединен с соответствующим входом каммутатора выход которога подключен к управляющему входу сумматора второй вход которого соединен с вйходом запоминающего блока неизвестных, вход которого подключен к выходу сумматора.

Кроме того, в устройстве блок выделения приращения неизвестных содержит регистр, две группы элементов И, элементы НЕ и группу элементов ИЛИ, входы которых соединены с информационными входами блока, выход каждого элемента ИЛИ, кроме последнего, подключен к первому входу соответствующего элемента И первой группы и через элемент HE к первому входу соответствующего элемента И второй группы, вторые входы первых элементов И первой и второй групп соединены с первым управляющим входом блока, выходы элементов И первой группы подключены соответственно к входам регистра, выход которого является выходом блока, выход каждого элемента И второй группы подключен к вторым входам последующих элементов И первой и второй групп, выход последнего элемента

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

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

СДВИГОМ.

Устройство содержит запоминающие блоки 1 коэффициентов, накапливающие сумматоры 2, регистры 3, блок 4 выделения приращения неизвестных, блок

5 управления сдвигом, коммутатор 6, сумматор 7, запоминающий блок 8 неизвестных, блок 9 формирования тактовых сигналов, группа элементов

ИЛИ 10, элементы НЕ 11, группы элементов И 12, 13, регистр 14, шифратор 15, счетчик 16, триггер 17, элемент И 18.

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

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

813446 итерации решения системы уравнений в накапливающие сумматоры 2 поступают соответственно коды свободных коэффициентов, хранящиеся в регистрах 3. Далее коды свободных членов из накапливающих сумматоров 2 подаются на входы регистров 3 соответственно, где запоминаются,и на соответствующие входы блока 4 выделения приращения неизвестных. В этом блоке происходит выделение старшего разряда наибольшего по модулю свобод- 10 ного члена. Далее с выхода блока 4 выделения приращения неизвестных полученный код приращения неизвестного поступает на вход блока 5 управления сдвигом, где преобразует-, 15 ся в другой код, который управляет сдвигом содержимого накапливающих сумматоров 2 на.число разрядов, равное весу значащей единицы кода прира; щения неизвестного, а также поступа- 30 ет на вход сумматора 7.

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

2 определяется сигналом на их управ- ЗО ляющем входе. Этот сигнал представляет собой код знака соответствующего свободного члена (в последующих итерациях — соответствующей невязки) и поступает с выхода коммутатора 6, который в каждом такте итерации осуществляет последовательную коммутацию выходов знаковых разрядов регистров

3 с помощью сигнала, поступающего на его управляющий вход от блока 9 °

В каждой итерации в соответствую- 40 щем такте производится операция суммирования или вычитания в сумматоре

7 (в зависимости от сигнала на управляющем входе), полученного значения . приращения неизвестного в блоке 4 4 выделения приращения неизвестных с его предыдущим значением, которое хранится в запоминающем блоке 8 неизвестных. Затем на место предыдущего записывается нсвое значение $O неизвестного.

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

Затем к содержимым накапливающих сумматоров 2 прибавляются коды свободных членов (в последующих итера циях — коды невязок) соответственно. Щ

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

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

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

На входи соответствующих элементов ИЛИ 10 поступают одноименные разряды всех кодов невязок, а на выходах элементов ИЛИ получается сигнал (ноль или единица}, который свидетельствует об отсутствии или наличии данного разряда во всех кодах невязок. Полученное слово подается на входы элементов И 13 и через элементы НЕ 11 на входы элементов И 12 соответственно. Схема на элементах ИЕ и И представляет собой приоритетную цепь, которая при наличии сигнала на управляющем входе блока 4 выделения приращения неизвестных выделяет старший разряд входного слова, который устанавливается в регистре 14 на время следующей итерации. Так, например, входное слово 00110101 приоритетная цепь преобразует в слово

00100000. Хранимый в регистре 14 код и представляет собой величину приращения неизвестного.

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

На вход шифратора 15 поступает . код приращения неизвестного, который шифрируется и в обратном коде заносится в счетчик Iб. При этом сигнал -иа первом управляющем входе блока 5 управления сдвигом устанавливает триггер 17 в состояние, открывающее элемент И 18, и через него иа выход блока 5 управления сдвигом проходят тактирующие импульсы, которые поступают от блока 9 на второй управляющий вход блока 5, Сигнал переполнения счетчика 16 сбрасывает триггер 17 в противоположное состояние и подача тактирующих импульсов на выход блока 5 прекращается. Таким образом, с помощью блока 5 управления сдвигом получают серию импульсов, необходимых для сдвига содержимых накапливающих сумматоров 2. Причем количество этих импульсов равно весу значащей единицы в коде приращения неизвестного, Замена операции полнораэрядного (к — разрядного) умножения на одноразрядную, позволяет сократить аппаратурные затраты.

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

Устройство для решения систем линейных уравнений, содержащее сумматор, запоминающий блок неиэвест813446

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

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

2. Евреинов Э.В., Праншвили И.В. цифровые автоматы с настраиваемой стру ур й, М., Энергия, 1974, P ° 195> Фиг.6-7 (прототип). ных, регистры, накапливающие сумматоры и запоминающие блоки коэффициентов, выход каждого из которых подключен к первому входу соответствующего накапливающего сумматора, второй вход которого соединен с первым выходом соответствующего регистра, о т л и ч а ю щ е е с я тем, что, с целью сокращения оборудования, оно содержит блок выделения приращения неизвестных, блок управления сдвигом, коммутатор и блок формирования тактовых сигналов, выходы которого подключены соответственно к первому и второму управляющим входам блока выделения приращения неизвестных, блока управления 13 сдвигом и к управляющему входу коммутатора, выход каждого накапливающего сумматора подключен к входу со= ответствующего регистра и к соответствующему информационному входу 20 блока выделения приращения неизвестных, выход которого подключен к пер- вому входу сумматора и к входу блока управления, сдвигом, первый выход которого соединен с входом блока фор- мирования тактовых сигналов, второй выход блока управления сдвигом подключен к первым .управляющим входам накапливающих сумматоров, вторые управляющие входы которых соединены с выходом коммутатора, второй выход каждого регистра соединен с соответствующим входом коммутатора, выход которого подключен к управляющему входу сумматора, второй вход которого соединен с выходом запоминающе- M го блока неизвестных, вход которого подключен к выходу сумматора.

2. Устройство по п.l, о т л и ч а ю щ е е с я тем, что блок виделения приращения неизвестных содер- 4Q жит регистр, две группы элементов

И, элементы НЕ и группу элементов

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

И второй группы, вторые входы первых элементов И первой и второй групп соединены с первым управляющим входом блока, выходы элементов И первой группы подключены соответственно к входам регистра, выход которого является выходом блока, выход каждого элемента И второй группы подключен к вторым входам последующих элементов И первой и второй групп, выход последнего элемента ИЛИ соединен с первым входом последнего элемента

И первой группы, управляющий вход регистра является вторым управляющим входом блока.

3. Устройство по п.l, о т л и ч а ю щ е е с я тем, что блок управления сдвигом содержит элемент

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

813446

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

Редактор И. Касарда Техред Л. Пекарь Корректор E,Ðîøêo

Заказ 775/б3 Тираж 745 Под пи сное

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

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

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