Устройство для решения матричного уравнения вида ах=в

Устройство для решения матричного уравнения вида ах=в

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для решения систем линейных уравнений и обращения матриц. Целью изобретения является упрощение устройства. Устройство содержит 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 табл.

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

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

РЕСПУБЛИН (51)4 G 06,F 15/347

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

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

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

ПРИ ГКНТ СССР

К АBTOPCHOMY СВИДЕТЕЛЬСТВУ t (21) 4187149/24-24 (22) 28.01.87 (46) 23.09.89. Бюл, - 35 (72) В.П.Якуш, С.Г.Седухин, В.А,Мищенко, Л.Б.Авгуль и А.Н.Семашко (53) 681.325(088.8) (56) Седухин С.Г. Параллельная интерпретация прямых методов линейных алгебры. — Программирование, 1984, Ф 4, с, 57 68.

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

)) 1444820, кл, G 06 F 1.5/347, 1987. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ МАТРИЧ-

НОГО УРАВНЕНИЯ ВИДА АХ=В (57) Изобретение относится к вычислительной технике и может быть испольИзобретение относится к вычислительной технике и может быть исполь.зовано в специализированных вычисли,тельных машинах и устройствах обработки данных для решения систем линейных уравнений и обращения плотных п и матриц.

Цель изобретения — упрощение устройства, В основу работы предлагаемого устройства положен метод Гаусса-Жордана, при котором для решения систем линейных уравнений АХ=В расширенная

n -(n+m) матрица (.А/В ) сводится к

n-(nba) матрице fE/Х1, где Š— единичная (и п) матрица, по рекуррента ным соотношениям для а; =а;., i=1 ï, 1

j=l,n+m (при обращении матриц — m n, „„SU„„1509932 А1

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

/2+nm операционных блоков; (i,i)-й операционный блок (i=1 и) содержит регистр, узел вычисления обратной величины числа, две группы элементов

И, группу элементов ИЛИ и триггер; (i,j)-й операционный блок (i=2,ï+m, j=1,и, i--1> j) содержит четыре триггера, три регистра, умножитель, вычитатель, четыре группы элементов И, группу элементов ИЛИ и элемент ИЛИНЕ, Поставленная цель достигается за счет реализованных структурных

М решений. 2 з.п. ф-лы, 4 ил., 2 табл. .

- а расширенная и 2п матрица (А/Е7 сводится к п-2п матрице (Е/А 1; k 1 и °

У У (Ч () )1 () ц а< =а „,: /а),),, k 4 j < п+ш, (W () -1) () -1) () ) а; =а;;-а;>а„., 1

ij-го операционного блока (ОБ) (i,j=

=l,и; i=j); на фиг, 3 — функциональная схема ij-го ОБ (i=2,n+m, j 1,n, i-1-> j); на фиг. 4 — временные диаграммы устройства °

1509932

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

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

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

Операционный блок 3; (i=2,n+m;

j=l,ï; i-1 ) j) (фиг. 3) содержит первую группу входов 14, второй 20 вход 15, синхровход 16, регистры 1719,.умножитель 20, вычитатель 21, триггеры 22-25, группы элементов

И 26-29, группы элементов ИЛИ 30 и

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

Рассмотрим работу ОБ 3;> (i=j=l,n), логика работы которого показана в табл. 1, При подаче на 1 входов первой группы входов 5 значения элемента а „, а на (1+1)-й вход 5 — нулевого сигнала, в регистр 7 записывается значение элемента а „, триггер 12 устанавливается в нулевое состояние. С инверсного выхода триг- 35 гера 12 единичный сигнал открывает группу элементов И 10, через которую значение 1/а „ с выхода узла 8 вычисления обратной величины числа подается на вход группы элементов ИЛИ 40

11. С выхода группы элементов ИЛИ 11 значение 1/а „подается на выход 13

ОБ. Если триггер 12 устанавливается в единичное состояние, то открывается группа элементов И 9 и на выход 45

13 ОБ через группу элементов ИЛИ 11 подается значение элемента ав, .

Рассмотрим работу ОБ 3;.(х=2,п+ш; 5

j=1,n; i-1ъ, j) (фиг. 3), Логика работы этого ОБ задается табл. 2,На нулевом такте при подаче на 1 входов о первой группы входов значения С „и нулевых сигналов на (1+1)-й и (1+

+3)-й входы 1. в регистр 17 записывается значение С „,.триггеры 22 и 24 устанавливаются в нулевое состояние., С выходов триггеров 22 и 24 нулевые сигналы подаются на входы элемента

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

С выхода регистра 18 значение В подается на второй вход умножителя 20, на выходе которого формируется произо ведение С,„В, которое записывается в регистр 19. На первом такте подаются значение С на 1 входов 1, sx нулевой сигнал на (1+1)-й вход 1 и единичный сигнал на (1+2)-й вход 1, на второй вход 15 подается В . В бх регистры 17 и 18 записываются соответственно значения С и В . Триггер ьх ь!!

