Устройство для решения матриц Советский патент 1978 года по МПК G06F7/38 

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

Известны устройства для выполнения операций над матрицами, содержащие регистры, счетчики, логические схемы, арифметические устройства 1.

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

Операция обращеиия матриц, выиолняемая на существующих ЭВМ, требует большого объема памяти (при достаточно высоком иорядке матрицы) и больших затрат машинного времени.

Наиболее близким техиическим решеиием к данному предложению является устройство для решения матриц, содержащее входной регистр, входы которого соединены с информационными входами устройства, четыре группы блоков суммирования и вычитания, блок деления, блок обращения чисел, блок управления 2.

Недостатком его является невозможность выполнения операции «обращение матрицы.

Целью изобретения является расширение

функциональных возможностей устройства, благодаря выполнению операции «Ьбращеиие матрицы.

Цель изобретения достигается тем, что в устройстве выходы входиого регистра соединень со входами блоков суммирования н вычитания первой группы, выходы которых соеднисны со входами блоков суммирования н вычитания второй группы, выходы которых соединены со входамн блоков суммирования

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

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

Таким образом, обращение матриц сводится к обращению чисел, количество которых равно порядку (числу элементов в строке матрицы), а операции умножения и деления,

присущие известным методам обращения матриц, заменяются суммированием н вычитанием.

В устройстве реализован следующий алгоритм обращения матриц.

Исходную матрицу можно записать в виде а b

L

b а

где 1|а|1 и ||6|| являются таклсе матрицами с норядком, уменьшенным относительно иорядка исходной матрицы L в два раза.

Обращенная матрица может быть записана в виде

с d

L-I

d с

где

-l(a + 6)-i+(a-6)-iJ; d (a + b)-(a-b)-.

Причем в общем случае с и d являются также матрицами и легко определяются из вышенриведеиных выражений.

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

разложеиие вектор-строки исходной матрицы до 2 чисел;

обращение 2 чисел, получениых в результате разложения;

свертка обращеииых чисел по ирнведеииому алгоритму

я

2;

