Устройство для LV-разложения матриц Советский патент 1992 года по МПК G06F15/347 

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

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

На фиг. 1 представлена структурная схема устройства для разложения матриц; на фиг.2 - структурная схема устройства для Ш-разложения матриц для случая М 2 и Н 4; на фиг.З - пример схемы вычислительного модуля 6.

Устройство для Ш-разложения матриц (фиг.1) содержит информационный вход 1, первый 2, второй 3 и третий 4 управляющие входы, синхровход 5, вычислительные модули 6i (I 1, М), первый 7, второй 10, третий 9 и четвертый 8 узлы задержки, группу элементов ИЛИ 11, элементы ИЛИ 12, 13 и 14 и выход 15.

Вычислительный модуль 6 (см.фиг.З) содержит информационный вход 16. первым 17, второй 18 и третий 19 управляющие входы, синхровход 20. умножитель 21, вычитз- тель 22. узел вычисления обратной величины числа 23, регистры 24 и 26, тргг- геры29,30,31,32,33и34, первый25, Бтирой 28 и третий 27 узлы задержки, группы элементов И 35 - 42, группы элементов ИЛИ 43 - 45, элементы И 46 - 52, элементы ИЛИ 53 -57, элементы НЕ 58 -60, информационный выход 61, первый 62, второй 63 и третий 64 управляющие выходы.

В основу работы устройства для Ш-разложения матрицы А {ay}, I.J 1, Н на нижнюю треугольную с единицами по главной диагонали L {Itj} и верхнюю треугольную матрицу U положены следующие рекуррентные соотношения:

1.,H:ukk akk(k) i k.

at/ ) aij. i,l т, н; k i, н: ukk akk ; j k, ukj эк/Ч I k, k j , H, lik aik(k)-ukk4;

H,

k i H, j k, aij(k+1) ai,(k) - ,k ukj, k j k j H.

Предполагается, что фиксированное число М может принимать значения в пределах от 2 до Н и соотношение Н/М - целое число. Если Н/М не целое число, то следует рассматривать матрицу А размером (Н х Н1), где Н1 МГ (обозначение П - означает наибольшее сверху целое). Матрица А1 получается добавлением к матрице А Н1 - Н - новых строк и столбцов, все элементы которых равны нулю, за исключением лежащих на диагонали, равных единице. После Ш-разложения в матрицах L и U элементы строк и столбцов с номерами большими Н не принимаются во внимание.

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

и ж+2 - о.

i+H+2

1,еслиу 0и (dfi) (1,1HO,1K1.0)

1, если у 1,

О, если У 0и() (0,0)/

гдео|/3 и у - значения соответственно на первом, втором и третьем управляющих входах вычислительного модуля на j-м такте,

iA vj, г/У -значения соответственно на первом, втором и третьем управляющих выходах вычислительного модуля на j-м такте,

а1,если(а,/ . }) (1.1,0)t0.1,0)V,. 1), AJ+1 aj-1 /aj k, если (d . ff . у) (1, О, О),

-ЈЈ -

. если (о1 , ft , у1) ) (О, О, О)

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

iJ+1

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

k, I, p, q - параметры,определяемые алгоритмом.

Рассмотрим работу вычислительного модуля 6. Вычислительный модуль б работает в пяти режимах, которые задаются управ- ляющими сигналамиа,/3 и у,

подаваемыми соответственно на управляющие входы 17, 18 и 19. Соотеетствующиезначенияуправляющих сигнаов (о1, {$ , у1) на j-м такте определяют управляющие сигналы

a.J+1 и1-(о1., у1) 1 1,5,

где I - номер режима работы, которые подаются на соответствующие логические элементы вычислительного модуля 6. Причем управляющий сигнал обеспечивает запись в регистр или триггер на j-м такте, а управляющий сигнал на 0+1)-м такте.

