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

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

Иллюстрации

Показать все

Реферат

 

ОП И

САНИЕ

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

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

Республик (»)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 (прототип).