, (

операция деления результатов свертки на число /(2 (П - показатель порядка матрицы ).

На фиг. 1 представлеиа блок-схема устройства для обращения диодных матриц восьмого порядка; иа фиг. 2 - блок-схема устройства обращения матриц четвертого порядка.

Устройство обращения матриц содержит входы 1, входной регистр 2, иредназиачеииый для заниси в него вектор-строки обращаемой матрицы, нсрвую груииу блоков суммирования и вычитания, содержащую блоки суммирования 3 и блоки вычитания 4; вторую груииу блоков суммирования и вычитания, содержащую блоки суммирования 5, 6 и блоки вычитания 7, 8; третью группу блоков суммирования и вычитания, содержащую блоки суммирования 9, 10, И, 12 и блоки вычитаиия J3, 14, 15, 16, блок ячеек обращения чисел 17, четвертую группу блоков суммироваиия и вычитаиия, содержащую блоки суммирования 18, 19, 20, 21 и блоки вычитания 22, 23, 24, 25; блок ячеек деления 26, выходы устройства 27 и блок управления 28, предназначенный для

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

Запишем исходную диадную матрицу:

а b

1: b а

где

01

а --15

т. е. а и о являются также матргщами.

Работа устройства иачииается с того, что через входы 1 в регистр 2 заинсынастся вектор-строка исходной матрицы, т. е. е ||о 1 2о|{;

затем, по сигналам из блока управления 28 в блоке 3 вычисляются и заиоминаются суммы 5+2 7, а в блоке 4 вычисляются и заиоминаются разности 5 - 2 3 и , причем блоки 3 и 4 работают параллельно. Таким образом в блоках 3 п 4 вычисляются комионснты:

с . 3 -41-1 . 2 +L-4 aj ,

61-1

7

3

-г

76

9

4

Затем блоком управления 28 открываются входные вентили (иа чертеже не показаны) блоков суммирования 9 и 10 и вычитания 15 и 16.

В блоке 9 вычисляется сумма 7 + . а в блоке 10 разиость 7 - , в блоке 15 вычисляется сумма 3+(-4) -1, а в блоке 16 разиость 3- (-4) 7. Блоки 9, 10, 15, 16 работают параллельно м вычисляют следующие компоиеиты:

i б Т + (- )

- (13-1 +1-М;

1 (761-1

(+)

d .::4(13-1-1-0;

3 -4

--4(3

-4)1-1 +

-4 3

+ (3(--4).: -L(bi+7-);

:

-(3-(-4).:4(-l-I-7-), т. е. к началу очередного такта раооты устройства на выходах блока 9 существует сумма 13, блока 10 - разность 1, блока 15 - сумма - 1, блока 16 - разность 7. Выходы блоков 9, 10, 15, 16 соединены со входамн ячеек обращения чнсел блока 17, по сигналу из блока управления 28, в блоке 17 будут обращены числа, постунающие из блоков 9, 10, 15, 16, т. е. на выходах блока 17 к началу следующе 1 1 1 1 го такта будут получены числа -, 1, -1,-. 1оУ Затем по сигналу кз блока управления 28 в блоке суммирования 18 будет получена компонента ,, , iWJ- . 2 13 J 2 13 26 В блоке 19 будет вычислена компонента d -

в блоке 24 вычнслится компонента

6 14

-1 +

с

в блоке 25

d (-l2 V

14

оатем по сигналу из блока управления 25 результаты, полученные; в блоках 18, 19, 24, 25, работающих параллельно, будут переданы в блок ячеек деления 26. Результат деления по сигналу из блока угфавления 28, который откроет первую группу выходных вентилей блока деления 26, выходы которых соединены со входами регистра 2, будут записаны в регистр 2, т. е. в регистр 2 будут записаны числа (мы не пользуемся двоичными эквивалентами этих чисел при рассмотрении работы устройства, т. к. на наш взгляд при этом теряется наглядность). По сигналу из блока управления 28 в блоке суммирования 3 будет получен компонент

f Л 11 J JL. 13 V 7 j2 91

9

d - -1Г-- + Г- -M-- - 2 L 13 +V 7 yj- 2

a в блоке 4

/ JL

V 7

91

L 1

V 7 yj

2 91

По сигналу из блока управлен1 я 28, который откроет группу вентилей, входы которых связаны е блоками 3, 4 и блоком управлен1 Я, а выходы с блоком деления 2, 6 результаты нз

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

25

УстройетБО для решения матриц, содержащее входной регистр, входы которого соединеиы с информационными входами устройства,

четыре группы блоков су«1мирования и вычитания, блок дсло;;1:я, блок обращения чисел, блок управления, о т л и ч а ю щ е е с я тем, что, с расширения функциональных возможностей устройства благодаря выполнению

операции «Обращение матрицы, в нем выходы входного соединены со входамн б.юког, суммирования и вычитания первой rpyriribi, выходы которых соеди; е; Ы со входами б.юков суммирования и вычитания второй

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

четвертой группы, выходы которых подключены ко вторым входам блока делеи.я, выходы которого являются информационными выходами устройства, управляющие входы вход91ного регистра, блоков суммирования и вычнтаиия, блока деления и блока обращения чисел соединены с еоотво1ст15уюн1, выходами блока управлеш.я.

Источники информации, иринятые во внимание при экснертнзе

1.Авторское свидетельство СССР Л 320810, кл. G 06F 7/38, 1971.

2.Авторское свидетельство СССР №404090, кл. G 06F 15,32. 1972. блоков 3, 4 будут переданы в блок деления 26 и по сигналу из блока управления 28, который теперь откроет группу вентилей блока 26, связанную с устройством, на которое работает устройство обращения матриц, на выходы 27 будет .выдана вектор-строка обращенной матрнцы, т. е. II 91 91 91 91 Результат на выходах 27 нредставляется двоичными кодами, мы же его составили в виде дроби для наглядности. Таким образом применение метода, позволяющего свести операнию обращения матриц к обращению чисел, дало возможность получить сравнительно простое устройство. Такое устройство позволит значительно сократить машинное время при решении задач, связанных с обращением матриц, на универсальных ЭВМ. f1 I ,-Ч1 I- h--- I f ii m

/ -r.Л. |.iJ I 1 i--:-f- i-: мМ J : ii.