Устройство для обращения матриц

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН

))5 G 06 F 15/347

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ THHT СССР

К д ВТОРСНОМУ СВИДЕТЕЛЬСТВУ (21) 4421734/24-24 (22) 05.05.88 (46) 30.06.90. Бюл. )) 24 (72) А.П.Царев и И.И.Чебан (53) 681,325(088.8) (56) Авторское свидетельство СССР

Р 1387013, кл. G 06 F 15/347,1986.

Авторское свидетельство СССР

Р 1339585, кл. G 06 F 15/347, 1985. (54) УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ МАТРИЦ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализи, рованных матричных вычислителях, Изобретение относится . к вычислительной технике, предназначено. цля выполнения операций, связанных с обращением матриц, и может быть использовано в специализированных устройствах обработки информации при решении задач, сводящихся к действиям над матрицами.

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

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

Устройство содержит генератор 1 тактовых импульсов, триггер 2, прямой выход 3 триггера 2, обратный вы„„SU„„1575204 А 1

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

Гаусса-Жорцана. Модификация традиционного алгоритма заключается в перестановке строк и столбцов на каждом шаге рекуррентной процедуры обращения матрицы. 6 ил. ход 4 триггера 2, счетчик 5, выход 6 счетчика 5, группу входов устройства 7, бпок 8 ввода, вычислительный блок 9, вторую группу информационных входов )0 блока ввода, блок ll вывода, группу выходов 12 устройства.

Блок ввода S содержит (N +1) мульти

2 плексоров 13 (N +)) злементов И 14.

Вычислительный блок 9 содержит (N +l) регистров 15, умножитель 16,(2N-)) делителей !7, (N-1) инверторов. 18, (М-l) арифметических узлов 19, коммутатор 20, (И +1) регистров 21

Блок вывода 11 содержит (N +I) злементов И 14. Арифметический узел 19 ij (где i j = 1, N — 1) содержит умножитель 22, сумматор 23, В устройстве реализован алгоритм для обращения матрицы порядка N, основанный на методе исключения. Обращение матрицы А порядка N происходит за М итераций. На каждой итерации

1575204

= N

I,N-l,j=N (n-<) а 11 (n- )

