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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК цу 4 G 06 Г 15/347

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К A ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

flO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4284951/24-24 (22) 17.07.87 (46) 07.03.89. Бюл. N - 9 (72) В.П. Якуш, С.Г.Седухин, П.И.Соболевский и Н.А.Лиходел (53) 681.32(088.8) (56) Седухин С.Г. Систематический подход к проектированию вычислительных структур на базе сверхбольших. интегральных схем. Препринт Ф 589.—

Новосибирск. ВИ СО АН СССР, 1985, с. 40, рис. 12.

Авторское свидетельство СССР по ,заявке Ф 4159878/24,кл. G 06 F 15/347

1986.

„„Я0„„1464171 А 1 (54) УСТРОЙСТВО ДЛЯ ОПЕРАЦИЙ НАД

МАТРИЦАМИ (57) Изобретение относится к вычислительной технике и может быть использовано для операций над матрицами. Целью изобретения является расширение функциональных воэможностей.

Устройство содержит первую группу информационных входов t второй информационный вход 2, синхровход 3, операционные блоки 4, выходы 5 — 7.

Поставленная цель достигается благодаря возможности вычисления определителя плотной матрицы. 4 ил.

1464171 п В 1 ) 1, == а, /b«, 1

=- — (a"

Ь„ 3

Ъ;,с,), к= !

1 (:(«- 3 с (2) Кс, j(n.

Ь;, = а;,, )-1

Ь = а; — Pb;„c), 3 к <

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

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

; вычисления определителя плотной и « и матрицы.

На фиг. 1 представлена структурная схема устройства для случая и =

3; на фиг. 2 — функциональная схе- 15 ма (i,))-ro операционного блока первой группы (i,j = 1, n, i = j); на фиг. 3 — функциональная схема (i,j}ro операционного блока второй группы (i 2, n, j = 1, п — 1, i " j) на 20 фиг. 4 — временные диаграмьы работы устройства.

Устройство для случая и = 3 (фиг.1) содержит первую группу информационных входов 1 (j = 1, n), второй ин- 25 формационный вход 2, синхровход 3, операционные блоки 4 (i,j = 1,n), группу информационных выходов 5 (j = 1, n) группу информационных выходов 6 ° (i =- 1, n — 1) и инфор- 30 мационный выход 7. Операционный блок (фиг. 2) первой группы (i, j = 1,п, j) содержит информационные входы 8 и 9, синхровход 10, регистры

11 и 12, умножитель 13, делитель 14, триггер 15, элементы И 16 и 17, группу элементов И 18, элемент НЕ 19 выходы 20 — 22. Операционный блок (фиг. 3} второй группы (= 2, и, ) 1, n — 1, i - j) содержит инфор- 40 мационные входы 23 и 24,, синхровход

25, регистры 26-28, умножитель 29, вычитатель 30, триггеры 31 и 32, элементы И 33 и 34, группу элементов

И 35, группу элементов И 36, группу, элементов ИЛИ 37, элемент НЕ 38 и выходы 39 и 40.

В основу работы устройства положен алгоритм разложения плотной и и матрицы А на нижнюю треугольную п и

50 матрицу В и верхнюю треугольную п ° п матрицу С с единичной диагональю, т.е. А = ВС. Элементы Ь; и с; определяются по формулам:

При этом определитель A/

Ь„. „, ° ° °, Ь„„°

