Главная страница  |  Описание сайта  |  Контакты
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ (N X N)- МАТРИЦЫ
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ (N X N)- МАТРИЦЫ

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ (N X N)- МАТРИЦЫ

Патент Российской Федерации
Суть изобретения: Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для вычисления всех собственных значений (n n)-матрицы. Цель изобретения - сокращение аппаратурных затрат. Цель достигается тем, что устройство содержит вычислительный модуль 8 первого типа, 2n - 1 вычислительных модулей 9 второго типа и блок 10 анализа. Основу вычислительного модуля первого типа составляет узел вычисления обратной величины числа, а вычислительного модуля второго типа - умножитель и сумматор. В основу устройства положен итерационный треугольный степенной метод вычисления собственных значений для (n n)-матрицы. 7 табл. , 5 ил.
Поиск по сайту

1. С помощью поисковых систем

   С помощью Google:    

   С помощью Яндекс:  

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2012050
Класс(ы) патента: G06F15/347
Номер заявки: 5031555/24
Дата подачи заявки: 10.03.1992
Дата публикации: 30.04.1994
Заявитель(и): Якуш В.П.; Лиходед Н.А.; Соболевский П.И.; Тиунчик А.А.
Автор(ы): Якуш В.П.; Лиходед Н.А.; Соболевский П.И.; Тиунчик А.А.
Патентообладатель(и): Якуш Виктор Павлович
Описание изобретения: Изобретение относится к вычислительной техике и может быть использовано в высокопроизводительных специализированных машинах и устройствах обработки сигналов для вычисления всех собственных значений (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 первого типа, вычислительные модули 9i (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(1≅i≅n)матрицы A= { aij} , 1≅i, j≅n, где имеет место распределение >>. . . >.
В основе вычислительной схемы треугольного степенного метода лежит последовательное вычисление матриц
C= . .
Rm= m= 1, 2, . . . по правилу A ˙Cm-1= Bm; Bm= Cm Rm, где Co= { C(o)ij} , 1≅i, j≅n- некоторая нижняя треугольная матрица с единицами по главной диагонали.
При этом r(m)ii _→ λi при m _→ ∞, 1≅i≅n , следовательно, при достаточно больших m можно положить λi≈rii(m), 1≅i≅n.
Если итерационный процесс прерван на шаге с номером m, то приближенное вычисление собственных векторов xi матрицы A может быть выполненно по правилу
RmV(im)= r(mii)V(im) (т. е. сначала находится решение V(m)i треугольной системы линейных алгебраических уравнений),
x(im)= CmV(im), xi≈ x(im).
Эти соотношения показывают, что если для вычисления собственных значений матрицы A достаточно диагональных элементов r(m)ii, то для нахождения собственных векторов требуются еще и внедиагональные элементы матриц Rm и Cm.
На каждом итерационном шаге m перемножения матриц A˙ Cm-1 и LU - разложение матрицы Bm на матрицы Cm и Rm представляются следующими рекуррентными соотношениями:


Формируют следующие матрицы, элементы которых подаются на соответствующие входы устройства:
матрицу ,
матрицу n где знак * обозначает любое значение 0 или 1/
матрицу элементы dij представляют l-разрядные числа aij и одноразрядное число γ , принимающее значение 0 или 1,
матрицу , 1
Вычислительные модули и блок анализа работают следующим образом.
Вычислительный модуль 8 первого типа обладает возможностью реализации следующих функций:
Vj+1= αj;
Wj+1= βj, где αjиβj - значения соответственно на первом и втором настроечных входах вычислительного модуля на j-м такте;
Vj+1 и Wj+1 - значения соответственно на первом и втором настроечных выходах вычислительного модуля на (j+1)-м такте,
Aj+1=
Bj+1= bj, где aj и bj - значения соответственно на первом и втором информационных входах вычислительного модуля на j-м такте;
Aj+1 и Bj+1 - значения соответственно на первом и втором информационных входах вычислительного модуля на (j+1)-м такте,

Вычислительный модуль 9 второго типа обладает возможностью реализации следующих функций:
Vj+1= αj;
Wj+1= βj, где αjиβj - значения соответственно на втором и третьем настроечных входах вычислительного модуля на j-м такте;
Vj+1 и Wj+1 - значения соответственно на первом и втором настроечных выходах вычислительного модуля на (j+1)-м такте;
Aj+1= aj, если μj1 ∨ μj2 ∨ μj3 ∨ μj4= 1
= где bj, aj и cj - значения соответственно на первом, втором и третьем информационных входах вычислительного модуля на j-м такте;
К - параметр, определяемый алгоритмом;
Aj+1 - значение на первом информационном входе вычислительного модуля на (j+1)-м такте;
Cj+n-1 - значение на втором информационном выходе вычислительного модуля на (j+n-1)-м такте;

γj - значение на первом настроечном входе вычислительного модуля на j-м такте.
По управляющему сигналу μj запись в регистр осуществляется на (j+1)-м такте, а по управляющему сигналу σj - на j-м такте.
Вычислительный модуль 8 первого типа работает в четырех режимах, которые задаются управляющими сигналами αиβ , подаваемые соответственно на входы 15 и 16.
В первом режиме ( αj, βj)= (1, 1), при этом на выходе элемента И 28 формируется единичный сигнал ( μ1j= 1), который открывает группу элементов И 23. На вход 13 подается число aj, которое записывается в регистр 18 и через группы элементов И 23 и ИЛИ 27 выдается на выход 32. Число bj подается на вход 14, записывается в регистр 19 и выдается на выход 33.
Во втором режиме ( αj, βj)= (0, 0). При этом на выходе элемента И 29 формируется сигнал μ2j= 1, который открывает группу элементов И 25. Число bj записывается в регистр 19 и выдается на выходы 32 и 33.
В третьем режиме ( αj, βj )= (0, 1). На выходе элемента И 30 формируется сигнал μ3j= 1, который открывает группу элементов И 26. На выход 14 подается число bj, которое записывается в регистр 19 и выдается на выход 33. На выход 32 подается через узел 20 вычисления обратной величины числа, группы элементов И 26 и ИЛИ 27 число 1/bj.
В четвертом режиме ( αj, βj)= (1, 0). На выходе элемента И 31 формируется сигнал μ4j= 1. Открывается группа элементов И 24. В регистр 19 записывается число bj, которое выдается на выход 33. С инверсного выхода регистра 19 выдается число -bj через группы элементов И 24 и ИЛИ 27 на выход 32.
Вычислительный модуль 9 второго типа работает в пяти режимах, которые задаются управляющими сигналами α, βиγ , которые подаются соответственно на входы 40, 41 и 39.
Во всех режимах осуществляется запись чисел из регистра 47i (i= ) в регистр 47i+1. На выход 72 подается число, записанное в регистр 47n-1. Управляющие сигналы αиβ записываются соответственно в триггеры 51 и 52 и подаются соответственно на выходы 73 и 74.
В первом режиме ( αj, βj, γj)= (0, 1, 0), на выходе элемента И 66 формируется сигнал μ1j= 1, который открывает группы элементов И 56, 57, 58 и элемент И 64. В регистр 43 записывается число aj, в регистр 45 - число cj. На выходе умножителя 49 число cj. На выходе умножителя 49 формируется произведение aj ˙cj, которое на (j+ 1)-м такте записывается в регистры 46 и 471. Число aj через группу элементов И 57 выдается на выход 71.
Во втором режиме ( αj, βj, γj)= (1, 0, 0), на выходе элемента И 67 формируется сигнал μ2j= 1, открываются группы элементов И 55, 57 и 59. Число aj записывается в регистр 43 и через группу элементов И 57 выдается на выход 71. На выходе умножителя 49 формируется произведение aj. <содержимое регистра 46> , на выходе сумматора 48 - сумма cj+aj. < содержимое регистра 46>, которая на (j+1)-м такте записывается в регистр 471.
В третьем режиме ( αj, βj)= (0, 0), на выходе элемента И 68 формируется сигнал μ3j= 1. Открываются группы элементов И 54, 55 и 57. В регистр 43 записывается число aj, которое выдается на выход 71. На выходе умножителя 49 формируется произведение aj ˙bj (число bjзаписывается в регистр 44), на выходе сумматора 50 - сумма cj+aj ˙bj (в регистр 45 записывается число cj), которая записывается на (j+1)-м такте в регистр 471.
В четвертом режиме ( αj, βj )= (1, 1). На выходе элемента И 69 формируется сигнал μ4j= 1. Вчислительный модуль 9 работает как в третьем режиме.
В пятом режиме ( αj, βj, γj)= (0, 1, 1). На выходe элемента И 65 формируется сигнал σj= 1, который открывает группу элементов И 53. Число bj через группы элементов И 53 и ИЛИ 61 подается на вход регистра 471, которое на j-м такте по заднему фронту тактового импульса записывается в регистр 471.
Рассмотрим работу блока 10 анализа (фиг. 5).
Приближения к собственным значениям матрицы λi(m) (i= ) подаются на вход 75 в моменты времени
t= ( -1)n+i+mn2, где m - номер итерации, m= 1, 2, 3, . . . , (m).
Запись приближений к собственным значениям λi в регистры 78j(j= ) осуществляется тактовыми импульсами, которые подаются с выхода элемента И 83 в моменты времени t. В табл. 1 приведены состояния делителя 85 по модулю счета (n+1), делителя 86 по модулю счета n2, триггера 84 и регистров 78j (j= ) для n= 3. На (n2-1)-м такте на выходе делителя 86 формируется единичный сигнал, который на n2-м такте устанавливает делитель 85 в нулевое состояние, а триггер 84 в единичное состояние, который открывает элемент И 83. На (n2+1)-м такте через элемент И 83 тактовый импульс подается на синхровходы регистров 78, в которые осуществляется запись собственных чисел. Триггер 84 устанавливается в нулевое состояние. На ((i-1)n+i+mn2-1)-м такте (i ≠ 1) на выходе делителя 85 формируется единичный сигнал, который на ((i-n)n+i+mn2)-м такте (i ≠ 1) открывает элемент И 83 и разрешает запись в регистры 78j. На (n2(m+1)-1)-м такте на выходе делителя 86 формируется единичный сигнал, который на (n2(m+1))-м такте устанавливает триггер 84 в единичное состояние и разрешается запись в регистры 78j. На (n2(m+1))-м такте выполняется проверка точности вычислений - ε. Если данное соотношение выполняется, то на выходе 89 признака окончания вычислений формируется единичный сигнал δ = 1. При этом с выходом 88i(i= ) снимаются значения λi. Если данное соотношение не выполняется, то итерационный процесс вычисления собственных значений λi продолжается. Проверка соотношения - ε выполняется вычитателями 79i, схемами 80i сравнения (i= ) и элементом И 81.
Рассмотрим работу устройства (фиг. 1).
На выходы 1i и 4i (i= ) подаются элементы входной матрицы { dij} = { aij, γ} в моменты времени
tdij= i+(j-1)n+p+mn2, i= , j= , p= , m= 0, 1, 2, . . .
На вход 2 подаются элементы c(o)qj, 1≅ j< q в момент времени
tcqj(o)= (q-1) n+j-1.
На выходы 5 и 6 подаются соответственно управляющие сигналы α и β матриц { τij} и { τijI} в моменты времени
t= (i-1)n+j-1, i, j = ;
t= (i-1)n+j-1+mn2, i, j = , m = 1,2,3, . . .
Собственные значения λi(m) формируются на выходах 11 (i= ), при значении δ= 1 на выходе 12 в моменты времени
t= n2(m+1).
Элементы матрицы { n(m)ij} формируются на выходе 33 вычислительного модуля 8 в моменты времени
t= (i-1)n+j+mn2, i, j = , m = 1,2,3, . . .
На фиг. 2 показана организация входного и выходного потоков данных для n= 3. В табл. 2-7 приведены состояния триггеров, регистров и значения на выходах вычислительных модулей 8 и 9.
На десятом такте в блоке 10 анализа (табл. 1) формируется значение λ1(1), на четырнадцатом такте - λ2(1), на восемнадцатом такте - λ1(1), на девятнадцатом такте - λ1(2), на двадцать третьем такте - λ2(2), на двадцать седьмом такте - λ3(2) . На двадцать седьмом такте выполняется проверка соотношения - ε . Если на выходе 12 формируется признак δ = 1, то значения λi снимаются с выходов 11. Если признак δ = 0, то итерационный процесс вычисления λi продолжается.
Формула изобретения: УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СОБСТВЕННЫХ ЗНАЧЕНИЙ (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" первого делителя, выходы первого делителя и второго элемента И подключены соответственно к первому и второму входам элемента ИЛИ, выход которого подключен к второму входу третьего элемента И, выход которого подключен к синхровходам всех регистров.