24 устанавливается в единичное состояние, единичный сигнал открывает группы элементов И 27 и 29. На перBbIH вход умножителя 20 подается через группу элементов И 27 и группу элементов ИЛИ 30 произведение г=ВО С „, на второй вход — значение В с выхоьх да регистра 18. На выходе умножителя

20 формируется значение rB !... которое подается на вход вычитателя 21, на второй вход которого подается ! значение С,„ с выхода регистра 17, На выходе вычитателя 21-формируется

1 значение Сц„-rB „, которое через открытую группу элементов И 29 и группу элементов ИЛИ 31 подается на 1 выходов, первой группы выходов 33.

На (1+1)-м и (1+2)-м выходах 33 имеются нулевые сигналы, так как триггеры 23 и 25 находятся в нулевом состоянии

На втором такте OB работает аналогично. Триггер 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 пода- ются соответственно нулевой и единич5 150993 ный сигналы. На последующих тактах

ОБ работает аналогичным образом.

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

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

1О

Очередность подачи элементов а и нулевого значения 0, где t— э

t номер такта (фиг. 1) . Элементы а ...

i=i,n подаются на 1 входов первой группы входов 1, . Одновременно с эле- !5 ментами а на (1+1)-й вход первой !

1 группы входов 1, подается на нулевом такте дополнительный разряд О, на

1,2,...,п-l тактах — дополнительный разряд l, íà и такте — дополнительный 20 1 разряд О. Элементы а; -(i=i,n; j=2, n+m) подаются на 1 входов первой группы входов 1; (i=2,n+m). Одновремеино с элементами а, на (1е1)-й и (1+2)-й входы 1. (i=2,п+тп) подаются на (i-1)-м такте соответственно дополнительные разряды О и 0 на

i+1 i+n-2 тактах — соответственно дополнительные разряды О и 1, на (i+n-1)-м такте — соответственно до30 полнительные разряды 1 и О.

О

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

3 записывается элемент а,.

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

1 элемент а и дополнительно раз1) 12 ряды 0 и О подаются соответственно на 1-й, (1+1)-й и (1+2)-й входы 1 (фиг. 1). В ОБ 3„, в регистр 7 запиcblBBeTcH элемент а 2„. В ОБ 3, в регистр 17 записывается элемент а 12в регистр 18 — значение 1/а„„, в регистр 19 " значение а",=а, /а.„,(11 (фиг ° 4).

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

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

0 и .О подаются соответственно на

1-й, (1+1)-й и (1+2)-й входы 1 . В

ОБ З„в регистр 7 залисывается а3,, В ОБ 3,на. выходе вычитателя 2) фор-,. мируется а =а, -а Да,, В ОБ 3 э,в ре2 6 гистр 17 записывается а,, в регистр

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

На третьем такте нулевое значение

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

0 и О подаются соответственно на

1-й, (1+1)-й H (1+2)-й Bxo

ОБ 31! в регистр 7 записывается Мулевое значение. В ОБ З,на выходе вычитателя 21 формируется значение а =а -а,га, . В ОБ Зэ,,на выходе

32 эг 17 31 вычитателя 21 формируется значение а =а. -а а „ . В ОБ 312в регистр 7 гэ записывается значение а 1

22

На четвертом такте на вход l l, может подаваться элемент а„новой системы линейных уравнений или нулевое значение с дополнительным разрядом

О, на 1-й, (1+1)-й и (1+2)-й входы

l подаются соответственно нулевое

О значение О и дополнительные разряды 1 и О, на 1 — й, (1+1)-й и (1+2)-й входы 1 — соответственно элемент э а и дополнительные разряды О и l, на 1-й, (1+l)-й и (1+2)-й входы 1, соответственно элемент а и дополни4 г тельные разряды О и 1, на 1-й, (1++1)-й и (1+2)-й входы — соответ5 ственно элемент а, и дополнительные разряды 0 и О. В ОБ 3, в регистры

17 и 18 записываются нулевые значения. В ОБ 3 в регистр 7 записывается элемент а . В ОБ 3„ формируется регистр 1 : ."аписывается значение агэ= г /a z,, В ОБ 3, формируется знарегистр 19 записывается значение а (i)

1Г

15/ «

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

+i)-й, (1+2)-й входы 1 соответственна элемент а и дополнительные разряды О и 1 на 1-й, (1+1)-й, (1+2)-й входы 15 подаются соответственно элемент и дополнительные разряды О и 1, В ОБ З, в регистр 7 записывается значение a iÄ, В ОБ 33„ в регистры

1509932

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

Сг) сг) й) г, > значение а". а „-а, 1 а „. В ОБ З„,,в з з регистр 19 записывается значение а . В ОБ 3,формируется значение (21 а () з гз гб 15 2г

