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

00

оо

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

Цель изобретения - повышение быстродействия.

На фиг. 1 представлена функциональная схема устройства для обращения (пХ) плотных матриц для случая на фиг. 2 - функциональная схема соединения четырех операционных блоков; на фиг. 3 и 4 - временные диаграммы устройства; на фиг. 5 - таблицы, описываюшие логику работы операционных блоков.

Устройство- для содержит информационные входы li,..., l4 группы, операционные блоки (ОБ) 2, ..., 244, выходы 3, .., 34, синхровход 4.

ОБ 2,7() содержит первую группу входов 5, синхровход 6, умножитель 7, узел 8 вычисления обратной величины числа, регистры 9 и 10, триггеры 11 -14, элементы И 15 и 16, группы элементов И 17 и 18, элемент ИЛИ-НЕ 19, группу элементов ИЛИ 20, первую группу выходов 21, вторую группу выходов 22, третью группу выходов 23 (фиг. 2).

ОБ 2ij (,п; j l, п-1; ) содержит синхровход 6, первую группу входов 24, вторую группу входов 25, умножитель 26, сумматор 27, регистры 28-30, триггеры 31-34, элементы И 35 и 36, группу элементов И 37, первую группу выходов 38, вторую группу выходов 39 (фиг. 2).

ОБ 2ij (i, , n; ) содержит сннхровход 6, первую группу входов 40, вторую группу входов 41, умножитель 42, сумматор 43, регистры 44-48, триггеры 49-56, группу элементов И 57, элементы И 58 и 59, первую группу выходов 60, вторую группу выходов 61.

В основу работы устройства обращения (пХп) матрицы А(а;7), положен метод, при котором расширенная (пХ2п) матрица А, Е сводится к (пХ2п) матрице по рекуррентным соотношениям

(О)- ,,

ДЛЯ а, i, j l,n и ,,п

(X) Ск-0 IK-i) . , ,

.

(К) i. I - 1 - 1 I

а,/ аг/-а,, , .

Логика , работы ОБ 2i/() задается табл. 1, ОБ 2,-;(,,n-ij ) - табл. 2, ОБ 2,-/(,n-1; ,) - табл. 3 (фиг. 5).

Устройство работает следующим образом.

В исходном состоянии регистры 9, 10, 28, 29, 30, 44-48 и триггеры 11 - 14, 31-34, 49-56 (фиг. 2) ОБ 2ij(, ,n) устанавливаются в нулевое состояние цепи установки (не показано).

Очередность подачи элементов а)/ матрицы А, где t - номер такта, показана на фиг. 1. Элементы а), подаются на ш входов первой группы входов ОБ. Одновременно с элементами aj/ на т-|-1-й и ш+З-й входы

0

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

На нулевом такте элемент ал и допол- 5 нительные разряды 1 и О подаются соответственно на ш входов, т-|-1-й вход и Ш+2-Й вход первой группы входов li ОБ 2ii. При этом на вход элемента И 16 подается единичный дополнительный разряд, а на его выходе формируется единичный сиг- 0 нал, который разрешает запись элемента an в регистр 10 по заднему фронту тактового импульса. Кроме того, дополнительный единичный разряд устанавливает и триггер 11 в единичное состояние (фиг. 2-4).

5 На первом такте на вход li подаются элемент и дополнительные разряды

0и 1, на вход Ь - элемент a2i и дополнительные разряды 1 и О (фиг. 1). В ОБ 2 i триггер 11 устанавливается в нулевое, состояние, триггеры 12 и 13 - в единичное состояние, в регистр 9 записывается элемент а:9, так как на вход элемента И 15 подается единичный дополнительный разряд и на его выходе формируется единичный сигнал, который разрешает запись элемента в регистр

5 9 по заднему фронту тактового импульса (фиг. 2-4). На входе узла 8 вычисления обратной величины числа формируется значение I/an, которое поступает на вход умножителя 7, на второй вход которого подается элемент . На выходе умножителя 7 форми0 руется значение a i2 ai2/an, которое через открытые элементы И 17, ИЛИ 20 подается на выходы 21-23. В ОБ 22i триггер 31 устанавливается в единичное состояние, на входе элемента И 35 формируется единичный сигнал, с помощью которого по зад5 нему фронту тактового импульса в регистр 29 записывается элемент a2i (фиг. 2-4). На втором такте на вход 11 подаются соответственные элементы и дополнительные разряды О и 1, на вход 12 - элемент 22

д и дополнительные разряды О и 1, на вход 1з - элемент а и дополнительные разряды

1и О (фиг. 1). В ОБ 2п в регистр 9 записывается элемент ais, триггер 13 устанавливается в нулевое состояние, триггер 14 - в единичное состояние. На выходе умножи5 теля формируется значение a i 3 ai3/an. В ОБ 221 в регистр 28 записывается элемент ai2, в регистр 30 - элемент а22, триггер 31 устанавливается в нулевое состояние, триггеры 32 и 33 - в единичное состояние. На входе умножителя 26 формируется зна0 чение а72а2, которое поступает на вход сумматора 27. На второй вход сумматора 27 через-открытые элементы И 37 подается элемент 822. На выходе сумматора 27 формируется значение а22 а22-aV2 a2i. В ОБ 2i2 в

