устройство для вычисления собственных значений (n x n)- матрицы

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

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ (N X N)-МАТРИЦЫ, содержащее вычислительный модуль первого типа, 2n - 1 вычислительных модулей второго типа и блок анализа, причем вычислительный модуль первого типа содержит два регистра, узел вычисления обратной величины числа, два триггера, четыре группы элементов И, группу элементов ИЛИ и четыре элемента И, вычислительный модуль второго типа содержит первый, второй и третий регистры, умножитель, сумматор, три тригера, семь групп элементов И, две группы элементов ИЛИ и элементы И с первого по четвертый, а блок анализа содержит 2n регистров, n вычитателей, n схем сравнения и первый и второй элементы И, причем i-й информационный вход группы и i-й настроечный вход группы устройства (i = ) подключены соответственно к первому информационному входу и первому настроечному входу i-го вычислительного модуля второго типа, первый информационный вход и первый и второй настроечные входы устройства подключены соответственно к первому информационному входу и первому и второму настроечным входам вычислительного модуля первого типа, первый информационный выход вычислительного модуля первого типа подключен к второму информационному входу первого вычислительного модуля второго типа, первый информационный выход j-го вычислительного модуля второго типа (j = ) подключен к второму информационному входу (j + 1)-го вычислительного модуля второго типа, третий информационный вход j-го вычислительного модуля второго типа подключен к второму информационному выходу (j + 1)-го вычислительного модуля второго типа, второй информационный выход первого вычислительного модуля второго типа подключен к второму информационному входу вычислительного модуля первого типа, второй информационный выход которого подключен к первому информационному входу анализа, второй информационный вход которого подключен к входу задания точности вычислений устройства, синхровход которого подключен к синхровходам всех вычислительных модулей и блока анализа, l-й выход блока анализа (l = ) подключен к l-му выходу устройства, выход признака окончания вычислений которого подключен к (l + 1)-му выходу блока анализа, причем в вычислительном модуле первого типа первый информационный вход модуля подключен к информационному входу первого регистра, выход которого подключен к первым входам элементов первой группы, второй информационный вход модуля подключен к информационному входу второго регистра, инверсный выход которого подключен к первым входам элементов И второй группы, а прямой выход - к первым входам элементов И третьей группы и входу узла вычисления обратной величины числа, выход которого подключен к первым входам элементов И четвертой группы, выходы элементов И первой, второй, третьей и четвертой групп подключены соответственно к первому, второму, третьему и четвертому входам элементов ИЛИ группы, выходы которых подключены к первому информационному выходу модуля, первый и второй настроечные входы которого подключены соответственно к информационным входам первого и второго триггеров, прямой выход первого триггера подключен к первым входам первого и второго элементов И, а инверсный выход - к первым входам третьего и четвертого элементов И, прямой выход второго триггера подключен к вторым входам первого и четвертого элементов И, а инверсный выход - к вторым входам второго и третьего элементов И, выходы первого, второго, третьего и четвертого элементов И подключены соответственно к вторым входам элементов первой, второй, третьей и четвертой групп, синхровход модуля подключен к синхровходам всех регистров и триггеров, а каждом из вычислительных модулей второго типа первый информационный вход модуля соединен с информационным входом первого регистра, выход которого соединен с первым входами элементов И первой группы, выходы которых соединены с первыми входами элементов ИЛИ первой группы, выходы которых соединены с первыми входами умножителя, выходы которого соединены с входами первого слагаемого сумматора, выходы которого соединены с первыми входами элементов И второй группы, выходы которых соединены с первыми входами элементов ИЛИ второй группы, второй информационный вход модуля соединен с информационным входам второго регистра, выходы которого соединены с вторым входом умножителя, третий информационный вход модуля соединен с информационным входом третьего регистра, выходы которого соединены с входами второго слагаемого сумматора и первыми входами элементов И третьей группы, выходы которых соединены с вторыми входами элементов ИЛИ первой группы, прямой выход первого триггера соединен с первыми входами первого и второго элементов И, инверсный выход первого триггера соединен с первыми входами третьего и четвертого элементов И, прямой выход второго триггера соединен с вторыми входами второго и третьего элементов И, инверсный выход второго триггера соединен с вторыми входами первого и четвертого элементов И, синхровход модуля соединен с синхровходами всех регистров и триггеров, а в блоке анализа первый информационный вход блока соединен с информационным входом первого регистра, выход l-го регистра (l = ) соединен с l-м выходом блока и первым входом l-го вычитателя, второй вход которого соединен с выходом (l + n)-го регистра, а выход - с первым входом l-о схемы сравнения, второй вход которой соединен с вторым информационным входом блока, отличающееся тем, что в каждый вычислительный модуль второго типа введены четвертый регистр, группа из n - 1 регистров, пятый и шестой элементы И, элемент НЕ и два элемента ИЛИ, а в блок анализа введены два делителя, третий элемент И, элемент ИЛИ и триггер, при этом первый и второй настроечные выходы вычислительного модуля первого типа подключены соответственно к второму и третьему настроечным входам первого вычислительного модуля второго типа, первый и второй настроечные выходы j-го вычислительного модуля второго типа подключены соответственно к второму и третьему настроечным входам (j + 1)-го вычислительного модуля второго типа, первый и второй настроечные выходы и второй информационный выход вычислительного модуля первого типа соединены соответственно с прямыми выходами первого и второго триггеров и выходом второго регистра вычислительного модуля первого типа, а в вычислительном модуле второго типа первый информационный вход модуля соединен с первыми входами элементов И четвертой группы, вторые входы которых соединены с выходом пятого элемента И, первый вход которого соединен с первым настроечным входом модуля и информационными входами третьего триггера, инверсный выход которого соединен с третьими входами первого и третьего элементов И, второй настроечный вход модуля соединен через элемент НЕ с первым входом пятого элемента И, второй вход которого соединен с третьим настроечным входом модуля, первый информационный выход которого соединен с выходами элементов И пятой группы, первые входы которых соединены с выходом второго регистра, а вторые входы - с выходом первого элементов ИЛИ, первый вход которого соединен с выходом третьего элемента И, вторыми входами элементов И третьей группы, первыми входами элементов И шестой группы и первым входом шестого элемента И, выход которого соединен с синхровходом четвертого регистра, информационный вход которого соединен с выходом умножителя и вторыми входами элементов И шестой группы, выходы которых соединены с вторыми входами элементов ИЛИ второй группы, третьи входы которых соединены с выходами элементов И четвертой группы, а выходы - с информационным входом первого регистра группы, выход k-го регистра группы (k = ) соединен с информационным входом (k + 1)-го регистра группы, выход (n - 1)-го регистра группы соединен с вторым информационным выходом модуля, выход первого элемента И соединен с вторыми входами элементов И второй группы, первыми входами элементов И седьмой группы и вторым входом первого элемента ИЛИ, третий вход которого соединен с первым входом второго элемента ИЛИ, выходом четвертого элемента И и третьими входами второй группы, четвертые входы которых соединены с выходом второго элемента И, четвертым входом первого элемента ИЛИ и вторым входом второго элемента ИЛИ, выход которого соединен с вторыми входами элементов И первой группы, выход четвертого регистра соединен с вторыми входами элементов И седьмой группы, выходы которых соединены с третьими входами элементов ИЛИ первой группы, первый и второй настроечные выходы модуля соединены с прямыми выходами первого и второго триггеров, синхровход модуля соединен с синхровходами регистров группы и вторым входом шестого элемента И, а в блоке анализа выход i-го регистра соединен с информационным входом (i + 1)-го регистра, выход l-й схемы сравнения подключен к l-му входу первого элемента И, выход которого подключен к выходу признака окончания вычислений блока, синхровход которого подключен к первым входам второго и третьего элементов И и счетным входам первого и второго делителей, выход второго делителя подключен к информационному входу триггера, выход которого подключен к второму входу второго элемента И и входу установки в "0" первого делителя, выходы первого делителя и второго элемента И подключены соответственно к первому и второму входам элемента ИЛИ, выход которого подключен к второму входу третьего элемента И, выход которого подключен к синхровходам всех регистров.

