Устройство для lu-разложения матриц

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений. Предложенное устройство позволяет сократить аппаратурные затраты за счет уменьшения количества процессорных элементов и связей их с блоком синхронизации. Сущность работы устройства состоит в том, что оно раскладывает квадратную матрицу A = [A<SB POS="POST">IJ</SB>] размерности N на две треугольные: нижнюю левую L и верхнюю правую U, такие, что LU = A. ПРИЧЕМ НА ГЛАВНОЙ ДИАГОНАЛИ МАТРИЦЫ U СТОЯТ ЕДИНИЦЫ. ПРЕОБРАЗОВАНИЕ МАТРИЦЫ A ВЫПОЛНЯЕТСЯ ПО АЛГОРИТМУ ИСКЛЮЧЕНИЯ ГАУССА, В ПРОЦЕССЕ КОТОРОГО ПОЛУЧАЮТСЯ ЭЛЕМЕНТЫ L<SB POS="POST">IJ</SB> И U<SB POS="POST">IJ</SB>. 3 ИЛ.

СВОЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

15ц 4 С 06 F 15/347

ОПИСАНИЕ ИЗОБРЕТЕНИЯ г) К ABTOPCHOMV СВИДЕТЕЛЬСТВУ зации, вход которого является входом запуска устройства, информационный вход операционного блока l.i подключен к информационному выходу операционного блока 1.(i"1), при этом информационный вход операционного блока 1,1 является входом устройства,а информационныи выход операционного блока 1.(N-1) является выходом устройства, первый и второй управляющие входы операционного блока l.i подключены соответственно к первому и второму управляющим выходам операционного блока 1.(i-l), третий управляющий вход операционного блока 1.1 подключен к потенциалу логического

"0", третьи управляющие входы операционных блоков 1.2-1,(N-l) и первый

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЭОБРЕТЕКИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4348725/24-24 (22) 28. 12. 87 (46) 23.09.89. Бюл. № 35 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) Ю.С,Каневский, С.Э.Котов и О.В,Масленников (53) 681.333(088.8) (56) Авторское свидетельство СССР № 1249531, кл. G 06 F 15/32, 1984.

Авторское свидетельство СССР

¹ 1354206, кл. G 06 F 15/347, 10.07.86. (54) УСТРОЙСТВО ДЛЯ LU-РАЗЛОЖЕНИЯ

МАТРИЦ (57) Изобретение относится к автоматике и вычислительной технике и моИзобретение относится к автоматике и вычислительной технике и может быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений.

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

На фиг, 1 представлена структурная схема устройства для разложения матриц; на фиг. 2 — структурная схема блока синхронизации; на фиг. 3— структурная схема i-ro операционного блока.

Устройство для LU-разложения матриц содержит операционные блоки l,i (i=1 N-1), где N — размерность разлагаемой матрицы и блок 2 синхрони„„Я0„„1509933 А1

2 жет быть использовано при построении специализированных устройств, предназначенных для решения систем линейных уравнений. Предложенное устройство позволяет сократить аппаратурные затраты за счет уменьшения количества процессорных элементов и связей их с блоком синхронизации.

