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

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

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

На фиг.1 представлена схема предлагаемого устройства для обращения матриц; на фиг.2 - схема блока ввода; на фиг.З - схема вычислительного блока; на фиг.4 - схема блока вывода; на фиг.5 - схема арифметического узла; на фиг.6 - схема коммутатора.

Устройство содержит генератор 1 тактовых импульсов, триггер 2, прямой выход 3 триггера 2, обратный выход 4 триггера 2, счетчик 5, выход 6 счетчика 5, группу входов устройства 7, бпок 8 ввода, вычислительный блок 9, вторую группу информационных входов 10 блока ввода, блок 11 вывода, группу выходов 12 устройства. Блок ввода 8 содержит (N +1) мульти - плексоров 13, (N4+l) элементов И 14. Вычислительный блок 9 содержит (N+1) регистров 15, умножитель 16,(2N-1) делителей 17$ (N-1) инверторов 18, (N-1)4 арифметических узлов 19, коммутатор 20, (N2+l) регистров 21. Блок вывода 11 содержит () элементов И 14. Арифметический узел 19 ij (где i,j 1, N-1) содержит умножитель 22, сумматор 23.

В устройстве реализован алгоритм для обращения матрицы порядка N, основанный на методе исключения. Обращение матрицы А порядка N происходит за N итераций. На каждой итерации

сл

4 СЛ ГО

