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

 

Устройство для операций над матрицами относится к области вычислительной техники, в частности к устройствам предназначенным для решения задач методами матричной алгебры , в том числе в устройствах. осуществляющих рершние систем линей-1 ных алгебраических уравнений, в цифровых имитаторах случайных процессов с зад анными корреляционными свойствами, в устройствах моделирования и анализа случайных процессов. Цель изобретения - расширение функциональных возможностей устройства за счет реализации операции разложения матрицы. Поставленная цель достигается тем, что в известное устройство, содержащее регистр сдвига , умножитель, два блока памяти и накапливающий сумматор, введены третий блок памяти, вьгчитатель, делитель , три адресных регистра, два блока элементов И и блок управления. 1 з.п. ф-лы, 2 ил. табл. S (Л to со tsd

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

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

РЕСПУБЛИН (50 4 С 06 F 15/347 ф(Ps p,@.п; „

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

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

13 „

ЦЬЯИОТИА

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3870007/24-24 (22) 18.03.85 (46) 23.02.87. Вюл, М 7 (72) С,Д.Вышков, И.Е,Петров, В.Г.Денисов, Л.В.Сабаев и С.А.1Иептулин (53) 681 ° 325(088.8) (56) Авторское свидетельство СССР

Ф 647687, кл. G 06 F 15/31, 1979.

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

Р 717779, кл. G 06 F 15/336, 1976, (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД

МАТРИЦАМИ (57) Устройство для операций над матрицами относится к области вычислительной техники, в частности к, устройствам предназначенным для решения задач методами матричной алгебры, в том числе в устройствах, „„SU„„1292008 А 1 осуществляющих решение систем линей-I ных алгебраических уравнений, в цифровых имитаторах случайных процессов с заданными корреляционными свойствами, в устройствах моделирования и анализа случайных процессов.

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

1 э.п. ф-лы, 2 ил. 1 табл.

1292008

Io o

d I r r i ò

Е ° ° d ° ° °

On О..!

C=LD, 0 О ... 0

Д20 ... 0 с„d, О где С=

С 31 аd ° ° 0I Еddаdd с NI С4 С» С!»1

1 с,, =а,.; — 2 с,„1„.„ к=3

13 с .

13 2

1 (2) а11а1 2а13 а,а,а, ° З1 22 33 ..а,„ где А= а а 34

42 »3

Ф а;„=

1 0 0 0 О О...О

1 0 0 О 0...0

3 32

° Э ° ° d ° ° ° Ь Ф °

»1 42 4

d1 0 О ... О

О и 0 ... 0

О О п3 ° ° ° О

О О oood»

D-! 1 1„Г,,...

О 1 yn... tge, Изобретение относится к вычислительной технике, в частности к устройствам, предназначенным для решения задач методами матричной алгебры. 5

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

На фиг. 1 представлена структур- 1О ная схема устройства для операций над матрицами, на фиг. 2 -- схема блока управления.

Устройство содержит регистр 1 сдвига, умножитель 2 блоки 3 -3

» 3

15 памяти, накапливающий сумматор 4, вычитатель 5, делитель 6, адресные регистры 7, -7„, группы 8, и 8.

2 элементов И, блок 9 управления с выходами 10-17 ° 20

Блок 9 управления содержит генератор 18 тактовых импульсов, счетчик

19, постоянный запоминающий блок 20, элементы 21„ -21, задержки, элементы

И 22,-22, группы 23 -23 элементов

И, группы 24, и 24 элементов ИЛИ„

Работа устройства основывается на следующем.

Из теории линейной алгебры известно, что положительно определенную эрмитову _#_1N матрицу А комплексных чисел можно представить в виде

A=LDL

2 знак комплексного сопряжения;

3 нижняя треугольная матрица с единичной главной диагональю;

D — диагональная матрица с поло- 5 жительными элементами;

L матрица эрми,ово сопряженная, Вычисление элементов матриц и

3 обосновано на вычислении элементов

1 вспомогательной матрицы с;, =d;.

При этом А=С L

Вычисление элементов матриц С и L осуществляется в соответствии с выражениями где i=1 N — номер строки;

j=l,i — номер столбца, (3)

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

До начала вычислений в регистр сдвига по информационному входу устройства записываются в следующей последовательности элементы исходной матрицы А. В начале записывается элемент первой строки а затем

11 1 элементы второй строки а а за212 221 тем элементы третьей строки а. а

31 а и т.д. Последними записываются элементы N-й строки а а а ... а

422 й3 2»»

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

Обработка информации в устройстве осуществляется в течение M тактов, формируемых блоком 9 управления., Число тактов определяется размерностью матрицы и составляет веN(N +5) личину М= ------- . Для управления

6 процессом вычислений в устройстве используются пять импульсных команд

К,-К„, которые вырабатываются в блоке 9 управления соответственно на!

292008 выходах 10-14. Формирование команд в каждом такте работы осуществляется в определенные фиксированные моменты времени л

Назначение команд и моменты нремени их формирования: команда К, осуществляет сдвиг информации н регистре 1 сдвига и сброс накапливающего сумматора 4, формируется в момент времени команда К является командой чтения блоков 3, и 3д памяти, формируется в момент времени команда К, является командой чтения блока 3 памяти, формируется в момент времени команда К является командой за4 писи н блок 3, памяти, формируется в момент времени команда К является командой за5 писи в блоки 3, и 3, памяти, формируется в момент времени

В процессе работы устройства вырабатываются не все команды К, -К сразу, а только те из них, которне необходимы для обработки информации в текущем такте работы.

Кроме формирования команд, блок

9 управления вырабатывает на своих выходах 15-17 адреса чтения и записи кодов с, 1 и d, хранящихся соответственно н блоках 3 3 памяти. При этом формирование адресов чтения блоков 3, и 3, памяти, а также адресов чтения или записи блока 3 памяз ти осуществляется н момент времени

t, формирование адресов записи информации блоков 3, и 3 памяти— в момент времени з

При обработке информации в устройстве интервал времени и -t используется для выполнения операций умножения, сложения и вычитания, интервал времени t -t - для выпол-. э нения операции деления.

Реализацию процесса обработки информации поясняет таблица, где указаны m — - номер такта обработки; номер строки; j — номер столбца; значения считываемых из регистра 1 сдвига и блоков 3, -3З памяти элементов, а, с, I, d; значения вычисляемых и записываемых в блоки 3,-3 памяти элементов с, У, d; номера используемых команд К,-К ; значения адресов блокон 3, -Зз памяти для чтения элементов с, I d. Таблица приведена для случая обработки матрицы с N=4.

В соответствии с таблицей в первом такте вычислений при щ=1, i=1

j=-1 блок 9 управления вырабатывает команду К,. которая производит сдниг информации в регистре 1 сдвига и сброс накапливающего сумматора 4.

В результате этого на выходе регистра сдвига и соответственно на выходе нмчитателя 5 устанавливается

>О число а . Одновременно происходит перепись кода адреса записи, равногп единице, вычисляемого элемента

d, из блока 9 управления в адресный региСтр 7 . По команде К производят3 4

15 ся запись элемента d =а н блок 3

1 11 3 памяти и передача em на выход устройства с помощью группы 8, элементов И.

Во втором такте вычислений при

20 m=2, i=2, j=l по команде К, на выходе регистра 1 сдвига и соответственно на выходе вычитателя 5 устанавливается число а . Одновременно проЯ1 исходят перепись кодов адресон запи25 си, равных единице, вычисляемых элементов с и Т соответственно в ад 11 Я1 ресные регистры 7, и 7 и перепись кода адреса чтения, равного единице, ранее вычисленного элемента d н ад1

30 ресный регистр 7 . По команде К производится чтение блока 3, памяти.

В результате этого число d поступа1 ет на второй вход делителя 6, на первый нход которого от вычитателя 5 поступает число с =а . По команде

Ь э

К 5 производится запись числя с и

21

У соответственно н блоки 3 и 3

11 1 памяти. Одновременно осуществляется передача элемента I, на выход устрой40 ства с помощью группы 8 элементов И.

В третьем такте вычислений при

m=3, i=2, 1=2 по команде К, на выходе регистра 1 сдвига устанавлинается число а и производится сброс накаФ%

45 пливающего сумматора 4. Одновременно происходит перепись кодов адресов чтения, равных единице, считываемых ,элементов с,и 1„ соответственно в адресные регистры 7, и 7 и перепись и кода адреса записи, равного двум, вы. числяемого элемента d в адресный регистр 7 з. По команде К производится чтейие блоков 3, и 3 памяти, в результате чего элементы cù и 1, 55 поступают на входы умно т я 2 Полученное произведение с „ I„ без изменения проходит через сумматор 4 и вычитается из элемента а в вычитателе 5. Результат вычислений — эле1297008 сов.

Щ

:0 мент Й по команде К записывается в блок 3: памяти и передается на вы3 ход устройства с помощью группы 8, элементов И °

Аналогичным образом осушествляет— ся процесс обработки информации в остальных тактах работы. При этом следует иметь ввиду, что в том такте, где команда К, не формируется, на выходе регистра 1 сдвига сохраняется предыдущее значение элемента а,, Отсутствие сброса сумматора 4 позволяет осуществлять потактное на— копление произведений и вычисление с,:„ в соответствии с выражением (1).

Полностью процесс вычислений заканчивается в такте с чомером т=М.

Формирование управляющих сигналов в блоке 9 управления осуществляется по команде начала вычислений, которой запускается генератором 18 тактовых импульсов. Вырабатываемые генератором !8 импульсы считываются счетчиком 19. Формируемый им код номера такта m поступает как адрес в постоянный запоминаюший блок 20, в ячейках которого хранятся команды управления и коды адресов памяти для каждого такта работы. В результате этого на выходе постоянного запоминающего блока 20 устанавливается содержимое соответствующей ячейки памяти. С помощью 3sIpMpHToB H

22,-22, и групп 23 -23, элементов

И импульсами, поступающими от элементов 21, -21» задержки, производится опрос соответствующих выходных разрядов постоянного запоминакшего блока 20, При этом элементы И 22

22, обеспечивают соответственно формирование команд К,-К, . Группы

23 -23 элемнтов И обеспечивают формирование кодов адресов памяти следующим образом: группы 23 3 v. 234 элемент в И п1=изводят соответственно перепись кодов адресов чтения и записи для блока 3, памяти; группы 23, и 23. элементов И про6 изводят соответственно перепись кодов адресов чтения и записи для блока 3 памяти; группа 23, элементов И произво, лт перепись кодов адресов чтения или записи для блока З,памяти.

Предлагаемое устройство за счет реализации в нем операции разложения матрицы имеет широкие функциональные возможности, что позволяет его ис .пользовать Tl с. епиализированных устройствах, предназначенных для решения задач методами матричной алгебры, в том числе в устройствах, осуществляющих решение систем линейных алгебраических уравнений, обращение матриц, в цифровых имитаторах случайных процессов с заданными корреляционными свойствами в уcTpoHcT вах моделирования случайных процесФ о р м у л а и з о б р е т е н и я! . Устройство для операций над матрицами, содержащее два блока памяти, накапливающий сумматор, умножитель, первый информационный вход которого соединен с выходом первого блока памяти, второй информационный вход умножителя соединен с выходом второго блока памяти, выход умножителя соединен с информационным входом накапливающего сумматора, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет реализации операции разложения матрицы, в него введены третий блок памяти, регистр сдвига, вычитатель, блок деления, три адресных регистра, две группы элементов

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

1292008

1 1

2 2

3 2

4 3

5 3

6 3

d (К,, К, 1 (° К э( к,, к, к,, к„к, К,, K К, К э э а, с„х„

1 э э(0 0 1 1 1

I 1 0 0 2

0 0 1 2 1

1 1 2 3 2 а., 2 а,э с1, 1 а

3(2 э э сэ, 3 а,эсэ, 3 — с э

?э(с э(I

2(а, сээ 2„

0 0

7 . 3 ээ а

2 3 0 0 3 а, с„т„

8 4

9 4

0 0 !

4 1

2 а„ с„ а 1 М 41 ти

I 1 2 5 2 записи первого и второго блоков памяти и с первыми входами элементов

И второй группы, шестой, сельм(:и и восьмой выходы блока управления соединены с информационными входами первого, второго и третьего адресных регистров соответственно, ныхо— ды которых соединены с адресными входами первого, второго и третьего блоков памяти соответственно, выход третьего блока памяти соеди— нен с входом делителя блока деления, выход которого соединен с информационным входом второго блока памяти и с вторыми входами элементов И второй группы, выходы элементов И первой и второй групп являют,ся выходом устройства.

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок управления содержит генератор тактовых импульсон, счетчик, постоянный запоминающий блок, четыре элемента задержки, пять элементов И, пять групп элементов И, две группы элементов ИЛИ, причем вход пуска блока управления соединен с входом генератора тактовых импульсов, выход которого соединен с тактовым входом счетчика и с входом первого элемента задержки, выход счетчика соединен с адресным входом постоянного запоминающего блока, первый выход которого соединен с первым входом первого элемента И, второй выход по- З5 стоянного запоминающего блока соединен с первым входом второго элемента И, третий выход постоянного запоминающего блока соединен с первыми входами третьего и четвертого элементов И, четвертый выход г!остоя1(ного запоминающего блока соединен с первым входом пятого элемента И, пятый, шестой, седьмой, восьмо!1 и девятый выходы постоянного запоминающего блока соединены соответственно с первыми входами элементов И первой, второй, третьей, четнертой и пятой групп, ныход первого элемента задержки соединен с вторым входом первого элемента И, с вторыми входами элементов И первой, третьей и пятой групп и с входом второго элемента задержки, выход которого соединен с вторым входом второго элемента И и входом третьего элемента задержки, выход которого соединен с вторыми входами третьего и пятого элементов И, вторыми входами элементов И второй и четвертой групп и с входом четнертого элемента задержки, выход которого соединен с вторым входом четвертого элемента И, выходы элементов И первой, второй, третьей и четвертой групп соединены с первыми и вторыми входами элементов ИЛИ первой и второй групп соответственно, выходы первого, второго, третьего, пятого, четнертого элементов И являются первым, вторым, третьим, четвертым и пятым выходами блока соответственно, выходы элементов ИЛИ первой и второй групп и выходы элементов И пятой группы являются шестым, седьмым и восьмым выходами блока.

1292008

Вычисляете элементы спольэуемые команды праелення е эле1 1 4 с У d

К,, К

?,„d

К, К с я1

К,, К, 14 4 4

К,, К

Упр

Нхо

10 4 Э а, с„

11 4 3

12 4 4 а

1Э 4 4

Итрормациончый

УмоР

Продолжение таблиць>

1 2 0 0 0

2 Э 3 6 Э

4 0 0 0

2 5 0 0 0

Э 6 0 0 4

l?92008

Составитель 3.йершнева

Техред Л. Сердюкова

Корректор О.Луговая

Редактор Б.11етраш

Заказ 273/49 Тираж б73 Подписное

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

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

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