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

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик о11805336

К АВТОРСКОМУ СВИ ЕТЕЙЬСТВУ (61) Дополнительное к авт. сеид-ву р у (3 (22) За»влеио 04.09.78 (23) 2663885/18-24 е присоединением за»вки йо 06 15/324

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

СССР по делам изобретений н открытий (23) Приоритет©щ бликоВеио 150281., Ьоллетеиь те9 6

Дата опубпмяования описани» 176 2ф1 (53) УДК 681. 14 (,088.8} ;1;; ,Py ...,..

5 " ° /аQ

"- RJf!en

: ° у 1суу) /

ifg (72) Авторы изобретения

А. И. Стасюк (71) Заявитель

Киевский институт инженеров rpa (541 УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ

АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

1 г

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

3Î

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

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

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

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

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

Указанная цель достигается тем, что в устройство, содержащее П блоков элементов И и сумматоры-вычнта- тели, объединенные в П столбцов, введены и блоков вычитателей, причем первый вход .-ro (x = 1,2, . .Ytt-1, % — количество разрядов представления информации) разряда j -ro блока вычитателей t ) = 1, 2,..., П } является соответствующим входом устройства, ко второму входу tI -го разряда ) -го ,блока вычитателей соответственно подключен выход -го разряда j -го столбца каждого сумматора-вычитателя, вход (+1)-го разряда которого соединен с выходом заема < -го разряда -го блока вычитателей, каждый -й блок элементов И выполнен из .К однотипных групп (К = 1,2,...,п) элементов И, каждая из которых выполнена в виде треуголььой матрицы, состоящей из (щ-1) строк и столбцов, первые входы элементов И каждого j -го столбца к-ой группы элементов И всех блоков эле805336 ментов И объединены и подключены к выходу q --го разряда к-ro блока вычитателей и являются выходом устройства, вторые входы диагональных элементов. И к-ой группы ) -го блока лементов И объединены и являются оответствующими входами устройства, а вторые входы последующих элементов

И, параллельных диагональным элементам И к- ой группы -го блока элементов И, объединены и являются соответствующими входами устройства, выходы элементов И rt -ой строки треугольной матрицы всех к групп элементов И -ro блока элементов И соединены со входами(Ill -j) -ro разряда сумматороввычитателей j -ro столбца, выход переноса q --го разряда каждого сумматоравычитателя ) -го столбца соединен со входом переноса (+1) -го .разряда, а . также тем, что каждый j -ый разряд

) --го блока вычитателей содержит элемент И и сумматор по модулю два, первый вход которого является первым входом 4 -ro разряда -го блока вычитателей, второй вход и выход сумматора по модулю два соединены c,соответствующими входами элемента И, выход которого является выходом заема i -ro разряда j -го блока вычита1 телей, выход сумматора по модулю два является выходом блока вычитателей.

На чертеже представлена блок-схема устройства для решения систем линейных алгебраических уравнений для случая, когда h = 2, п1 = 3.

Для того, чтобы вычислить Х, необходимо систему спектральных

Устройство содержит и блоков 1 элементов И, каждый из которых выполнен из к однотипных групп 2 .элементов И (к = 1,2,...,Ii), каждая из которых выполнена в виде верхней треугольной матрицы, состоящей из(п-1) строк и столбцов элементов И 3; и столбцов сумматоров-вычитателей 4, каждый 1 -й разряд (4 1, 2,..., tll -1 ) „ столбца сумматора-вычитателя 4 выполнен в виде одноразрядного сумма © тора 5 на (y-i) входов, П блоков 6 вычитателей, каждый j -й разряд каждого блока 6 вычитателей выполнен в виде сумматора 7 по модулю два и элемента И 8.

1$ Работа предлагаемого устройства поясняется на примере решения системы линейных алгебраических уравнений порядка П представленной в разрядной фОрме „ твида

М

re A - разрядная матрица, представляющая собой разрядное изображение матрицы коэффициентов A системы алгеб-, раических уравнений X B — разрядные векторы представляющие собой разрядное изображение вектора неизвестных

Х и правых частей В решаемой системы уравнений.

В развернутом виде выражение (1) при и = 2 и m = З,.где m — количество разрядов представления информации, получаем уравнений 2 представить в виде

805336 или соответственно ф

