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

,9180 Р 15/34 ИЕ ИЗОБРЕТЕНИЯ СВИДЕТЕЛЬСТВУ 21) 4 22) 1 46) 0 е начальая матрийства Е - единичная матрица;и - размерность матрицы А.Скорость сходимости алгоритма определяется выражением1 А - А------ В(.-1Е - А Аок - ЦАЦ КВ качестве начального приближения, если оно не известно, можно выбрать единичную матрицу.На фиг.1 приведена структурная схема устройства для обращения матриц; на фнг. 2 " блок вычисления коэффициента 1 ц ; на фиг.3 - блок вычисления элементов матрицы В; на фиг.4 " блок вычисления итераций; на фиг.5- временная диаграмма работы блока вычисления коэффициента ц .Устройство (фиг.1) ср ею вый информационный вход но оложи ения триц. ения шинах для обра определенных м ение фунойства Цель изобрециональных воз за счет обраще расши ей уст ожител пол ос еделенных ма Цель дос ии алгоритмаый имеет в оригиналь но матриц, кот Е + Ака; одержит пе1, первый лижение; ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИПРИ ГКНТ СССР(56) Авторское свидетельство СССРУ 813444, кл. С 06 Г 15/324, 981.Авторское свидетельство СССРУ 595726, кл. С 06 Г 7/38, 978.(54) УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ МАТРИЦ(57) Изобретение относится к областивычислительной техники и может быть Изобретение относится к вычислиельной технике и может быть испольовано в цифровых вычислительных маиц.гается использование 2использовано В цифровых вычислитель ных системах для обращения матриц, Цель изобретения - расширение функциональных возможностей устройства за счет обращения положительно опр - деленных матриц. Цель достигается применением оригинального итерационного алгоритма обращения.,матриц -А =(2 ф) Е 4 А В, где В=Е -(2/р) А;ШЫ Иа; А - исходнаяК,дматрица размерности и; А - ное приближение; Е - единичн ца, Структура и работа устро являются адекватным отражением приве- а денного алгоритма, 5 ил.ф(Фиг.2) содержит генератор 27, сдвиговый регистр 28, сумматор 29, буФерный регистр ЗО, регистр 31 максимума, схему 32 сравнения, триггеры 33 и 34, элементы И 35 и 36.Блок работает следующим образом. 25По сигналу от внешнего источникапроисходит запуск генератора 27, вырабатывающего две серии импульсов:прямую и инверсную. Но каждому импульсу на вход сумматора 29 поступает элемент строки обрабатываемойматрицы, на выходе сумматора 29 формируется результат сложения этогоэлемента с текущим значением промежуточной суммы, хранящейся в буферном регистре ЗО, Через и импульсовна (и+)-м,. выходе сдвигового регистра 28 появляется единичный потенциал(результат продвижения единицы, занесенной в первый разряд сдвиговогорегистра 28), по которому триггер33 переходит в единичное состояние изапрещает перезапись информации вбуферный регистр 30. Одновременнопроисходит сравнение чисел в буФерном регистре 30 и регистре 31 максимума. Если число в буферном регистребольше числа в регистре максимума,схема 32 сравнения устанавливаеттриггер 34 в единичное состояние итем самым разрешает прохождение(и+2)-го импульса перезаписи информации из буферного регистра в регистр максимума, В противном случаесодержимое регистра максимума необновляется, По (и+3)-му импульсу55буферный регистр и триггер 34 обиуляются, по (и+4)-му импульсу обнуляется триггер 1 33 и в первом разряде сдвигового регистра устанавливаетсяединица. Блок готов к вычислению очередного значения суммы элементовстроки матрицы н определению текущего максимального значения, Черези циклов и регистра максимума хранится значениеБлок вычисления элементов матрицыВ (фиг.З) содержит управляемый генератор 37, кольцевой сдвиговый регистр 38, коммутатор 39, вычитатель40.Блок работает следующим образом,В исходном состоянии в первый разрядсдвнгового регистра 38 занесена единица, остальные разряды обнулены.По единичному сигналу с первого разряда сдвигового регистра коммутатор39 подклкяает вычитатель к второмуи третьему информационным входамблока вычисления элементов матрицы3, на которые подаются соответственно числа и" и "0". По сигналу запуска с блока управления генератор переходит в автоколебательный режим, Покаждому импульсу генератора единица,занесенная в первый разряд сдвиговогорегистра, продвигается в соседнийстарший разряд. Через каждые и тактов коммутатор подает числа "1" и"О" на вход вычитателя. На второйвход вычитателя поступает текущийэлемент матрицы 2/ М А, Процесс вычисления прекращается по появлениюзапрещавшего сигнала на входе генератора 37.Блок вычисления итерации (Фиг.4)содержит узлы 41 и 42 задержки, элементы ИЛИ 43 и 44, узел 45 памяти,регистры 46 и 47, скалятор 48, коммутатор 49, кольцевой регистр 50 исумматор 51,Блок работает следующим образом.По команде запуска управления из блока 10 памяти через узел 45 памяти врегистры 46 и 47 заносятся соответственно столбец матрицы В и строкаматрицы А. В скаляторе 48 вычисляется элемент матрицы, который в случаенеобходимости в соответствии с алгоритмом (1) складывается с 2/1,что обеспечивается кольцевым сдвиговым регистром 50 и коммутатором 49В результате на выходе блока формируется элемент матрицы очередногоприближения А;, По сигналу с выходапризнака пятого цикла вычисленийблока управления осуществляется по1647591 5элементное чтение матрицы А;,(., с одновременным занесением в те же ячейки узла 45 памяти значений новой матрицы А(, .Устройство работает следующим образом,В первый блок памяти заносятся элеМенты обращаемой матрицы, а в блок вычисления итераций - элементы матрицы начального приближения, По сигналу запуска блок управления вырабатывает сигнал признака первого цикла вычислений, по которому первый блок памяти переходит к режиму чтения, а блок вычисления коэффициента- к вычислению М . С первого блока Формирования адреса на адресный вход первого блока памяти поочередно поступают адреса упорядоченного множества элементов матрицы, которое синхронизируется признаком чтения. В блоке вычисления коэффициента каждый поступающий элемент матрицы обрабатывается в соответствии с формулой (3). По истечении (и+4) такЯ тов на выходе блока формируется значение. Затем по сигналу с выхода признака второго цикла вычислений блока управления в блоке деления вы 2числяется значейие -- . Блок управГления вырабатывает сигнал признака третьего цикла вычислений, по которому первый блок памяти переходит в режим чтения и запускаются блоки умножения и блок вычисления элементов матрицы В. Одновременно упорядоченные адреса элементов матрицы А формируются в блоке 23, Элементы матрицы В, вычисленные в блоке 7, заносятся в соответствующие ячейки второго блока 10 памяти, В блоке управления формируется циклически серия импульсов то на выходе признака четвертого цикла вычислений, то на выходе признака пятого цикла вычислений. На втором выходе второго блока 24 Формирования адреса Форми" руются адреса элементов столбцов матрицы А и строк матрицы В, которые поступают в блок 5 для вычисления элементов матрицы А Полученные значения заносятся в третий блок 11 памяти, в котором по завершении четвертого цикла вычислений оказываются занесенными все элементы матрицыв 1А к+4По сигналу с выхода признакапятого цикла вычислений блока управления происходит перезапись элементов матрицы А+( из третьего блокапамяти в блок вычисления итераций.Одновременно в блоке 1 3 вычисляется разность соответствующих((элементов матриц А и А,которая сравнивается в схеме сравнения 15 с заранее заданным допускомЯ, поданным на второй информационный вход устройства 26. В случае,если разность превысит допустимую,импульс с выкода схемы сравнения переведет триггер 6 в единичное состояние. В начале пятого цикла вычислений сигнапом с выхода дешифратора1 7 триггер 16 обнуляется, Дешифратор20 1 селектирует адрес первого элемен"та матрицы. Когда в блоке 23 Формирования адреса сформируется адрес последнего элемента матрицы, на выходедешифратора 19, селектирующего адреспоследнего элемента, вырабатываетсясигнал окончания вычислений, которыйв случае выполнения- условияА 1(- АК (Е(триггер 16 остается в ну 1 левом состоянии) поступает через30 элемент И 18 на выход признака окончания вычислений устройства и на одноименный вход блока управления. Еслив процессе сравнения элементов матрицА и А, триггер,16 перейдет иединичное состояние, то сигнал сего выхода запретит прохождение сигнала окончания вычислений на входблока управления, произойдет повторение четвертого и пятого циклов вычис 40 лений. формула изобретения 45 Устройство дпя обращения матриц,содержащее блок деления, блок вычитания, блок управления, регистр, триг-, гер, элемент И и элемент ИЛИ, о т - л и ч а ю щ е е с я тем, что, с 50 целью расширения функциональных возможностей устройства за счет обращения положительно определенных матриц, в него введены три блокапамяти, блок вычисления коэффициента Ц, блок умноженияф два блока Формирования дд реса, блок вычисления элементов матрицы В, схема сравнения, два дешифратора, блок вычисления итераций, причем информационный вход устройстваподключен к информационному входу первого блока памяти, первый выход которого соединен с информационным входом блока вычисления коэффициента Ц , выход которого подключен к первому входу блока деления, выход которого подключен к первый информационным входам блока вычисления итераций и бло-. ка умножения, второй информационный 1 О вход и выход которого подключены соответственно к второму выходу первого блока памяти и первому информационному входу блока вычисления элементов матрицы В, второй и третий информационные входы которого подключены соответственно к перввму и второму информационным входам группы устройства, выход блока вычисления элементов матрицы В подключен к информационному входу второго блока памяти, вьиод которого подключен к второму информационному входу блока вычисления итераций, первый информационный выход которого соединен 25 с информационным входом третьего бпока памяти, выход которого подключен к третьему информационному входу блока вычисления итераций, информационному выходу устройства и перво- Зо му входу вычитателя, выход и второй вход которого соединены соответственно с первым входом схемы сравнения и выходом регистра, вход которого подключен к второму информационному выходу блока вычисления итераций, второй вход и выход схемы сравнения подключены соответственно к второму информационному входу устройства ивходу установки триггера, вход обнуления и выход которого подключены соответственно к выходу первого дешифратора и первому входу элемента И, второй вход и выход которого подключены соответственно к выходу второго дешифратора и выходу признака окончания вычислений устройства, объединенному с одноименным входом блока управления, вход запуска и выход признака первого цикла вычислении котб 1 Я 5 го подключены соответственно к входузапуска устройства и входу запускаблока вычисления коэффициента Й,объединенному с входом признака первого цикла вычислений первого блокаформирования адреса и первым входомэлемента ИЛИ, выход которого подключен к входу управления записью-считыванием первого блока памяти, входадреса которого соединен с первымвходом адреса второго блока памятии первым выходом первого блока формирования адреса, вход признака третьего цикла вычислений которогоподключен к выходу признака третьегоцикла вычислений блока управления,второму входу элемента ИЛИ, входамзапуска блока умножения блока вычисления элементов матрицы В и второго блока памяти, второй вход адресакоторого подключен к первому выходувторого блока формирования адреса,вход запуска которого подключен квыходу признака четвертого цикла вычислений блока управления, входу запуска третьего блока памяти и первомувходу запуска блока вычисления итераций, первый вход адреса которогоподключен к второму выходу второгоблока формирования адреса, выходпризнака пятого цикла вычислений блока управления подключен к входу запуска первого блока формирования адреса, третьему входу элемента И, второму входу запуска блока вычисленияитераций, второй вход адреса которогоподключен к второму выходу первогоблока формирования адреса, входампервого и второго дешифраторов и входу адреса третьего блока памяти, выход признака второго цикла вычислений блока управления подключен к вхо"ду запуска блока деления, вход усгановки начальных данных блока вьщйсления итераций является третьим информационным входом устройства.1647591 Составитель К.Кухаренкоедактор Н,Гунько Техред М.Дидык Корректор Л.Патай льский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 роизводственно"и Заказ 1401 Тираж, 421 ВНИИПИ Государственного комитета113035, Москва, Ж Подписноеизобретениям и открытиям при ГКНТ ССС Раушская наб., д. 4 И