Устройство для решения матричного уравнения вида АХ=В Советский патент 1989 года по МПК G06F17/16 G06F17/11 

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

Цель изобретения - упрощение уст- .ройства.

В основу работы предлагаемого устройства положен метод Гаусса-Жор- дана, при котором для решения систем линейных уравнений расширенная n-() матрица СА/В сводится к n-() матрице В/Х, где Е - единичная () матрица, по рекуррент- :

ным соотношениям для а;

ij

,n,;

j l,n+m (при обращении матриц - ,

а расширенная п.2п матрица А/ЕJ сводится к п«2п матрице k 1,п;

М (k-D/ () , , . , Va,,,,, k j n+m;

Hf--i j

(U) (W) (k-l) a ;; -a;; a. j

(kl

4ji

j fj

(I (n) , , ,

, in, .

1 41 in, k j n+m; (1)

СЛ

Ha фиг. I представлена структур ная схема устройства для решения матричных задач для случая и на фиг. 2 - функциональная схема ij-ro операционного блока (ОБ) (i,j 1,п; ); на фиг. 3 - функциональ- ная схема ij-ro ОБ (,n+m; ,n; j) на фиг. 4 - временные диаграммы устройства.

20

Табл. 1 и 2 показывают логику работы ОБ.

Устройство для случая и (фиг, 1) содержит группы информаци- г онных входов 1,-, синхровход 2, операционные блоки 3 , ,3 j,, .,. , , выходы 4 и 4 . Размерности структуры устройства тип показаны пунктирными линиями (фиг. 1).ГО

Операционный блок 3jj() (фиг. 2) содержит группу входов 5, синхровход 6, регистр 7, узел 8 вычисления обратной величины числа, группы элементов И 9 и 10, группу 15 элементов ИЛИ 11, триггер 12, выход 13.

Операционный блок 3,-.(,п+т; j l,n; ) (фиг. 3) содержит первую группу входов 14, второй вход 15, синхровход 16, регистры 17- 19,.умножитель 20, вычитатель 21, триггеры 22-25, группы элементов И 26-29, группы элементов ИЛИ 30 и 31, элемент ИЛИ-НЕ 32, первую группу вькодов 33 и второй выход 34.

Рассмотрим работу ОБ 3;j (,n), логика работы которого показана в табл. 1. При подаче на 1 входов первой группы входов 5 значения элемента а, а на (1+1)-й вход 5 - нулевого сигнала, в регистр 7 записывается значение элемента з., триггер 12 устанавливается в нулевое состояние. С инверсного выхода триггера 12 единичный сигнал открьшает группу элементов И 10, через которую значение выхода узла 8 вычисления обратной величины числа подается на вход группы элементов ИЛИ 11. С выхода группы элементов РШИ 11 значение 1/а подается на выход 13 ОБ. Если триггер 12 устанавливается в единичное состояние, то открывается группа элементов И 9 и на выход 13 ОБ через группу элементов ИЛИ 11 подается значение элемента .

Рассмотрим работу ОБ 3 ,-j (,n+m; j ,n; ) (фиг. 3), Логика pa- . боты этого ОБ задается табл. 2.На нулевомтакте при подаче на 1 входов первой группы входов значения нулевых сигналов на (1+1)-й и (1+ +3)-й входы 1 в регистр 17 записывается значение Сg, триггеры 22 и 24 устанавливаются в нулевое состояние,, С выходов триггеров 22 и 24 нулевые сигналы подаются на входы элемента ИЛИ-НЕ 32, на выходе которого фор15099324

мируется единичный сигнал, разрешающий запись в регистр 19 и открывающий группу элементов И 26. Через группу элементов И 26 и группу элементов ИЛИ 30 значение подается на первьй вход умножителя 20. На второй

40

вход 15 ОБ подается значение Б, которое записывается в регистр 13, С выхода регистра 18 значение В подается на второй вход умножителя 20, на выходе которого формируется произведение , которое записывается в регистр 19. На первом такте подаются значение 1 входов I, нулевой сигнал на (1+1)-й вход 1 и единичный сигнал на (1+2)-й вход I, на второй вход 15 подается В, . В регистры 17 и 18 записываются соответственно значения с и В 24 -

Триггер

Останавливается в единичное состояние, единичньй сигнал открывает группы элементов И 27 и 29. На первьй вход умножителя 20 поддается через

25 группу элементов И 27 и группу элементов ИЛИ 30 произведение , на второй вход - значение выхода регистра 18. На выходе умножителя 20 формируется значение гВ, кото30 рое подается на вход вьтитателя 21, на второй вход которого подается значение Cg с выхода регистра 17, На выходе вьгчитателя 21 формируется значение Cg -rBgx которое через от35 крытую группу элементов И 29 и группу элементов ИЛИ 31 подается на 1 выходов, первой группы выходов 33, На (1+1)-м и (1+2)-м выходах 33 имеются нулевые сигналы, так как триггеры 23 и 25 находятся в нулевом состоянии.

50

На втором такте ОБ работает аналогично , Триггер 25 устанавливается в

45 единичное состояние. На (1+1)-й выход 33 подается нулевой сигнал, а на (1+2)-й выход 33 - единичный сигнал. На третьем такте на (1+1)-й вход 14 подается единичньгй сигнал, а на (1+2)-й вход 14 -нулевой сигнал. Триггер 22 устанавливается в единич- ное состояние, триггер 24 - в нулевое состояние, Открьшается группа элементов И 28, через которую с вы55 хода регистра 19 подается значение г В СвхНа вход группы элементов ИЛИ 31 и соответственно на 1 выходов 33, На (1+1)-й и (1+2)-й выходы 33 пода- ются соответственно нулевой и единич0

г О

5

мируется единичный сигнал, разрешающий запись в регистр 19 и открывающий группу элементов И 26. Через группу элементов И 26 и группу элементов ИЛИ 30 значение подается на первьй вход умножителя 20. На второй

0

вход 15 ОБ подается значение Б, которое записывается в регистр 13, С выхода регистра 18 значение В подается на второй вход умножителя 20, на выходе которого формируется произведение , которое записывается в регистр 19. На первом такте подаются значение 1 входов I, нулевой сигнал на (1+1)-й вход 1 и единичный сигнал на (1+2)-й вход I, на второй вход 15 подается В, . В регистры 17 и 18 записываются соответственно значения с и В 24 -

Триггер

Останавливается в единичное состояние, единичньй сигнал открывает группы элементов И 27 и 29. На первьй вход умножителя 20 поддается через

5 группу элементов И 27 и группу элементов ИЛИ 30 произведение , на второй вход - значение выхода регистра 18. На выходе умножителя 20 формируется значение гВ, кото0 рое подается на вход вьтитателя 21, на второй вход которого подается значение Cg с выхода регистра 17, На выходе вьгчитателя 21 формируется значение Cg -rBgx которое через от5 крытую группу элементов И 29 и группу элементов ИЛИ 31 подается на 1 выходов, первой группы выходов 33, На (1+1)-м и (1+2)-м выходах 33 имеются нулевые сигналы, так как триггеры 23 и 25 находятся в нулевом состоянии.

На втором такте ОБ работает аналогично , Триггер 25 устанавливается в

единичное состояние. На (1+1)-й выход 33 подается нулевой сигнал, а на . (1+2)-й выход 33 - единичный сигнал. На третьем такте на (1+1)-й вход 14 подается единичньгй сигнал, а на (1+2)-й вход 14 -нулевой сигнал. Триггер 22 устанавливается в единич- ное состояние, триггер 24 - в нулевое состояние, Открьшается группа элементов И 28, через которую с выхода регистра 19 подается значение г В СвхНа вход группы элементов ИЛИ 31 и соответственно на 1 выходов 33, На (1+1)-й и (1+2)-й выходы 33 пода- ются соответственно нулевой и единичгистр 17 записывается а

и

в регистр

Ш

18 - значение 1/а , в регистр 19 - значение а/, а ,j/а, (фиг. 4).

На третьем такте нулевое значение О и дополнительный разряд О подаются соответственно на 1-й и (1+1)-й вход 1 элемент дополнительные разряды О и 1 подаются соответственно на 1-й, (1+1)-й и (1+2)-й входы Ц, элемент дополнительные разряды О и 1 подаются соответственно на 1-й, (1+1 )-й и (1+2)-й входы Ц, . элемент а и дополнительные разряды О и О подаются соответственно на 1-й, (1+1)-й и (1+2)-й входы Ц.. В ОБ 3f} в регистр 7 записывается riy- левое значение, В ОБ 3 на выходе вычитателя 21 формируется значение

ный сигналы. На последующих тактах ОБ работает аналогичным образом.

Устройство работает следунлцим образом.

В исходном состоянии регистры 7, 17-19, триггеры 12, 22-25 устройства устанавливаются в нулевое состояние (фиг. 2 и 3, не показано).

Очередность подачи элементов 3;; и нулевого значения О , где t - номер (фиг. 1). Элементы аj, , ,п подаются на 1 входов первой группы входов 1 . Одновременно с эле- . ме«тами aj -Ha (1+1 )-й вход первой группы входов 1, подается на нулевом такте дополнительный разряд О, на 1,2,...,п-1 тактах - дополнительный разряд 1, на п такте - дополнительный 2Q разряд 0. Элементы а , (,п; , n+m) подаются на 1 входов первой группы входов 1; (,п+т). Одновременно с элементами (1+1 )-й и На четвертом такте li, мо- (1+2)-й входы I. (,n+in) подаются 25 жет подаваться элемент а, новой сис- ий (i-l)-M такте соответственно до- темы линейных уравнений или нулевое полнительные разряды О и О, на i, i+1,...,i+n-2 тактах - соответственно дополнительные разряды О и 1, на (i+n-l)-M такте - соответственно дополнительные разряды 1 и 0.

На нулевом такте элемент а и дополнительный разряд 0:подаются на вход ОБ 3, (фиг. 1). .В. регистр 7 ОБ 3 записывается элемент а,.

На первом такте элемент а . и дополнительный разряд I подаются соответственно на 1-й и (1+1)-й. входы и дополнительно раз,Ы,

32

(1)

п 31

а 3, . В ОБ Зэ,.на выходе

вычитателя 21 формируется значение а -aj,,aj,. В ОБ 3,jB регистр 7

,- гз

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

71

30

1 , элемент ряды О и О подаются соответственно на 1-й, (1+1)-й и (1+2)-й входы 1 (фиг. 1). В ОБ 3 в регистр 7 запиВ ОБ 3,, в резначение с дополнительным разрядом О, на 1-й, (Г+)-й и (1+2)-и входы 1- подаются соответственно нулевое

4

значение О и дополнительные разряды 1 и О, на 1-й, (1+1)-й и (1+2)-й входы 12 - соответственно элемент а дополнительные разряды О и 1, на 1-й, (1+)-й и (1+2)-й входы 1 соответственно элемент а и дополнительные разряды О и 1, на 1-й, (1+- +1)-й и (1+2)-й входы 1 - соответственно элемент а и дополнительные

40

сывается элемент а

21

гистр 17 записывается элемент а в регистр 18 - значение l/a, , в регистр 19 - значение ,,/а, . (фиг. 4).

На втором.такте элемент а и до- полнительньй разряд 1 подаются соответственно на 1-й и (1+1)-и входы 1, , элемент а,и дополнительные разряды О и 1 подаются соответственно на 1-й, (1+1)-й и (1+2)-й входы 1, элемент а и дополнительные разряды О и .0 подаются соответственно на 1-й, (1+О-й и (1+2)-й входы 1 . В ОБ 3, в регистр 7 записывается aj, . В ОБ 3,на.выходе вычитателя 21 фор45

разряды О и 0. В ОБ регистры 17 и 18 записываются нулевые значения. В ОБ 2г регистр 7 записывается элемент я,. В ОБ 3, формируется значение а, . В ОБ 3 .в регистр 19 записывается значение а с -2/a j-i. В ОБ 3, формируется значение , а, . В ОБ 3,в регистр 19 записывается значение

а

15

/а,

50

55

На пятом такте на 1-й, (1+1)-й и (1+2)-и входы Ij подаются соответственно нулевое значение О и дополнительные разряды 1 и О, на 1-й, (1+ +1)-й, (1+2)-й входы 1 соответственно элекент дополнительные разряды О и 1 на 1-й, (1+1)-й, (1+2)-й входы Ij подаются соответственно элемент и дополнительные разряды О и I . В ОБ 3,-в регистр 7 записываетмируется . В ОБ 3j,B ре- ся значение а,, В ОБ Зз, в регистры

гистр 17 записывается а

и

в регистр

18 - значение 1/а , в регистр 19 - значение а/, а ,j/а, (фиг. 4).

На третьем такте нулевое значение О и дополнительный разряд О подаются соответственно на 1-й и (1+1)-й вход 1 элемент дополнительные разряды О и 1 подаются соответственно на 1-й, (1+1)-й и (1+2)-й входы Ц, элемент дополнительные разряды О и 1 подаются соответственно на 1-й, (1+1 )-й и (1+2)-й входы Ц, . элемент а и дополнительные разряды О и О подаются соответственно на 1-й, (1+1)-й и (1+2)-й входы Ц.. В ОБ 3f} в регистр 7 записывается riy- левое значение, В ОБ 3 на выходе вычитателя 21 формируется значение

Q На четвертом такте li, мо- 5 жет подаваться элемент а, новой сис- темы линейных уравнений или нулевое

,Ы,

32

(1)

п 31

а 3, . В ОБ Зэ,.на выходе

вычитателя 21 формируется значение а -aj,,aj,. В ОБ 3,jB регистр 7

,- гз

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

71

2Q На четвертом такте li, мо- 25 жет подаваться элемент а, новой сис- темы линейных уравнений или нулевое

30

значение с дополнительным разрядом О, на 1-й, (Г+)-й и (1+2)-и входы 1- подаются соответственно нулевое

4

значение О и дополнительные разряды 1 и О, на 1-й, (1+1)-й и (1+2)-й входы 12 - соответственно элемент а дополнительные разряды О и 1, на 1-й, (1+)-й и (1+2)-й входы 1 соответственно элемент а и дополнительные разряды О и 1, на 1-й, (1+- +1)-й и (1+2)-й входы 1 - соответственно элемент а и дополнительные

40

5

разряды О и 0. В ОБ регистры 17 и 18 записываются нулевые значения. В ОБ 2г регистр 7 записывается элемент я,. В ОБ 3, формируется значение а, . В ОБ 3 .в регистр 19 записывается значение а с -2/a j-i. В ОБ 3, формируется значение , а, . В ОБ 3,в регистр 19 записывается значение

а

15

/а,

0

5

На пятом такте на 1-й, (1+1)-й и (1+2)-и входы Ij подаются соответственно нулевое значение О и дополнительные разряды 1 и О, на 1-й, (1+ +1)-й, (1+2)-й входы 1 соответственно элекент дополнительные разряды О и 1 на 1-й, (1+1)-й, (1+2)-й входы Ij подаются соответственно элемент и дополнительные разряды О и I . В ОБ 3,-в регистр 7 записывается значение а,, В ОБ Зз, в регистры

17 и 18 записываются нулевые значения. В ОБ 3jjформируется значение . В ОБ 3,формируете

-33 -5, -2,

значение aV:; а,, . В ОБ

,формируется . ..,, . В ОБ 3,,i регистр 19 записывается значение . В ОБ 3,,формируется значение

-J Г

15 21На последующих тактах ОБ устройства работают аналогичным образом.

Первый элемент

-5/3) . л .. -с

О)

тл

формируется

на восьмом такте на выходе 4,. На выходе на девятом такте форьетрует- ся элемент Xj,,, а элемент 1,

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

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

Q элементов И первой группы, второй вход которых соединен с прямым выходом триггера, а выход - с первыми входами элементов ИЛИ группы, вторые входы которых соединены с выходами

аз на десятом такте. Элементы X ,j, элементов И второй группы, вторые

(3) ,, Y 3; л, на tjwvnne лвходы КОТОрЫХ СОбДИНвНЫ С ИНВврСНЫМ

Х и X j формируются на выходе 4 соответственно на девятом, десятом и

одиннадцатом тактах (фиг, 1).

(.Устройство для решения матрргчно- го уравнения вида , где А - матрица регулярности п-п, X и В - матрицы размерности n.m (n,m - разрядность расширеной матрицы А/БЗ), содержащее n(n+l)/2+nm операционных блоков, причем i-й информационный вход (,n-(-m) устройства подключен

выходом триггера, информационный в1сод которого соединен с (1+1 )-м входом первой группы блока, синхроФормула изобретения. 20 вход которого соединен с входом разрешения записи регистра и с синхро- вкодом триггера, выход группы элементов ИЛИ является выходом блока.

3. Устройство по п. I, о т л и- 25 чающееся тем, что ij-й опе- рационный блок (, n+m; ,n, i-l /j) содержит три регистра, умножитель, вычитатель, четыре триггера, четыре группы элементов И, к входам первой группы il-ro операци- 30 .группу элементов ИЛИ и элемент РШИ- .онного блока, синхровход устройства НЕ, причем 1 входов первой группы подключен к синхровходам операцион- блока соединены с информационным вхо- ных блоков, о тличающееся .дом первого регистра, выход которого тем, что, с п,елью упрощения устрой- соеддаен с первым входом вычитателя ства, выход первой группы ij-r.o one- ,с и с первыми входами элементов И пер- рационного блока (,11; ,n-2; . вой группы, выходы которых соедине- . 1-2 / j) подключен к входам первой . ны с первыми входами элементов ИЛИ группы (1, j+l)-ro операционного бло- первой группы, вторые входы которых ка, 1 входов и (1+1)-й вход первой соединены с выходами элементов И группы (1 - разрядность элементов 40 второй группы, а ВЬЕКОДЫ - с первым матрицы) (1,1)-го операционного бло- входом умножителя, второй вход кока (,п) подключены соответствен- торого соединен с вторым выходом бло- но к 1 выходам и (1+2)-му выходу пер- ка и с выходом второго регистра, вы- вой группы (1,1-1)-го операционного ход умножителя подключен к информаци- блока, где 1 - разрядность элементов онному входу третьего регистра и

второму входу вычитателя, информаци-

матрицы, выходы первой группы ij-ro операционного блока (, п+т; ,n-l) подключены к входам первой . группы (1, j+l)-ro операционного блока, второй выход ij-ro операци- онного блока (,n+in-l; j l,Tn; i j) с оединен с вторым входом (1+1, j)-ro операционного блока, выход (.1,п-)-го операционного блока под50

онный вход второго регистра соединен с второй группой входов блока, выход вычитателя соединен с первыми входами элементов И четвертой группы, выход, которых соединен с первыми входами элементов ИЛИ второй группы, выход которых соединен с 1 выходами первой группы выходов блока, вторые

ключен к (1-п)-му выходу устройства входы элементов ИЛИ второй группы

/ «. -V.JJ

(, П+т).

2. Устройство по п. 1, отличающееся тем, что ij-onepa- ционный блок (,n) содержит ресоединены с выходами элементов И третьей группы, первые входы котор соединены с выходом третьего регис ра и с первыми входами элементов И

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

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

элементов И первой группы, второй вход которых соединен с прямым выходом триггера, а выход - с первыми входами элементов ИЛИ группы, вторые входы которых соединены с выходами

онный вход второго регистра соединен с второй группой входов блока, выход вычитателя соединен с первыми входами элементов И четвертой группы, выход, которых соединен с первыми входами элементов ИЛИ второй группы, выход которых соединен с 1 выходами первой группы выходов блока, вторые

соединены с выходами элементов И третьей группы, первые входы которых соединены с выходом третьего регистра и с первыми входами элементов И

1509932 О

второй группы, вход разрешения запи- щюнным входом второго триггера, выси третьего регистра соединен с объ- ход которого является (1+2)-м выходом единенными выходами элемента ИЛИ-НЕ первой группы выходов блока, синхро- и с вторыми входами элементов И первой группы, (1+1)-й вход первой труппы входов блока соединен с информационным входом первого триггера, выход которого соединен с первым входом элемента ИЛИ-НЕ, с вторыми входа- ю ми элементов И третьей группы и с информационным входом второго триггера, выход которого является (1+1)-м выходом первой группы выходов блока, (1+2)-и вход первой группы блока tS соединен с информационным входом третьего триггера, выход которого соединен с вторым входом элемента ИЛИ- НЕ, с вторыми входами элементов И

вход блока соединен с входами разрешения записи первого и второго регистров, с синхровходами первого, второго, третьего и четвертого триггеров.

Т а б л и ц а 1

Вх

1

J,

второй и четвертой групп и с информа- 20

щюнным входом второго триггера, выход которого является (1+2)-м выходом первой группы выходов блока, синхро-

вход блока соединен с входами разрешения записи первого и второго регистров, с синхровходами первого, второго, третьего и четвертого триггеров.

Т а б л и ц а 1

юнным входом второго триггера, од которого является (1+2)-м вы ервой группы выходов блока, син

Вх

1

J,

Изобретение относится к вычислительной технике и может быть использовано для решения систем линейных уравнений и обращения матриц. Целью изобретения является упрощение устройства. Устройство содержит N(N+1)/2 +NM операционных блоков

(I,I)-й операционный блок (I = 1,N) содержит регистр, узел вычисления обратной величины числа, две группы элементов И, группу элементов ИЛИ и триггер

(I,J)-й операционный блок (I = 2, N+M, J = 1,N,I-1≥J) содержит четыре триггера, три регистра, умножитель, вычитатель, четыре группы элементов И, группу элементов ИЛИ и элемент ИЛИ-НЕ. Поставленная цель достигается за счет реализованных структурных решений. 2 з.п. ф-лы, 4 ил., 2 табл.

Таблица 2