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

/3 ПИСАНИЕ ИЗОБРЕТЕНИ У госуддественный номитет сссрпо делдм изоБрятиний и открытии ВТОРСНОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССР В 595726, кл. С 06 Г /38, 1975Авторское свидетельство СССР В 894722, кл, 6 06 Е 15/36, 1980. (54) УСТРОЙСТВО ДЛЯ ВЫПОЛНЕНИЯ ОПЕРАЦИЙ ОБРАЩЕНИЯ МАТРИЦ(57) Изобретение относится к вычислительной технике. Целью изобретения является расширение функциональных возможностей за счет получения псевдообратных матриц для вырожденных квадратных, прямоугольных, плохообусловленных матриц и для матриц,. полученных перемножением векторов. Устройство содержит три блока памяти, выполненные на регистрах и предназначенные для хранения матриц, три блока формирования матриц, шесть блоков элементов задержки, блок умножения и блок управления. Устройство позволяет получать псевдообрат"ные матрицы не для узкого классаматриц, образованных умножением вектора-столбца на вектор-строку, адля любых матриц, плохообусловленных, вырожденных, квадратных,.прямоугольных, в том числе и для матриц, полученных перемножением векторов. Вспомогательная матрица представляет собой обычную единичнуюматрицу (для квадратной матрицы) илиединичную матрицу с отброшенным и-щколичеством строк или столбцов. Псевдообратная матрица для вспомогательной единичной матрицы представ- феляет собой транспонированную единичную (Иии усеченную единичную) меу, Ярицу. Псевдообрашение осуществляется убоевпосредством последовательной заменыво вспомогательной матрице 5; а,":АДстолбцов а. столбцами матрицы ХХХХ,Д, которую необходимо обратить. Постоянно на каждом шаге вычисляется псевдообратная матрица, 1 з.п,ф-лы, 5 ил,12657 30 Изобретение относится к вычислительной технике.Целью изобретения является расширение функциональных воэможностейза счет получения псевдообразных 5матриц для вырожденных, квадратных,прямоугольных, плохообусловленныхматриц и для матриц, полученных перемножением векторов.На фиг. 1 представлена схема уст Оройства на фиг, 2 и 3 - схемные примеры блоков формирования матриц, наФиг. 4 - схема блока умножения и суммирования на фиг. 5 - схема блокауправления. 15Устройство содержит блоки 1 и 2памяти, блок 3 управления, блок 4памяти, блоки 5 и 6 формированияматриц, блок 7 умножения и суммирования, блок 8 умножения, блоки 9-14элементов задержки, умножители 15,узлы 16 умножения и суммирования,сумматоры 17, делители 18, узлы 19коммутации, группы 20 элементов И,25узлы 21 памяти, схема 22 сравнения,буферный запоминающий узел 23, умножители 24, узлы 25 коммутации,сумматоры 26, узлы 27 умножения исуммирования, схема 28 сравнения,группы 29 элементов И, делители 30,узлы 31 и 32 памяти, умножитель 33,сумматор 34, генераторы 35 прямоугольных импульсов, счетчики 36, элементы 3 И, генератор 38 прямоугольных импульсов и счетчик 39, 35Устройство работает следующим образом.Блок 1 памяти хранит вспомогательную матрицу 511 пщ, котораяможет быть представлена в вице вектора-столбца а; размера п 11 и матрицы А; размера п щ:5, =1 а А,Блок 2 памяти хранит матрицу размера п щ, подлежащую обращению,которая может Быть представлена ввиде вектор-столбцов Х1 1,Х=Х, Х, .,Х, . Х 1.50Блок 4 соцержит известную длявспомогательной матрицы 5 псевдообратную матрицу 5. щ,п 1. Работаустройства начинается после поступления с блока 3 признака смены информации и импульсов на сдвиг информации в блоке 2, В результате навыходе блока 2 будут сигналы, соот 96 2ветствующие элементам вектор-столбца Х; 1 п 11. Эти сигналы поступают на входы блока 1, вытесняя из него элементы вектора-столбца а,. В результате в блоке 1 образуется новая матрица Т;= А; ХД, псевдообратную для которой необходимо найти. Сиг-, налы с выходов блока 1 поступают на блок 5 формирования матриц А,. Сигналы Х; с выхода блока 2 проходят на входы блоков 10 и 11 элементов задержки. На вход блока 5 поступают сигналы, считанные иэ блока 4, соответствующие элементам матрицы ,. Они считываются из блока 4 по сигналам блока 3. Кроме того, по этим же сигналам из блока 1 считывается матрица А, размера п щи поступает на вход блока 9 элемента задержки, На выходе блока 5 появляются сигналы, соответствующие элементамФ псевцообратной матрицы А размером щ п; Эти сигналы поступают на вход блока 8 умножения, на другой вход которого поступают задержанные на время Формирования матрицы А сигналы, соответствующие элементам вектора-строки Х,. С выходов блока 8 сигналы, соответствующиеФ элементам вектора-строки А,Х 1 раз" мера щ п, поступают на вход блока 6 формирования матриц, на вход которого поступают также сигналы с выхода блока 5, задержанные на время Формирования матрицы и вектора в блоке 9 сигналы о матрице А;, а также задержанные на это же самое время в блоке 11 сигналы о векторе Х;, В блоке 6 происходит Формирование вектора-строки, который является последней строкой псевдообратной для матрицы Т; матрицы Т. , которая имеет вид+, Нн 1Сигналы, соответствующие элементтам строки 6 , поступают на вход блока 7, на другие входы которого поступают задержанные в блоке 12 на время формирования строки сигналы с выхода блока 8 умножения и с выхода блока 5 Формирования матриц, задержанные в блоке 13 сигналы о составляющих А,. В результате на выходе блока 7 получаются сигналы, соответствующие элементам матрицы Н;ц размерности 1 щп 1. Эти сигналы, 3 1265 так же как и задержанные в блоке 14 на время Формирования Н; сигналы отвекторе П , поступают на вход блока 4, осущестнляя н нем полную замену старой псендообратной матрицы 5; на 5 новую 5. Перед этим из блока 3 на блок 4 поступает сигнал С 5, который приводит н исходное состояние блок 4 перед записью н него вычисленной псевдообратной матрицы. Блок 3 вы дает преобразованные н импульсы сигналы на блок 2, из которого вытесняется следующий столбец. Операции по Формированию псендообратной матрицы для матрицы Х продолжаются до 15 тех пор, пока из блока 2 не будут вытеснены все щ столбцов матрицы Х. В этом случае н блоке 4 на каждом шаге Формируется некоторая промежуточная псевдообратная матрица, кото рая на последнем шаге будет равна псевдообратной матрице Х для матрицы Х. Таким образом для псевдообращения матрицы размерности (и я требуется ш шагов. Блок 3 осущест вляет не только формирование импульсов .на вытеснение инФормации из блока 2, но и Формирование сигналов для управления блоками устройства. ЗОБлок 5 Формирования матриц (Фиг,2) работает следующим образом.Сигналы о векторе а; поступают на вход блока 5, а именно на вход умножителя 15, на вход которого о ступают сигналы с выхода блока 4, Сигналы с выхода умножителя 15, соответствующие составляющим вектораФстолбца 5; а; я 11, поступают на вход сумматора 17, на второй вход которо го поступает информация о векторе 9 размерности ш 1, имеющего видд =100 ОДИз узла 21 (хранения д) считыва ется информация по сигналу С 1 кольцевого счетчика 36. Сигналы с выхода сумматора 17 поступают на входы схемы 22 сравнения, в котором происходит сравнение вектора (ц"5 а,) с 50 нулевым вектором той же размерности я 11. В результате сравнения сигналы с выхода схемы 22 сравнения поступают на входы одной из двух групп 20 элементов И в зависимости 55 от того, равен результат сравнения нулю илн нет. Информация о составляющих вектора 9 из узла 21 одновре 796 4менно поступает на узел 19 нектарастолбца 9 и далее - на умножитель,на второй вход которого поступаютсигналы о составляющих матрицы. Сигналы о векторе-строке проходят через группу 20 элементов И, если результат сравнения н схеме сравненияне равен нулевому вектору, и посту"пают на вход умножителя 15, на второй вход которого одновременно поступает информация о составляющих нектора-столбца (9-5. а;), Выходные сигналы, соответствующие элементам матрицы(ц, а,)п 5; щ п,поступают на вход делителя 18, на второй вход которого поступает скалярная величина, Эта величина Фор" мируется следующим образом.Сигналы о составляющих вектора 5.а, поступают на узел 19 и далее на узел 16 умножения суммирования, на второй вход которого поступают сигналы о составляющих вектора 5,а) На выходе узла 16 Формируется скалярная величина, которая поступает на вход сумматора 17, на второй вход которого поступает информация о единице, хранимой н узле 21 ч считанной оттуда сигналом С кольцевого счетчика 36, Получившийся на выходе сигнал вида 1-(5; а;) (5; а;)1 приходит на вход делителя 18. С выхода 18 сигнала матрицы М поступают на вход сумматора 17, на второй вход которого поступают сигналы об элементах матрицы 5, В сумматоре 17 происходит вычитание из элементов матрицы 5 размера щ и 1 элементов матрицы . И размера л п. С выхода сумматора 17 сигналы поступают на вход узла 23 для исключения верхней нулевой строки. В результате на выходе узла 23 будут сигналы, соответствующие элементам матрицы А; размера 1 вп 1 . В том случае, когда в схеме 22 сравнения получается нулевой вектор, то сигналы с выхода схемы 22 поступают на первые входы элементов И второй группы, на вторые входы которых поступают сигналы о составляющих вектора 5; а;, которые проходят далее на умножитель 15. Одновременно сигналы о векторе 5;а, поступают иа первый вход умножителя 15, на второй вход которого поступают сигналы о транспонированной матрице5 12657 (5.,) 1 п (ч 1 с узла 19. Сигналы с выхода умножителя 15 о составляющих вектора (5,) (5;а;) 1 п 1) поступают на вход узла 19 транспонирования и далее на вход узла 16 умножения и суммирования, на второй вход которого поступают сигналы с тех же составляюпрзх вектора (5;) (5 а;). На выходе узла 16 получается скалярный сигнал, соответствующий величине 1 О5,) (5,) 5,) (5,(1 .Этот сигнал поступает на вход делителя 18, Сигналы с выхода узла 19матрицы (51) поступают на первый 15вход умножителя 15,. на второй входкоторого поступают сигналы о состав+ляющих матрицы 5 т. На выходе данного умножителя 15 получаются сигналы, соответствующие элементам матри+ т(- цы 5, (5,) (й (т. Эти сигналы поступают на второй вход умножителя 15,на первый вход которого поступаютсигналы с элементов И 20. На выходеумножителя 15 получаются сигналы осоставляющих вектора 5,(5.,) (5,а;)размера 1(т( 1). Эти сигналы поступаютна первый вход умножителя, на второйвход которого поступают сигналы овекторе-столбце ц 5, 1 п), На выходе 30данного умножителя 15 получаютсясигналы о составляющих матрицы5,5, 5 а;гп 5; размера 1 е п), Этисигналы поступают на делитель 18 свыхода которого сигналы проходят навход сумматора 17, в котором из сигналов, соответствующих матрице 5;,вычитаются сигналы, соответствующиематрице М=(5,5, 5 а;9 5; )/5 5 а;(яп, поступают на узел 23, на вы"ходе которого формируются сигналы осоставляющих матрицы А+, размера щ"1тп ) по сигналам СЗ счетчика 36. По 45сигналу "Сброс" осуществляется приведение всех узлов в исходное состояние.Блок 6 (фиг, 3) работает следующим образом,Сигналы соответствующие элемен - 0там матриц А;1 щ"1 и) и А; п щ,поступают на вход умножителя 24,на выходе которого формируются сигналы, соответствующие элементамматрицы А;А, размера (п п); Этисигналы поступают на сумматор 26,в котором вычитаются из единичнойматрицы размера п п, поступающей 96 Ьна вход сумматора из узла 31 по сиг калам С счетчика 36. Сигналы с выхода сумматора 26 поступают на вход умножителя 24, на вход которого поступают сигналы о составляющих вектора Х, п 1). Сигналы с выхода этого умножителя 24, соответствующие элементам вектора (1-А,А;)Х, п 1, поступают на вход схемы 28 сравнения сигналов о векторе с нулевым вектором, а также на вход узла 27 умножения и суммирования, на вход которого поступают сигналы о составляющих транспонированного векторатХ,11 и 1 с узла 25. На выходе узла 27 формируется скалярный сигнал, соответствующий величине Х 1"А;А;)Х;, который поступает на нход делителя 30. На вход делителя 30 поступают прошедшие через элементы И 29 (если результат сравнения не равен нулю) сигналы о составляющих вектора 1(1-А;А.)Х;. В результате на выходе делителя 30 Формируются сигналы, соответствующие составляющим вектора-столбца 6; п 1), Эти сигналы проходят через узел 25, на выходе которого получается искомая вектор- строка. В том случае, если результат сравнения в схеме 28 сравнения равен нулю, то сигналы с него поступают на входы элементов И другой группы, Сигналы о составляющих век" тора А,Х, ш1 поступают на вход узла 25, после чего проходят на вход узла 27, на второй вход которого поступают сигналы о векторе А;Х,. На выходе узла 27 Формируется скалярный сигнал, соответствующий величитне (А Х,) (АХ,). Этот сигнал поступает на сумматор 26, в котором про" исходит его суммирование с единичным сигналом, поступившим из узла 32 по сигналу С 2 счетчика 36. Выходной сигнал сумматора 26 поступает на делитель 30, на второй вход которого поступают прошедшие через элементы И 29 сигналы с выхода умножителя 24, соответствующие элементам векто-Ф т фра (А,) А,Х; п. 11. На вход умножителя 24 поступают сигналы о составляю" щих вектора А,Х;1(з 1), а на другой вход - сигналы с выхода узла 25 (А об элементах этой матрицы п щ). Сигналы с выхода делителя30, соответствующие величинам А+, А+1 Х;/1+(АХ) (А,Х; ) поступают на вход узла 25, на выходе котооо1265796 8 ходное блока 4, по сигналу "Сброс" приведение в исходное блоков 5-8,7го формируются сигналы об искомом векторе Ь; 1 п 1. По сигналу "Сброс осуществляется приведение в исходное всех узлов блока 6.Блок 7 (фиг. 4) работает следующим образом.Поступающие на его вход сигналыт о составляющих вектора-строки и; 1 т фп 1 и вектора-столбца А,Х;1 шЦ поступают на входы умножителя 33, на выходах которого формируются сигт н ы о составля щих матрицы А;Х Ь; размерности щп, Зти сигналы поступают на вход сумматора 34, на другой вход которого поступают сиг+ г налы о составляющих матрицы А;рф хп 1. На выходе сумматора 34 формируются сигналы искомой матрицы НФ 4н =А;-А;Х;Ь ,. По сигналам С 4 эта информация переписывается в блок 4, а по сигналу "Сброс" осуществляется приведение в исходное состояние умножителя 33 и сумматора 34.Генератор 35 и счетчик 36 в блоках 5 и 6 предназначены для синхронизации работы устройства. Узел коммутации осуществляет переворот матрицы относительно главной диагонали (операцию транспонирования). Все блоки памяти содержат в своем состане, например, регистры сдвига, столько, сколько необходимо в каждом иэ рассмотренных в устройстве блоков. Буферный запоминающий узел представляет собой узел памяти, состоящий, например, из регистра сдвига, однако считывание информации в этом узле осуществляется со всех параллельных регистров сдвига, кроме первого. Блок 3 управления работает сле" дующим образом.По сигналу пуска включается вработу генератор 38, импульсы с которого поступают на вход счетчика39, сигнал с выхода счетчика 39 Споступают на одни входы элементовИ 37, на вторые входы которых поступают импульсы с выхода генератора 38. Импульсы с выходов элементов И 37 поступают на входы блока 2,Время действия импульсов определяется временем действия сигнала СПо сигналам С 1 осуществляется считывание информации из блоков 4 и 1,по сигналам С 2, СЗ, С 4 - синхрони -зация работы блоков 5-7, по сигналуС 5 осуществляется приведение в ис 1 О 5 20 25 30 35 40 45 50 Формула изобретения 1, Устройство для выполнения операций обращения матриц, содержащее первый блок памяти и блок управления, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет получения псевдообратных матриц для вырожденных, квадратных, прямоугольных, плохообусловленных матриц и для матриц, полученных перемножением векторов, в него введены блок умножения и суммирования, второй и третий блоки памяти, первый и второй блоки формирования матриц, блок умножения и шесть блоков элементов задержки, причем первая и вторая группы информационного выхода первого блока памяти подключены соответственно к первому информационному входу первого блока формирования матриц и к входу первого блока элементов задеряжи, выход второго блока памяти соединен с информационным входом первого блока памяти и с входами второго и третьего блоков элементов задержки, выход второго блока элементов задержки соединен с первым информационным входом блока умножения, выход которого подключен к входу четвертого блока элементов задержки и к первому информационному входу второго блока формирования матриц, второй информационный вход которого, второй информационный вход блока умножения и вход пятого блока элементов задержки соединены с выходом первого блока формирования матриц, второй информационный вход которого соединен с выходбм третьего блока памяти, выходы первого и третьего блоков элементов задержки соединены соответственно с третьим и четвертым информационными входами второго блока формирования матриц, выход которого соединен с первым информационным входом блока умножения и суммирования и через шестой блок элементов задержки подключен к первому информационному входутретьего блока памяти, выходы четвертого и пятого блоков элементовзадержки соединены соответственно с вторым и третьим информационными входами блока умножения и суммирования,2657 20 выход которого подключен к второмуинформационному входу третьего блокапамяти, вход пуска блока управленияявляется входом пуска устройства,установочный выход блока управленияподключен к установочным входам блокаумножения первого и второго блоковформирования матриц и блока умножения и суммирования, группа выходовсчитывания блока управления подключена к группе входов считывания второго блока памяти, первый синхронизирующий выход блока управления подключен к входам считывания первого итретьего блоков памяти, второй, третий, четвертый и пятый синхрониэирующие выходы блока управлениясоединени соответственно с синхронизирующими входами первого и второго блоков формирования матриц,блока умножения и суммирования итретьего блока памяти, причем первыйблок формирования матриц содержитумножители, делители, сумматоры,узлы коммутации, узлы памяти, схему сравнения, буферный запоминающийузел, счетчик и геНератор прямоугольных импульсов, вход которого является синхрониэирующим входом первого блока формирования матриц, а вы- З 0ход подключен к счетному входу счетчика, установочный вход которогоявляется установочным входом первого блока формирования матриц, выходыразрядов счетчика подключены соот.ветственно к входам считывания первого и второго узлов памяти и буфер"ного запоминающего уэла, выход которого является выходом блока, первыйвход первого умножителя является пер вым информационным входом первогоблока формирования матриц, выход .первого узла памяти соединен с пер-,вым входом первого сумматора и черезпервый узел коммутации - с первым 45входом второго умножителя, выход первого умножителя соединен с первымвходом третьего умножителя, с вторымвходом первого сумматора и черезвторой узел коммутации - с первым 50входом первого узла умножения и суммирования, выход второго умножителяподключен к первым входам четвертогоумножителя и элементов И первой группы, выходы которых соединены с первым 55входом пятого умножителя, выход которого соединен с первым входом первого делителя, выход которого подключен к первому входу второго сумматора, выход которого соединен с первым информационным входом буферногозапоминающего узла, выход первогосумматора соединен с вторим входомпятого умножителя и с входом схемысравнения, выход ненулевого значениякоторой соединен с вторыми входамиэлементов И первой группы, выход нулевого значения схемы сравнения соединен с первыми входами элементов Ивторой группы, вторые входы которыхи второй вход первого узла умножения и суммирования соединены с выходом первого умножителя, выход первого узла умножения и суммированиясоединен с первым входом третьегосумматора, второй вход которого соединен с выходом второго узла памяти,выход третьего сумматора соединен свторым входом первого делителя, второй информационный вход первого блока формирования матриц соединен свторыми входами первого и второгоумножителей и второго сумматора, спервым входом четвертого сумматора,с входами третьего узла коммутациии шестого умножителя, выход которогоподключен к первому входу седьмогоумножителя, второй вход которого соединен с выходами элементов И второйгруппы, выход третьего узла коммутации соединен с вторым входом третьего умножителя, выход которого соединен с первым входом второго узла ум"ножения и суммирования, второй входкоторого через четвертый узел коммутации соединен с выходом третьегоумножителя, выход второго узла умножения и суммирования соединен спервым входом второго делителя, выход которого подключен к второму входу четвертого сумматора, второй входвторого делителя соединен с выходомчетвертого умножителя, второй входкоторого соединен с выходом седьмого умножителя, выход четвертогосумматора подключен к второму информационному входу буферного запоминающего узла, второй блок формирования матриц содержит узлы коммутации, умножители, сумматоры,. делители, узлы памяти, узлы умножения исуммирования, группы элементов И,счетчик и генератор прямоугольныхимпульсов, вход которого является,синхронизирующим входом второго блока формирования матриц, а выход под"12657 ключен к счетному входу счетчика, установочный вход которого является установочным входом второго блока формирования матриц, второй информационный вход второго блока формирования матриц соединен с первым входом первого умножителя и через первый узел коммутации - с первым входом второго умножителя, первый информационный вход второго блока фор О мирования матриц соединен с вторым входом второго умножителя, с первым входом первого узла умножения и суммирования и через второй узел коммутации - с вторым входом первого уз ла умножения и суммирования, второй вход первого умножителя является третьим информацнонным входом второго блока формирования матриц, четвертый информационный вход которого соеди нен с первым входом третьего умножителя и через третий узел коммутации - с первым входом второгоузла умножения и суммирования, входы первого сумматора соединены соответственно с 25 ,выходами первого умножителя и пер. -вого узла памяти, выход первого сумматора подключен.к второму входу третьего умножителя, выход которого соединен с вторым входом второго уз- ЗО ла умножения и суммирования, с первыми входами элемента И первой группы и с входом схемы сравнения, . выходы которой подключены соответственно к первым входам элементов И второй группы и к вторым входам элементов И первой группы, входы первого делителя соединены соответственно е выходом второго узла умножения и суммирования и с выходами эле О 96 12ментов И первой группы, входы четвертого узла коммутации соединены соответственно с выходами первого и второго делителей, выход четверто. го узла коммутации является выходом второго блока Формирования матриц, входы второго делителя соединены соответственно с выходом второго сумматора и с выходами элементов И вто" рой группы, вторые входы которых соединены с выходом второго умножителя, входы второго сумматора соединены соответственно с выходами второго узла памяти и первого узла умножения и суммирования, выходы разрядов счетчика подключены соответственно к входам считывания первого и второго узлов памяти.2. Устройство по пе 1, О т л ич а ю щ е е с я тем, что блок управления содержит элементы И, счетчик и генератор прямоугольных импульсов, вход которого является входом пуска блока, а первый выход подключен к счетному входу счетчика, выход первого разряда которого соединен с первыми входами элементов И, выходы последующих разрядов счетчика являются соответственно с первого по пятый синхронизирующими выходами блока управления, выход переполнения счетчика соединен с установочным выходом блока и с установочным входом счетчика, вторые входы элементов И соединены с вторым выходом генерато ра прямоугольных импульсов, третьи входы подключены к пятому синхронизирующему выходу блока, выходы элементов И являются группой выходов считывания блока.2 Г 57 ц 6 а,г л,Составитель А,гереновТехред А.Кравчук Корректор Л.Пилипенк актор А.Воро ак 1303 Производственно-полиграфическое предприятие, г, Ужгород,ул. Проекти Тираж 67И ГасударственноГо ком делам изобретений н от Москва, Ж, Раушская Подписноетета СССРрытийнаб д. 4/5