Устройство для решения системлиНЕйНыХ АлгЕбРАичЕСКиХ уРАВНЕНий Советский патент 1981 года по МПК G06F17/12 

541 УСТРОЙСТЮ ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

Изобретение относится к вычислительной технике и может быть применено автономно, либо в качестве спец процессора, в комплексе с цифровой .вычислительной машиной, для оператив ного решения систем линейных алгебра ических уравнений, например, в систе мах автоматического управления динамическими объектами. Известно устройство для решения систем линейных алгебраических уравнений, содержащее блок умножения, сумматор, реверсивный счетчик, одноразрядные сумматоры, элементы И этом устройстве организация вычислительного процесса осуществляется в виде последовательности шагов, что определяет их относительно невысокое быстродействие. Наиболее близким к изобретению, по технической сущности является устройство, содержащее одноразрядные сумматоры-вычитатели, объединенные в п столбцов по П последовательно со единенных в каждом, сдвиговые регист ры, блоки элементов И, элементы ИЛИ, блок анализа Гз. Необходимость производить достато но большое количество итераций приводит к низкому быстроде 1ствию устройства . Цель изобретения - увеличение быстродействия устройства для решения систем линейных алгебраических уравнений. Указанная цель достигается тем, что в устройство, содержащее П блоков элементов И и сумматоры-вычитатели, объединенные в п столбцов, введены ц блоков вычитателей, причем первый вход i-ro (4 1,2,.. .ТП-1, ttl - количество разрядов представления информации) разряда j -го блока Вычитателей (j 1,2,..., П| являет.ся соответствующим входом устройства, ко второму входу i го разряда j -го .блока вычитателей соответс твенно подключен вькрд -t-ro разряда j -го столбца каждого сумматора-вычитателя, вход (+1)-го разряда которого соединен с выходом заема i -го разряда j -го блока вычитателей, каждый j -и блок элементов И выполнен из k однотипных групп (К 1,2,...,п) элементов И, каждая из которых выполнена в виде треугольной матрицы, состоящей из (т-1) строк и. столбцов, первые входы элементов И каждого i -го столбца к-ой группы элементов Я всех блоков элементов И объединены и подключены к выходу -го разряда к-го блока вычитателей и являются выходом устройства, вторые входы диагональных элементов. И к-ой группы j -го блока Элементов И объединены и являются соответствующими входами устройства, а вторые входам последукшщх элементов И, параллельных диагональным элементам И к-ой группы i -го блока элементов И, объединены и являются соответ ствующими входами устройства, выходы элементов И л -ой строки треуголь ной матрицы всех к групп элементов И j-го блока элементов И соединены со входами ГП -1)-го разряда сумматороввычйтателей i -го столбца, выход пере носа /I -го разряда каждого сумматоравычитателя j -го столбца соединен со входом переноса {i +1)-го разряда, а акже тем, что каждый -J -ый разряд j-го блока вычитателей содержит элемент И и сумматор по модулю два, пер вый вход которого является первым входом -го разряда j -го блока вычитателей, второй вход и выход сумматора по модулю два соединены с соответствующими входами элемента И, выход которого является выходом заема i-ro разряда j-го блока вычитателей, выход сумматора по модулю два является выходом блока вычитателей. На чертеже представлена блок-схем устройства для решения систем линейных алгебраических уравнений для слу чая когда h 2, m 3.

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

«7

Ч

2

ч

X.

( X.

.

f

fa О,

,

Ч

()

представить

виУстройство содержит П блоков 1 элементов И, каждый из которых выполнен из к однотипных групп 2 .элементов И (к 1,2,...,П), каждая из которых выполнена в виде верхней треугольной матрицы, состоящей из(ГП-1) строк и столбцов элементов И 3; п столбцов сумматоров-вычитателей 4, каждый -и разряд (л 1,2,...,М -1), столбца сумматора-вычитателя 4 выполнен в виде одноразрядного сумматора 5 на() входов, п блоков 6 вычитателей, каждый i -и разряд каждого блока 6 вычитателей выполнен в виде сумматора 7 по модулю элемента И 8. Работа предлагаемого устройства поясняется на примере решения систеыа линейных алгебраических уравнениТй порядка П , представленной в разрядной форме И. (1) -разрядная матрица, представлякядая собой разрядное изображение матрицы коэффициентов А системы алгебраических уравнений; -разрядные векторы представлякмдие собой разрядное изображение вектора неизвестных X и правых частей В решае.мой системы уравнений. В развернутом виде выражение (.1} при п 2 и m 3,, где m - количество разрядов представления информации , получаем

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

- - -.

Разрешив систему спектральных уравнений 4) относительно Xj , i 1,2,... mr j . l,2,...,n при условии

Г j

ац: при . . 15

LO , КИ.2,...,г, :

получаем

А Ь- х, ««4 Р/ .aVJ

,

,,, р .

х| Ц-а1,,х1 ;-Ь, .Г6)

Решив систему уравнений 6} с учетом единиц переноса из младших разрядов , в старшие на основании данных, представленных в таблице истиииости

(7)

i .

,Х:-1-е разряды -ых подвекторов х, В разрядных векторов В-Х соответственно; .

Р; - значение переноса из (1-1)гс BV- разряд;

т

т

,

L

Гз)

Г)

5,

; - величина, принимающая знас: , , Р .

,г ,(2,V2...., получаем соответственно вектор X. Работа устройства для решения систем линейных алгебраических уравнений начинается при подаче на его K,i)-e одные шины ссэртветственно значений коэффициентов 5 Ур матрицы А и на е входные шины значений вектора правых частей §.,После окончаний переходного процесса в устройство на выходе элементов И 3 к-й группы . 2 элементов И j -го блока 1 элементов И образуются частичные произведе - на выходах одноразрядных

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

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

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