Во всех режимах работы на информационный вход 16 подается элемент а, который записывается в регистр 24, информация задерживается узлом задержки 25 на Н тактов (узел задержки 25 содержит Н последовательно соединенных регистров), управляющие сигналы о./,у подаются соответственно на входы 17, 18 и 19 и записываются соответственно в триггеры 27, 28

и 34, Управляющие сигналы с$ л ($ выдаются соответственно на выходы 62 и 63 с

задержкой на (Н + 2) тактов.

Регистры 24 и 25 (I 1, Н) построены на двухтактных триггерах и в них запись информации осуществляется по заднему фронту тактового импульса. Регистр 26 построен на однотактных триггерах и информация в него записывается по переднему фронту тактового импульса.

В первом режиме подаются управляющие сигналы ( d , ft , у1) (1, 1,0). При этом формируются сигналы ai +1 1. Открываются группы элементов 37, 40 и элемент И 52. Элемент а с выхода регистра 24 через группы элементов И 40 и ИЛИ 45 подается

на выход 61, На выходе узла вычисления обратной величины числа 23 формируется значение 1/а , которое через группы элементов И 37 и ИЛИ 43 записывается в регистр 25i на 0+1)м такте. Управляющий

сигнал у1 0, подаваемый на вход 19, устанавливает триггер 34 в нулевое состояние и с его инверсного выхода единичный сигнал через элементы И 52 и ИЛИ 56 выдается на выход 64, т.е. на выход 64 выдается у1 1.

Во втором режиме ( « , /З1 , у) (0, 1, 0). Открываются группы элементов И 36, 40 и элемент И 52. Элемент а с выхода регистра 24 через группы элементов И 36 и ИЛИ 43 записывается в регистр 25i и через группы элементов И 40 и ИЛИ 45 подается на выход 61. На выход 64 выдается управляющий сигнал у 1.

В третьем режиме ( d , $ , у1) (1, О, О). Открываются группы элементов И 35, 38, 39 и элементы И 46.52. На выходе умножителя 21 формируется значение l а и (а )подает- ся на первый вход умножителя 21 через группы элементов И 38 и ИЛИ 44, на второй вход и подается с выхода регистра 25н), которое через группы элементов И 39 и ИЛ И 45 подается на выход 61. В регистр 25i записывается содержимое и регистра 25н через группы элементов И 35 и ИЛИ 43. В регистр 26 значение l а и записывается на 0+1)-м такте, т.к. по управляющему сигналу а 1 элемент И 46 открыт и по переднему фронту тактового импульса, проходящего через элемент И 46 на синхровход регистра 26, разрешается запись в регистр 26 на (+1)-м такте. На выход 64 выдается

управляющий сигнал } 1.

В четвеотом режиме (а , ft , у) (О, О, О). Открываются группы элементов И 35, 41, 42 и элемент И 51. На первый вход умножителя 21 через группы элементов И 41 и ИЛИ 44 подается содержимое I регистра 26, на второй вход - содержимое и регистра 25, на выходе которого формируется значение 1 и , которое подается на второй вход вычитате- ля 22. На первый вход вычитателя 22 подается элемент а, на выходе которого формируется значение а -1 и , которое подается через группы элементов И 42 и ИЛИ 45 на выход 61. В регистр 25i записывается содержимое и регистра 25н. Управляющий cигнaлj у 0 устанавливает триггер 34 в нулевое состояние, нулевой сигнал с его прямого выхода через элементы И 51 и ИЛИ

56 подается на выход 64 (у 0).

В пятом режиме (2J , (У . у ) (.. 1). где обозначение принимает значение 0 или 1. Открываются группы элементов И 35, 40 и элемент И 51. В регистр 25i записывается содержимое регистра 25н. На выход 61 подается с выхода регистра 24 элемент а . Управляющий сигнал у1 1 устанавливает триггер в единичное состояние, единичный сигнал с его прямого выхода через элементы И 51 и ИЛИ 56 подается на выход 64

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

Элементы aij подаются на вход в моменты времени

taij-(H)H+J-1.

На входы 2 и 3 подаются комбинации управляющих сигналов ch -- ( а , fi) - (1, 1), 52 (а,Ј) (0, 1). дз- («./) 0,0) и

