Пристрій для операцій над матрицями

Изобретение относится к цифровой вычислительной технике и может быть использовано для операций над матрицами в арифметических сопроцессорах и специализированных процессорах. Известно устройство для операций над матрицами (Авт. св. СССР №1464171), содержащее первую гр уппу информационных входов, второй информационный вход, синхроввод, операционные блоки, выходы. Работа устройства основана на треугольном разложении и вычислении определителя плотной (n * n) матрицы, реализующем алгоритм разложения плотной n * n матрицы A на нижнюю треугольную n * n матрицу B и верхнюю треугольную матрицу C с единичной диагональю. При этом определитель /A/ равен произведению диагональных элементов, т.е. /A/ = b11 * b22 * b33 * bnn. Недостаток прототипа заключается в больших аппаратурных затратах при выполнении операций над матрицами высокого порядка. Задачей изобретения является усовершенствование устройства путем использования алгоритма расщепления исходной матрицы A на компоненты, представляющие собой смыкающиеся квадранты - матрицы Ai на Wi и Zi, что позволяет вычислять определитель плотной матрицы n * n матрицы A с помощью простого устройства, решающего систему линейных уравнений не выше второго порядка, независимо от порядка исходной матрицы, в отличие от рассмотренного разложения на верхнюю и нижнюю треугольные матрицы, где количество операционных блоков соизмеримо с порядком матрицы. Выполнение поставленной задачи достигается тем, что в известное устройство для операций над матрицами, содержащее матрицу исходных коэффициентов A, матрицы коэффициентов разложения B и C введен операционный блок, матрицы коэффициентов разложения W и Z, блок управления, причем первый, второй и третий информационные входы операционного блока соединены двухсторонними связями с информационными входами матриц A, W и Z соответственно. Первый, второй и третий выходы блока управления соединены с управляющими входами матриц A, W и Z соответственно. Четвертый, пятый и шестой выходы блока управления соединены с первым, вторым и третьим управляющими входами операционного блока. Предлагаемое устройство для операций над матрицами обладает существенным отличием по сравнению с известными техническими решениями, поскольку именно совокупность отличительных признаков: операционного блока, решающего уравнения не выше второго порядка, блоков матриц разложения W и Z их взаимосвязь между собой и известными признаками, присущими прототипу, позволяет упростить конструкцию. Кроме того, только совокупность отмеченных выше признаков с дополнительными признаками дает возможность упростить конструкцию, что невозможно осуществить с помощью прототипа и други х выявленных аналогов. Устройство (фиг.1) содержит матрицу исходных коэффициентов 1, матрицы коэффициентов разложения 2, 3, операционный блок 4, блок управления 5, причем первый, второй и третий информационные входы операционного блока 4 соединены двухсторонними связями с информационными входами матриц A-1, W-2 и Z-3 соответственно. Первый, второй и третий выходы блока управления 5 соединены с управляющими входами матриц A-1, W-2 и Z-3 соответственно. Четвертый, пятый и шестой выходы блока управления 5 соединены с первым, вторым и третьим управляющими входами операционного блока 4. Операционный блок (фиг.2) содержит блок из четырех регистров 6, блоки умножения 7 8, блок вычитания 9, делители 10 - 13, умножители 14 - 17, сумматоры 18 - 19, умножители 20 - 21, вычитатели 22 - 23, регистр 24, умножитель 25, причем вход блока из четырех регистров 6, соединен с матрицей исходных коэффициентов A1, первый - четвертый выходы которого соединены со входами группы умножителей 7 - 8, выходы которых являются входами вычитателя 9, выход которого соединен со вторыми входами четырех делителей 10 - 13, первые входы которых являются выходами 1, 2, 3 и 4 блока из четырех регистров, где хранятся значения матрицы исходных коэффициентов A-1, а вы ходы соединены с первыми входами группы умножителей 14 - 17, вторые входы пар умножителей 14, 16 и 15, 17 соединены с пятым и шестым выходом блока из четырех регистров, где хранятся значения матрицы исходных коэффициентов A-1 соответственно, выходы которых соединены со входами сумматоров 18 19, выходы которых являются входами матрицы коэффициентов W-2, соединенные со вторыми входами умножителей 20 - 21, первые входы которых соединены с матрицей коэффициентов Z3, а выходы являются входами вычитателя 22, выход которого соединен со вторым входом вычитателя 23, первый вход которого является седьмым выходом блока из четырех регистров, где хранятся значения матрицы коэффициентов A, выход которого соединен с первым входом блока умножения 25, второй вход которого является выходом регистра 24, входом которого является выход устройства вычитания 9. В устройстве реализован метод смыкающихся квадрантов, основанный на разложении и расщеплении матрицы коэффициентов A на компоненты W и Z, т.е. A = W * Z, где W и Z для матрицы третьего порядка имеют вид: Элементы матриц W и X определяются по формулам: алгоритма: и заносится в регистр 6 операционного блока 4. Операционный блок решает систему линейных уравнений порядка 2 ´ 2, выполняя операции умножения, вычитания и деления по микрокомандам, поступающим из блока управления 5, т.е. Элементы Wi,1, Wi,n для i = 1, 3, ..., -1 определяются в результате решения следующей системы уравнения второго порядка: Значение уравнения элемента Z22 определяется из При этом определитель /A/ = d * Z22, где d определитель выше указанной системы уравнений второго порядка. В общем виде определитель плотной матрицы A для четного количества элементов матрицы равен: и для нечетного количества элементов матрицы На фиг.1 приведена структурная схема предлагаемого устройства; на фи г.2 функциональная схема операционного блока; на фиг.3 временная диаграмма работы операционного блока. Устройство работает следующим образом. В исходном состоянии регистры 6, 24 устройства устанавливаются в нулевое состояние. Процедуру вычисления определи1 теля плотной матрицы рассмотрим на примере плотной матрицы третьего порядка Выполним процедуру разложения матрицы A на W и X где Z11 =a11 * Z12 = a 12 * Z13 = a13 * Z 31 = a31 * Z 32 = a32 * Z 33 = a33 . Элементы первой и последней строки матрицы Z равны элементам соответствующих строк исходной матрицы A. В первом такте из матрицы 1 коэффициентов A сигналами из блока управления выбирается пара строк согласно следующего Во втором такте значения коэффициентов уравнения Z11, Z33, Z 13 , Z31 поступают на входы умножителей 7 - 8, на выходе которых формируется значение Z11 * Z33 и Z 13 * Z 31 соответственно. В третьем такте значения произведений поступают на вход вычитателя 9, на выходе которого формируется значение детерминанта d, которое записывается в регистр 24 В четвертом такте элементы матрицы Z33, Z 31, Z13 , Z 11 и значение detB поступают на вход гр уппы делителей 10 - 13, на выходах которых формируются значения Z33/d; Z31/d; Z 13/d; Z 11 /d. В пятом такте значения частных и коэффициентов a11 и a21 поступают на вход умножителей 14 - 17, на выходах которых формируются значения их произведений. В шестом такте значения произведений поступают на входы сумматоров 18 - 19, на выхода х которых формируются значения коэффициентов W21 и W23, которые поступают на вход матрицы коэффициентов W. получим матрицу Следующий этап - вычисление коэффициента преобразования Z22 по следующему алгоритму: В седьмом такте из матрицы коэффициентов Z выбирается пара значений элементов Z12 и Z23 и поступает на первые входы умножителей 20 - 21, на вторые входы которых поступают ранее вычисленные значения коэффициентов W21 и W23 из матрицы коэффициентов W. На выходах умножителя 20, 21 формируются значения произведений Z32 * W23 = 3 * (-5) = -15 и Z12 * W21 1 * 4 = 4. В восьмом такте значения произведений поступают на вход вычитателя 22, на выходе которого формируется промежуточный результат уравнения: Z12 * W21 - Z32 * W23 = +4 - 15 = -11, который подается на второй вход вычитателя 23, на первый вход которого поступает значение коэффициента a22 из матрицы A. В девятом такте на выходе вычитателя 23 формируется значение коэффициента Z22 = 2 - (-11) = 13, которое поступает на первый вход умножителя 25, на второй вход которого поступает значение детерминанта системы линейных уравнений второго порядка, хранящееся в регистре 24. В десятом такте на выходе умножителя 25 формируется произведение Z22 * d = 13 * 2 = 26, соответствующее определителю плотной матрицы третьего порядка A. Использование в предлагаемом устройстве избыточной позиционной системы счисления с весовыми коэффициентами -1, 0, 1 для представления значений функции позволяет совместить процесс поразрядного ввода и переработки информации при вводе операндов старшими разрядами вперед и способствует решению проблемы минимизации числа внешних выводов операционного блока для решения системы линейных уравнений. Операционный блок реализован в виде БИС с использованием КМОП 2-микронной технологии. Матрица как конструктивный элемент представляет собой регистровый блок на основе триггерных элементов, выполненных на пластине кремния размером 3,5 * 3,5мм по 2-микронной КМОП технологии с двойной металлизацией.