На последующих тактах ОБ устройства работают аналогичным образом, Первый элемент Х „=а, формируется, 3) (31 на восьмом такте на выходе 4 „. Ha выходе 4, на певятом такте формируется элемент X г а 4 а элеме т

1з1 (з)

=а на,песятом такте. Элементы Х,, з

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

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

15

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

1,устройство для решения матричного уравнения вида АХ=В, где А — матрица регулярности п-п, Х и  — матрицы размерности n m (n,m — разряд- 25 ность расширеной матрицы ГА/В)), содержащее n(n+I)/2+nm операционных блоков, причем i-й информационный вход (i=1,n+m) устройства подключен к входам первой группы il-го операци- 30 .онного блока, синхровход устройства подключен к синхровходам операционных блоков, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства, выход первой группы ij -го операционного блока (г.=З,n j=l n-2;

i-2 Ъ j) подключен к входам первой группы (i, j+1)-го операционного блока, 1 входов и (1+1)-й вход первой группы (1 — разрядность элементов матрицы) (i,i)-го операционного блока (i=2,n) подключены соответственно к 1 выходам и (1+2)-му выходу первой группы (i,i-l)-го операционного блока, где 1 - разрядность элементов 45 матрицы, выходы первой группы ij-ro .операционного блока (i=n+l, n+m, j-=1,п-1) подключены к входам первой группы (i j+1)-го операционного блока, второй выход ij-го операционного блока (i=l,n+m-1; j=l, и»

i ri j) соединен с вторым входом (i+I, j)-го операционного блока, выход (i,п) — ro операционного блока подключен к (i-и)-му выходу устройства

55 (i=n+1, n+m).

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

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

3, Устройство по и. 1, о т л ич а ю щ е е с я тем, что ij-й операционный блок (i=2, n+m, j=l,n, 1-17r j) содержит три регистра, умножитель, вычитатель, четыре триггера, четыре группы элементов И, группу элементов ИЛИ и элемент ИЛИНЕ, причем 1 входов первой группы блока соединены с информационным входом первого регистра, выход которого соединен с первым входом вычитателя и с первыми входами элементов И первой группы, выходы которых соединены с первыми входами элементов ИЛИ первой группы, вторые входы которых

k соединены с выходами элементов И второй группы, а выходы — с первым входом умножителя, второй вход которого соединен с вторым выходом блока и с выходом второго регистра, выход умножителя подключен к информационному входу третьего регистра и второму входу вычитателя, информаци- онный вход второго регистра соединен с второй группой входов блока, выход вычитателя соединен с первыми входами элементов И четвертой группы, выход. которых соединен с первыми входами элементов ИЛИ второй группы, выход которых соединен с 1 выходами первой группы выходов блока, вторые входы элементов ИЛИ второй группы соединены с выходами элементов И третьей группы, первые входы которых соединены с выходом третьего регистра и с первыми входами элементов И

9 1509932 !0 второй группы, вход разрешения запи- ционным входом второго триггера, выси третьего регистра соединен с объ- ход которого является (1+2)-м выходом единенными выходами элемента ИЛИ-НЕ первой группы выходов блока, синхрои с вторыми входами элементов И пер- вход блока соединен с входами раэреше5 вой группы, (1+1)-й вход первой груп- ния эаписи первого и второго репы входов блока соединен с информа- гистров, с синхровходами первого, ционным входом первого триггера, . второго, третьего и четвертого тригвыход которого соединен с первым вхо- repos. дом элемента ИЛИ-НЕ, с вторыми входа- ð Таблица ми элементов И третьей группы и с информационным входом второго триг- Входы гера, выход которого является (1+1)-м выходом первой группы выходов бло- 1 ка, (1+2)-й вход первой группы блока !5 соединен с информационным входом тре- 1 тьего триггера, выход которого. сое- вх динен с вторым входом элемента ИЛИНЕ, с вторыми входами элементов И а 1 а а а ах внх вх второй и четвертой групп и с информа- 20

Выход а ав вх

Таблица 2

Выходы I группы

t I

Номер Входы I группы

Выход II гр.

Содержимое (RGr ) такта

1-1 1+1 1+2!

-1 1+1 1+2

0 0 г=Вв Csx

0 Вв„

1 Ввх

Вах

0 В

0 В ах

0 Сах

1 Свх

Свх

Вв цВ ах

0 0 r

0 1 r

С„-гВ „

С в. ГВвх

Bs =B вх ю

В.„,„=В,„

0 1

1 0

4 ° С ах

5 С,„ г=В „С „

0 0 r

Вен„=В вх

В ах

Свх вх гг уг

1509932

Quc.Þ

3п

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

Редактор М,Бланар Техред Л.Олийнык Корректор В.Кабаций

Заказ 5815/48 Тираж 668 Подписное

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

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

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