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

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

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

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

Устройство содержит регистр 1 сдвига, умножитель 2, блоки памяти, накапливающий сумматор 4, вычитатель 5, делитель 6, адресные регистры 7, -7, , группы 8, и 8 элементов И, блок 9 управления с выходами 10-17.

Блок 9 управления содержит генератор 18 тактовых импульсов, счетчи 19, постоянный запоминающий блок 20 элементы 21, -21 задержки, элементы И 22j-22j , группы 23 -23 элементов И, группы 24J и 24, элементов ИЛИ.,

Работа устройства основывается н

следующем. I

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

А

,

,i-

JN

Ni fJ/Nj

-,r

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

L

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

О d,

о

О

О О

dj. .. О

О О О d,

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

Р Е f

L J, Lj,. . . L

О 1

MI

L

0 0 1

:.

00 о .. 1 . L - матрица эрмитово-сопряженная.

Вычисление элементов матриц L и D обосновано на вычислении элементов всггомогательной матрицы

где С

При этом L .

Вычисление элементов матриц С и L осуществляется в соответствии с выражениями

ij u -Ц- С|

5.

t

R--1

() (2)

где ,N - номер строки; ,i - номер столбца,

i-. -&. С (3)

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

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

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

ик

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

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

процессом вычислений в устройстве используются пять импульсных команд К -Kg, которые вырабатываются в блоке 9 управления соответственно на

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

ft

Назначение компнд и моменты вре- мени их формирования:

команда К| осуществляет сдвиг информации в регистре 1 сдвига и сбро накапливающего сумматора 4, формируется в момент времени t,;

команда К является командой чтения блоков 3, и 3, памяти, формируется в момент времени t ;

команда К,, является командой чтения блока 3j памяти, формируется в момент времени t ;

команда К является командой записи в блок 3 памяти, формируется в момент времени

команда К является командой за- писи в блоки 3 , и 3j памяти, формируется в момент времени t .

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

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

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

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

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

В результате этого на выходе регистра I сдвига и соответственно на выходе яычитателя 5 устанавливается число а . Одновременно происходит перепись кода адреса записи, равного единице, вычисляемого элемента d, из блока 9 управления в адресный регийтр 7 . По команде К производятся запись элемента d а в блок 3 памяти и передача его на выход устройства с помощью группы 8| элементов И.

Во втором такте вычислений при , , по команде К на выходе регистра 1 сдвига и соответственно на выходе вычитателя 5 устанавливается число а. Одновременно происходят перепись кодов адресов записи, равных единице, вычисляемых элементов с, и Т соответственно в адресные регистры 7, и 7 и перепись кода адреса чтения, равного единице, ранее вычисленного элемента d в адресный регистр 7 J. По команде К. производится чтение блока 3 памяти, В результате этого число d поступает на второй вход делителя 6, на первый вход которого от вычитателя 5 поступает число . По команде К производится запись числа Cj и 1 соответственно в блоки 3, и 3 памяти. Одновременно осуществляется передача элемента Ij, на выход устройства с помош.ью группы 8j элементов И

В третьем такте вычислений при , , по команде К на выходе регистра 1 сдвига устанавливается число a,,j и производится сброс накапливающего сумматора 4. Одновремен- но происходит перепись кодов адресов чтения, равных единице, считываемых

.элементов l соответственно в адресные регистры 7, и 7 и перепись кода адреса записи, равного двум, вы числяемого элемента d в адресный регистр 7. По команде К производится чтение блоков 3, и 3 памяти, в результате чего элементы и 1, поступают на входы умножителя . .Полученное произведение с 1 без изменения проходит через сумматор 4 и вычитается из элемента а в вычита- теле 5. Результат вьтислений - элемент d , по команде К записывается в блок 3,, памяти и передается на вм- ход устройства с помо.щью группы 8 элементов И.

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

Формирование управляющих сигналов в блоке 9 управления осуществляется по команде начала вычислений, которой запускается генератором 18 тактовых импульсов. Вырабатываем1.1е генератором 18 импульсы считьгваются счетчиком 19. Формируемый им код номера такта m поступает как адрес Б постоянный запоминающий блок 20 в ячейках которого хранятся команды управления и коды адресов памяти для каждого такта работы. В результате этого на выходе постоянного запоминающего блока 20 устанавливается содержимое соответствующей ячейки памяти, С помощью элементов И и групп 23-23 элементов И импульсами, поступающими от элементов 21, -21 задержки, производится опрос соответствующих выходных разрядов постоянного запоминаюшего блока 20. При этом элементы И 22 225 обеспечивают соответственно формирование команд Kj-Kj . Группы

23-23 элемнтов И обеспечивают формирование кодов адресов памяти следующим образом:

группы 23 ,j и

23 элементов И производят соответственно перепись кодов адресов чтения и записи для блока 3 памяти;

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

bо

изводят соответственно перепись кодов адресов чтения и записи для блока 3 памяти;

группа 23 элементов И произво.гшт перепись кодов адресов чтения или записи для блока 3 памяти.

Предлагаемое устройство за счет реализации в нем операции разложения матри1ды имеет широкие функциональные возможности,, что позволяет его использовать н сг рлшалияиронанных устройствах, предназначенных для решения задач методами матричной алгебры, в том числе в устройствах, осущест5 вляющих решение систем линейных ал- 1 ебраических уравнений, обращение матриц, в цифровых имитаторах случайных процессов с заданными кор- реляционнь ми cвoйcтвa n, в устройст10 вах моделирования случайных пропес- сов,

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

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

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

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

35 вход регистра сдвига является информационным входом устройства, выход регистра сдвига соединен с входом уменьшаемого вычитателя, вход вычитаемого которого соединен с выходом

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

7

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

o

5

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

0

5

0

Инсрормационный Вход

1292008

10 Продолжение таблицы

Редактор В Л1етраш

Составитель З.Шершнева Техред Л.Сердюкова

Яаказ 273/49 Тираж 673Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и о-ткрытий 113035, Москва, , Раушская наб,, д. 4/5

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

fpu,z.2

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

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