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

 

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

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

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

РЕСПУБЛИК

А1 (19) (11) (51) 4 С 06 F 15 347

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕН Я:, -"""

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ =- —— (21) 4182130/24-24 (22) 13.01.87 (46) 15,12.88.Бюл. 1Р 46 (72) В.П.Якуш, С.Г.Седухин, Л.Б.Авгуль, А.Н.Семашко и О.В.Подрубный (53) 681,325 (088.8) (56) Авторское свидетельство СССР

N - 12!1754, кл. G 06 F 15/347, 1984, Авторское свидетельство СССР

N - 1387013, кл. G 06 F 15/347, 21.10.86. (54) УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ МАТРИЦ И РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВ-.

НЕНИЙ (57) Изобретение относится к вычислительной технике и может быть использовано для решения систем линейных уравнений и обращения матриц. Целью изобретения является расширение функциональных возможностей. Устройство

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

1444820 (k-i) I (К-i)

/а ц (к- ) (к-i) (К

1сс3(п + m

25 (к) °

1с ) п + ш а

k) (к)

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

В основу .работы предлагаемого устройства положен метод ГауссаЖордана, при котором для Решения системы из и линейных уравнений 15

АХ=В с m-правыми частями, расширенная матрица PAIB) сводится к пХ(п+ш)-матри .це (E ) Х J,где Š— единичная (пХп)-матрица, по рекуррентным соотношениям

20 для а; = а;; 1=1,п; )=1,n+m, 1с1,пi

X. = a . 16 i п 1 — ) "m (й) (nI

1) (,ð+) Для обращения плотной (nxn)-матрицы расширенная (пх2п)-матрица )A j E) сводится к (EJA )-матрице по рекур» рентным соотношениям (1), в этом слу- 35 чае ш=п и В = E, На фиг,l представлена структурная схема устройства; на фиг.2 — функциональная схема lj-ro операционного блока (ОБ); на фиг.3 — функцио- 10 нальная схема ij-ro ОБ (i=2,n; j

l,п); на фиг.4 — временные диаграммы устройства..

Устройство для случая п=3 и m=2 (фиг.l) содержит группы 1,,1,1з информационных входов, операционные блоки 2ц,2, ...,,2, регистры 3,, 3, 3, синхровход 4 и выходы 5, 5, и 5з. ОБ 2 ) (j=l ï) (фиг.2) содержит пеРвую гРуппу входов 6, синхровход 7, регистры 8 и 9„ узел деления 10, триггеры 11 и 12, элементы

И 13 и III, группу элементов И 15, элемент НЕ 16 и группу 17 выходов блока. ОБ 2," (i=2,ï; j=l,п) (фиг.3) содержит первую группу входов 18, ВТор группу ВхороВ 19» синхровход

20, регистры 21 — 23, умножитель 24, вычитатель 25, триггеры 26 — 28, эле1 менты И 29 и 30, элемент НЕ 31, группу элементов И 32, первую группу выходов 33 и вторую группу выходов 34, Устройство работает следующим образом.

В исходном состоянии регистры 3„,, 3, 3, 8, 9, 21, 22, 23, триггеры

11, 12, 26, 27 и 28 устройства устанавливаются в нулевое состояние (непоказано).

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

t ) первой группы входов 11 ОБ 2,, (i

=l,n) подается дополнительный разряд, принимающий значение О для случая а ° или l для а;., j )1. В

+. общем случае на (1+1)-й вход первой или второй групп входов ОБ 2 устройства подается дополнительный разряд )(-, равный О, если а .; (i-l=k) иначе дополнительный разряд .+ равен

1, где k — - номер рекуррентного шага. о

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

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

l вход 1, элемент а, и дополнительный разряд 0 — на вход 1> (фиг.l).

В ОБ 2 и в регистр 8 записывается элемент а,, т.к. на вход элемента

И 13 подается дополнительный единичный разряд и на его выходе формируется единичный сигнал, который разрешает запись в регистр 8 (фиг.2 и

4). Триггер 11 устанавливается в единичное состояние. На выходе узла деления 10 формируется значение а < = а /а„, > которое через откры0)

11 тые элементы Й 15 подается на вход

17. В ОБ 2, аналогичным образом элемент а записывается в регистр

22.

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

4 ный разряд, на вход 1Э вЂ” элемент а и дополнительный единичный разряд. В OR 2 11 формируется значение (1)

5 а, = а15/а„, в ОБ 22, — значение (1 (.1

a zq = a z4- а,< a z,, в ОБ 23, — значениеа, =а -а, а,, вОБ21 (а) (1) (1)

10 а = az» /а, в ОБ 222 в регистр

О)

22 записывается элемент а, в регистр 3, записывается элемент а, (1 с дополнительным нулевым разрядом. В пятом такте на вход 1 может пода5

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

Ц или нулевое значение с дополнительным нулевым разрядом, на вход 1 подается элемент а с дополнительным единичным разрядом, в ОБ 2, в случае

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

25— — а, а, в ОБ 2 э — значение

21 а() = а — a(а в ОБ 2,z — значе34 34 14 Э! ние а = а zÄ /a«, в ОБ 2 2ь — значе(z> (0 (0

24 ние а 1 = а " — а< .. а n) в ОБ 23

30 33 ЭЭ z3 32 в регистр 22 записывается элемент а, в регистр 3, записывается (2.1

12 () элемент а с единичным дополнитель1Э ным разрядом.

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

Первый элемент Х „= а14 формируется на восьмом такте на выходе

33 ОБ 2 23 (на выходе устройства 54).

Элемент Х, = à 4 -форМируется на девятом такте на выходе ОБ 53, эле(Э) (>) мент Х 3, = а з4 — на десятом такте на выходе регистра 3. (на выходе

З (3) (Э)

45 устройства 5 ), Элементы Х, Х (3)

Х фиксируются соответственно на

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

144 и дополнительный разряд 1, на вход

1 - элемент а, и дополнительный разряд О (фиг.1), В ОБ 2 „ в регистр

8 записывается элемент а», триггер !

1 находится в единичном состоянии, триггер 12 устанавливается в единичное состояние, на выходе узла деле(1) ния формируется значение а

1Э а1Э /а„, которое подается на выход

17 (фиг. 2 и 4), В ОБ 2 2, в регистр

21 записывается элемент а, триггер

26 устанавливается в единичное состояние, в регистр 23 записывается элемент а(, ), триггер 28 находится в нулевом состоянии, на выходе умножителя 24 формируется значение а(, ) ка, которое поступает на вход вычи21 тателя 25, на второй вход которого подается элемент а, на выходе вычитателя 25 формируется значение

«) (1)

a2z a z a z1 котоРое .чеРез открытые элементы И 32 подается на выход 33 (фиг.3 и 4) с дополнительным нулевым разрядом. В ОБ 23, элемент записывается в регистр 22 (фиг.3).

На третьем такте на вход 11 подаЭ ются элемент а11 и дополнительныи

Э разряд 1, на вход 12 — элемент а . и дополнительный разряд 1, на вход

13 — а и дополнительный разряд 1.

В ОБ 2 „ формируется значение а, = a«/ан, В ОБ 221 В регистр 2 (1)

1 зайисывается элемент а, в регистр

23 — элемент а,), триггеры 26 — 28 () находятся в едйничном состоянии, на выходе вычитателя 25 формируется зна(1) () чение а Э = а23- а, ° а (которое подается через открытые элементы

И 32 на выход 33 с дополнительным единичным разрядом (фиг.3 и 4). В .ОБ 2, в регистр 21 записывается элемент а, в регистр 23 — элемент (1) а триггер 26 находится в единич1Z. ном состоянии, а триггеры 27 и 28 — в в нулевом. На выходе вычитателя 25 формируется значение а = а (1) — а() . а . которое подается на выход

1Z 3<

33 с дополнительным нулевым разрядом (фиг,3 и 4), В ОБ 221 в регистр

9 записывается элемент а 2 (фиг.2) 55

На четвертом такте на вход 1, по4дается элемент а, и дополнительныи единичный разряд, на вход 12 — элемент а24 и дополнительный единичФормула изобретения

1. Устройство для обращения матриц и решения систем линейных уравне= ний, содержащее и операционных блок ков, где n — - размерность матрицы пхп коэффициентов системы линейных уравнений, причем i-я группа информационных входов устройства подключена к первой группе входов il-ro

l 444820 операционного блока (i=1 n}„ синхровход устройства подключен к синхровходам операционных блоков, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных вазможностей путем решечия систем из п ли— нейных уравнений с m правыми частями, н него введены и регистров, причем синхровход устройства подключен к сннхровходам регистров, выходы группы 1„ -ro операционного блока подключены к входам второй группы

2j-ro операционного блока (j =1,n), выходы первой группы ij-ro операцион-1 ного блока подключены к входам первой группы (i-l,j +1)-ão операционного блока (i=.",n, j=l,n-l), выходы второй группы ij-го операционного блока подключены к входам второй группы 2О (i+1,j}-го операционного блока (i=2,n-l j=1,n) выходы второй группы nj-ro операционного блока подключены к информационному входу j-га регистра (j=l,n),âûõîä j-ro регистра

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

in-ro операционного блока подключен к (i-1)-му выходу устройства.

2, Устройство по п.l, о т л и— ч а ю щ е е с я reM, что lj-й операционный блок (1=1,п) содержит два регистра, узел деления, два триггера, два элемента И, группу элементов И, элемент НЕ, причем 1 входов первой группы блока, где 1 — разрядность чисел, соединены с информациан- 40 ными входами первого и второго регистров, (1+1)-й вход первой группы соединен с первым входом первого элемента И, с информационным входом первого триггера и с входом элемента НК, выход которого соединен с первым входом второго элемента И, выходы первого и нторого элементов И соединены с сннхровхадами сооТВВТсТВеННо первого и второго регистров, выходы

50 которых соединены соответственно с первым и вторым входами узла деления, ВыхОд которого саедннен с перными входами элементов И группы, вторые входы которых соединены с выхо,цам первого триггера, который соединен с информационным входом второго триггера, синхравход блока соединен с BTopb!MH входами первого и второго элементов И, с синхравхадами первого и второго триггерон. выходы элементов И группы и выход второго триггера подключены к группе выходов бло-. ка, 3. Устройство io п,l, а т л ич а ю щ е е с я тем, что ij-й опе- рационный блок (i=2,n;j =1,n) содержит три регистра, умнажитель, вычита-. тель, три триггера, два элемента И, группу элементов И, элемент НЕ, причем 1 входов первой группы блока сое динены с информационными входами первого и второго регистров, (1+1)-й вход первой группы соединен с первым входом второго элемента И, с информационным входом первого триггера и с входам элемента НЕ, выход которого соединен с первым входом первого элемента И, выходы первого и второго элементов И соединены с синхровходами соответственно первого и второго регистров, ныхады которых соединены с первыми входами соответственно нычитателя и умножителя, второй вход которого соединен с выходом третьего регистра, а выход — с вторым входом нычитателя, выход которого соединен с первьми выходами элементов И группы, второй вход которых соединен с выходом первого триггера, который соединен с информационным выходом второго триггера, 1 входов и (1+l)-й вход второй группы блока соединены с информационными нходами соответственно третьего регистра и третьего триггера, выходы которых подключены к выходам второй группы блока, ныходы группы элементов И и второго триггера падкгпочены к выходам первой группы выходов блока, синхравход блока соединен с вторыми входами первого и второ, о элементов И, с синхравходами первого, второго и третьего триггеров и с синхравходом третьего регистра.

1444820!

444820

Составитель N.Ñèëèê

Техред А.Кравчук

Корректор Л.Пилипенко

Редактор М; Циткина

Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

1)3035, Москва, М(-35, Раушская наб., д, 4/5

«Ю

Заказ 6508/50

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, ч