Описание изобретения к патенту

Изобретение относится к вычислительной техике и может быть использовано в высокопроизводительных специализированных машинах и устройствах обработки сигналов для вычисления всех собственных значений (n x n)-матрицы.

Цель изобретения - сокращение аппаратурных затрат.

На фиг. 1 представлена структурная схема устройства для вычисления собственных значений (n x n)-матрицы; на фиг. 2 - структурная схема устройства для n= 3; на фиг. 3 - функциональная схема вычислительного модуля первого типа; на фиг. 4 - функциональная схема вычислительного модуля второго типа; на фиг. 5 - функциональная схема блока анализа.

Устройство для вычисления собственных значений (n x n)-матрицы (фиг. 1) содержит группу информационных входов 1, первый 2 и второй 3 информационные входы, группу настроечных входов 4, первый 5 и второй 6 настроечные входы, синхровход 7, вычислительный модуль 8 первого типа, вычислительные модули 9_i (i= ) второго типа, блок 10 анализа, группу выходов 11 и выход 12 признака окончания вычислений.

Вычислительный модуль 8 первого типа (фиг. 3) содержит первый 13 и второй 14 информационные входы, первый 15 и второй 16 настроечные входы, синхровход 17, регистры 18 и 19, узел 20 вычисления обратной величины числа, триггеры 21 и 22, группы элементов И 23-26, группу элементов ИЛИ 27, элементы И 28-31, первый 32 и второй 33 информационные выходы, первый 34 и второй 35 настроечные выходы.