5

регистр 44 записывается а:2, триггер 49 устанавливается в единичное состояние (фиг. 2-4).

На третьем такте на вход 11 подаются элемент а 4 и дополнительные разряды О и 1,

на вход Ь - элемент а|з и дополнительные разряды О и 1, на вход Ь - элемент аза и дополнительные разряды О и 1, на вход U - элемент а и дополнительные разряды 1 и О (фиг. 1). В ОБ 2|1 в регистр 9 записывается аи, на выходе умножителя формируется значение ам ам/а1|, которое через элементы И 17 и ИЛИ 20 подается на вь1ходы 21-23. В ОБ 22i в регистр 28 записывается a i3, в регистр 30 - а2з, на выходе умножителя 27 формируется значение 323 323-aiaaai, которое поступает на выход 38. В ОБ 2|2 в регистр 44 записывается а%, в регистр 45 - a li триггер 49 устанавливается в нулевое состояние, триггеры 53 и 50 - в единичное состояние. В ОБ 222 в регистр 10 записывается a lJ, триггер 11 устанавливается в единичное состояние (фиг. 2-4).

На четвертом такте на вход подаются произвольное т-разрядное число (признак) и дополнительные разряды О и О, на вход 2 - элемент а24 и дополнительные разряды О и 1, на вход 1з - элемент а|з и дополнительные разряды О и 1, -на вход 14 - элемент и дополнительные разряды О и 1 (фиг. 1).

В ОБ 2ii триггер 12 устанавливается в нулевое состояние, при этом на выходе элемента ИЛИ-НЕ 19 формируется единичный сигнал, который открывает группу из элементов И 18 и через элементы ИЛИ 20 значение l/aii поступает на входы 21-23. В ОБ 221 в регистр 28 записывается а , в регистр 30 - а24. На выходе сумматора

27формируется значение а2 4 а24 а иа21, которое поступает на вход 38. В ОБ 2i2 в регистр 44 записывается а и, в регистр 45 - a i3, в регистр 46 - aVL триггер 50 устанавливается в нулевое состояние, триггеры 51 и 54 - в единичное состояние. В ОБ 222 в регистр 9 записывается афз, триггер 11 устанавливается в нулевое состояние, триггеры 12 и 13 - в единичное состояние. На выходе умножителя 7 формируется значение а21/а22, которое поступает на выходы 21 - 23 (фиг. 2-4).

На пятом такте на вход Ь может подаваться элемент а новой матрицы А или нулевое значение с дополнительными разрядами 1 и О, на вход 2 - признак и дополнительный разряды О и О, на вход 1з - аз4 и дополнительные разряды О и 1, на вход U-а4з и дополнительные разряды О и 1 (фиг. 1). В ОБ 2ii в регистр 10 записывается элемент а° новой матрицы или нулевое значение, триггер 11 устанавливается в единичное состояние. В ОБ 221 в регистр

28записывается Ь „, триггер 33 устанавливается в нулевое состояние, на выходе сумматора 27 формируется значение b 2i -a2i/aii в ОБ 2i2 в регистр 44 записывается Ьл, в регистр 45 - aVi, в регистр 46 -

,0)

сг)

