Устройство для обращения матриц Советский патент 1986 года по МПК G06F17/16 

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

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

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

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

На фиг.1 представлена функциональная схема устройства для обращения матриц; на фиг.2 - функциональная схема сумматоров константы; на фиг.З - функциональная схема коммутатора; на фиг.4 - функциональная схема вычислителя; на фиг.З - функциональная схема буферного блока памяти; на фиг.6 - функциональная схема блока управления; на фиг.7 - функциональная схема мультиплексора предварительной коммутации; на фиг.8 - функциональная схема мультиплексора выделения диагонального элемента; на фиг.9 - функциональная схема мультиплексора уменьшаемых; на фиг.10 - функционалная схема мультиплексора первых сомножителей на фиг.11 - функциональная схема мультиплексора вторых сомножителей; на фиг.12 - функциональная схема формирователя знаменателя вычислителя; на фиг.13 - функциональная схема второго умножителя; на фиг.14 - функциональная схема третьего умножителя; на фиг.15 - функциональная схема второго сумматора; на фиг.16 - функциональная схема формирователя сигнала выбора; на фиг.17 - временная диаграмма работы блока управления; на фиг.18 - таблица результатов вычислений на выходах блоков на каждом шаге вычислений.

Устройство обращения матриц (фиг.1) содержит информационные входы 1 элементов матрицы, И сумматоров константы 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

5

0

выдачи результата ключа 6.

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

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

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

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

Блок управления 8 (фиг.6) содержит генератор 41 тактовых импульсов, первый одновибратор 42, триггер 43.1 запуска, триггер 43.2 выдачи, триггер 44 состояния, эле- 5 мент И 45, элемент НЕ 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 ц 5 элемент И-НЕ 62.

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

5

0

требуется обратить матрицу порядка rt

А

Согласно алгоритму для вычисления матрицы необходимо провести вычисления матриц: А А , ,.,. А , где ,аЕ- единичная матрица и

(т)

g(m-0 Ст-0 (т-0 im mj .

i - ио :- -

o(m-i) mj

«гп

р М, m 5 , .

°т ,. ,. (, n J О, т J

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

А

12 1

21 3 1 1 1

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

А

-2 -1 5 1 О -1 1 1 -3

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

121213111,

поступает через ц сумматоров константы 2 на первый информационный вход 11 коммутатора 3, при этом на сумматорах константы 2 из диагональных элементов матрицы вычитается 1, поступающая по шине 10 первой константы из блока 7 (двоичный эквивалент чисел не используется при рассмотрении работы устройства, так как при этом теряется наглядность). Таким образом, на входе 11 коммутато12117554

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

021203110,

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

Основная работа устройства осу10 ществляется блоком 8 управления и . начи1;ается подачей сигнала на вход 51 внешнего запуска (фиг.17). При этом сбрасывается в нуль счетчик 48, переводится в нулевое состояние

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

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

5 его выходе на первом шаге формируется О. На всех последующих шагах на выходе 22 присутствует 1. Так как вьшод 22 является управляющим для мультиплексора 27 предваритель50 ной коммутации, то в соответствии с законом работы, на его выход передается последовательность чисел с шины 11 при сигнале на выводе 22, равном О (первьй шаг вычислений) или пос55 ледовательность чисел с шины 13 при сигнале на вьшоде 22, равном 1 СФИГ.7), т.е. на первом шаге на выходе мультиплексора 27 предваритель35

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

О 2 1 2 О 3 1 J О, которая поступает на входы мультиплексоров вьщеления диагонального элемента 28, уменьшаемых 29, первых сомножителей 30 и вторых сомножителей 31 (фиг.З).

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

0.

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

1002031 10.

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

121.

Кроме того, последовательность чисел по шине 32 также поступает на вход мультиплексора 31 вторых сомножителей, на выходе которого на перне 10 первой константы, в первый умножитель 60. В итоге на первом шаге на шину 37 поступает число

-1

5

С выходов мультиплексоров первых со множителей 30 и вторых сомножителей 31 последовательность чисел поступа ет на входы второго умножителя 34

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

15

20

25

30

35

40

021042021,

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

0-2-10 -4 -2 0-2 -1,

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

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

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

А

вом шаге вычислений (фиг.1) появляет- (фиг.6), разрешающий запись инфор

ся последовательность чисел 021

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

1211755

не 10 первой константы, в первый умножитель 60. В итоге на первом шаге на шину 37 поступает число

-1

5

С выходов мультиплексоров первых сомножителей 30 и вторых сомножителей 31 последовательность чисел поступает на входы второго умножителя 34

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

021042021,

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

0-2-10 -4 -2 0-2 -1,

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

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

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

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

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

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

I

2117558

5записывается последовательность чисел

-2-1510-111 -3, .

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

10 регистра 40 буферного блока 5 поступает сигнал 1 разрешения чтения. Номер четвертого синхроимпульса по ступает также на вход схемы сравнения 49, в результате чего на ее

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

6и, соответственно, на вывод резуль- 20 тата, а также перебросит в нулевое

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

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

/J К

/О

мг.

ФивЛ

.LJL

;

yff

е

.

п

20

1Ь

4

19 П

И 13

Jn

I Ц:

;5

л

/5

Г

Г7

5/А

3

22

21 фиг. 6

(риг.7

J 2 П /75 ZZ

фиг. 8

W

/fX/

V 3

/7

14 75

37

17

фиг. 12

сриг. /J

г 3

/7

УВ

15

(риг. /4

фие. 15

20

/Ч 2

3 4

52

55

I П П П О П П П

ч

ггл-Л гигт

I I I L

бЦ

В ш

62

г

fff

фиг. 17

Фиё. 16

Составитель А.Ушаков Редактор Т.Парфенова Техред Л.Микеш . Корректор

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д.4/5

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