Вычислительный модуль 9 второго типа (фиг. 4) содержит первый 36, второй 37 и третий 38 информационные входы, первый 39, второй 40 и третий 41 настроечные входы, синхровход 42, регистры 43-47, сумматор 48, умножитель 49, триггеры 50-52, группы элементов И 53-59, группы элементов ИЛИ 60 и 61, элементы ИЛИ 62 и 63, элементы И 64-69, элемент НЕ 70, первый 71 и второй 72 информационные выходы, первый 73 и второй 74 настроечные выходы.

Блок 10 анализа (фиг. 5) содержит первый 75 и второй 76 информационные входы, синхровход 77, регистры 78, вычитатели 79, схемы 80 сравнения, элементы И 81-83, триггер 84, делители 85 и 86, элемент ИЛИ 87, группу выходов 88 и информационный выход 89.

В основу работы устройства положен итерационный треугольный степенной метод вычисления собственных значений _i(1in)матрицы A= { a_ij} , 1i, jn, где имеет место распределение >>. . . >.

В основе вычислительной схемы треугольного степенного метода лежит последовательное вычисление матриц

C= . .

R_m= m= 1, 2, . . . по правилу A C_m-1= B_m; B_m= C_m R_m, где C_o= { C^(o)_ij} , 1i, jn- некоторая нижняя треугольная матрица с единицами по главной диагонали.

При этом r^(m)_ii _ _i при m _ , 1in , следовательно, при достаточно больших m можно положить _ir_ii^(m), 1in.

Если итерационный процесс прерван на шаге с номером m, то приближенное вычисление собственных векторов x_i матрицы A может быть выполненно по правилу

R_mV⁽_i^m)= r^(m_ii⁾V⁽_i^m) (т. е. сначала находится решение V^(m)_i треугольной системы линейных алгебраических уравнений),

x⁽_i^m)= C_mV⁽_i^m), x_i x⁽_i^m).

Эти соотношения показывают, что если для вычисления собственных значений матрицы A достаточно диагональных элементов r^(m)_ii, то для нахождения собственных векторов требуются еще и внедиагональные элементы матриц R_m и C_m.

На каждом итерационном шаге m перемножения матриц A C_m-1 и LU - разложение матрицы B_m на матрицы C_m и R_m представляются следующими рекуррентными соотношениями:





Формируют следующие матрицы, элементы которых подаются на соответствующие входы устройства:

матрицу ,

матрицу n где знак * обозначает любое значение 0 или 1/

матрицу элементы d_ij представляют l-разрядные числа a_ij и одноразрядное число , принимающее значение 0 или 1,

матрицу , 1

Вычислительные модули и блок анализа работают следующим образом.

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

V^j+1= ^j;

W^j+1= ^j, где ^jи^j - значения соответственно на первом и втором настроечных входах вычислительного модуля на j-м такте;

V^j+1 и W^j+1 - значения соответственно на первом и втором настроечных выходах вычислительного модуля на (j+1)-м такте,

_Aj+1₌

B^j+1= b^j, где a^j и b^j - значения соответственно на первом и втором информационных входах вычислительного модуля на j-м такте;

A^j+1 и B^j+1 - значения соответственно на первом и втором информационных входах вычислительного модуля на (j+1)-м такте,



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

V^j+1= ^j;

W^j+1= ^j, где ^jи^j - значения соответственно на втором и третьем настроечных входах вычислительного модуля на j-м такте;