Сущность работы устройства состоит в том, что оно раскладывает квадратную матрицу А= (а;; 1размерности N на две треугольные: нижнюю левую Ь и верхнюю правую U, такие, что LU=A. Причем на главной диагонали матрицы U стоят единицы. Преобразование матрицы А выполняется по алгоритму исключения Гаусса, в процессе которого получаются элементы 1;; и U;.. 3 ил.

3 1509933 управляющий вход операционного блока

1.1 подключены к потенциалу логической "1", а третий управляющий выход операционного блока 1.1 является вхо- дом признака блока 2 синхронизации, выход которого подключен ко второму управляющему входу операционного блока 1,1, Каждый операционный блок содержит !О первый коммутатор 3, блок 4 умножителя-деления, вычитатель 5, второй

6 и третий 7 коммутаторы, регистр 8, блок 9 памяти объемом 2N-! слов, пер,вьй D-триггер 10, первый элемент 15

И 11, первый счетчик 12, пятый элемент ИЛИ 1 3, схему 14 сравнения, второй элемент И 15, второй D òðèããåð

16, третий элемент ИЛИ 17, первый элемент ИЛИ 18 RS-триггер 19, вто- 20 рой элемент ИЛИ 20, второй счетчик

21, третий 22 и четвертый 23 D-триггеры, четвертый элемент ИЛИ 24.

Блок 4 умножения-деления может быть построен по любой известной схе" ме и содержать сумматор и несколько регистров для хранения операндов, промежуточных и окончательных результатов.

Запоминающее устройство объемом

2N-1 представляет собой блок регистров, аналогичный примененному в микропроцессорной секции 1804ВС1, который имеет два адресных входа, один из которых работает только на чте- 35 ние, два выхода данных и один вход для записи данных. В нашем. случае адресный вход А секции ВС1 является первым адресным входом запоминающего устройства, а адресный вход В, 40 допускающий как чтение, так и запись, является вторым адресным входом запоминающего устройства. Выход

А секции ВС! является вторым выходом запоминающего устройства, а выход

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

Блок 2 синхронизации (фиг. 2) со- 0 держит генератор 25 синхронизйрующих импульсов, выход которого соединен с синхровходами всех .регистров, ЛЗУ, счетчиков и D-триггеров устройства (не пОказано) и с синхровходом 55 счетчика 2Ь, выходы которого подклю-, чены к первой группе входов схемы 27 сравнения, на вторую группу входов которой постоянно подается значение

k+2)...,N;

