Устройство для операций над матрицами Советский патент 1988 года по МПК G06F17/16 

НшК

Т

О9 00

Фиг.1

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

Цель изобретения расширение функциональных возможностей за счет решения систем линейных уравнений и обращения матриц.

На фиг.1 представлена структурная схема устройства для операций над матрицами; на фиг.2 - функциональная схема операционного блока 1 j (J «2, ..., N); на фиг.З - функциональная схема операционного блока

i. j ( , 3N; j 1,2, . .. , N) ; на

фиг,A - функциональная схема элемента задержки К(,2,.,.,N-1); на фиг.5 - схема распределителя импульсов; на фиг,6 - 8 - блок-схема алгоритма функционирования устройства.

2

Устройство содержит Ь} операцион- ных блоков 1.i.j(i,), N-1 элементов 2 задержки, распределитель 3 импульсов.

Операционный блок l.) содержит входной регистр 4, блок 5 деления, синхровход 6.

i Операционный блок 1,1. j ( 1 ,N) содержит регистр 7 первого сомножителя, умножитель 8, вычитатель 9, регистр 10 второго сомножителя, выходной регистр 1I, синхронходы 12 - 4. Элемент.2.К (,N-1) содержит регистры 15 и 16 и синхровходы 17 и 18,

Распределитель 3 содержит генератор 19 синхроимпульсов, элемент И 20 счетчик 21 тактов, блок 22 памяти микрокоманд, выходы 23-29 распределителя.

Выход 23 подключен к управляющим входам 6.1,1 и 6.1.3, выход 24 - к управляющим входам 12,2.1 и 12.2.3, выход 25 - к входам 12.3,1 и 12„3.3, выход 26 - к входу 6,1,2, выход 27 - к входу 12.2.2, выход 28 - к входу

12.3.2,выход 29 - к управляющим входам 13,2,1, 13,3,1, 13,2,2, 13.3.2,

13.2.3,13,3.3, 14.2.1, 14.3.1, 14.2.2,.14.2,3, 14.3.3, 17,1, 17,2, 18.1, 18.2,

Устройство для операций над матрицами может вьтолнять Ш-разложение} вычислять обратную матрицу, решать

систему N линейных уравнений методом Гаусса-Жордана. Вычисления основаны на преобразовании исходной матрицы в треугольную для LU-разложения либо в единичную.Для получения LU-разложения устройство обрабатывает исходную матрицу размерности N N. При решении системы линейных уравнений и при вычислении обратной матрицы выполняет- - ся обработка расширенной матрицы размерности N И, которая представляет собой исходную матрицу размерности N N, к которой справа дописана матрица размерности ).

При вычислении обратной матрицы к исходной матрице справа дописывается единичная матрица размерности N N (в этом случае N) и после того, как исходная матрица будет преобразована в единичную, на месте приписанной.справа единичной получим обратную.

При решении системы линейных уравнений к исходной матрице (N«N) справа дописьюается S столбцов свободн ых членов (в этом случае ) и после того, как исходная матрица будет преобразована в единичную, на месте столбцов свободных членов получим семейство решений данной системы линейных уравнений. Число- S при данной организации вычислений может быть любым натуральным,

Все перечисленные алгоритмы объединяют идентичность базовой операции преобразования:

а