V^j+1 и W^j+1 - значения соответственно на первом и втором настроечных выходах вычислительного модуля на (j+1)-м такте;

A^j+1= a^j, если ^j₁ ^j₂ ^j₃ ^j₄= 1

= где b^j, a^j и c^j - значения соответственно на первом, втором и третьем информационных входах вычислительного модуля на j-м такте;

К - параметр, определяемый алгоритмом;

A^j+1 - значение на первом информационном входе вычислительного модуля на (j+1)-м такте;

C^j+n-1 - значение на втором информационном выходе вычислительного модуля на (j+n-1)-м такте;



^j - значение на первом настроечном входе вычислительного модуля на j-м такте.

По управляющему сигналу ^j запись в регистр осуществляется на (j+1)-м такте, а по управляющему сигналу ^j - на j-м такте.

Вычислительный модуль 8 первого типа работает в четырех режимах, которые задаются управляющими сигналами и , подаваемые соответственно на входы 15 и 16.

В первом режиме ( ^j, ^j)= (1, 1), при этом на выходе элемента И 28 формируется единичный сигнал ( ₁^j= 1), который открывает группу элементов И 23. На вход 13 подается число a^j, которое записывается в регистр 18 и через группы элементов И 23 и ИЛИ 27 выдается на выход 32. Число b^j подается на вход 14, записывается в регистр 19 и выдается на выход 33.

Во втором режиме ( ^j, ^j)= (0, 0). При этом на выходе элемента И 29 формируется сигнал ₂^j= 1, который открывает группу элементов И 25. Число b^j записывается в регистр 19 и выдается на выходы 32 и 33.

В третьем режиме ( ^j, ^j )= (0, 1). На выходе элемента И 30 формируется сигнал ₃^j= 1, который открывает группу элементов И 26. На выход 14 подается число b^j, которое записывается в регистр 19 и выдается на выход 33. На выход 32 подается через узел 20 вычисления обратной величины числа, группы элементов И 26 и ИЛИ 27 число 1/b^j.

В четвертом режиме ( ^j, ^j)= (1, 0). На выходе элемента И 31 формируется сигнал ₄^j= 1. Открывается группа элементов И 24. В регистр 19 записывается число b^j, которое выдается на выход 33. С инверсного выхода регистра 19 выдается число -b^j через группы элементов И 24 и ИЛИ 27 на выход 32.

Вычислительный модуль 9 второго типа работает в пяти режимах, которые задаются управляющими сигналами , и , которые подаются соответственно на входы 40, 41 и 39.

Во всех режимах осуществляется запись чисел из регистра 47_i (i= ) в регистр 47_i+1. На выход 72 подается число, записанное в регистр 47_n-1. Управляющие сигналы и записываются соответственно в триггеры 51 и 52 и подаются соответственно на выходы 73 и 74.

В первом режиме ( ^j, ^j, ^j)= (0, 1, 0), на выходе элемента И 66 формируется сигнал ₁^j= 1, который открывает группы элементов И 56, 57, 58 и элемент И 64. В регистр 43 записывается число a^j, в регистр 45 - число c^j. На выходе умножителя 49 число c^j. На выходе умножителя 49 формируется произведение a^j c^j, которое на (j+ 1)-м такте записывается в регистры 46 и 47₁. Число a^j через группу элементов И 57 выдается на выход 71.

Во втором режиме ( ^j, ^j, ^j)= (1, 0, 0), на выходе элемента И 67 формируется сигнал ₂^j= 1, открываются группы элементов И 55, 57 и 59. Число a^j записывается в регистр 43 и через группу элементов И 57 выдается на выход 71. На выходе умножителя 49 формируется произведение a^j. <содержимое регистра 46> , на выходе сумматора 48 - сумма c^j+a^j. < содержимое регистра 46>, которая на (j+1)-м такте записывается в регистр 47₁.

В третьем режиме ( ^j, ^j)= (0, 0), на выходе элемента И 68 формируется сигнал ₃^j= 1. Открываются группы элементов И 54, 55 и 57. В регистр 43 записывается число a^j, которое выдается на выход 71. На выходе умножителя 49 формируется произведение a^j b^j (число b^jзаписывается в регистр 44), на выходе сумматора 50 - сумма c^j+a^j b^j (в регистр 45 записывается число c^j), которая записывается на (j+1)-м такте в регистр 47₁.

