Устройство для решения систем линейных алгебраических уравнений
ОП И
САНИЕ
Союз Советских
Социалистических
Республик (»)543943
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЙТИЛбСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено25.02.75 (21) 2108752/24 с присоединением заявки № (23) Приоритет (43) Опубликовано 25,01,77,Бюллетень № 3 (45) Дата опубликования описания 10.05.77 (51) М, Ки.
G06 Г 15/32
Государственный комитет
Совета Министров СССР по делам нзооретений н открытий (53) УДК 681,326 (088.8) В, П, Боюн, Л, Г. Козлов, E. Н, Малиновский и С. И, Третьяков (72) Авторы изобретения (71) Заявитель
Ордена Ленина институт кибернетики АН Украинской CCP (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ
АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
Изобретение относится к вычислительной технике и предназначено дпя специализированных вычислительных устройств.
Известно устройство дпя решения систем линейных алгебраических уравнений, содержащее интеграторы коэффициентов, интеграторы свободного члена и интеграторы неизвестных причем выходы интеграторов коэффици) ентов каждого столбца соединены с входами интеграторов свободного члена того же столб- 0 ца, выходы которых подключены к входам интеграторов неизвестных того же столбца и входам интеграторов коэффициентов соответствующих строк jl) .
Недостатками этого устройства являются!5 бопьшое количество оборудования, запаздывание в обработке приращений, трудность ре щения систем уравнений высоких порядков, трудность контроля конца решения малое быстродействие. 20
Наиболее бпизким по техническому реше. нию к предлагаемому является устройство дпя решения систем линейных апгебраических уравнений содержащее одноразрядные сумматоры-вычитатепи и сдвиговые регист- 25 ры, управляющие входы которых соединены с управляющей шиной, а выходы - с первыми входами соответствующих одноразрядных сумматоров-вычитателей, объединенных в тт-столбцов по д поспедоватепьно со» единенных одноразрядных сумматоров-вычитателей в каждом, управляющие входы одноразрядных сумматоров-вычитатепей каждой строки соединены с входом соответствующего реверсивного счетчика (2).
Недостатком этого устройства является низкое быстродействие à необходимости производить большое количество итераций:
К
2 (к разрядность кодов). цепь изобретения - повышение быстродействия.
Поставленная цель достигается тем, что в каждый столбец введены (й + 1)-ый cnahtговый регистр, блок анализа, два элемента И и элемент ИЛИ, причем выход
Д -го одноразрядного сумматора-вычитатепя каждого столбца соединен с первым аходом (tl + 1)-го одноразрядного сумматора-вычитатепя и с первым. входом эпемента ИЛИ, выход которого соединен с входом
543943 (t1 + 1)-го сдвигового регистра, выход знакового разряда (и + 1)-го сдвигового регистра соединен с первым входом блока анализа, выход которого соединен с входом соответствующего реверсивного счетчика, выход (И + 1)-го сдвигового регистра соединен со вторым входом блока анализа и через первый элемент И вЂ” со вторым входом элемента ИЛИ и со вторым входом первого одноразрядного сумматора-вычитателя соответствующего столбца, а через второй элемент И вЂ” со вторым входом (д + 1)-го одноразрядного сумматоравычитателя, выход которого соединен с третьим входом блока анализа, вторые вхо« 5 ды элементов И всех столбцов и управляющие входы реверсивных счетчиков соединены с управляющей шиной.
На чертеже изображена блок-схема предлагаемого устройства.
Устройство состоит из сдвиговых регистров 1, одноразрядных сумматоров-вычитателей 2, элементов ИЛИ 3, элементов И
4 5 блоков анализа 6 и реверсивных счет) чиков 7. 25
Блок анализа 6 предназначен для выделения знака разности невязок р -ой и (р -1) -ой итерации соответствующего уравнения системы, определения знака прираще. ния соответствующего неизвестного и за- зо поминания кода знака на время итерации.
Устройство работает следующим образом, Коды коэффициентов а при неизвестных
1 э5 системы: уравнений заносятся в соответствуюшие сдвиговые регистры 1, В (r + 1)ые сдвиговые регистры заносятся соответственно коды свободных членов В блоке 6 устанавливается код знака соответствующего свободного члена b ° . Ре40 версивные счетчики 7 устанавливаются в нулевое состояние (p + 1)-ые однораз> рядные сумматоры-вычитатели 2 работакт в режиме вычитания, С выхода (д + 1)-ro сдвигового регистра 1 код соответствую45 щего свободного члена b начиная с млад-»
1 ) ших разрядов, через элемент И 4 поступает на второй вход первого одноразрядного сумматора-вычитателя 2 соответствующего
50 столбца, а через элемент ИЛИ 3 перезаписывается в (q + 1)-ый сдвиговый регистр
1. Этот код, просуммировавшись с соответствующими коэффициентами, поступившими со сдвиговых регистров, подается через элемент ИЛИ 3 в (h + 1)-ый регистр 1
55 и на первый вход соответствующего (11 1
+ j 1»
-го одноразрядного сумматора-вычитателя 2, на второй вход которого через элемент И 5 поступает код из (Ж + 1 ) — го сдвигового регистра 1. В зависимости от результатов вычитания (р - 1)-ой ир-ой невязок соответствующий код сигнала с выхода (д + 1)-го одноразрядного сумматоравычитателя 2 подается на третий вход блока анализа 6, на первый и второй входы которого поступают в этот момент знаки предыдущей и настоящей невязок. По коду сигнала на своем третьем входе блок анализа
6 определяет код приращения Ь Х„ на своем, выходе. Код приращения Ь х, с выхода блока анализа 6 подается на вход счетчика 7, где суммируется с предыдущим содержимым последнего и на управляющие входы всех одноразрядных сумматоров-вычитателей 2 соответствующих строк для установления режима работы одноразрядных сумматоров-вычиталей. После каждой итерации по управляющему сигналу, подаваемому на управляющие входы реверсивных счетчиков 7, их со— держимые сдвигаются на один разряд в сторону старших разрядов. По управляющим сигналам, поступающим на управляющие входы сдвиговых регистров 1 соответствукщих строк, производится сдвиг кодов соответствующих коэффициечтов g, в сторону младших разрядов и их перезапись в тот же регистр.
В качестве иллюстрации работы устройства проведено решение следующей системы алгебраических уравнений:
«+ Ха Х5= 4
Х "а+ > ç =- о
Точное решение данной системы
Х =0,3 Х =-0,2 Х =-0,6.
Считают что величины неизвестных не
) превосходят единицы, т.е. решение начинают со старшего разряда, вес которого равен
О, 5. Процесс решения сведен в таблицу.
Технико-экономический эффект, который достигнут за счет введения в каждый столбец (и + 1)-го сдвигового регистра, блока анализа, двух элементов И и элемента
ИЛИ, а также новых связей между блоками состоит в том, что быстродействие предлагаемого устройства в 2 /к раз больше по сравнению с известными устройствами, что, например, при разрядности K -10 дает выигрыш по быстродействию примерно в 100 раз.
543943
I
l !
I
I
1
1
I
I !
1
1
1 л 1 о о
С »
D»
CD о
I о !
Я
С
CO (Q о о о
1Q
С 4 л л о о с х
cd й(С СО
4 Х с
Оам
+ +
1 CO
o o (Q Щ
o o
+ я (с
o o
О» о ! с»
I !
I ! !
+ !
СО
o !! +
П Ж
СО
o o
С » С;!
o a
I и сс с!
o o!
1- Ю
o o
I
1
I
+
1
1 !
l !
1 с! о
1 !
I
I !
t 1
О1
1
I
tQ
С » о
1
I
1 ! 1
1
1
cO I
О1
1
I
Ñ »
1 !
I !
l
I !
I (Q
t с! о
tQ
С"» о
LQ
D) л1 о
1Q
1-Ч о
1-1
lQ
С о
tQ
С 4 л о !
tQ
Я
Л1 о
+ (Q
Сс» о
С 1
I
1
1 !
I
1
I ! (С» 1
t о о
I
1
1
tQ
CO о
1
1 ! и 1
С1)
O 1
1
I !
1
I !
1
I (С» I с 1
О1
I
I
1 сс I
1
I
I
I
10 о
С"» о о
I (0
Я
СО о
Я с»
СО о о !
tQ
t с! о
I (Q
СО о о
t сс
CQ о
Я
Я
CO о о !
Ж !
Я о
Я
I
I
1
I
I ! !
1
1 л
I
1
I
С1) (Д
CD 1
tQ
1
1
1
С1 I
CO о
O 1
1 !
1 !
1 !
I
l
I ! I
О1
О1
I
I
I с» I
1 !
I
1
I
Я
Гсс с» л о
1Q
Я
СО
Г) о (Q
Я
1-1
Сс» о о
И о
СО о о ! л
1С»
t
СО о о ((t
СО
1-1
Л о !
tQ
Л
Сс» о о !
1Q
СО о о
Я
Сс»
О»
Я 1
О1 !
1 сС CQ
t Я
СО т-1
Ю с» о Ч
o o!
fQ Я (Ч Я
Ю CD (0 СС» л
o o
o o
+ +
1Д 1Q
СС» (СО о о о
1-(543943
БНИИПИ Заказ 872/64 Тираж 818 Подписное
Филиал ППП Патент", г. Ужгород, ул. Проектная, 4
Формула изобретения
Устройство для решения систем линейных алгебраических уравнений, содержащее одноразрядные сумматоры-вычитатели и сдвиговые регистры, управляющие входы которых соединены с управляющей шиной, а выходы -с первыми входами соответствующих одноразрядных сумматоров-вычитателей,обь единенных в Ф -столбцов по т последователь- 10 но соединенных одноразрядных сумматороввычитателей в каждом, управляющие входы одноразрядных сумматоров-вычитателей каждой строки соединены с входом соответствующего реверсивного счетчика, о т— личаюшееся тем,что,сцелью увеличения быстродействия устройства, в каждый столбец введены (p + 1)-ый сдвиговый регистр, блок анализа, два элемента
И и элемент ИЛИ, причем выход q -го одноразрядного сумматора-вычитателя каждого столбца соединен с первым входом (g + 1)-го одноразрядного сумматора— вычитателя и с первым входом элемента
ИЛИ, выход которого соединен с входом. (И + 1)-го сдвигового регистра, выход знакового разряда (p + 1)-го сдвигового регистра соединен с первым входом блока анализа, выход которого соединен с входом соответствующего реверсивного счетчика, выход (Vi + 1)-го сдвигового регистра соединен со вторым входом блока анализа и через первый элемент И - co вторым входом элемента ИЛИ и со вторым входом первого одноразрядного сумматоравычитателя соответствующего столбца, а через второй элемент И вЂ” со вторым входом (И + 1)-го одноразрядного сумматора-вычитателя выход которого соединен с третьим входом блока анализа, вторые входы элементов И всех столбцов и управ» ляющие входы реверсивных счетчиков соединены с управляющей шиной.
Источники информации, принятые во внимание при экспертизе:
1. Неслуховский К, С. цифровые дифференциальные анализаторы», М., "Машиностроение", 1968, стр. 148, фиг. 85.
2. Майоров Ф, М. "Электронные цифровые интегрирующие машины", М., 1962, стр. 86, фиг. 59 (прототип).
