Устройство для обращения матриц и решения систем линейных уравнений Советский патент 1988 года по МПК G06F17/16 G06F17/11 

00

ю

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

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

В основу работы предлагаемого устройства положен метод Гаусса- Жордана, при котором для решения системы из п линейных уравнений с т-правыми частями, расширенная матрица LА. 1в сводится к пХ(п+т)-матри.це Е 1 Х1,где Е - единичная (пХп)-мат- рица, по рекуррентным соотношениям

М

i,n; ,n+ra;

l -; ; +

.

. -Kj

П n + m

.i - обращения плотной (nvn)-матрицы расширенная (nx2n)-матрица Е сводится к ()-матрице по рекург рентным соотношениям (1), в этом слу чае и В Е,

На фиг.1 представлена структурная схема устррйства; на фиг.2 - функциональная схема Ij-ro операционного блока (ОБ); на фиг.З - функцио- нальная схема ij-ro ОБ (,п; j , ,п); на фиг.4 временные диаграммы устройства.

Устройство для случая и (фиг. 1) содержит гр-уппы 1, , 1 д., Ц информационных входов, операционные блоки 2„ ,2,i,...,2,3) регистры 3, Ъ, 3, синхровход 4 и выходы 5м Sj., и 5,. ОБ 2,j (j l,n) (фиг.2) содержит первую группу входов 6, синх- ровход 7, регистры 8 и 9, узел деления 10, триггеры 11 и 12, элементы И 13 и I i, группу элементов И 15, элемент НЕ 16 и 17 выходов блока. ОБ 2, j (,n; j-l,n) (фиг.З) содержит первую группу входов 18, вторую группу входов 19, синхровход 20, регистры 21 - 23, умножитель 24, вычитатель 25, триггеры 26 - 28, эле

0

5

0

5

0

5

0

5 д

менты И 29 к 30, элемент НЕ 31, группу элементов И 32, первую группу выходов 33 и вторую группу выходов 34.

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

В исходном состоянии регистры 3,, 3;t Зз, 8, 9, 21, 22, 23, триггеры 11, 12 , 26, 27 и 28 устройства устанавливаются в нулевое состояние (непоказано) .