В четвертом режиме ( ^j, ^j )= (1, 1). На выходе элемента И 69 формируется сигнал ₄^j= 1. Вчислительный модуль 9 работает как в третьем режиме.

В пятом режиме ( ^j, ^j, ^j)= (0, 1, 1). На выходe элемента И 65 формируется сигнал ^j= 1, который открывает группу элементов И 53. Число b^j через группы элементов И 53 и ИЛИ 61 подается на вход регистра 47₁, которое на j-м такте по заднему фронту тактового импульса записывается в регистр 47₁.

Рассмотрим работу блока 10 анализа (фиг. 5).

Приближения к собственным значениям матрицы _i^(m) (i= ) подаются на вход 75 в моменты времени

t= ( -1)n+i+mn², где m - номер итерации, m= 1, 2, 3, . . . , (m).

Запись приближений к собственным значениям _i в регистры 78_j(j= ) осуществляется тактовыми импульсами, которые подаются с выхода элемента И 83 в моменты времени t. В табл. 1 приведены состояния делителя 85 по модулю счета (n+1), делителя 86 по модулю счета n², триггера 84 и регистров 78_j (j= ) для n= 3. На (n²-1)-м такте на выходе делителя 86 формируется единичный сигнал, который на n²-м такте устанавливает делитель 85 в нулевое состояние, а триггер 84 в единичное состояние, который открывает элемент И 83. На (n²+1)-м такте через элемент И 83 тактовый импульс подается на синхровходы регистров 78, в которые осуществляется запись собственных чисел. Триггер 84 устанавливается в нулевое состояние. На ((i-1)n+i+mn²-1)-м такте (i 1) на выходе делителя 85 формируется единичный сигнал, который на ((i-n)n+i+mn²)-м такте (i 1) открывает элемент И 83 и разрешает запись в регистры 78_j. На (n²(m+1)-1)-м такте на выходе делителя 86 формируется единичный сигнал, который на (n²(m+1))-м такте устанавливает триггер 84 в единичное состояние и разрешается запись в регистры 78_j. На (n²(m+1))-м такте выполняется проверка точности вычислений - . Если данное соотношение выполняется, то на выходе 89 признака окончания вычислений формируется единичный сигнал = 1. При этом с выходом 88_i(i= ) снимаются значения _i. Если данное соотношение не выполняется, то итерационный процесс вычисления собственных значений _i продолжается. Проверка соотношения - выполняется вычитателями 79_i, схемами 80_i сравнения (i= ) и элементом И 81.

Рассмотрим работу устройства (фиг. 1).

На выходы 1_i и 4_i (i= ) подаются элементы входной матрицы { d_ij} = { a_ij, } в моменты времени

t_dij= i+(j-1)n+p+mn², i= , j= , p= , m= 0, 1, 2, . . .

На вход 2 подаются элементы c^(o)_qj, 1 j< q в момент времени

t_cqj^(o)= (q-1) n+j-1.

На выходы 5 и 6 подаются соответственно управляющие сигналы и матриц { _ij} и { _ij^I} в моменты времени

t= (i-1)n+j-1, i, j = ;

t= (i-1)n+j-1+mn², i, j = , m = 1,2,3, . . .

Собственные значения _i^(m) формируются на выходах 11 (i= ), при значении = 1 на выходе 12 в моменты времени

t= n²(m+1).

Элементы матрицы { n^(m)_ij} формируются на выходе 33 вычислительного модуля 8 в моменты времени

t= (i-1)n+j+mn², i, j = , m = 1,2,3, . . .

На фиг. 2 показана организация входного и выходного потоков данных для n= 3. В табл. 2-7 приведены состояния триггеров, регистров и значения на выходах вычислительных модулей 8 и 9.

На десятом такте в блоке 10 анализа (табл. 1) формируется значение ₁⁽¹⁾, на четырнадцатом такте - ₂⁽¹⁾, на восемнадцатом такте - ₁⁽¹⁾, на девятнадцатом такте - ₁⁽²⁾, на двадцать третьем такте - ₂⁽²⁾, на двадцать седьмом такте - ₃⁽²⁾ . На двадцать седьмом такте выполняется проверка соотношения - . Если на выходе 12 формируется признак = 1, то значения _i снимаются с выходов 11. Если признак = 0, то итерационный процесс вычисления _i продолжается.