1+( (и-t

-а

4д

N j = N- l

55 вычисляется новая матрица А, где (n)

n = 1,N, следующим образом

n-< (ь- ) („.1) à i o а, ° +а,,— — —, i,j = 1,Ж вЂ” 1 (+11tt +я((tt ) а t,t (о) г (о) ) — t ((l)

Здесь А =А = (а ; А =А

Г (N))

=!а (— искомая обращенная матри11 ца, Для вычисления определителя матрицы А вводится дополнительный эле(о) мент а о = l и на каждой итерации .параллельно с вычислением промежуточной матрицы А(" вычисляется значение а ", где n - =1,N, следующим (о) образом: (n) (n- ) о о (н)

A a a °

При включении устройства триггер 2 устанавливается в "О", т.е. на прямом выходе 3 триггера 2 устанавливается "0", а на обратном выходе 4 триггера 2 устанавливается "!". Счетчик 5 устанавливае-ся в "О", на выходе 6 счетчика 5 — "О". На выходе 6 счетчика 5 устанавливается "1" только тогда, когда содержимое счетчика 5 меняется с "О" на "1". Во всех остальных случаях на выходе 6 счетчика 5 — "О". Устройство готово к работе.

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

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

10 ! 5

35 прямом выходе триггера 2 устанавливаегся "О". На выходе 6 счетчика 5 устанавливается "1", которая поступает на первый управляющий вход блока 8 ввода и с первого управляющего входа на управляющие входы мультиплексоров 13„ которые работают следующим образом: если на управляющем входе "1", то на выход npoïóñêèîò данные с входов 7; если на управляющем входе "О", — то данные с входов 10. Вследствие того„ что на управляющие входы мультиплексоров !2 подана 1, то с входов 7 пропускаются и в данные а ; а, а,...,а,„д и, (о) .. (a) (о) (а>

1, I t, 2 М М так как с прямого выхода 3 триггера 2 на управляющие входы элементов

И 14 блока 8 ввода и на тактовые входы регистров !5 подается "1", данные поступают на информационные входы вычислительного блока 9 и записываются в регистры 15, причем в регистр 15 записывается элемент а(, а в ре(о) гистр 15, где i,j = 1,N, эле-. мент a "") . (о)

lP

Далее на выходе умножителя 16 формирует ся а о а „, и з аписыв ае тс я (o) (a)

1,1 в регистр 21 . На выходе делителя 17. формируется 1/а(,) и поступает на

1.1 вход коммутатора 20. На вьиоде делителя 17.;, где i = 2,N, формируеч(о) ся а(; /а „), на вьиоде;.(елителя 17,, где j = М + l, 2N — 1, форми(о) (о( руется а,,о-.(1., /а „ и поступает

I 11 на j -Н +1.1 вход коммутатора 20.

На выходе инвертора 18, где

f0)

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

Э У

1. -< t tit и поступает на l.i + 1 выход коммутатора 20 и на первые входы арифметических узлов 19 " где j 1 N — 1.

9 Ф

Одновременно с этим генератор 1 тактовых импульсов вырабатывает следующий тактовый импульс, который, поступая на вход триггера 2, устанавливает его в обратное состояние, т.е. на прямом выходе 3 триггера 2 устанавливается "0", а на обратном выходе 4 триггера 2 устанавливается "1".

С прямого выхода 3 триггера 2 "О", поступая на вход счетчика 5, не изменяет его содержимое, на выходе 6 счетчика 5 присутствует "0". "0" на прямом вьиоде 3 триггера 2 не позволяет записывать информацию через ,блок 9 ввода в регистры 15, "!" с обратного выхода 4 триггера 2 подается на тактовые входы арифметичес1575204 ких узлов 19 и синхронизирует поступающие на их информационные входы данные ° На выходе арифметического

I узла 19 ;, где i j =- 1,N — 1, формируется а" < (+ а (1 . а ((1

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

1 в/Э где i,j = 1,N, записывается а1 1 (1

Генератор 1 тактсвых импульсов"вырабатывает третий тактовый импульс, который поступает на счетный вход триггера 2, в результате чего на пря мом выходе 3 триггера 2 устанавливается "1", а на обратном выходе 4 триггера 2 устанавливается "0". Содержимое счетчика 5 становится "2", на выходе 6 счетчика 5 — "0". С прямого выхода 3 триггера 2 "1" подается на тактовые входы регистров 15 и 21 и на управляющие входы элементов И 14 блока 9. С выхода 6 счетчика 5 "0" подается на управляющие входы мультиплексоров 13 блока 9, в результате чего происходит считывание из регистров 21, данные из которых подаются на информационные входы 10 блока 8 ввода. Через мультиплексоры 13 данные проходят с входов 10 и далее проходят через элементы И 14 блока 8 ввода и поступают на входы регистра 15. Далее устройство работает аналогично первому такту. На 4-м, 6-м,....,(2N) †.м тактах: устройство работает аналогично второму такту; на 5-м, 7-м,...,(2N-1)-м тактах — аналогично третьему такту.

В конце такта в регистре 21 присут(М ствует а, т.е. det А. В регистре 21;, где i, j = l N; а(.".,элемент искомой обращенной матрицы А

На (2N + 1)-м такте на входы 7 блока 8 ввода можно подавать элементы следующей матрицы В, подлежащей обращению. Генератор 1 тактовых импульсов вырабатывает (2N + 1)-й тактовый импульс, который поступает на счетный вход триггера 2. В результате этого на прямом выходе 3 триггера 2 присутствует "1", и поэтому содержимое счетчика 5 изменяется с "0" на

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

Формула

t0 ного регистра, выход первого входного регистра подключен к первому вхо55 ду умножителя, выход которого подключен к информационному входу первого выходного регистра, выход второго входного регистра подключен к

Устройство для обращения матриц, содержащее блок ввода, блок вывода, l5 генератор тактовых импульсов, триггер, счетчик, выход которого подключен к управляющему входу блока вывода и первому управляющему входу блока ввода, информационные входы первой и группы которого образуют группу N+I входов устройства (N - размерность обращаемой матрицы), группа N +1 выходов которого образована группой выходов блока вывода, выход генератора тактовых импульсов подключен к входу триггера, прямой выход которого соединен со счетным входом счетчика, о т л и ч а ю щ е е с я тем, что,с целью расширения функциональных возЗО можностеи за счет вычисления определителя обращаемой матрицы, в устройство введен вычислительный блок, i-й инфо эма аионный вход которого (i = 1, N +1) подключен к одноименно35 му выходу блока ввода, i-й информационный вход второи группы которого подключен к одноименному информационному входу блока вывода и выходу вычислительного блока, первый управля4Q ющий вход которого подключен к второму управляющему входу блока ввода и прямому выходу триггера, инверсный выход которого подключен к второму управляющему входу вычислительного . и

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

° является i-м информационным входом вычислительного блока, i-м выходом которого является выход i-го выход1575204 второму входу умножителя и первым входам, всех делителей второй вход

j-ro делителя (j = 2,N) подключен к).выходу (j+I)-го входного оегиогоа, второй вход К-го делителя (K=N+1 2N-1) подключен к выходу (N(K-N) + +2)-го входного регистра, выход первого делителя подключен к первому входу коммутатора, j-й вход которого соединен с первым информационным вхо,:дом (m,j"1)-го арифметического узла (п11 у N-1) и с выходом (j-1)-го инвертора, вход которого соединен с выходом j-го делителя, выход К-го делителя подключен к (N(K-N)+1)-му входу коммутатора, 1- и выход которого (1 1,N+) подключен к информационному входу (1+1)-го выходного регистра, второй информационный вход (m,ï)-ro арифметического узла (n=1,N-1) подключен к второму входу (n+N)-ro дегщтеля, третий информационный вход и выход (m,n)-ro арифметического узг ла подключены, соответственно к выхору (mN+2+n)-ro- входного регистра и (mN+1+n)-му входу коммутатора, входы разрешения записи входных регистров, объединенные между собой, соединены с входами разрешения чтения выходных регистров и подключены к первому управляющему .входу .вычислительного блоКа, второй управляющий вход которого соединен с тактовыми входами всех арифметических узлов, каждый из которых содержит умножитель, и сумматор, причем, первый и второй информацион15 ные входы умножителя являются соответ ственно первым и вторым информационными вхоцами арифметического узла, тактовым входом которого является тактовый вход умножителя, выход кото20 рого соединен с первым входом сумматора, второй вход и выход которого являются соответственно третьим информационным входом и выходом арифметического узла.

1575204

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

Заказ 1786 Тираж 568 Подписное

ВНИИПИ Государственного комитета по изобретениям и открьггиям при ГКНТ С СР

113035, Москва, Ж-35, Раушская наб., д. 4/5

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

У, И.

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

Техред M.Õîäàíè÷ Корректор М.Кучерявая