Очередность подачи элементов а- , где t -номер такта, показана на фиг, 1 . Элементы а, подаются на 1 входов первой группы входов Ij , соответствующих ОБ (,n). Одновременно с элементами а- на (1+1)-и вход первой группы входов 1 j. ОБ 2, (i 1,п) подается дополнительный разряд , принимающий значение О для случая а- или 1 для а;: , j 1. В общем случае на (1+1)-и вход первой или второй групп входов ОБ 2 устройства подается дополнительный раз(fl

ряд, равный О, если a;-(), иначе дополнительный разряд )(- равен 1, где k - номер рекуррентного шага.

На нулевом такте элемент а° и дополнительный разряд О подаются соответственно на 1 входов и (1+1)-й вход первой группы выходов 1 , ОБ 2 , , При этом на вход элемента НЕ 16 подается нулевой сигнал и на его выходе формируется единичный сигнал, который открьшает элемент И 14 и соответственно разрешает запись элемента в регистр 9 (фиг.2),

На первом такте элемент а, и дополнительный разряд 1 подается на вход 1I, элемент а и дополнительный разряд О - на вход 1 (фиг.1). В ОБ 2 (, в регистр 8 записывается элемент а т.к. на вход элемента И 13 подается дополнительный единичный разряд и на его выходе формируется единичный сигнал, который разрешает запись в регистр 8 (фиг,2 и 4). Триггер 11 устанавливается в единичное состояние. На выходе узла . деления 10 формируется значение

тые элементы И 15 подается на вход 17. В ОБ 2J, аналогичным образом элемент aj, записьгоается в регистр 22,

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

а Ia которое через открыи дополнительный разряд 1, на вход Ij - элемент а,,, и дополнительный разряд О (фиг.1). В ОБ 2,, в регистр 8 записьгаается элемеит a,j , триггер 1I находится в единичном состоянии, триггер 12 устанавливается в единичное состояние, на выходе узла делет ния формируется значение ajV a,}/a,j , которое подается на выход 17 (фиг.2 и 4). В ОБ 2 г, в регистр 21 записьгоается элемент а,,, триггер 26 устанавливается в единичное состояние, в регистр 23 записьшается

45

(О 111

Ij - элемент

и дополнительный единичный раз В OR 2 1 формируется значение

а,,, , в ОБ 2 21 - значени 324 3Hajj,B ОБ 2, - значеныи разряд, на вход

-я ряд,

М

ние а„ а ,,

- .

о

я

в ОБ 2,i10

S il В ОБ . в регистр

22 записьшается элемент а

(О

31

элемент а

(О iz

в ое

гистр 3, записьшается элемент с дополнительным нулевым разрядом.

пятом такте на вход 1. может пода- .

триггер 28 находится в 15 ваться элемент а новой матрицы А

Ij - элемент

и дополнительный единичный раз- В OR 2 1 формируется значение

а,,, , в ОБ 2 21 - значение 324 3Hajj,B ОБ 2, - значеазряд, на вход

ние а„ а ,,

- .

о

я

в ОБ 2,i

S il В ОБ . в регистр

22 записьшается элемент а

(О

31

в оегистр 3, записьшается элемент с дополнительным нулевым разрядом. В

пятом такте на вход 1. может пода- .

ваться элемент а новой матрицы А

Изобретение относится к вычислительной технике и может быть использовано для решения систем линейных уравнений и обращения матриц. Целью изобретения является расширение функциональных возможностей. Устройство содержит п операционных блоков и п регистров, где п - количество уравнений системы. Операционный блок (i,j), где i 2,п; j 1,п, содержит три регистра, умножитель, вычи- татель, три триггера, два элемента И, элемент НЕ, группу элементов И. One- рационный блок (l,j), где j , содержит два регистра, узел деления, два триггера, два элемента И, группу элементов И и элемент НЕ. Поставленная цель достигается за счет использованных структурных решений. 2 з,п, ф-лы, 4 ил. с s (Л

нулевом состоянии, на выходе умножителя 24 формируется значение a J ч , которое поступает на вход вычи тателя 25, на второй вход которого подается элемент а. на выходе вы- читателя 25 формируется значение

(О (1)

На третьем такте на вход 1, подаются элемент а, и дополнительный разряд 1, на вход элемент а и дополнительный разряд 1, на вход

Ц а ,2 и дополнительный разряд 1

В ОБ 2 ц фррмируется значение (t)

а

и

а,/а

II

В ОБ 221 в регистр 2 записьшается элемент а, в регистр 23 - элемент а ,5 триггеры 26 - 28 находятся в единичном состоянии, на выходе вычитателя 25 формируется значение гъ о 21 которое подается через открытые элементы И 32 на выход 33 с дополнительным единичным разрядом (фиг.З и 4). В ,ОБ 2, в регистр 21 записывается элемент а.,, , в регистр 23 - элемент

()

триггер 26 находится в единич а,2.ном состоянии, а триггеры 27 и 28 - в в нулевом. На выходе вычитателя 25 формируется значение а - . а . которое подается на выход 33 с дополнительным нулевым разрядом (фиг.З и 4). В ОБ 22, в регистр 9 записьшается элемент а (фиг.2)

На четвертом такте на вход 1.

дается элемент а,

и дополнительный

единичный разряд, на вход 1 элемент и дополнительный единичили нулевое значение с дополнительным нулевым разрядом, на вход L подаете-

ся элемент а,у с дополнительным единичным разрядом, в ОБ 2, в подачи нулевого значения с дополнительным нулевым разрядом регистр 9 и триггер 11 устанавливаются в нулевое состояние (фиг.2 и 4), в ОБ 2,

rbODMHDVeTCH ЧНЯЧйНИР Я-,- Я-,-

5

формируется значение а

15

125

- .( 1

t

. а

71

в ОБ 2 Я1 - значение

.оОГ

Э4

в ОБ 2,л - значе-12.

0

в регистр 3. записьшается

- а а

34 Н Э1

ние , в ОБ . - значе- ние а Д- ,. ,, в ОБ 2,. в регистр 22 записьшается элемент

я

а j , D п Ц1 |

элемент а, с единичным дополнительным разрядом.

5 На последующих тактах ОБ устройства работают аналогичным образом, Первый элемент X,f а формируется на восьмом такте на выходе 33 ОБ 2i, (на выходе устройства 5).

Элемент -формируется на

21

девятом такте на выходе ОБ Sj эле- на десятом так-

мент X 5, а 3

5

те на выходе регистра 3 (на выходе устройства 5). Элементы , Х,,

0

W X J, фиксируются соответственно на

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

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

операционного блока (i,n)5 синхро- вход устройства подключен к синхро- входам операционных блоков, отличающееся тем, что, с целью расширения функциональных возможностей путем решения систем из п ли нейных уравнений с m правыми частями, в него введены п регистров, причем синхровход устройства подключен к синхровходам регистров, выходы группы Ij-ro операционного блока подключены к входам второй группы 2j-ro операционного блока (), выходы первой группы ij-ro операцион кого блока подключены к входам первой группы (-1 лj +1)го операционног блока (1-Г,п| ,n-l), выходы второй группы ij-ro операционного блока подключены к входам второй группы (i+l,j)-ro операционного блока

(,n-l;3 1,п), выходы второй группы nj-ro операционного блока подключены к информационному входу j-ro регистра ( ,п) , выход j-ro регистра

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

г

5

0

о 5

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

Фае.