Устройство для обращения матриц

 

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

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

РЕСПУБЛИК (19) (11) (51)4 G 06 F 15/347 (21) 3771109/24-24 (22) 12.07.84 (46) 15.02.86. Бюл. N - 6. (72) П.А.Кот, О.P.Äóäà, С.Н.Борисен ко, Л.Н.Коновалов и А.А.Жалило (53) 681.325(088.8) (56) Авторское свидетельство СССР

Р 320810, кл. G 06 Г 7/38, 1971.

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

У 404090, кл. G 06 F 15/32, 1972.

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

У 595726, кл. С1 06 Г 15/347, 1975. (54)(57) 1.УСТРОЙСТВО ДЛЯ ОБРАЩЕНИЯ

МАТРИЦ, содержащее блок управления, ключ выдачи, выходы которого являются выходами «1 элементов обращенной матрицы устройства, где i =(,и — номер строки матрицы, j = (,n — номер столбца матрицы, n — порядок матрицы, И сумматоров константы, вычислитель, включающий первый и второй сумматоры, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет обращения матриц произвольной размерности, в него введены коммутатор, буферный блок памяти, блок памяти констант, выход первой константы которого подключен к первым входам сумматоров константы, вторые входы которых являются информационными входами соответствующих

ij элементов диагонали матрицы (= =1р ), выходы и сумматоров константы и информационные входы ij элемен;тов матрицы (< 1,n, j =(,n, i g1) образуют первый информационный вход коммутатора, выход буферного блока памяти подключен к второму информационному входу коммутатора и к информационному входу ключа выдачи, третий и четвертый информационные входы коммутатора подключены к выходам второй и третьей константы блока памяти констант, входы промежуточных результатов уменьшаемых, первых и вторых сомножителей вычислителя подключены к одноименным выходам коммутатора, вход кода управления и вход выбора которого подключены к одноименным выходам блока управления, выход выдачи ре:зультата которого подключен к входу стробирования информации ключа вы- дачи, выходы первой и второй константы блока памяти констант подключены к одноименным входам вычислителя соответственно, выход которого подключен к информационному входу буферного блока памяти, первый и второй входы записи которого подключены к прямому и инверсному выходам записи блока управления, вход константы которого подключен к выходу четвертой константы блока памяти констант, коммутатор содержит мультиплексоры предварительной коммутации, выделения диагонального элемента, уменьшаемых, первых и вторых сомножителей, первый, второй инфор-, мационные и адресный входы мультиплексора предварительной коммутации являются первым, вторым информационными входами входом выбора ком1211755 мутатора соответственно, выходы значений диагональных элементов мультиплексора предварительной коммутации подключены к информационным входам мультиплексора выделения диагонального элемента, выход мультиплексора предварительной коммутации подключен к первым информационным входам мультиплексоров уменьшаемых и первого сомножителя и к информационному входу мультиплексора второго сомножителя, вторые информационные входы мультиплексоров уменьшаемых и первого сомножителя объединены и являются третьим информационным входом коммутатора, третий информационный вход мультиплексора уменьшаемых является четвертым информационным входом коммутатора, адресные входы мультиплексоров выделения диагонального элемента, уменьшаемых, первых и вторых сомножителей объединены и являются входом кода управления коммутатора, выходы мультиплексоров вьщеления диагонального элемента, уменьшаемых, первых и вторых сомножителей являются одноименными выходами коммутатора, а в вычислитель введены блок вычисления обратной величины, с первого по третий умножители, выход первого сумматора вычислителя через блок вычисления обратной величины подключен к перво-му входу первого умножителя, второй вход которого является входом первой константы вычислителя, первый и второй входы первого сумматора являются входом промежуточного результата и входом второй константы вычислителя соответственно, первый и второй входы второго умножителя являются входами первого и второго сомножителей вычислителя, выходы первого и второго умножителя подключены к первому и второму входам третьего умножителя, выход которого подключен к первому входу второго сумматора, второй вход и выход которого являются входом уменьшаемых и выходом вычислителя, блок управления содержит триггер запуска, триггер выдачи, триггер состояния, генератор тактовых импульсов, первый и второй одновибраторы, элемент И, элемент НЕ, счетчик, схему сравнения, формирователь сигнала выбора, вход установки триггера запуска и вход сброса триггера выдачи объединены и являются входом запуска блока управления устройства, выход триггера запуска подключен к информационному входу триггера состояния, выход которого подключен к первому входу элемента И, выход которого подключен к входу элемента НЕ и через первый одновибратор к счетному входу счетчика и является прямым выходом записи блока управления, выход элемента НЕ является инверсным выходом записи блока управления, выход генератора тактовых импульсов подключен к входу синхронизации триггера состояния и через второй одновибратор к второму входу элемента И, выход счетчика подключен к первому входу схемы сравнения, к входу фор-. мирователя сигнала выбора и является выходом кода управления блока управления, выход формирователя сигнала выбора и выход триггера выдачи являются выходами выбора и выдачи результата блока управления, второй вход схемы сравнения является входом константы блока управления, выход схемы сравнения подключен к входам сброса триггеров запуска и состояния и к входу установки триггера выдачи.

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

50

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

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

На фиг.1 представлена функциоHGBbHBH eM T oH o P - l5 щения матриц; на фиг.2 — функциональная схема сумматоров константы; на фиг.3 — функциональная схема коммутатора; на фиг.4 — функциональная схема вычислителя, на фиг.5— функциональная схема буферного блока памяти, на фиг.6 — функциональная схема блока управления; на фиг.7 — функциональная схема мультиплексора предварительной коммутации, на фиг.8 — функциональная схема мультиплексора вьщеления диагонального элемента, на фиг.9— функциональная схема мультиплексора уменьшаемых; на фиг.f0 — функциональ30 ная схема мультиплексора первых сомножителей, на фиг.11 — функциональная схема мультиплексора вторых сомножителей; на фиг.12 — функциональная схема формирователя знаменателя вычислителя; на фиг.13— функциональная схема второго умножителя, на фиг.14 — функциональная схема третьего умножителя; на фиг.15 — функциональная схема второго сумматора; на фиг.16 — функциональная схема формирователя сигнала выбора; на фиг.17 — временная диаграмма работы блока управления на фиг.18 — таблица результатов вычислений на выходах блоков на каждом шаге вычислений, Устройство обращения матриц (фиг.1) содержит информационные входы 1 элементов матрицы, ff сумматоров константы 2, коммутатор 3, вычислитель 4, буферный блок 5 памяти, ключ 6 выдачи, блок 7 памяти констант, выходы 9 элементов обращенной матрицы, шину 10 первой константы, первый информационный вход 11 коммутатора, шину 12 третьей константы, второй информационный вход 13 коммутатора 3, выходы 14-17 промежуточного результата уменьшаемых первых и вторых сомножителей соответственно, выход 18 вычислителя 4, шину 19 второй константы, вход 20 кода управления коммутатора

3, шину 21 четвертой константы, вход 22 выбора коммутатора 3, прямой и инверсный входы 23 и 24 записи буферного блока 5 памяти, вход 25 выдачи результата ключа 6 °

Группа и сумматоров константы 2 содержит сумматоры 26 по числу диагональных элементов матрицы.

Коммутатор 3 (фиг.3) содержит мультиплексор 27 предварительной коммутации, мультиплексор 28 вьщеления диагонального элемента, мультиплексор 20 уменьшаемых, мультиплексор 30 первых сомножителей и мультиплексор 31 вторых сомножителей.

Вычислитель 4 (фиг.4) содержит формирователь знаменателя 33, второй и третий умножители 34 и 35, второй сумматор 36, первый, второй входы 37 и 38 и выход третьего умножителя 35 °

Буферный блок 5 памяти (фиг.5) содержит первый и второй регистры 40.

Блок управления 8 (фиг.6) содержит генератор 41 тактовых импульсов, первый одновибратор 42, триггер 43.1 запуска, триггер 43.2 выдачи, триггер 44 состояния, элемент И 45, элемент HE 46, второй одновибратор 47, счетчик 48, схему

49 сравнения и формирователь 50 сигнала выбора, вход 51 запуска блока 8 -и устройства, выход 52 генератора 41, информационный вход

53 триггера 44, первый и второй входы 54 и 55 элемента И 45, выход

56 схемы 49, счетный вход 57 счетчика 48.

Мультиплексоры 27-31 выполнены по схемам, приведенным на фиг ° 7-1 с использованием мультиплексоров 58.

Формирователь знаменателя 33 (фиг. 12) вычислителя 4 содержит первый сумматор 26, блок 59 вычисления обратной величины, первый умножитель 60.

Формирователь 50 сигнала выбора (фиг.16) содержит элемент НЕ 61 и элемент И-НЕ 62.

В устройстве реализован следующий алгоритм для обращения матрицы порядка и (алгоритм Ершова). Пусть требуется обратить матрицу порядка И а„а,г ... а<„ агг " аг

0ni апг " аnn

1211755 ра 3 формируется последовательность чисел

021203110, которая поступает на мультиплексор

27 предварительной коммутации 27 (фиг.3) коммутатора 3.

1О

l5

20 (m) а"

11 в=

Ф) р (, „rn =1,n) 121

А=213 t 1 1

-2 -1 5

1 0-1

1 1-3

121213111, Согласно алгоритму для вычисления

-1 матрицы A необходимо провести

° (oj (%) (7) (n) вычисления матриц: А >А,А „„, Д где A 1 = А — Е, а Š— единичная матрица и а(m m11 (m i) (т-<1 jm mj а.. 1 ф rn 1 1о - ) Ф

thm (ю-1) ! + а „

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

Нетрудно показать, что обратная ей будет матрица

Работа устройства начинается с того, что по входам 1 исходная матрица в виде последовательности ее элементов, полученная разложением по строкам поступает через и сумматоров константы 2 на первый информационный вход 11 коммутатора 3, при этом на сумматорах константы 2 из диагональных элементов матрицы вычитается

"1", поступающая по шине 10 первой константы из блока 7 (двоичный эквивалент чисел не используется при рассмотрении работы устройства, так как при этом теряется наглядность).

Таким образом, на входе 11 коммутато25

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

51 внешнего запуска (фиг.17). При этом сбрасывается в нуль счетчик 48, переводится в нулевое состояние триггер 43.2, закрывая ключ 6, который запрещает вывод информации из буферного блока 5 во время вычислений, а также переводится в единичное состояние первый триггер 43.1, обеспечивая появление "1" на информационном входе триггера 44 (фиг.17). Перевод триггера 44 в единичное состояние происходит в момент появления на его счетном входе тактового импульса от генератора 41 тактовых импульсов. В результате с выхода триггера 44 "1" поступает на первый вход элемента И 45, обеспечивая прохождение синхроимпульсов, поступающих на второй ее вход от первого одновибратора 42. С выхода элемента И 45 синхроимпульсы поступают на вход второго одновибратора 47, формирующего импульсы, по-заднему фронту синхроимпульсов, которые являются счетными импульсами счетчика 48. Период следования синхроимпульсов выбирается из условия полного завершения одного шага вычислений.

На первом шаге вычислений с выхода счетчика 48 поступает в двоичном коде "1" на выход 20 и на вход формирователя 50, в соответствии с законом работы которого (фиг.16) на

его выходе на первом шаге формируется "0". На всех последующих шагах на выходе 22 присутствует "1". Так как вывод 22 является управляющим для мультиплексора 27 предварительной коммутации, то в соответствии с законом работы, на его выход передается последовательность чисел с шины

11 при сигнале на выводе 22, равном

"0" (первый шаг вычислений) или последовательность чисел с шины 13 при сигнале на выводе 22, равном "1" (фиг.7), т.е. на первом шаге на выходе мультиплексора 27 предваритель11755 Ф не 10 первой константы, в первый умножитель 60. В итоге на первом шаге на шину 37 поступает число

10

02 104202 1, 15

О.

25

1002031 10.

121

021

S 12 ной коммутации будет сформирована последовательность чисел

021203110, которая поступает на входы мультиплексоров выделения диагонального элемента 28, уменьшаемых 29, первых сомножителей 30 и вторых сомножителей

31 (фиг.3).

В соответствии с законом работы мультиплексора 28 выделения диагональных элементов (фиг.8) к его выходу подключается шина, номер диагонального элемента которой совпадает с номером шага вычислений переданного по шине кода управления 20 из блока 8 управления, т.е. на первом шаге на выход 14 передается число

Последовательность чисел по шине 32 поступает на вход мультиплексора 29 уменьшаемых, на выходе которого в соответствии с законом работы и номером шага вычислений (фиг.9) сформируется на первом шаге последовательность чисел

Последовательность чисел с выхода мультиплексора 27 предварительной коммутации поступает на вход мультиплексора 30 первых сомножителей (фиг. 10), на выходе которого на первом шаге в соответствии с законом работы и номером шага вычислений, поступающего по шине 20, сформируется следующая последовательность чисел

Кроме того, последовательность чисел по шине 32 также поступает на вход мультиплексора 31 вторых сомножителей, на выходе которого на первом шаге вычислений (фиг.1) появляется последовательность чисел

По выходу 14 с мультиплексора 28 выделения диагонального элемента число "0" на первом шаге поступает на вход формирователя знаменателя 33 (фиг.12), где складывается с "1", поступающей по шине 19 второй константы блока 7 констант, преобразуется в обратную величину в блоке вычисления обратной величины 59 и умножается на "-1", поступающую по ши35

С выходов мультиплексоров первых сомножителей 30 и вторых сомножителей

31 последовательность чисел поступает на входы второго умножителя 34 (фиг.13), где производится их взаимное перемножейие, в результате чего на выходе на первом шаге формируется последовательность чисел

1 которая по шине 38 поступает на вход третьего умножителя 35 (фиг.14), в котором все числа последовательности умножаются на число, переданное по шине 37 из формирователя знаменателя 33, в результате чего на первом шаге на шину 39 передается последовательность чисел

0 -2 -1 0 -4 -2 0 -2 -1, которая в свою очередь складывается в соответствии с номерами с последовательностью чисел, поступающей по шине 15, во второй сумматор 36 (фиг.15), на выходе которого на первом шаге формируется последовательность чисел

1 -2 -1 2 -4 1 1 -1 -1.

Данная последовательность чисел по шине 18 поступает на входы первого регистра 40 буферного блока 5 . (фиг.5), который служит для развязки между собой шагов вычислений и устранения эффекта "гонок". Во время вычисления на каком-либо шаге на первый регистр 40 по выводу 23 поступает управляющий сигнал " 0" с выхода элемента И 45 блока управления 8 (фиг.6), разрешающий запись информации в данный регистр, в то время как по выводу 24 на второй регистр

40 поступает "1" с выхода элемента И-НЕ 46 блока управления 8, разрешающая чтение информации из этого регистра. Период следования синхроимпульсов с выхода первого одновибратора 42 выбираешься таким образом, чтобы за время существования низкого перепада напряжения на его выходе полностью завершались вычисления на данном шаге и запись результата в первый регистр 40 (фиг.17). При

1211755 8

5 записывается последовательность чисел ности. появлении высокого потенциала на выходе элемента И 45 на первый регистр 40 йоступает "1", а на второй

"0", т.е. происходич перезапись ин — формации из первого регистра во второй. При появлении следующего синхроимпульса выдается разрешение на чтение результата из второго регистра 40 и на запись результата следующего шага вычисления в первый регистр 40. Количество шагов вычислений равно порядку обращаемой матрицы. Результаты на выходах отдельных блоков для каждого шага приведены в таблице (фиг.18).

На каждом шаге вычисления в схеме сравнения 49 происходит сравнение номера шага вычисления, поступающего с выхода счетчика 48 и числа "4" (в общем случае " +1", где 1 порядок матрицы), поступающего по шине четвертой константы 21 из блока констант

7 (фиг.6) . В результате окончания последнего третьего шага вычисления во второй регистр 40 буферного блока

-2 — 1 5 1 0 — 1 1 1 -3, представляющая элементы обращенной матрицы А . В момент появления следующего четвертого синхроимпульса на выходе элемента И 45 блока управления 8 на управляющий вход второго

10 регистра 40 буферного блока 5 поступает сигнал "1" разрешения чтения.

Номер четвертого синхроимпульса поступает также на вход схемы сравнения 49, в результате чего на ее

15 выходе формируется управляющий импульс, который переводит триггер 43.2 в единичное состояние, тем самым выдав разрешение на открытие ключа

6 и, соответственно, на вывод резуль—

20 тата, а также перебросит в нулевое состояние триггеры 43.1 и 44, что соответствует запиранию блока управления 8 и окончанию вычисления.

Устройство решает задачу обращения для матриц произвольной размер1211755

ff

Фиг.Я

1г

11 ъ

/б

1У 10

1б

17 фиа4.

Q

gruc. 5

5, 1211755

32

32

13 фиа 10

A+I г г

)211755!

2!!755

)211755 (pub. f7

Составитель А.Ушаков

Редактор Т.ПарФенова Техред Л.Микеш Корректор Т Колб

Заказ 642/54 Тираж 673 Подписное

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

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

Филиал ППП "Патент", г.Ужгород, ул.Проектная, 4