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

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

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

На фиг. 1 представлена crpyKiyp- HIR схема устройства для случая п 3; на фиг. 2 - функциональная схема (i,j)-ro операционного блока (i,j 2,n, i ); на фиг. 3 - функциональная схема (i,i)-ro операци

очного блока (,n, ,n-l, i j ) i на фиг. 4 - функциональная схема (1,1)-го оперчпнонного. блока ; на фиг. 5 - Лункииокчльная схема элемента задер-кки. н;, фиг. 6 и 7 т временные диаграммы работы устройства.

Устройство соцержит первую группу информационных входов 1: (1,п), второй информационный вход 2, син- хровход 3, операционные блоки 4;: (i,j ,n,i i). элгменты 5; задержки (1 1 , . группу - фопмационных вы

и г т oiirt

инфо;

(i 1.п-1)

И 3 Ч ;

г- ф- рОЛГ Ч i., Г.. HL

; м.ки ; 1( - ИГ - Г , .li.

;., 9 и 10, rs -у. 1ьхогц и 3 , умни) ень J ,

г р 16, - леленты метг. ов И 14, -ЧПР- 21-23.

Опер 1ци( нчъ и Гпок второй т руппы ( j-Г.р-;; i j ) содержит (фиг.З) тонные входы и 25, синхровхо) /. 6, регистры 27-29, умножитель 30, i ы гтателъ 31 , тргп - геры 32 и 33, зл -менты И 34 и 35, первую rpyiiiv злемент-ов И 36, вторую группу 3:ie гон И 37, группу элементов ИЛИ 38, x4-vp {f HE 39, вьп-сс-дь- 40 и 41,

Операционный лок(1,1) содержит (фиг.4) информационные входы 42 и 43, синхрон ол регистр 45, умножитель 46, вЬ).-:оды 47 и 48.

Элемент задерч-к-т (фиг,5) содержит вход 49, сткфивкод 50, регис ы 51 и 52, выход 53 ,

В ОСНОВУ .-. О,.ты устрепсгва положен алгоритм p.i }.,- | мч плотной ()матрицы А на нижнюю треугольную (nin)- матрицу В и верхнюю треугольную (п« п)-матрицу С с единичной диагональю, т.е. А ВС. Элементы Ъ;: и с;- определяются по формулам

(I)

При этом определитель del (Л) - Ъ1( Ъ22 , ,ЪП„ Если а , а;; для

Ч

1 fci, ,1 -п, то .алгоритм треугольного разложения (1) нч V-м шаге гычис- Лекий flv - ,п) м. -ч- г зада) в виде следующей системы рок рр итных

соотношении

25

(2)

ри -апнси я матриц I1 С тг, ,

j -, . ;J ,. j

ритма

(2)

эпеменходе

-феделяют ™1 в .ю Ь- а ; ,0 .при .: i-ь г; . чрп

0

5

0

5

Opi, ппиглмии лботы устройства в оС.о-чня тни - а в скобках указывается HOMOI 1-го рекуррентного птага, а в обозначении а1 - номер i указывает такт работы устройства.

Потоки данных на входах и выходах устройства показаны на фиг. 1, временные работы устройства - на фиг.6 и 7.

Эг.сменты а и дополнительный раз- рйд 0 или 1 подаются одновременно соответственно на m разрядов и (т-И)-и разряд входов первой группы в последовательности, указанной при описании работы устройства.

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

В исходном состоянии регистры 12, )3, 27, 28, 29, 51 и 52 и триггеры 16, 32 и 33 устройства устанавливаются в нулевое состояние (фиг.6 и 7)

Работу устройства рассмотрим для треугольного разложения и вычисления определителя одной матрицы ()

На нулевом такте на вход ъ подается элемент а.

0. При этом в блоке

4,,в регистр 12 записывается значе3}

,° ние а „ Ъи , которое подается на выход 6 устройства, на выходе умножителя 14 формируется значение Ъ , так как на первый его вход подается значение Ь„ , а на второй вход - постоянно единица.

На первом такте элементы а2 , О и а. Л , 1 подаются соответственно на

На четвертом такте на вход 1, подается элемент , 1,1, на вход 14 - нулевое значение и дополнительный разряд 0. При этом в блоке 4, формиг г-ж/.. f v It

(О

af° О)

Ч

входы 14 и Ц. При этом в блоке 4 формируется значение а, г с, , которое подается на вход 25 бло10

руется значение а 1} а - , которое подается на вход 24(блока 421) а на вход 24г блока 4, - дополнительный разряд 0, на выход 62 подается значение С (1 , в блоке 4г7 формируется значение а

m

а(Л /al l которое

23

подается на вход 25 блока 42f , в блоке 4г1 в регистр 27 записывается значение Ьаг, которое подается на вход

писывается элемент а, Ъ2, , который 15 42 блока 4 41 } в блоке 4М в регистр подается на вход 9 блока 42г, а на : 45 записывается значение Ь„ , кото- вход 92гблока - дополнительный разряд 0, значение Ъ( с выхода 23

ка 4 }г , в блоке 4эг в регистр 27 зарое подается на выход 6t

На пятом такте на вход 1, подаются нулевое значение и дополнитель- 9П ный разряд 0, в блоке 4f) формируется значение аЩ - а , - - Ь„, которое подается на вход 42 блока 4- значение с4, подается на выход l , в блоке 414 в регистр 45 записывает- 25 ся значение b5i, которое подается на выход 6 .