(.V: J

/)-1) (К-П, (к-.() (К-П

п к - ,к

1 - ;

45

a :: Va К 1,2N,

ij K+I,К+2,.,.,N,

При этом для LU-разложения

0

5

и.;

(К--0 , (к-О

(,К-(1

а,- /а,- , 1, а, .

К 1,2N, ij К,К+1 ,

K+2,...,N.

Поскольку все вычисления выполня- .ются аналогично, для примера рассмотрим работу устройства при вычислении обратной матрицы размерности 3 3 ,

Условимся, что информация в регистры принимается в конце такта

3

и определитель исходной матрицы не равен нудю. Итак, имеется исходная матрица

U443003

произведение /С

, (о)

,- , которое поступает на вход вычитателя 9.2.1, и на его выходе получается выраже

Изобретение относится к вычислительной технике и может быть исполь зовано для выполнения матричных one- раций. Целью изобретения является ; расширение функциональных возможностей. Устройство содержит N операци - онньгх блоков 1, N- элементов 2 держки и распределитель 3 импульсов Операционный блок 1 ,1 . j содержит вход ной регистр и блок деления J ,N, операционный блок 1.i.j(,N, j r/N) содержит два регистра сомножителей, умножитель, вычитатель, выходной регистр. Поставленная цель дос- тигается за счет введения новых элементов и связей. 8 ил.

Элементы матрицы С поступают на входы операционных блоков построчно со сдвигом на один такт, т.е. первая строка поступает на первый вход операционного блока 1,1,1, начиная с первого такта, вторая строка поступает на первый вход операционного блока 1.2.1, начиная с второго такта, третья - на вход блока 1.3.1, начиная с третьего такта.

В

-,()

li, Во ВТОпервом такте элемент i,, принимается в регистр 4.1.1. ром такте элемент сД поступает на вход блока 1.1.1, на вьпсоде которого получается частное U, «

(О

C,j .Это частное в конце такта принимается в регистр lU..l блока 1.2,1, а элемент С , l, принимается в регистр 7.2.1.

В третьем такте элемент поступает на вход блока 1.1,1, на выходе которого получается частное

и,5 . Элемент поступает на первый вход блока 1.2.1, На выходе умножителя 8,2.1, получается

ие С

,(0

1г

С

21

,1)

г

/с °

/ Ь(,

с

21

1

12

В

конце ()

,(°) /„W

такта частное С. /С

и

п

С

ч

частное гистр

принимается в регистр 10,2,1,

Ло (о) ()

С,, С„ - в ре- 10.3.1, С,гг

записывается в

в регистр 11.2, в регистр 7.3.1 В четвертом

1, элемент

г С М

такте элемент

с - н

подается на вход блока 1.1,1, на выходе которого получается частное

0

5

0

,Со) ,„(0) „со

.„ /С„ С,4 , на выходе произведение

умножитеc Vc

Ь,, /Vv,,

ля 8.2.1 (О1

X с 2 , которое подается на вход вычитателя 9.2,1. На второй вход вычитателя поступает элемент

(ol

С 21 , И на выходе вычитателя 9.2,1 Ml „(о) (о) ,(0) с)

получается С

с„ и

/с;;

21

На выходе умножителя 8,3,1 получа(о)

ется произведение

/С ° п /

э(

на

первый вход блока 1.3.1 поступает

ю) элемент С 31 и на выходе вычитателя

О) (о „(оУ

2

Э

Г -Г /

- г- I

5

II

и 1

.(о) ;(°

ное С гистр 10.2.1,

В конце такта част принимается в ре- частное /С

45

50

40

-С

-L,

- В регистр 10.3,1, частное в регистр 15.1,

U (2

k (г / - )(

с 12. записьшается

в регистр 4.1,2, (О

23

- в регистр 11.2.1, С5J - в регистр 11.3.1.

(о)

В пятом такте элемент €,5 ется на вход блока 1.1.1, на

которого получается

„(в)

15/С 11

пода- выходе

на выходе умножителя 8.2.1 - проиэ(о) . to) ведение С ц /С ,

тателя 9.2.1 - выражение С

Cj, , на выходе вычи(0 24

г 1x24

(О)(О)(о)

- с ,4 / с , С

2т

,на выходе умножителя

55

8,3.1 - произведение

на выходе вычитателя

С

СМ эз

,,( - L ,,j

р{оЬ„(о). (о) - 3 11 И

9,2.1 - выражег ие /

вычитателя

.Л° f

рет истра 11.2.1 С ос вход блока 1.1.2, на выС 54

на выходе

-( pW f-H

,.W г t, /IM, (.I 1 Г I . -i . 1 Ь 24

ходе которого получается частное

24

На выходе умножнтеЛЯ 8.2.2 получается произведение

а на выходе вычитате- ажение С С

..г / 40

гз

В конце такта част

Г

- 16

, частное

принимается в .И/.:о)

тр 10.3,1,

15 1

частнае

.35

- в

ъ

регистр 15,1, част- - в регистр I6.S

частное С. С

U

(О) 12

-

Ь

7,3„2, частное

гистр 10.2.2, частное c

в регистр 10.3.2, С 5-

С,, - в регистр 11.2.2.

В седьмом такте на вытеля 9.2.1 получается в

выхода вычитателя 9.2.1 принимается в регистр П. 2.1, С 2 - в ре

:} - в регистр 5, - в регистр 11.3.2. В восьмом

гистр 1 1 .3. I , С

199

J .г./, ,

такте на выходе вычитателя 9.3, получается выражение

с -ja

С .;

(о)

35

бло1са 1.1.2 к - ( частное

выходе . г

; / и 24 - Ь

на

гС)

i6 j

на выходе вычитателя 9.2.2 - выраже- J2) (0 (Оу(0 (0

ние С

5

С

35

- с;-;/с

21

12

на выте-

/ 40

з

ходе вычитателя 9.3.2 - выражение -(11 -.(1) .W .,.(1) „О)

С выхода - 14 z f Czi; С г гистра 11.2.2 C.J4 подается на вход блока 1.1.3, йа выходе которого получается частное С 1 . В

53

(О) /.,Ло)

5

л / --.1.О

rje такта частное С , /ь.

нимается в регистр

,И ,„(0) (,)

С,5г /С (« 05

ное С,

р

()

0

26

частное С 10,3.2,

/Сгг (1)

25- гг частное

в регистр

(2)

:S

частное 16.

при - в регистр 10.2,2, /С

- в

0, /г

гг

регистр (-5

24

Е регистр

в регистр

О , «)

частное

iZ

U)

/С

3

- (

И

- в

регистр 10.2.3. С вы(2

хода регистра 11.3.2 принимается в регистр 7.2.3. С выхода вычит-з- СО

теля 9.3.1 С

гб

запнсьгаается в оегистр 11.3.1, С V - в регистр

l.AA{ J 11.2.2, Г/,у - в регистр 11.3.2.

В девятом такте на выходе вычита- теля 9.2.2 получается выражение

,(Я

36

.М

ДО

J6 - Zi

:10

М)

/C -ii - ) , на выходе

(i)

вычитателя 9.3.2 - выражение С ,5 -

-0,5 - C y/Cjj- с,2 , на выходе

блока 1.1.3 - частное С /с Д / на выходе вычитателя 9.2.3 выражение с;: ciV- C, в конце такта частное С, , C,g принимается в регистр 16,1, частное

регистр 10.3.2, частное С - в регистр

(О

- в регистр 16.2, частное в регистр 7.3.3, частное ,,

,)

55- 33

CV5- В регистр 10.2.3, частное в регистр 10.3.3,

(О

С выхода сумматора 9.2.2 С , записывается в регистр 11.2.2, С ,J . - в регистр 11.3.2, - в регистр П.2,3.

В десятом такте на выходе вычитателя 9.3.2 получается выражение

„аТ () „(О ,„(1) „(It

C,g t.,g- Сгб/Сгг С,, на выходе бл,(з) 6

ка 1.1.3 - частное на выходе сумматора 9.2.3,- выражение С С,5 - с , сГЛ на выходе сумматора 9.3,3 - выражение nt псг) ,а). т

Z i

, (1 , О - «

С-; с ;, - с Д /cf,- C;i . в конце

такта частное С гв принимй ется в регистр 15.2, частное

С 25/С 11 If регистр 16.2, частное С jg /С

11 - W 25U) ,„Й (Э)

. ,3 - 3+ регистр 10,2.3, частное С fjVc, С,у - в регистр 10.3.3. С fg записывается в регистр 11,3.2, С в регистр 11.2.3, . в регистр 11.3.3;

В одиннадцатом такте на выходе вчитателя 9,2.3 получаем выражение

р з) p(t) 16 -16

„(г ,„(2) „(i)

Cjg/Cjj- с,} , на выходе вычитателя 9.3,3 - выражение .

W лг- (а) (г) Cj5 Сэ5/С 5Л С 13 В конце такт

Hi , (1) (г) частное принимается

3 регистр 16,2, частное

С) в регистр 10,3,3,

б

сывается в регистр 11,2.3, С рег истр 11.3.3.

эапи- - в

В двенадцатом такте на выходе вычитателя 9 , 3 , 3 получается выражение „и) (1) (Я ,01 (г) -26 С 1б t ft/t ii 2з которое в . конце Тгчкта принимяется в регистр

П.З/s,

iip;i этом вычисление обратной матрицы заканчивпется. Начиная с восьмого такта на первых выходах блоков 1,1,3, 1,2,3, 1,3,3 появляются элементы обратной матрицы

о

-

ы

30

35

40

20

На выходах устройства получаются элементы обратной матрицы по строкам, т,е. на выходе блока 1.1.3 по- 2g являются элеме1ггы третьей строки, т.е, на выходе блока 1,2.3 - первой, на выходе блока 1.3,3- - второй.

Для общего случая N выходов распределение строк следующее: i-я строка результата выдается с (i+1)- го выхода (для i 1,,..,N-1), N-Я строка - с 1-го выхода.

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

При решении системы линейных уравнений в качестве элементов матрицы В подаются свободные члены заданной системы уравнений. Тогда на вьгходе получается семейство решений этой . системы уравнений. Столбец

с,4 Ci5( 3 является решением системы при столбце свободных членов

Ъ„ Ь, Ь,,, столбец С,У с П с( с- решением свободных членов

и т.д.

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

55

Устройство для операций над матрицами, содержащее N(N+l)/2 операционных блоков и распределитель ин- ,пульсов, выходы которого подключены к синхровходам операционных блоков.

91

где N - размерность матрицы, отличающееся тем, что, с целью расширения функциональных возможностей за счет решения систем линейных уравнений и обращения матриц, в него введены N (N-l)/2 операционных блоков и N-1 элементов задержки, причем первый вход i,.l-ro операционного блока подключен к i-му входу устройства, (,N), первые выходы i.N-x и l.j-x операционных блокоз подключены к выходам устройства,

4300310

(,N, ,N),первый вход i,j-ro операционного блока подключен к первому выходу (i+l )(j- )-го операциои- 5 кого блока, (,N-l; ,N), первый вход операционного блока N,j подключен к выходу (j-l)-ro элемента задержки, (,N), вход которого подключен к второму выходу N ()го операционного блока (,N), второй вход i,j-ro операционного блока подключен к второму выходу(i-l ) , операционного блока (,N; ,N).

10

и.г.г

PrW.,,

PrW.,l /C, Pr 11. г , PrTi. C ° - tjf

PrW2J :-c , P,fP.}.1 :--c ,, P,,5.,:-c , /cff--c ,

РГ 11.1.2): - fij; РГ 11. СгУ;

1)

fr f.3.

P,r0.l.,l /C f-C , j P,0.}. ,t

P, is. c ,1/c ,--c ; ; .f,is. с, г

« .г.г 41/f 7--fЙ / r«.f.---cil; Pr. - ..г. cЙ

г

fii

Ф

РГ 10.2. o7/r. г 10.3. C l/cff C ; /.r5.f : c|;Vo c; ; Р,/. , T.f;

РГ 7J. ../., Я /о. г ; r/j A/; - л-11.2. Pr1U., l; p,i1.2.2 :--cl l ,

Pr I0,3.i :--clpc} c , Рг,1.:-с /сУ-сУ ; Pr i6.i : -clt/cif cf,t PrW.2.2 i-cii/c i--c,; Pr /.J.2.:.c/fA/ гIt /,f5:2.--r/J /r,

в-4 .5. .г/. о 5; Pr11.2.2 :-CJl ; Pr11.S.

Prif,,/cff--cil; PriB.i : l/cff-c;i :

.Гг :- С 1/С 1-с11; Рг10,,

Pr75..4 Vr/r--c4 ; P./.z.-.

/ r /,J :--r/|V 35 -C/4 ; .. PrH3,l :-C/e ; РГ /y.f.f ; Prff.3.

:illi: 5

Pr16.,i/Cff C;ih PrW.5.2 - ci l/ci f5.. .cfl; РГ 16.2 : -- .3.3x Pr10.2.) -cII ;

Яг . .3 . c il/cff РГ /. . 2 .- -

Pr.3.

- gM-M -MM MMM M «a ii iM ti i «i iMi«H «iiMiM MH n tiji «чадшишпчашш и «л. . n и.и i i. ч .i

V

Pr15,.. PrW. Pr/.5 :-- JVr/J -r/f; .. 44- Pr11.2. . 3. ;

:P Ifi - r /r r

/r /0./. - (

/,/.3. .2.,7;

в J.

.5.3.-

( /fgH g ц )

10

//

/

аг.