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

 

Изобретение относится к вычислительной технике и может быть использовано для операций над матрицами . Целью изобретения является расширение функциональных возможностей. Устройство содержит первую группу информационных входов 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

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

 

Похожие патенты:

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

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

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

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

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

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

Изобретение относится к автоматике и вычислительной технике

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

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

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

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

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

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

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

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