На шестом такте в блоке 4М в реформируется значение al/z - a JaVi гистр 45 записывается значение b,j,

блока подается на элемент 52 задержки.

На втором такте элементы э,( , 0; а|2, 1 и а,3 , 1 подаются соответственно на входы l,, и j- Ри этом в блоке 4, формируется значение со , которое подается на вход 25 блока 4 , в блоке

,«) „(°1 „f« J .

чение определителя det(A) Ь3э, которое подается на выход 8.

которое подается на вход 9, блока 444; которое подается на выход 6,, на выа на вход 9гблока 42i - дополнитель- зо х°Де умножителя 46 формируется знаный разряд 0, в блоке i4 в регистр

12 записывается значение Ъ4) , которое

подается на выход 6г, в блоке 4,в

Аналогичным образом устройство „,. работает в поточном режиме. Состояние триггеров и регистров устройства в поточном режиме показаны на временных диаграммах работы устройства (фиг.6 и 7).

регистр 27 записывается значение

3

а(0 - Ъ 331 ЬЯ

На третьем такте элементы а

32

1

и а

2

1 подаются соответственно на

40

входы 1 , и 12 , а на вход Ц - нулевое значение и дополнительный разряд 0. При этом в блоке 433в регистр 12 записывается нулевое значение, в

блоке 4,, формируется а,, а °,(0 (02 «

-а2( av,3 , которое подается на вход 9(

блока 42г, а на вход 92 блока 42iдополнительный разряд 1. в блоке 4 т Af- (i,i)-x операционных блоков, (1,1)

f i С° (О о) ч )„ У .

,- аэ,а14 операционный блок, ( ,п,п-размерФормула изобретения

Устройство для операций над матрицами, содержащее первую группу

SZ

формируется значение а Ъзг , которое подается на вход 244 блока .42) , а на вход 2А блока 4j - дополнительный разряд 0, на выход подается значение С сг , в блоке 4 «г в регистр 12 записывается значение Ь22, которое подается на вход умножителя 14, с выхода элемента 52 задержки значение подается на второй вход умножителя 14, на выходе умножителя 14 формируется произведение Ь,, Ьг2 на выход 6 2 подается значение Ь2г, в блоке регистр 27 записывается значение Ь3 ность матрицы), вторую группу (i,j)-x операционных блоков ( ,n, iz. j ) причем синхровход устройства подклю„ чен к синхровходам всех операционных блоков, первый информационный вход (1 j)rc операцио того блока подключен к первому выходу (д +1, операционного блока, t(i,,n-l,,

се n-размерность матрицы), второй TIH- формационный вход (i,j)-ro операционного блока подключен к второму выходу (i,j + 1)-го операционного блока, (,,n-l,i j) j-й инфорНа четвертом такте на вход 1, подается элемент , 1,1, на вход 14 - нулевое значение и дополнительный разряд 0. При этом в блоке 4, формиг г-ж/.. f v It

(О

af° О)

руется значение а 1} а - , которое подается на вход 24(блока 421) а на вход 24г блока 4, - дополнительный разряд 0, на выход 62 подается значение С (1 , в блоке 4г7 формируется значение а

m

а(Л /al l которое

23

чение определителя det(A) Ь3э, которое подается на выход 8.

х°Де умножителя 46 формируется зна40

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

Устройство для операций над матрицами, содержащее первую группу

операционный блок, ( ,п,п-размерность матрицы), вторую группу (i,j)-x операционных блоков ( ,n, iz. j ) причем синхровход устройства подключен к синхровходам всех операционных блоков, первый информационный вход (1 j)rc операцио того блока подключен к первому выходу (д +1, операционного блока, t(i,,n-l,,

n-размерность матрицы), второй TIH- формационный вход (i,j)-ro операционного блока подключен к второму выходу (i,j + 1)-го операционного блока, (,,n-l,i j) j-й информационный вход первой группы устройства подключен к первому информационному входу (n,j)-го операционного блока (j«l,n), второй информационный вход устройства подключен к второму информационному входу (п,п)- го операционного блока, первый выход (i,i)-операционного блока подключен к i-му выходу первой группы устройства,(,п), второй выход (i, 1)-го операционного блока подключен к (1-1)-му выходу второй группы устройства, (,п), третий выход (1,1) го операционного блока подключен к третьему выходу устройства, отличающееся тем, что, с целью пвышения быстродействия при обработке массива матриц, в него введены (п-1) элементов задержки, причем (1,1)-й

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

Изобретение относится к области вычислительной техники и может быть использовано для операций над матрицами. Целью изобретения является повышение быстродействия при операциях с массивами матриц. Устройство содержит первую группу информационных входов 1, второй информационный вход 2, синхровход 3, операционные блоки 4, элементы задержки 5, группы 6, 7 информационных выходов, информационный выход 8. Цель достигается введением новых элементов и связей. 6 ил.

б

Л

Щ

omcsi

I

о