да, ( а,/) (0, 0) в виде следующей f ncf L- довательности;,

Ј 61°, д2 д22д2 Ј.&. (2

,

где е ГТИ.

На вход 4 постоянно подастся нулевой сигнал.

На выходе 15 устройства формируются uij(lij)-l элементы в моменты времени

tui(llj) (1-1)Н + j + (Н/М - 1)Н2 + М - 1.

На фиг.2 приведены для Н 4 и М 2 организация входных и выходных потоков данных.

Таким образом, предлагаемое устройство по сравнению с прототипом содержит меньший объем оборудования, т.е. осуществляет Ш-разложение (И х Hl-матрицы с помощью М вычислительных модулей (М Н), а прототип -с помощью Н вычислительных модулей.

Формула изобретения Устройство для Ш-разложения матриц,

содержащее с первого по М-и операционные блоки (где Н/М - целое число, М Н, Н - размерность разлагаемой матрицы), причем выходы группы а-го операционного бг.о- ка (где а 1 ,..,,М-1) подключены

соответственно к информационным входа г/ (а + 1)-го операционного блока, первый и второй выходы а-го операционного блоке. подключены соответственно к первому и второму управляющим вхсдам (а + 1)-го операционного блока, вход синхронизации устройства подключен к входам синхронизации операционных блоков с первого по М-й, отличающееся тем, что, с целью сокращения аппаратурных затрат,

оно содержит с первого по третий элементы И, с первого по четвертый узлы задержки и группу элементов ИЛИ, причем входы коэффициентов разлагаемой матрицы устройства подключены соответственно к первым

входам элементов ИЛИ группы, выходы которых подключены к информационным входам группы первого операционного блока, выходы группы М-го операционного блока подключены соответственно к выходам результата устройства и соответственно к информационным входам первого узла задержки, выходы которого подключены соответственно к вторым входам элементов ИЛИ группы, с первого по третий входы

режима работы устройства подключены соответственно к первым входам первого, второго и третьего элементов И, выходы которых подключены соответственно к первому, второму и третьему управляющим входам первого операционного блока, третий выход а-го операционного блока подключен к третьему управляющему входу (а+1)-го операционного блика, первый, второй и третий выходы М-го операционного блока под- ключенысоответственнок

информационным входам второго, третьего и четвертого узлов задержки, выходы которых подключены соответственно к вторым входам первого, второго и третьего элементов И, вход синхронизации устройства подключен к входам синхронизации первого, второго, третьего и четвертого узлов задержки, при этом каждый операционный блок содержит узел вычисления обратной величины, вычитатель, умножитель, два регистра, шесть триггеров, три узла задержки, с первой по восьмую группы элементов И, с первого по седьмой элементы И, с первой потретью группы элементов ИЛИ, с первого по пятый элементы ИЛИ, с первого по третий элементы НЕ, причем в каждом операционном блоке информационные входы группы операционного блока подключены соответственно к информационным входам первого регистра, выходы которого подключены к первым входам элементов И первой, второй и третьей групп, к информационным входам первой группы вычитателя и к информационным входам узла вычисления обратной величины, выходы которого подключены к первым входам элементов И четвертой группы, РЫХОДЫ которых подключены соответственно к первым входам элементов ИЛИ первой группы, выходы которых подключены к информационным входам первого элемента задержки, выходы которого подключены соответственно к информационным входам первой группы умножителя, выходы которого подключены соответственно к первым входам элементов И шестой группы, соответственно к информационным входам второй группы вычитателя и соответственно к информационным входам второго регистра, выходы которого подключены соответственно к первым входам элементов И седьмой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ второй группы, выходы которых подключены соответственно к информационным входам второй группы умножителя, выходы вычитателя подключены соответственно к первым входам элементов И восьмой группы, выходы которых подключены соответственно к первым входам элементов ИЛИ третьей группы, выходы которых подключены соответственно к выкодэм группы операционного блока, первый управляющий вход которого подключен к входу первого элемента НЕ, к информационным входам первого и второго триггеров и к первому входу первого элемента ИЛИ. выход которого подключен к вторым входам элементов И пятой группы,

выходы которого подключены соответственно к вторым входам элементов ИЛИ первой группы, выход первого триггера подключен к первым входам второго и третьего элементов ИЛИ. выход второго элемента ИЛИ

0 подключен к вторым входам элементов И второй группы, выходы которых подключены соответственно к вторым входам элементов ИЛИ третьей группы, выход третьего элемента ИЛИ подключен к первому входу

5 первого элемента И, выход которого подключен к первому входу четвертого элемента ИЛИ, выход которого подключен к первому выходу операционного блока, второй управляющий вход которого подключен

0 к входу второго элемента НЕ, к информационному входу второго узла задержки и к первым входам второго и третьего элементов И, выход второго элемента И подключен к информационному входу третьего тригге5 ра, выход которого подключен к вторым входам элементов И четвертой группы, к второму входу второго элемента ИЛИ и к первому входу пятого элемента ИЛИ, выход которого подключен к первому входу чет0 вертого элемента И, выход которого подключен к второму входу четвертого элемента И, выход которого подключен к второму входу четвертого элемента ИЛИ. прямой и инверсный выходы второго триг5 гера подключены соответственно к вторым входам первого и четвертого элементов И, выход третьего элемента И подключен к информационному входу четвертого триггера и к вторым входам элементов И первой груп0 пы, выходы которых подключены соответственно к третьим входам элементов ИЛИ первой группы, выход четвертого триггера подключен к третьему входу второго элемента ИЛИ и к второму входу пятого элемен5 та ИЛИ, выход первого элемента НЕ подключен к вторым входам второго и третьего элементов И и к первым входам пятого и шестого элементов И, выход пятого элемента И подключен к второму входу пер0 вого элемента ИЛИ и к информационному входу пятого триггера, выход которого подключен к вторым входам элементов И третьей группы, к третьему входу пятого элемента ИЛИ, к первому входу седьмого

5 элемента И и вторым входам элементов И шестой группы, выходы которых подключены соответственно к третьим входам элементов ИЛИ третьей группы, выход второго элемента НЕ подключен к вторым входам пятого и шестого элементов И, выход шеетого элемента И подключен к третьему входу первого элемента ИЛИ и к информационному входу шестого триггера, выход которого подключен к вторым входам элементов И седьмой и восьмой групп и к второму входу третьего элемента ИЛИ, третий управляющий вход операционного блока подключен к входу третьего элемента НЕ, к третьим входам второго и пятого элементов И и к информационному входу третьего узла задержки, выход которого подключен к второму выходу операционного блока, третий

0

выход которого подключгч к вы4 од/ нторо С узла задержки, выход элемента НЕ подключен к третьим входам третьего и шестого элементов И, вход синхронизации операционного блока подключен к входам синхронизации первого, второго и третьего узлов задержки и к входам Запись-чтение первого - шестого триггеров и первого регистра и к второму входу седьмого элемента И, выход которого подключен к входу Запись-чтение второго регистра.

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных специализированных вычислительных машинах и устройствах обработки сигналов для Ш-разложения ( Н х Н )-матриц. Цель изобретения - сокращение аппаратурных затрат. Поставленная цель достигается тем, что устройство содержит М вычислительных модулей (М - фиксированное число, ОД Н), причем вычислительный модуль резл- пт арифметические операции умножения, вычитания и вычисление обратной вели« ы числа.3 ил.

..zr

2 $ЧЈ

ss

Ч Т