вычисляется новая матрица А(п , где n 1,N, следующим образом

4

Здесь А- А 1- If I ЛJ

- искомая обращенная матри, (МП га V С ,j J

ца. Для вычисления определителя матрицы А вводится дополнительный эле- (о)

мент

1

0 . и на каждой итерации параллельно с вычислением промежуточной матрицы А П вычисляется значение а

«О

где n 1,N, следующим

образом:

г

,(«- )

1.1

det A а

(}

При включении устройства триггер 2 устанавливается в О, 3

т.е. на прямом выходе

ется О, а на обратном выходе

П ( It

триггера 2 устанавлива4

триггера 2 устанавливается . Счетчик 5 устанавливается в О, на выходе 6 счетчика 5 - О. На выходе 6 счетчика 5 устанавливается 1 только тогда, когда содержимое счетчика 5 меняется с О на 1. Во всех остальных случаях на выходе 6 счетчика 5 - О. Устройство готово к работе.

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

С выхода генератора 1 тактовых импульсов поступает на вход триггера 2 тактовый импульс, в результате чего триггер 2 меняет свое состояние на обратное, т.Р. на прямом выходе 3 триггера 2 устанавливается , на обратном выходе 4 триггера 2 устанавливается О. Содержимое счетчика 5 увеличивается на 1 только тогда, когда на прямом выходе 3 триггера 2 устанавливается 1, поэтому на первом такте в счетчике 5 устанавливается 1. Если в счетчике 5 записано (N-1), то при установке 1 на

0

0

5

0

5

прямом выходе триггера 2 устанавливается О. На выходе 6 счетчика 5 устанавливаете 1, которая по.сту- пает на первый управляющий вход блока 8 ввода и с первого управляющего входа на управляющие входы мультиплексоров 13, которые работают следующим гбразом: если на управляющем входе 1, то на выход пропускают данные с входов 7; если на управляющем входе О, - то данные с входов 10. Вследствие того, что на управляющие входы мультиплексоров 12 подана 1, то с входов 7 пропускаются

панные а(0 я(0 я(0 данные afl , а , а , ...,aNN

и,

-и Чг

так как с прямого выхода 3 триггера 2 на управляющие входы элементов И 4 блока 8 ввода и на тактовые входы регистров 15 подается 1, данные поступают на информационные входы вычислительного блока 9 и записываются в регистры 15, причем в регистр 15 записывается элемент а , а в регистр 15,j , где i,j мент aW .

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

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

ii

формируется а(°

в регистр 21 . На выходе делителя 17,, формируется и поступает на 1.1 вход коммутатора 20.На выходе делителя 17; , где i 2,и, формирует((Л , (

с.я , /а1( , на выходе елителя 7-. где j N + I, , форми- l (crt /„ (ot

руется

. 5

Nfl

и поступает

на j - N + 1. 1 вход коммутатора 20. На выходе инвертора 58(, где

i

- Ы

(о)

1, N -1, формируется -а. /atl

i t t ui

0

0

и поступает на l.i +1 выход коммутатора 20 и на первые входы арифметических узлов 19 } где j 1, N-. Одновременно с этим генератор 1 тактовых импульсов вырабатывает следую- 5 Щий тактовый импульс, который, поступая на вход триггера 2, устанавливает его в обратное состояние, т.е. на прямом выходе 3 триггера 2 устанавливается О, а на обратном выходе 4 триггера 2 устанавливается 1. С прямого выхода 3 триггера 2 О, поступая на вход счетчика 5, не изменяет его содержимое, на выходе 6 счетчика 5 присутствует О. О на прямом выходе 3 триггера 2 не позволяет записывать информацию через блок 9 ввода в регистры 15, 1 с обратного выхода 4 триггера 2 подается на тактовые входы арифметичес5

ких узлов 19 и синхронизирует поступающие на их информационные входы

данные. На выходе арифметического I

узла 19-;, где i,j 1,N-1, форми- У(о + я(о) . я(о) ,«,,.

/руется а ч , . . „

m.jtf -n,i 1, jti ,

и поступает на i + I , j + 1 вход коммутатора 20. Из коммутатора 20 данные поступают ка информационные входы регистров 21 (фиг.6) и записываются в них. Таким образом в регистре 21„

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

М

в регистр 21

i.J

где i,j IjN, записывается аФ . Генератор 1 тактсвых импульсов- вырабатывает третий тактовый импульс, который поступает на счетный вход триггера 2, в результате чего на пря мом выходе 3 триггера 2 устанавливается , а на обратном выходе 4 триггера 2 устанавливается О. Содержимое счетчика 5 становится 2, на выходе 6 счетчика 5 - О. С прямого выхода 3 триггера 2 1 подается на тактовые входы регистров 15 и 21 и на управляющие входы элементов И 14 блока 9. С выхода 6 счетчика 5 О подаётся на управляющие входы мультиплексоров 13 блока 9, в результате чего происходит считывание из регистров 21, данные из которых подаются на информационные входы 10 блока 8 ввода. Через мультиплексоры 13 данные проходят с входов 10 и далее проходят через элементы И 14 блока 8 ввода и поступают на входы регистра 15. Далее устройство работает аналогично первому такту. На 4-м, 6-м,(2N}-rM тактах

устройство работает аналогично второму такту; на 5-м, 7-м,...,(2N-1)-м тактах - аналогично третьему такту. В конце такта в регистре 21ffnpHcyT Ю о

ствует а

т.е. det А. В регист(Ю

ре 21;tj, где i,j 1,N; а1:У ,эле- мент искомой обращенной матрицы А . На (2N + такте на входы 7 блока 8 ввода можно подавать элементы следующей матрицы В, подлежащей обращению. Генератор 1 тактовых импульсов вырабатывает (2N + l)-& тактовый импульс, который поступает на счетный вход триггера 2. В результате этого на прямом выходе 3 триггера 2 присутствует 1, и поэтому содержимое счетчика 5 изменяется с О на 1 и,следовательно, на выходе 6 счетчика 5 присутствует 1, тем самым элементы новой матрицы В с

75204 6

входов 7 блока 8 ввода через мульти- штексоры 13 и элементы И 14 блока 8 ввода записываются в регистры 15 вычислительного блока 9, а из регистров 21 через элементы И 14 блока 11 ввода считываются элементы первой обрашенной матрицы А . На (4N + 1)-м такте на выходах 12 блока вывода при10

-ii

сутствуют элементы матрицы В i Формула изобретения

.J

аря-а, ятивотстм. . ь2|

15

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

группы которого образуют группу N+1 входов устройства (N - размерность обращаемой матрицы), группа N4+l выходов которого образована группой

выходов блока вывода, выход генератора тактовых импульсов подключен к . входу триггера, прямой выход которого соединен со счетным входом счетчика, отличающееся тем, что,с целью расширения функциональных воз3° можностей за счет вычисления определителя обращаемой матрицы, в устройство введен вычислительный блок, 1-й информационный вход которого (i 1, N1) подключен к одноименно35 му выходу блока ввода, i-й информационный вход второй группы которого подключен к одноименному информационному входу блока вывода и выходу вычислительного блока, первый управля-

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

t

45 блока, содержащего N +1 входных

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

второму входу умножителя и первым входам,всех делителей второй вход j-ro делителя (j 2,N) подключен к|выходу (j+l)-ro входного регистра, второй входК-го делителя (,2N-1) подключен к выходу (N(K-N) + +2)-то входного регистра, выход первого делителя подключен к первому аходу коммутатора, j-й вход которого соединен с первым информационным вхо- дом (т,;)- )то арифметического узла ( N-1) и с выходом (j-l)-ro ин- . вертора, вход которого соединен с выходом j-ro делителя, выход К-го делителя подключен к (N()+1)-му входу коммутатора , 1-й выход которого (1 . подключен к информационному входу (l-H)-ro выходного регистра, второй информационный вход (т,п)-го арифметического узла (,N-l) подключен к второму входу (n+N)-ro де- дителя, третий информационный вход и выход (m,n)-ro арифметического уз

5

0

ла подключены, соответственно к выходу (mN+2+n)-го-входного регистра и (тЫ+1+п)-му входу коммутатора, входы разрешения записи входных регистров, объединенные между собой, соединены с входами разрешения чтения выходных регистров и подключены к первому управляющему входу .вычислительного блока, второй управляющий вход которого соединен с тактовыми входами всех арифметических узлов, каждяй из которых содержит умножитель, и сумматор, причем, первый и второй информационные входы умножителя являются соответ ственно первым и вторым информационными входами арифметического узла, тактовым входом которого является тактовый вход умножителя, выход которого соединен с первым входом сумматора, второй вход и выход которого являются соответственно третьим информационным входом и выходом арифметического узла.

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных матричных вычислителях. Целью изобретения является расширение функциональных возможностей устройства за счет вычисления определителя обращаемой матрицы. В устройстве, содержащем генератор тактовых импульсов, триггер, счетчик, блоки ввода и вывода и вычислительный блок, реализован метод исключения обращения матрицы, основанный на алгоритме Гаусса-Жордана. Модификация традиционного алгоритма заключается в перестановке строк и столбцов на каждом шаге рекуррентной процедуры обращения матрицы. 6 ил.

to

Фиг 2

Фг/г4

1

н

3-r

Ф.5

Редактор С.Лисина

Составитель К.Кухаренко

Техред М.Ходанич Корректор М.Кучерявая

Заказ 1786

Тираж 568

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ CQCP 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат Патент, г. Ужгород, ул. Гагарина, 101

Фиг.6

Подписное