Если а; = а, для 1с i,j (n, ()

° ) то алгоритм треугольного разложения (1) на К-м шаге вычислений (К = 1,п) может быть задан в виде следующей системы рекурентных соотношений: а. =а;, K(i+n, (к) (к-<)

sk, а„.:=а . /а, Кс )сп, (к) (к- ) (к) к) М () «к) При записи алгоритма (2) элементы матриц В и С определяются .в ходе вычислений так, что Ь; =- а(при х - j, Ь;; = a ; ïðè х j, с

= а",, при i (3

Элементы а; и дополнительный разряд 1 или О подаются соответст,венно íà m разрядов и (m. + 1)-й разряд входов 1 в порядке, указанном при,описании работы устройства.Устройство (при и = 3) работает следующим образом.

В исходном состоянии регистры 11, 12 и 26 — 28 триггеры 15, 31 и 32 устройства устанавливаются в нулевое состояние.

На нулевом такте на вход 1 поо дается элемент a„, О. При этом в блоке 4 «в регистр 11 записывается значение a,„- =Ь, которое по(о) дается на выход 5> устройства, на выходе умножителя 13 формируется значение b> так как на первый его вход подается значение b « а на второй вход - постоянно единица.

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

1 входы 1 и 1 . При этом в блоке 4 з формируется значение а, =с„=а, /a, которое подается на вхоп 24 блока

4171

4 блока 4,, в блоке 4, в регистр 26 записывается значение Ъ, которое подается на вход 8, блока 4«а

40 входу делимого делителя, операционный блок второй группы содержит первый и рого регистров операционного блока

45 втоРой гРуппы подключены соответст50

146

4 . В блоке 43 в регистр 26 записы(о) вается элемент а, = b,, который подается на вход 8, блока 4, а на вход 8 блока 4 — дополнительный разряд О. а

На втором такте элементы а, О, 3» а 1 и а 1 подаются соответстgg У »3 э венно на входы 1<, 1 и 13. При этом в блоке 4 формируется значение а,. = с, = а, /а „, которое подается на вход 24 блока 4 в блоке

l (»» (о)

4 формируется значение а а — а(1 а = Ь,которое подается на Z1 1Z вход 8, блока 4,, а на вход 8 блока 4 — дополнительный разряд

О, в блоке 4 в регистр 11 записывается значение b которое подается на выход 5 в блоке 4 3, в регистр (о}

26 записывается значение а, = Ь

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

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

3 входы 1» и 1, а на (m+1)-й вход первой группы входов 1 " дополнительный разряд 1. При этом в блоке

4 3 в регистре 11 хранится элемент (о! а „, в блоке 4 формируется значеИ (o) (> () ние 23 3 2, q3 j KOTopoe no дается на вход 8 блока 4, а на вход 8 блока 4 - дополнительный разряд 1, в блоке 4, формируется (1) (о} (<) И значение а 3 а, а3(а gg =Ь3 g которое подается на вход 23 3 блока

4, а на вход 23 блока 4 — доем полнительный разряд О, на выход 6 подается значение с„, в блоке 4 < в регистр 11 записывается значение

Ь, на выходе умножителя 13 формируется произведение Ь „ Ь, на выход 5 подается значение Ъ, в блоке 4, в регистр 26 записывается значение b >

На четвертом такте на вход 1» подается элемент а,, 1, а на (m +

+ })-й вход первых групп входов 1 и 13 — дополнительный разряд 1. При этом в блоке 4 . формируется значе3( (s} (o} (»} (q) а» a,3 котор подается на вход 23, блока 4,, а на вход 23 блока 4z, — дополнительный. разряд О, на выход 6 подается значение с,, в блоке 4 форЬ} (»} (»} мируется значение а = а /а

= с, которое подается на вход 24

5. !

О

25 на вход 8 блока 4« — дополнительный разряд О, в блоке 4<» в регистры 11 записывается значение Ь которое подается на выход 5, .

На пятом такте Hà (m + 1)-й вход первых групп входов 1,, 1 и 1 подается дополнительный разряд 1, в блоке 4, формируется значение а (z}

= а — а а . = Ь3„, которое по(<} (2} (М

З3 дается на вход 8, блока 4„, а на вход 8 блока 4, — дополнительньгй разряд О, значение с 1 подается на вь1ход 6,, в блоке 4«в регистр 1! записывается значение Ь, которое подается на выход 5,, На шестом такте на (m + 1)-й вход первых групп входов 1,,1 и 1 подается дополнительный разряд 1, в блоке 4 « в регистр 11 записывается значение Ъ 3, которое подается на

3Ь выход 5,, на выходе умножителя 13 формируется значение определителя

1»А(= Ъ„° b ... Ь„„, которое подается на выход 7.

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

Устройство для операций над матрицами, содержащее первую группу (i,i)-x операционных блоков (i — 1,и где п — размерность матрицы) и вторую группу (i,})-х операционных блоков (i j = 1,n, i j), причем операционный блок первой группы (i = 1,n) содержит делитель и первый регистр, выход которого подключен к второй Регистры, умножитель и вычитатель, причем выходы первого и втовенно к первому и второму входам умножителя, выход которого подключен к входу вычитаемого вычитателя, синхровход устройства подключен к синхровходам операционных блоков, первый информационный вход i, j-го операционного блока подключен к первому выходу (i + 1, j)-ro операционного блока (i, j = 1, и — 1, i» j), второй информационный вход i, j — го операционного блока подключен к второму выходу (i, j + 1)-го операционного блока (i = 2, n, j = 1, и—

i j) j-й вход первой группы ин1464171 формационных Входов у „>Ойс - . Н<здключен в первому инфорксциа>шо1.-.. входу (!1 J,)-г0 Опера1Д.;<21:попо б210ка (1 = 1 П} ВТОРОЙ выхг>>! (3. „1> "го

ОПЕРаЦИОННОГО ОЛОКа ПО><К,>110!а>1 К (1. 1) му ипфОрма! IEIOIIII. >к у в>:1хо>1>г первой группы устройств;-,,: (:.-2.,1, -, О т л и ч а ю >31 е е с SI тем <ч! .„

С ЦЕЛ ЬЮ P! IC11EIP е EIÈß «ГУ1-::. :",: < И 01.:1J . ЬНЬ<Х

ВОЗМОЖНОСТЕ11 BG СЧЕТ Вь>-11< С "113E}E;ll < П-" ределителя плотной и .;:.. -::а-! —.>- щь, г>то", poH инфОрма.ционг!ь>я вх Оп cT,> Ой "ва подключен к второму 1<13471:ма-!ион:::î><у

ВХОДУ 11. П- Г <3 ОTIPР= 1 1!1 ма>ц..<2Н( нОму вь>хОду втOp01! Г>у il!:,j "!< т)>0:lc . - ва (i = 1, n), тре-1 —.й в::к0,1, (i, I}--го операционного блî.::-., Гьо-,, ц<12-1сп к третьеь< ннформациоij "10»> =11х12,"ту >гс-.-ройства. второй Ejl;.фор1-а1!1>oн::.;:.:- в;Од (3. Х)-ГО ОПЕРЯГИО11нг Го .=„ЛО-Ка 1<-0,;г . ключен к третьему иь1х !Ijv < < + 1..

1 + 1)-го опера!и<>нного блока — n — 1 } I> Ог<сго=!-;>И,си<3.:->й бл,1;

> первой Гругпы в!3е,,1е .Ь1 .=-Орой рег:<с тр, умножитель тригг<--,;;, д -;- л<>к>акта

И группа элемен:.<3В И,, " <е! <ент Hå..

При 1ЕМ СИН>крОВХОД СПЕВЯ1П:Oj:РОГ< <>J 0-ка пер>3ой группы:1сд: лк -.—..н к с:-ахровходу триг1 epjI El -е>рвь> 1!опек пе1>=Bol О и ВторсГО элам<=<11 . в И„выл,., ы которых годкл>з<<ены сос. в ..Тствеи -0 синхровходам 11. Оного к втopC 0 <---гистров, информа >-10:;;ные в>10>ць1 ":OTOPbIK ПОДКПК>ЧЕНЫ X >>. Р 8=, >>1 г1аь> П< (> г< 01 О информационного <3x0(. Ока (тп — разрядность эбраб-. -. ы13аек::ь>-.-,- Дан-ных) (m + 1) -й разряд .;.;>торогс> п<эд= ключен к информацио>!ному входу триггера, второму вхоцу и",рва> 0 элемента И и через эл::еме>к liJ - к;-.; 1>рому

ВХОДУ ВТОР 01 0 Э>1 ЕМЕ. <Т11 1, В> Х \7! Вт 0"" рого регистра гоцкл>с.-:.:. к 1:01>в<>"..->- Вы ходу блока, входу ц- 2111 >епя и к ш37 вому входу умножите1<я, —:-T01 сll вход которого подкл.<.чен : >г>сро>му >:-..:,1<>ор-мационному 13ходу блока, первый., втОрОй Вхог<ы т. >В!<хо>-, < - -c> ".пекся га,г с:нхровходам второго и третьего регистров, информационные входы которых поцключены к п> разрядам первого .- Нформационного входа блока, (ш+1) -й разряд которого подключен к информапионному входу вторсго триггера, второму Входу второго элемента И и через элемент HE к второму входу

1ервого элемента И, выход третьего регистра подключен к входу уменьшаекого вы- :итателя, К-й разряд выхода

1;.оторог0 подключен к первому входу

К-го элемента И первой группы, второй вход и выход котор >го подключены соответственно к прямому выходу второго триггера и первому входу

К-го элемента ИЗБ группы> выход и второй вход которого подключены со-, ответственно к первому выходу блока и к HblxOJ3ó К-го элемента И второй группь;, первый и второй Входы которого подключены соответственно к К— му разряду выхода второго регистра и к инверсному выходу второго триггера, прямой выход которого подклю-=ен к информационному входу первого триггера, выход первого регистра подключен к второму выходу блока, B-T0p0EI информационный вход блока подключен к информационному входу перВого регистра, выход первого триггера подключен к (m+1)--му разряду первогo выхода блока.

И Г!7у1>пы пОДключены сООTBPTcTBeHHo к BblxOJ3у триггера, К-му разряду выхода делителя и к К-му разряду второго выхода блока, (К = 1, m), выход

<> умножит<зля подключен к третьему выходу блока, в операционный блок Второй группы введены третий регистр, Два триггера, два элемента И, две группы элементов И, группа элементов

ИХИ и элемент НЕ, причем синхровход

Операционного блока второй группы подключен к cHíõðовходу первого регистра . си нхр ОВХ Одам первоГО и Второг 0 триггеров, первым входам первого и в срого элементов И. выходы кото!р1-,1х подключе13ы соответственно к

1464171

1464171

Составитель М.Силин

Техред А. Кравчук Корректор А.Обручар

Редактор Н. Яцола

Заказ 826/52 Тираж 667 Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина,101