Г") Решив систему уравнений (6) с учетом единиц переноса иэ младших разрядов в старшие на основании данных, представленных в таблице истинности (7) Разрешив систему спектральных уравнений 4) относительно Х, j = g,2„„

N ) = 12,-, И при условии л 1 к

С2н = "Р" - ф} .

О К ; К=1,2,...,п получаем

3 З 2 2 2 2 3 4 3 1 3

Х = 6q qq Х j+Q 2Х2 6ЦХ»+ 012Х2+ P„

2 г 2 Ф 2

Х Ф,-а, Х О,2Х2

М 1

Х,-Ь„ з 3 2 2 Ф г s м a - у

2 2 О21Х Фг2%2Рг Х +с622Х2+ Рг,,г г 2 4.

Хг =Ьг О24Х1 Фогахг (6) где@,X -1-е разряды j -ых подвекторов

%, в 1разрядных векторов Ъ-% соот ветст1енно;

Ф вЂ” . значение переноса иэ (q- 1) -гс в м разряд; — величина, принимающая зна чеиие"5„=0,"5 = О,, -,„Х „,. „Х, "," à а 2„X „ Ü 22 „„,, 30 получаем соответственно вектор Х.

Работа устройства для решения систем линейных алгебраических уравнений начинается при подаче на его (к,j) -е входные шины соответственно

33 значений коэффициентова/„матрицы K и на -е входные шины значений век тора правых частей Й..После окончания переходного процесса в устройство на выходе элементов И 3 к-й группы.

2 элементов И j -го блока 1 элемей- тов И образуются частичные произведения 8 „х„ - иа выходах одноразрядных суьеааторов 5 j -го столбца 4 сумматора-вычитателя соответственно 5„, 5„, 2 3 г, Яи" на выходах сумматоров 7 по

4> модулю два j -го блока 6 вычитателей по выражениям (6),(7j образуются соответствующие разряды искомых векторов .Использование новых элементов и

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

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

805336

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

ВНИИПИ Заказ 10904/72 Тираж 756

Подписное

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

1; Устройство для решения систем линейных алгебраических уравнений, содержащее и блоков элементов И и

1 сумматоры-вычитатели, объединенные

П столбцов, о т л и ч а ю щ e e,с я тем, что, с целью повышения быстродействия, в него введены П блоков вычитателей, причем первый вход -го (л = 1,2,...,g-1,% -количество разрядов представления информаций) разряда -го блока вычитателей(1,2,..., nj является соответствующим входом устройства, ко второму входу q -го разряда,1 -го блока вычитателей соответствейно подключен вы- 1Я ход 4 -разряда каждого сумматора-вычитателя j -го столбца, вход(+1) -разря да которого соединен с выходом заема

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

1,2,..., И) элементов И, каждая из которых выполнена в виде треугольной матрицы, состоящей„ иэ (pl-1J строк и столбцов,первые входы элементов И каждого М - го столбца к-ой группы элементов,И всех блоков элементов И объединены и подключены к выходу g -го разряда к-ro блока вычитателей и яв.ляются выходом устройства, вторые входы диагональных элементов И к-ой .груп о пы -го блока элементов И объединены и являются соответствующими входами устройства, а вторые входы последующих элементов И, параллельных диаго-. нальным элементам И к-ой группы -го блока элементов И, объединены и являются соответствующими входами устройства, выходы элементов И х -ой строки треугольной матрицы всех к групп элементов И -ro блока элементов И соединены со входами у- 4j-ro разряда сумматоров-вычитателей 4 -го столбца, выход переноса < -ro разряда каждого сумматора-вычитателя g -го столбца соединен со входом переноса (j +1 } -го разряда.

2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что каждый

j-ый разряд j -го блока вычитателей содержит элемент И и сумматор по модулю два, первый вход которого является первым входом < -ro разряда 1 -го блока вычитателей, второй вход и выход сумматора по модулю два соединены с соответствующими входами элемента И, выход которого является выходом заема а -го разряда 1 -ro блока вычитателей, выход сумматора по модулю два является выходом блока вычитателей.

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

1. Авторское свидетельство СССР

9 529468, кл. C 06 j 1/00, 1975.

2. Авторское свидетельство СССР

9 543943, кл. С 06 Р 15/32, 1976 (прототип).