k у ° ° ° уNу jФ, k= 1» Nу,1 j =k+ 1 ° ((,-1 ((-ö

Ц%1 „ a%й е

1<

k+I у ° ° ° уХ1

° ° i уИ1 1Фу

Рассмотрим работу устройства.

Предположим N=4. Тогда прием информации во все регистры и блок памяти осуществляется по заднему фронту синхроимпульса, т.е. в конце такта, а в счетчики и D-триггеры— по переднему фронту синхроимпульса, т,е. в начале такта, Поступление исходных данных организовано следующим образом. На вход устройства каждый такт последовательно поступают элементы матрицы А=(а; (по столбцам, т.е. первые N тактов — элементы первого столбца матрицы А (в первом такте а „ во втором а,и т.д.), вторые N тактов — элементы второго столбца и т.д.

В исходном состоянии счетчики 1.2, 21 и 26, и D-триггеры 10 и 16 нахо.— дятся в нулевом состоянии, а RS-триггеры 19 и 28 и D-триггеры 22 и 23 установлены в единицу, на выходах схем 14 сравнения — нуль.

После сигнала "Запуск" RS-триггер 28 устанавливается в нулевое

i состояние, в HGpBOM такте 0-триггер

10.1 устанавливается в единицу.

На вход устройства подается значение а«, которое поступает на второй

N в двоичном коде, а выход ее связан с S-входом RS-триггера 28, R-вход которого является входом запуска уст4 ройства, выход последнего связан с

R-входом счетчика.26 и является выходом блока синхронизации, а инкрементирующий вход счетчика 26 является входом признака блока синхронизации.

Устройство для LU-разложения матриц предназначено для разложения квадратной матрицы А, разь(ерности И, на две треугольные: нижнюю левую L и верхнюю правую U такие, что Ь U A, причем на главной диагонали матрицы

U стоят единицы. Преобразование матрицы А=(а;! )выполняется по алгоритму исключения Гаусса, в процессе которого получаются элементы 1; и U1(. (s и I (Ц (" ам (g i) о а .=а. — — — — ° а „где а. =а. (/ ц а(%-ч ) N 1(j1 1<

5 15 вход вычитателя 5,! и вторые входы коммутаторов 3.1 и 6.1. Вычитатель

5.1 производит пропуск операнда (на выходе элемента ИЛИ 17 единица), коммутатор 7.1 пропускает а „ с.выхоаа вычитателя на вход регистра 8.1 (на выходе элемента ИЛИ 24 единица )и по заднему фронту синхросигнала а записывается в регистр 8.1.

Это же значение через коммутатор 6,1 поступает на вход записи данных блока памяти 9.1 и записывается (на выходе элемента ИЛИ 20 единица) в ячейку с нулевым адресом, поступающим с выхода счетчика 21, а D-триггер 22.1 сбрасывается в нуль.

Во втором такте а„=l „ с выхода регистра 8.1 поступает на информационный вход процессорного элемента, вычитатель 5.2 осуществляет пропуск операнда и 1 записывается в конце

11 такта в регистр 8.2, пройдя через коммутатор 7.2. В этом же такте содержимое счетчиков 12.1 и 21.1 увеличивается на единицу, а,поступает на вход устройства и далее записывается в блоке 9.1 памяти по адресу (001) (пройдя через коммутатор 6.!) и в регистр 8,1 (пройдя без изменений через вычитатель 5.1 и коммутатор 7.1), D-триггер 22.2 сбрасывается в нуль, В третьем такте 1„ из регистра

8,2 переписывается в регистр 8.3, пройдя через вычитатель 5..3 и коммутатор 7.3, и появляется на выходе устройства, В этом же такте а =1 „ из регистра 8,1 переписывается в регистр 8,2, пройдя через вычитатель

5,2 и коммутатор 7.2. Кроме того, в этом же такте содержимое счетчиков 12.1 и 21,1 снова увеличивается на единицу, а,поступает на вход устройства и далее записывается в блок памяти 9.1 по адресу (010) и в регистр 8.1, D-триггер 22.3 сбрасывается в нуль.

В четвертом такте 1,из регистра

8.2 переписывается в регистр.8.3 и .появляется на выходе устройства, ау1,переписывается из регистра

8.1 в регистр 8.2, содержимое счетчиков 12.1 и 21.1 увеличивается на единицу, на выходе схемы 14.1 сравнения появляется единица, а, поступает на вход устройства и записывается в блок 9.1 памяти по адресу (011) и в регистр 8.1.

1О !

4S

5.0

55 единицу, RS-триггер 19.1 сбрасывает- . ся в нуль, счетчик 12.1 и схема

14.1 сравнения также сбрасываются в нулевое состояние, a„> поступает с входа устройства через коммутатор

3.1 (на выходе элемента ИЛИ 13.1 нуль) на второй вход блока 4,1, на первый вход которого выдается из блока 9,1 памяти из ячейки с адресом (000), поступающим с выхода счетчика 12.1, значение а„, блок 4,1 выполняет операцию деления, и с его выхода «/а„=У,, пройдя через коммутатор

7.1 (на выходе элемента ИЛИ 24,1 нуль), записывается в регистр 8.1, и, пройдя через коммутатор 6.1 (на выходе RS-триггера 19.1 — нуль), записы— вается в блок 9.1 памяти по адресу (100), поступающему со счетчика

21,1 .

В шестом такте 1,из регистра 8.2 переписывается в регистр 8.3 и появляется на выходе устройства, U,q из регистра 8.1 переписывается в регистр 8,2, D-триггер 16.1 сбрасывается в нуль, содержимое счетчика

12.1 увеличивается на единицу, а счетчика 21.1 не меняется, а поступает с входа устройства на второй вход вычитателя 5,1, с первого выхода блока 9.1 памяти (на выходе элемента

ИЛИ 20. 1 — нуль) на первый вход коммутатора 3,1 выдается Б (из ячейки с адресом (100), поступающим с выхода счетчика 21.1), коммутатор 3.1 выдает а, на второй вход блока 4.1 (единица на выходе элемента ИЛИ 13, 1), на первый вход блока 4.1 который выполняет умножение, поступает а,из блока 9.1 памяти (из ячейки с адресом (001)z, поступающим с выхода счетчика 12,1), и с выхода блока 4.1 полученное произведение поступает на вычитатель, с выхода которого а,-а х!1, 1... принимается в регистр 8.1, пройдя через коммутатор 7,1. В этом же такте D-триггер 23. 1 сбрасывается в нуль (т.е, на его инверсном выходе — единица).

В седьмом такте U из регистра 8.2

1а переписывается в регистр 8.3 и появ09933 о

В пятом такте 1 „иэ регистра 8.2 переписывается в регистр 8.3 и появляется на выходе устройства, а, 1, 5 из регистра 8.1 переписывается в регистр 8.2, содержимое счетчиков

21.1 и 26 увеличивается на единицу, D-триггер 16.1, устанавливается в

1509933 ляется на выходе устройства, 1 из регистра 8.1 переписывается в регистр

8.2 и в блок 9.2 памяти (по адресу (000), поступающему с выхода счетчика 21.2). Содержимое счетчика 12.1 увеличивается на единицу, а счетчика

21.1 - не меняется, а поступает с входа устройства на второй вход вычитателя 5,1, с первого выхода блока памяти (через коммутатор 3.1) на вход блока 4.1 выдается а, а с второго выхода блока 9.1 памяти выдается а, (из ячейки с адресом (010), с выхода блока 4.1 полученное произведение поступает на вычитатель 5.1, с выхода которого а .,-а „;Г „=1,ц принимается в регистр 8.1. В этом же такте D-триггер 10.2 устанавливается в единицу. 20

В восьмом такте 1 иэ регистра

8.2 переписывается в регистр 8.3 и появляется на выходе устройства, счетчики 12.1; 12.2 и 21,2 увеличивают свое состояние на единицу, 1 иэ регистра 8.1 переписывается в ðåгистр 8.2 и записывается в блок 9.2 памяти по адресу (001), на выходе схемы 14.1 сравнения — единица, Я.4 .. поступает с входа устройства на 30 ,вход вычитателя 5.1, с первого выхода блока 9,1 памяти на вход .блока 4.1 выдается U„, а с второго выхода блока 9.1 памяти выдяется а 4 (из ячейки с ядресОм 35 (011),с выхода блока 4.1 полученное произведение поступает на вычитатель 5,1, с выхода которого а 4 -U«а 4,=1 принимается в регистр 8, .

В девятом такте 1 переписывает- 40 ся из регистра 8.2 в регистр 8.3 и появляется на выходе устройства, счетчики 12.2; 26; 21.1;.21.2 увеличивают свое состояние на единицу, 14 из регистра 8,1 переписывается в 45 регистр 8.2 и записывается в блок

9 ° 2 памяти по адресу (010), D-триггер 16.1 устанавливается в единицу, счетчик 12.1 и схема 14.1 сравнения сбрасываются в нуль, а: поступает с входа устройства через коммутатор

3.1 на второй вход блока 4,1, на пер" вый вход которого из блока 9.1 памяти выдается (из ячейки с адресом (000) ) значение а(1, блок 4.1 выполняет операцию деления, и с его выхода а,> fa „,=У,, пройдя через коммута.тор 7.1, записывается в регистр 8.! и; пройдя через коммутатор 6.1, записывается в блок 9.1 памяти по адресу (101),, поступающему со счетчика 21.1.

В десятом такте 14 из регистра

8,2 переписывается в регистр 8.3 и появляется на выходе устройства, U из регистра 8,1 переписывается в регистр 8.2, счетчики 12.2; 21.2 и

12.1 увеличивают свое состояние на единицу, на выходе схемы 14.2 сравнения появляется с входа устройства на вход вычитателя 5.1, с первогс выхода блока 9.) памяти через коммутатор 3.1 на вход блока 4 ° 1 поступает а (по адресу (101), поступающему со счетчика 21.1), на первый вход блока 4.1 поступает из ячейки, с адресом (001) значения а,, блок

4.1 выполняет умножение, на выходе вычитателя 5,1 получают значение а -U „.а,=а, которое принимается (1!. в регистр 8.1, пройдя через коммутатор 7.1.

В одиннадцатом такте U èç регистра 8.2 переписывается в регистр 8,3 и появляется на выходе устройства, счетчики !2.1 и 21.2 увеличивают свое состояние на единицу, D-триггер

16.2 устанавливается в единицу, а счетчик 12.2 и RS-триггер 19.2 сбрасываются в нуль, а из регистра 8.1 (>) 23 поступает через коммутатор 3.2 на второй вход блока 4.2, на первый вход из блока 9.2 памяти выдается значение 1 „(из ячейки с адресом (000), поступающим со счетчика

12.2), блок 4.2 выполняет деление, и с егО ВыхОдя а 2 /1 2 U 3 зяписыВя ется в регистр 8.2 и, пройдя через коммутатор 6.2, записывается в блок

9,2 памяти, по адресу (100), поступающему с выхода счетчика 21,2,В этом же такте а поступает с входа устройства на вход вычитателя 5,1 с первого выхода блока 9.1 памяти на второй вход блока 4.1 поступает U на первый вход его из блока 9.1 памяти выдается а,из ячейки с адресом (O!O), блок 4.1 выполняет умножение, и на выходе вычитателя 5,1 получают значение а -U>> а, =а з, коЖ торое принимается в регистр 8,1.

В двенадцатом такте U èç регистра 8,2 переписывается в регистр 8.3, D"òðèããåðû 16.2 и 23,2 сбрасываются в нуль, счетчики 12.2 и 12,! увеличивают свое состояние на единицу, (i) а4 из регистра 8.1 поступает на вход

9 1 вычитателя 5,2, с первого выхода блока 9.2 памяти, через коммутатор

3,2 на вход блока 4.2 поступает U тз на первый вход блока 4.1 поступает из блока 9,2 памяти 1, блоК 4.2 выполняет умножение, и на выходе вычитателя 5.2 получают значение (i) азз Uúç 1ьт=1зз котоРое записывается в регистр 8.2. В этом же такте а поступает с входа устройства на вход вычитателя 5.1, с первого выхода блока 9,1 памяти, на второй вход блока 4,1 поступает U на первый вход его из блока 9,1 памяти выдается а „ блок 4,1 выполняет умножение, и на выходе вычитателя 5 ° 1 получают (s) значение а 43 U )3 a ) а 43 которое принимается в регистр 8 ° 1. В этом же такте D-триггер 23.2 сбрасывается в нуль, а на выходе схемы 14,1 сравнения появляется единица, В тринадцатом такте D-триггер

10,3 устанавливается в единицу, 1 из регистра 8,2 переписывается в регистр 8.3 и, пройдя через .коммутатор

6.3, записывается в блок 9.3 памяти по адресу (000) . В этом же такте счетчики 21,1; 12.2 и 26 увеличивают свое состояние на единицу, а счетчик

12.1 сбрасывается в нуль, а,. из ве(е) гис тр а 8 . 1 поступает на вход вычитателя 5 . 2 с первого выхода блока

9 . 2 памяти на второй вход блока 4 ° 2 поступает U z, на первый вход его из блока 9,2 памяти поступает 1 4,, блок 4,2. выполняет умножение, и на выходе вычитателя 5.2 получают ()) значение а4 -U z 1 =1,, которое записывается в регистр 8.2. В этом же такте ам поступает на второй вход блока 4.1, на первый вход которого из блока 9,1 памяти выдается значение а,„, блок 4.1 выполняет операцию деления, и с его выхода а „ /a „ =

=U< записывается в регистр 8.1 и, пройдя через коммутатор 6.1 — в блок

9.1 памяти по адресу (!10), поступающему со счетчика 21,1.

В четырнадцатом такте счетчики

12.3; 21,3; 12.2 и 12 ° 1 увеличивают свое состояние на единицу, единица .появляется на выходе схемы 14.2 сравнения, 14 из регистра 8.2 пере" писывается в регистр 8.3 и, пройдя через коммутатор 6.3, записывается в блок 9.3 памяти по адресу (001) q.

В этом же такте U из регистра 8.1 переписывается в регистр 8.2, а),)с

509933 10 входа устройства поступает на выход вычитателя 5. 1, с первого выхода блока 9.1 памяти, на второй вход . блока 4.1 поступает U, на первый вход блока 4.1 поступает из блока 9.1 памяти а, блок 4.1 выполняет умножение, и на выходе вычитателя 5.1 (i) получают значение а -У,„. а., а,, (!! которое принимается в регистр 8.1.

В пятнадцатом такте D-триггер

16.2 устанавливается в единицу, счетчик 12,2 и RS-триггер 19.2 сбра.сывается в нуль. Счетчики 12.3;

21.3; 21,2 и 12.1 увеличивают свое состояние.на единицу, U) из регистра 8.2 переписывается в регистр

8.3. В этом же такте а(),из регистра

8.1 поступает через коммутатор 3.2

20 на второй вход блока 4.2, на первый вход которого из блока 9,2 памяти выдается 1,, блок 4.2 выполняет деление, и с его выхода значение а / (11

/1 =1)«записывается в регистр 8.2 и

25 блок 9.2 памяти по адресу (101) . В этом же такте а с входа устройства поступает на вход вычитателя 5.1, с первого выхода блока 9.1 памяти на второй вход блока 4.1 поступает U 4, 30 на первый вход блока 4.1 поступает из блока 9,1 памяти а,, блок 4,1 выполняет умножение, и на выходе вычитателя 5.1 получают значение а „-U «x (»

) а,=а, которое принимается в ре35 гистр 8,1.

В шестнадцатом такте счетчики

12.3 21.3; 12.2 и 12.1 увеличивают свое состояние на единицу, на выходах схем 14.1 и 14.3 сравнения тоже

40 единицы, U 4переписывается из регистра 8.2 в регистр 8.3. В этом же

И такте а из регистра 8.1 поступает на вход вычитателя 5.2, с первого выхода блока 9,2 памяти на второй

45 вход блока 4,2 поступает U,, на первый вход блока 4.2 поступает из блока 9.2 1, блок 4.2 выполняет умножение, и на выходе вычитателя 5.2

IIoJI aIoT значение a -U «1 >=a,„ которое принимается в регистр 8.2.В этом же такте а с входа устройства поступает на вход вычитателя 5.1, с первого выхода блока памяти на второй вход блока 4.1 поступает U на первый вход блока 4.1 поступает из блока 9,1 памяти а 4,, блок 4.1 выполняет умножение, и на выходе вычитателя 5.1 получают значение à «-U « а „,= (т)

=a (, которое принимается в регистр,8. 1.

3

Формула

11 150993

B семнадцатом такте счетчик 26 увеличивает свое состояние на единицу, на выходе схемы 27 сравнения появляется единица, RS-триггер 28 устанавливается в единицу, счетчики 26, 12.1 и 21.1 и П-триггеры 10.1 и 16.1 устанавливаются в нулевое состояние, таким образом происходит подготовка к обработке следующей исходной матри- IQ цы. В этом же такте счетчик 12.3 сбрасывается в нуль, счетчики 21.3 и

12.2 увеличивают свое состояние на единицу, а(из регистра 8.2 поступаЗ4 ет через коммутатор 3.3 на второй 15 вход блока 4.3, на первый вход которого из блока 9.3 памяти выдается

1, блок 4.3 выполняет деление, и (a) с его выхода значение а з /1 з =11 записывается в регистр 8.3 и блок 9,3 20 памяти по адресу (100) . В этом же такте а из регистра 8,1 поступает на вход вычитателя 5.2, с первого выхода блока 9,2 памяти на второй вход блока 4.2 поступает U,,на первый вход блока 4.2 поступает 1,1 из блока 9,2 памяти, блок 4.2 выполняет умножение, и на выходе вычита(() теля 5.2 получают значение а 4-U z4 i

14 =а 4, которое принимается в ре- 30 () гистр 8. 2.

В последнем (восемнадцатом) такте

Р-триггер 22.1 и RS-триггер 19,2 устанавливаются в единицу, счетчик

12,3 увеличивает свое состояние на единицу, а счетчики 12,2 и 21.2 и

D-триггеры 10.2 и 16.2 сбрасываются в нуль. В этом же такте а из регистра 8.2 поступает на вход вычитателя

5 3, счетчик 12.3 увеличивает свое 4Q состояние на единицу, с первого выхода блока 9.3 на второй вход блока

4.3 поступает U>4 на первый вход блока 4,3 поступает 14йиз блока памяти

9,3, блок 4.3 выполняет умножение, и на выходах вычитателя 5,3 получают

Значенне R 1 43 U 34 1 44 р котор< (7I е

44 принимается в регистр 8.3. !

На этом разложение квадратной матрицы А=(а; )размерности И=4 за11 канчивается. Поскольку каждый элемент входной матрицы А используется в каждом данном процессорном элементе только один раз, можно выполнять LUразложение потока матриц. Каждую следующую матрицу можно начинать подавать с (И +1)-го такта после нача l ла подачи предыдущей матрицы. и з о б р е т е н и .

1. Устроиство для LU разложения матриц, содержащее п-1 (n — размерность разлагаемой матрицы) операционных блоков и блок синхронизации, вы-, ход которого подключен к первому управляющему входу первого операционного блока, информационный вход которого является информационным входом устройства, Информационный вход i-то операционного блока (i--2, и-1) подключен к информационному выходу (i-1) — го операционного блока, а информационный выход (n-1)-го операционного блока является выходом устройства, отличающееся тем, что, с целью сокращения аппаратурных затрат, первый и второй управляющие входы i-го операционного блока подключены соответственно к первому и второму управляющим выходам (i-1)-го операционного блока, второй и третий управляющие входы первого операционного блока подключены соответственно к входам логической единицы и логическоro нуля устройства, а третьи управляющие входы остальных операционных блоков подключены к входу логической единицы устройства, третий управляюпц4й выход первого операционного блока подключен к первому входу блока синхронизации, второй вход которого является управляющим входом устройства.

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что операционный блок содержит регистр, вычитатель, блок умножения-деления, три коммутатора, два счетчика, блок памяти, четыре D-триггера, схему сравнения, RS-триггер, два элемента И и пять элементов ИЛИ, причем выход первого коммутатора соединен с первым информационным входом блока умножения-деления, выход которого соединен с первыми информационными входами вычитателя, второго и третьего коммутаторов, второй информационный вход вычитателя подключен к первому информационному входу первого коммутатора, второму информационному входу второго коммутатора и к информационному входу операционного блока, информационный выход которого соеди- нен с выходом регистра, вход .которо» го соединен с выходом третьего ком13 15 мутатора, второй информационный вход которого соединен с выходом выI читателя, выход второго коммутатора соединен е входом записи данных блока памяти, первый выход которого соединен с вторым информационным входом первого коммутатора, а второй выход — с вторым информационным входом блока умножения-деления, первый .управляющий вход операционного блока соединен с входами обнуления первого счетчика, первого и второго Dтриггеров, с S-входом RS-триггера, с первым входом первого элемента

ИПИ и с входом третьего D-триггера, выход которого является первым управляющим выходом операционного блока, второй управляющий выход которого соединен с выходом четвертого D-триггера, вход которого подключен к первому входу второго элемента ИЛИ, выходу RS-триггера, первым входам третьего и четвертого элементов ИЛИ и управляющему входу второго коммутатора, второй управляющий вход операционного блока подключен к входу первого D-триггера, выход которого соединен с первым входом первого элемента И и с инкрементирующим входом второго счетчика, выходы которого под09933 ключены к входам пятого элемента ИЛИ, первому адресному входу блока памяти и к входам первой группы схемы сравнения, входы второй группы которой соединены с входом задания N-1 в двоичном коде блока, выход схемы сравнения соединен с первым входом второго элемента И, входом второго .

D-триггера, вторым входом второго элемента ИЛИ и является третьим управляющим выходом операционного блока, третий управляющий вход которого соединен с вторым входом второго элемента И, выход которого соединен. с вторым входом третьего элемента

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

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

3р которого соединен с вторым адресным входом блока памяти. фЭ °

ЭФф

1509933

Фиг. 2

Составитель К.Кухаренко

Редактор M,Áëàíàð Техред Д.0лийнык Корректор C,Øåêìàð

Заказ 5815/48 Тираж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям нри ГКНТ СССР

113035, Москва, Я-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101