(1-1. ,{11J

ai2, в регистр 47 - аИ, в регистр 48 - а2з, триггер 51 устанавливается в нулевое состояние, триггеры 55 и 52 - в единичное состояние, на выходе сумматора 43 формируется а з а| з-а 2а2з. В ОБ 222 в регистр 9 записывается элемент а2 4, триггер - 13 устанавливается в нулевое состояние, а триггер 14 - в единичное состояние, на выходе умножителя 7 и соответственно элементов ИЛИ 20 формируется (фиг. 2-4). На последующих тактах работы в ОБ 2„ формируются значения элементов обратной матрицы аналогично согласно табл. I-3 (фиг. 5). Первый элемент обратной матрицы формируется на выходе ОБ 2|4 на такте с номером 10, а последний элемент bu - в ОБ 2|4 на такте с номером 16

(фиг. 1). Полученные элементы образуют обратную матрицу вида

А

b I 2 b I 3 b23

Ьзз Ьз.

J43

Таким образом,в предлагаемом устройстве для выполнения обращения (пХп) плотной матрицы требуется п операционных 25 блоков и (5п-4) тактов работы.

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

. Устройство для обращения плотных (пХп) матриц, содержащее п операцион30 ных блоков, отличающееся тем, что, с целью повыщения быстродействия, i-й информационный вход устройства соединен с первой группой входов ij-ro операционного блока (, п), первая группа выходов ij-ro опе- рационного блока (, п, , п-1)

35 соединена с первой группой входов i (j- + 1)-го операционного блока, вторая группа выходов ij-ro операционного блока (i,j l, п-1, ) соединена с второй группой входов (i+l)j-ro операционного блока,

.,. третья группа выходов ij-ro операционного блока (i,,n, ) соединена с второй группой входов (i-1, j)-ro операционного блока, вторая группа выходов ij-ro onepa- ционного блoкa(, ,n - 1, ,n) соединена с второй группой входов (i-l,j)-ro

45 операционного блока, первая группа выхо- дов (i,n-ro операционного блока (,п) соединена с i-м выходом устройства, управляющий вход которого соединен с синхровхо- дами Ij-x операционных блоков i,,n). 2. Устройство по п. 1, отличающееся

50 тем, что ij-й операционный блок (i,,n, ) содержит умножитель, узел вычисления обратной величины числа, два регистра, четыре триггера, две группы элементов И, два элемента И, группу элементов ИЛИ, элемент ИЛИ-НЕ, причем m входов первой

группы операционного блока соединены с информационными входами первого и второго регистров, где m - разрядность элементов матрицы, ()-й вход первой группы one

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

3. Устройство по п. 1, отличающееся тем, что, ii-й операционный блок (,n, 1, п-1, ) содержит умножитель, сумматор, три регистра, четыре триггера, два элемента И, и группу элементов И, при- чем m входов первой группы операционного блока соединены с информационными входами второго и третьего регистров, (m-f 1)-й вход первой группы операционного блока соединен с первым входом первого элемента И и с информационным вхо- дом первого триггера, в ()-й вход первой группы операционного блока соединен с первым входом второго элемента И и с информационным входом третьего триггера, вторая группа входов операционного блока соединена с информационным входом пер- вого регистра, выходы которого соединены с второй группой выходов операционного блока и с первым входом умножителя, второй вход которого соединен с выходом второго регистра, а выход - с первым входом сумматора, второй вход которого соединен с выходом элементов И группы, выход сумматора подключен к т-выходам

0

0

5

5

О 5

0

5

5

первой группы операционного блока, выходы первого и второго элементов И сЬединены с входами разрешения записи соответственно второго и третьего регистров, выход третьего регистра соединен с первыми входами элементов И группы, вторые входы которых соединены с выходом третьего триггера и с информационным входом четвертого триггера, выход четвертого триггера подключен к (ш4-2)-му выходу первой группы операционного блока, (т-|-1)-й выхрд которого соединен с выходом второго триггера, информационный вход которого соединен с вьгходом первого триггера, синхровход операционного блока соединен с входом разрешения записи первого регистра, вторым входом первого и второго элементов И и с синхровходами первого, второго, третьего и четвертого триггеров. (

4. Устройство по п. 1, отличающееся тем, что ij-й операционный блок (, п-1, , п, ) содержит умножитель, сумматор, пять регистров, восемь триггеров, два элемента И и группу элементов И, причем m входов первой группы операционного блока соединены с информационным входом первого регистра, выход которого соединен с информационным входом второго perHctpa, выход которого соединен с информационными входами третьего и четвертого регистров, выходы которых соединены соответственно с первым входом умножителя и с первыми входами элементов И группы, (т4-1) -и вход первой группы операционного блока соединен с информационным входом первого триггера, выход которого соединен с информационным входом второго триггера, выход которого соединен с первым входом первого элемента И и с информационным входом третьего триггера, выход которого соединен с информационным входом четвертого триггера, выход которого подключен к (m-f-l)-My выходу первой группы операционного блока, (т+2)-й вход первой группы которого соединен с информационным входом пятого триггера, выход которого соединен с информационным входом шестого триггера, выход которого соединен с первым входом второго элемента И и с информационным входом седьмого триггера, выход которого соединен с вторыми входами элементов И группы и с информационным входом восьмого триггера, выход которого подключен к (т-|-2)-му выходу первой группы операционного блока, вторая группа входов которого соединена с информационным вх одом пятого регистра, выход которого соединен с второй группой выходов операционного блока и с вторым входом умножителя, выход которого соединен с первым входом сумматора, второй вход которого соединен с выходами элементов И группы, выход сумматора подключен к m выходам .первой группы операционного блока, синхровход которого соединен с вторыми входами первого и второго элемента И и с вхо-пятого регистров, с синхровходами с пердами разрешения записи первого, второго ивого по восьмой триггеров.

Изобретение относится к области вычислительной техники и может быть использовано в специализированных вычислительных машинах и устройствах обработки данных. Целью изобретения является повышение быстродействия. Устройство содержит п операционных блоков (ОБ). РК-й ОБ () содержит умножитель, сумматор, три регистра, четыре триггера, два элемента И и группу элементов И. РК-й ОБ () содержит умножитель, узел вычисления обратной величины, два регистра, четыре триггера, два элемента И, две группы элементов И, элемент ИЛИ-НЕ, группу элементов ИЛИ. РК-й ОБ () содержит умножитель, сумматор, пять регистров, восемь триггеров, группу элементов И, два элемента И. Поставленная цель достигается за счет алгоритмических и структурных решений, реализованных в устройстве. 3 з.п. ф-лы, 5 ил. с (О (Л

а/ ;з й

22

6 5Ч32

.,2„а а

л

7 6 5 ч 3

« « V

и

П /5 5 .;;, „; )// f3 °

16 J5 gtf fiS ef.

if 62 °22

2ц,

15 /« /3 .„ 3- зг

. «S с ;

Таблица. /

Таблица 2

Таблица д