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

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(22) Заявлено 051278 (21) 2691525/18-24с присоединением заявки Ио(23) Приоритет -Опубликовано 15,0 3.8 1,Бюллвтеиь 89 10Дата опубликования описания 1503,81 Союз Советских Социалистических Республик(51)М. Кл 3 6 06 Р 15/324 Государственный комитет СССР по дедам изобретений и открытий).:.";:( В:т; кой Рс 1 ., Ордена Ленина институт кибернетики АН Украи(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ Изобретение относится к вычислительной технике и может быть применено при построении устройств для решения систем линейных алгебраичес ких уравнений.Известно цифровое устройство для решения систем уравнений, построенное на базе интеграторов, содержащее интеграторы коэффициентов, интеграторы свободных членов и интеграторы неизвестных, причем выходы интеграторов коэффициентов каждого столбца соединены с выходами интеграторов свободного члена того же столбца, выходы которых подключены ко входам интеграторов неизвестных того же столбца и входам интеграторов коэффициентов соответствующих строк 1).Недостатки этого устройства - большое ,количество оборудования, низкое быстродействие, трудность определения конца решения.Наиболее близким по технической сущности и достигаемому результату к предлагаемому является устройство для решения систем линейных алгебраических уравнений, которое содержит регистры свободных членов, запоминающий блок коэффициентов, сумматоры, множительные блоки и регистрынеизвестных, схемы приема, выходырегистров свободных членов соединеныс первыми входами первых сумматоровсоответствующих строк из сумматоров,ко вторым входам которых подключенывыходы множительных блоков соответственно, сумматоры соединены последовательно, причем выходы последнихи-ых сумматоров подсоединены соответственно ко входам схем приема, выходы которых подключены к соответствующим входам регистров неизвестных, выходы которых соединены с об 15 щей точКой объединенных первых входов соответствующих множительныхблоков каждой строки из множительныхблоков, выходы запоминающих блоковкоэффициентов подсоединены к общей20 точке объединенных вторых входовмножительных блоков соответствующихстрок (2,В этом устройстве с выходов запоминающих блоков на входы множительных блоков соответствующих строкпоступают значения коэффициентовпараллельным кодом, а с выходов регистров неизвестных в соответствующем такте и на входы соответствую 30 щих множительных блоков каждой стро 813446ки подаются последовательно, начиная с младших, разряды неизвестных. Полученные разряды произведений коэффициейтов на неизвестные в соответствующем такте суммируются между собой и с кадом свободного члена на последовательном сумматоре, состоящем из и сумматоров. Результат выполненных операций (код невязки) передается в схему приема, которая преобразует поступивший код невязки в код неизвестного (например, выделяется часть величины невязки), Полученное таким образом новое приближение неизвестного используется в следующей итерации.Недостаток этого устройства - 15 большое количество оборудования, которое заключается в основном в и строках из сумматоров и в и строках.из и множительных блоков, причем каждый из последних, в свою очередь, 20 содержит к - разрядный сумматор и к разрядный регистр. Цель изобретения - сокращение обоРудования, 25Поставленная цель достигается тем, что устройство для решения систем линейных уравнений, содержащее сумматор, запоминающий блок неизвестных, регистры, накапливающие суммато-о ры и запоминающие блоки коэффициентов, выход каждого из которых подключен к первому входу соответствующего накапливающего сумматора, второй вход которого соединен с первым выходом соответствующего регистра, содержит блок выделения приращения неизвестных, блок управления сдвигом, коммутатор и блок формирования тактовых сигналов, выходы которого подключены соответственно к первому 4 О и второму управляющим входам блоков выделения приращения неизвестных, блока управления сдвигом и к управляющему входу коммутатора, выход каждого накапливающего сумматора 45 подключен к входу соответствующего регистра и к соответствующему ин" формационному входу блока выделения приращения неизвестных, Выход которого подключен к первому входу сум матора и к входу блока управления сдвигом, первый выход которого соединен с входом блока формирования тактовых сигналов, второй выход блокаууправления сдВигом подключен к55 первым управляющим входам накапливающих сумматоров, вторые управляющие входы которых соединены с выходом коммутатора, второй выход каждого регистра соединен с соответстВующим входом коммутатора выход ко торого подключен к управляющему входу сумматоравторой вход которого соединен с вйходом запоминающего блока неизвестных, вход которого подключен к выходу сумматора.65 Кроме того, в устройстве блоквыделения приращения неизвестныхсодержит регистр, две группы элементов И, элементы НЕ и группу элементов ИЛИ, входы которых соединеныс информационными входами блока, выход каждого элемента ИЛИ, кроме последнего, подключен к первому входусоответствующего элемента И первойгруппы и через элемент НЕ к первомувходу соответствующего элемента Ивторой группы, вторые входы первыхэлементов И первой и второй группсоединены с первым управляющим входом блока, выходы элементов И первой группы подключены соответственно к входам регистра, выход которого является выходом блока, выход каждого элемента И второй группы подключен к вторым входам последующих элементов И первой и второйгрупп, выход последнего элементаИЛИ соединен с первым входом последнего элемента И первой группы, управляющий вход регистра являетсявторым управляющим входом блока, аблок управления сдвигом содержитэлемент И, триггер, счетчик и шифратор, вход которого является входом блока, выход шифратора соединенс входом счетчика, выход которогосоединен с первым входом триггераи с первым выходом блока, второйвход триггера подключен к первомууправляющему входу блока, второйуправляющий вход которого соединенс управляющим входом счетчика и спервым входом элемента И, второйвход которого подключен к выходутриггера, выход элемента И является вторым выходом блока.На фиг.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 устанавливаются в ноль. В нулевойитерации решения системы уравненийв накапливающие сумматоры 2 поступают соответственно коды свободныхкоэффициентов, хранящиеся в регистрах 3. Далее коды свободных членовиз накапливающих сумматоров 2 подаются на входы регистров 3 соответственно, где запоминаются,и на соответствующие входы блока 4 выделенияприращения неизвестных. В этом блоке происходит выделение старшегоразряда наибольшего по модулю свобод Оного члена. Далее с выхода блока 4выделения приращения неизвестных полученный код приращения неизвестного поступает на вход блока 5 управления сдвигом, где преобразует-, 35 ся в другой код, который управляет сдвигом содержимого накапливающих сумматоров 2 на число разрядов, равное весу значащей единицы кода прира; щения неизвестного, а также поступа ет на вход сумматора 7.В следующей первой итерации решения системы уравнений с выходов запоминающих блоков 1 коэффициентов в накапливающие сумматоры 2 поступа ют в каждом такте коэффициенты соответствующей строки системы уравнений, причем режим работы (сложение или вычитание) накапливающих сумматоров 2 определяется сигналом на их управ- ЗО ляющем входе. Этдт сигнал представляет собой код знака соответствующего свободного члена (в последующих итерациях - соответствующей невязки) и поступает с выхода коммутатора 6, который в каждом такте итерации осуществляет последовательную коммутацию выходов знаковых разрядов регистров3 с помощью сигнала, поступающего на его управляющий вход от блока 9В каждой итерации в соответствую щем такте производится операция суммирования или вычитания в сумматоре 7 (в зависимости от сигнала на управляющем входе), полученного значения .приращения неизвестного в блоке 4 4 выделения приращения неизвестных с его предыдущим значением, которое хранится в запоминающем блоке 8 неизвестных. Затем на место предыдущего записывается нсвое значение ЗО неизвестного.В результате алгебраического суммирования коэффициентов строк в соответствующих накапливающих сумматорах 2 происходит сдвиг полученных сумм на количество разрядов, определяемое блоком 5 управления сдвигом, Затем к содержимым накапливающих сумматоров 2 прибавляются коды свободных членов (в последующих итера циях - коды невязок) соответственно. ЩВсе следующие итерации осуществляются аналогично первой.Конец решения может быть определен, например, по достижении величины суммы квадратов невязок задан ного малого числа. Подсчет суммыквадратов невязок может осуществлятьблок 9 по информации, поступающейна его вход от блока 5 управлениясдвигом.Работа блока 4.выделения приращения неизвестных заключается в следующем.На входи соответствующих элемен"тов ИЛИ 10 поступают одноименныеразряды всех кодов невязок, а навыходах элементов ИЛИ получается сигнал (ноль или единица), которыйсвидетельствует об отсутствии илиналичии данного разряда во всехкодах невязок. Полученное слово подается на входы элементов И 13 и через элементы НЕ 11 на входы элементов И 12 соответственно. Схемана элементах НЕ и И представляетсобой приоритетную цепь, котораяпри наличии сигнала науправляющем входе блока 4 выделения приращения неизвестных выделяет старшийразряд входного слова, который устанавливается в регистре 14 на время следующей итерации. Так, например, входное слово 00110101 приоритетная цепь преобразует в слово00100000. Хранимый в регистре 14код и представляет собой величинуприращения неизвестного.Работа блока 5 управления сдвигом заключается в следующем.На вход шифратора 15 поступает .код приращения неизвестного, который шифрируется и в обратном кодезаносится в счетчик 16. При этомсигнал иа первом управляющем входеблока 5 управления сдвигом устанавливает триггер 17 в состояние, открывающее элемент И 18, и черезнего иа выход блока 5 управлениясдвигом проходят тактирующие импульсы, которые поступают от блока 9на второй управляющий вход блока 5,Сигнал переполнения счетчика 16 сбрасывает триггер 17 в противоположноесостояние и подача тактирующих импульсов на выход блока 5 прекращается. Таким образом, с помощью блока 5 управления сдвигом получаютсерию импульсов, необходимых длясдвига содержимых накапливающихсумматоров 2. Причем количество этихимпульсов равно весу значащей единицы в коде приращения неизвестного.Замена операции полнораэрядного(к - разрядного) умножения на одноразрядную, позволяет сократить аппа"ратурные затраты,Формула изобретенияУстройство для решения системлинейных уравнений, содержащее сум"матор, запоминающий блок неиэвест 813446Источники информации,принятые во внимание при экспертизе.1. Майоров Ф.М, Электронныецифровые интегрирующие машины, М.,1962,с.86.2. Евреинов Э.В. Праншвили И.В.Цифровые автоматы с настраиваемойструктурой, М Энергия, 1974,с.195, Фиг.6-7 (прототип). ных, регистры, накапливающие сумматоры и запоминающие блоки коэффициентов, выход каждого из которых подключен к первому входу соответствующего накапливающего сумматора,второй вход которого соединен с первым выходом соответствующего регистра, о т л и ч а ю щ е е с я тем,что, с целью сокращения оборудования, оно содержит блок выделенияприращения неизвестных, блок управления сдвигом, коммутатор и блокформирования тактовых сигналов, выходы которого подключены соответственно к первому и второму управляющим входам блока выделения приращения неизвестных, блока управления. 1сдвигом и к управляющему входу коммутатора, выход каждого накапливающего сумматора подключен к входу со. -ответствующего регистра и к соответствующему информационному входу 2 Облока выделения приращения неизвестных, выход которого подключен к пер-вому входу сумматора и к входу блокауправления, сдвигом, первый выходкоторого соединен с входом блока фор-мирования тактовых сигналов, второйвыход блока управления сдвигом подключен к первым .управляющим входамнакапливающих сумматоров, вторыеуправляющие входы которых соединеныс выходом коьвутатора, второй выход Зфкаждого регистра соединен с соответствующим входом коммутатора, выходкоторого подключен к управляющемувходу сумматора, второй вход которого соединен с выходом запоминающего блока неизвестных, вход которогоподключен к выходу сумматора.2. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок виделения приращения неизвестных содержит регистр, две группы элементовИ, элементы НЕ и группу элементовИЛИ, входы которыхсоединены с информационными входами блока, выход каждого элемента ИЛИ, кроме последнего, подключен к первому входу соответствующего элемента И первой группы и через элемент НЕ к первому входу соответствующего элемента И второй группы, вторые входы первых элементов И первой и второй групп соединены с первым управляющим входом блока, выходы элементов И первой группы подключены соответственно к входам регистра, выход которого является выходом блока, выход каждого элемента И второй группы подключен к вторым входам последующих элементов И первой и второй групп, выход последнего элемента ИЛИ соединен с первым входом последнего элемента И первой группы, управляющий вход регистра является вторым управляющим входом блока.3. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок управления сдвигом содержит элемент И, триГгер, счетчик и шифратор, вход которого является входом блока, выход шифратора соединен с входом счетчика, выход которого соединен с первым входом триггера и с первым.выходом блока, второй вход триггера подключен к первому управляющему входу блока, второй управляющий вход которого соединен с управляющим входом счетчика н с первым входом, элемента И, второй вход которого подключен к выходу триггера, выход элемента И является вторым выходом блока.е ака Филиал ППП Патент, г.ужгород ул.Проектная 75/б 3 ВНИИПИ по 113035, Тираж 745осударс твенного комитет лам изобретений и откр сква, Ж, Раушская на ПодпСССРийд,4