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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 17 9) Г 15/347 ГОСУДАРСТВЕННЫЙ КОМИТЕПО ИЗОБРЕТЕНИЯМ И ОЧНРЫТИЯПРИ ГКНТ СССР ИЗОБРЕТЕНИЯ ПИС ЕЛЬСТВ РАЦИЙ Н Бюл. У 9 С,Г,Седух и Н,А.Лих) 57) Изоб ительной н,дел ьзо тическийчислительхбольших.нт Ф 589, -Р, 1985,сте возможност ункциональных о содержит пер онных входов ный вход 2, си ные блоки 4, в ная цель дости нию в ширение ф Устройств информаци формацион операцион Поставлен даря возм лителя пл вую группу второй ин нхровход 3, свер репри Н ССС ыходы 5 - 7,гается благоения опреде 4 ил. СР поР 15/34 ьствокл. С ожности вычи отной матриц ВТОРСКОМУ С 8 И(56) Седухин С,Г. Сиподход к проектированых структур на базеинтегральных схем, ПНовосибирск, ВИ СО Ас. 40, рис. 12.Авторское свидетел,заявке В 4159878/24,1986. 4) УСТРОЙСТВО ДЛЯТРИЦАИИ етение относится к вычи технике и может быть ис о для операции над матрицаизобретения является рас1464171Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных машинах и устройствах цифро 5вой обработки сигналов для треугольного разложения и вычисления определителя плотной ии матрицы.Цель изобретения - расширение. Функциональных возможностей за счетвычисления определителя плотнойии матрицы.НаФиг. 1 представлена структурная схема устройства для случая п =3; на фиг, 2 - функциональная схема (,1)-го операционного блока первой группы Я 1 = 1, и,= ); нафиг. 3 - функциональная схема (,1)го операционного блока второй группы(х = 2, и, ) = 1, п - 1, х -. , на 20Фиг. 4 - временные диаграм)ы работыустройства.Устройство для случая и = 3 (фиг.1)содержит первую группу информационных входов 1 Ц = 1, и), второй информационный вход 2, синхровход 3,операционные блоки 4 (х,.) = 1,п),группу информационных выходов 5Ц = 1,.и), группу информационныхвыходов 6(з. =- 1, и - 1) и информационный выход 7. Операционный блок(фиг. 2) первой группы (х,= 1,п,) содержит информационные входы 8 и 9, синхровход 10, регистры11 и 12, умножитель 13, делитель 14,триггер 15, элементы И 16 и 17,группу элементов И 18, элемент НЕ 19выходы 20 - 22. Операционный блок(Фиг. 3) второй группы (1 = 2, и,1, и - 1, 1. - , содержит информационные входы 23 и 24 синхровход25, регистры 26-28, умножитель 29,вычитатель 30, триггеры 31 и 32,элементы И 33 и 34, группу элементовИ 35, группу элементов И 36, группу, элементов ИЛИ 37, элемент НЕ 38 ивыходы 39 и 40.В основу работы устройства положен алгоритм разложения плотной и и50матрицы А на нижнюю треугольную и и матрицу В и верхнюю треугольную п п матрицу С с единичной диагональю, т.е. А = ВС. Элементы Ь; и с; определяются по Формулам:Ь;, = а;(о)то алгоритм треугольного разложения(1) на К-м шаге вычислений (К = 1,п)может быть задан в виде следующейсистемы рекурентных соотношений; а, = а , Кс и, 1 к 1к) 1 К а.:= а, /а, К(,1 с и, (к)к) (к 1М 1 к) М1 К К)(2) Кс х, с и,Устройство (при и = 3) работает следующим образом.В исходном состоянии регистры 11, 12 и 26 - 28 триггеры 15, 31 и 32 устройства устанавливаются в нулевое состояние.На нулевом такте на вход 1 поодается элемент а)1, О. При этом в блоке 4 з в регистр 11 записывает(о)ся значение а, = Ьи , которое подается на выход 5 устройства, на выходе умножителя 13 формируется значение Ь,н, так как на первый его вход подается значение Ьц, а на второй вход - постоянно единица.На первом такте элементы а 0 и а, , 1 подаются соответственно на входы 1 и 1 э, При этом в блоке 4 зИ о) Со) формируется значение а, =с =а, /а которое подается на вхоп 24 блока При записи алгоритма (2) элементы матриц В и С определяются,в ходе вычислений так, что Ь; = а при х - ), Ь,; = а( при х 1, с- а прис. 3.Элементы а; и дополнительный разряд 1 или О подаются соответст,венно на ш разрядов и (ш + 1)-й разряд входов 1 в порядке, указанном при,описании работы устройства.4171блока 4 в блоке 4, в регистр 26записывается значение Ъ , котороеподается на вход 8, блока 4,ц, а 3146 4 . В блоке 4 э в регистр 26 записысо)вается элемент а , = Ькоторый подается на вход 8, блока 4, а на вход 8 блока 4 - дополнитель-. ный разряд О,На втором такте элементы а , Офэ 1 ф а 1 и а 1 подаются соответстиф 1 э Фвенно на входы 1, 1 и 1 э . При этом в блоке 4 формируется значение а,. = с, = а, /а,которое подается на вход 24 блока 4 в блоке 1(о) 4 э формируется значение аа - а а = Ь , которое подается на21 12вход 8, блока 4 а на вход 8 блока 4 - дополнительный разряд О, в блоке 4 в регистр 11 записывается значение Ькоторое подается на выход 5в блоке 4 з, в регистр 5.10 15 20 25 40 входу делимого делителя, операционный блок второй группы содержит первый и рого регистров операционного блока45 втоРой гРуппы подключены соответст 50(о) 26 записывается значение аНа третьем такте элементы а , 1э и а , 1 подаются соответственно на входы 1 и 1, а на (и+1)-й вход первой группы входов 1 э " дополнительный разряд 1. При этом в блоке 4 ээ в регистре 11 хранится элементФа , в блоке 4 формируется значе(1) (о) (л) О)ние аэ = аэ - а а 1 экоторое по дается на вход 8 блока 4 , а на вход 8 блока 4- дополнительный разряд 1, в блоке 4, формируется(1) (о)И значение а 2 а2 аэ( а ф 2 Ьэй ф которое подается на вход 23 э блока 4, а на вход 23 блока 4 - до фполнительный разряд О, на выход б подается значение с, в блоке 4 в регистр 11 записывается значение Ь , на выходе умножителя 13 формируется произведение ЬЬ, навыход 5 подается значение Ъ, в блоке 4, в регистр 26 записывается значение ЬНа четвертом такте на вход 1подается элемент а, , 1, а на (в ++ 1)-й вход первых групп входов 1и 1 э - дополнительный разряд 1. При этом в блоке 4 , формируется значеэ((4) (о) Я О) ние аээ = а - аа котороеподается на вход 23, блока 41, а на вход 23 блока 4 д, - дополнительный разряд О, на выход 6 подается значение с, , в блоке 4 форЬ)(1)мируется значение а = а э /а = с, которое подается на вход 24 на вход 8 блока 4 ц, - дополнительный разряд О, в блоке 4( в регистры 11 записывается значение Ькоторое подается на выход 5, .На пятом такте на (ш + 1)-й входпервых групп входов 11 и 1 подается дополнительный разряд 1, вблоке 4, формируется значение аСй)= а - а а . = Ьээ, которое по Ю Юээдается на вход 8, блока 4, а навход 8 блока 4, - дополнительныйразряд О, значение с э подается навь 1 ход 6 в блоке 4 н в регистр 11записывается значение Ь , котороеподается на выход 5На шестом такте на (ш + 1)-й входпервых групп входов 11 и 1 подается дополнительный разряд 1, вблоке 4 и в регистр 11 записываетсязначение Ъ э , которое подается наэхфвыход 5 на выходе умножителя 13формируется значение определителя1 = Ьн ЬЬ , которое подается на выход 7,формула изобретенияУстройство для операций над матрицами, содержащее первую группу (,х)-х операционных блоков (э.- 1,и, где и - размерность матрицы) и вторую группу (,-х операционных блоков (1 ) = 1,и,, причем операционный блок первой группы (1 = 1 и) содержит делитель и первый регистр, выход которого подключен к второй Регистры, умножитель и вычитатель, причем выходы первого и втовенно к первому и второму входам умножителя, выход которого подключен к входу вычитаемого вычитателя, синхровход устройства подключен к синхровходам операционных блоков,первый информационный вход ,1-гооперационного блока подключен к первому выходу (1. + 1, )-го операционного блока (х, ) = 1, и - 1, 1 ),второй информационный вход э., 1 - гооперационного блока подключен к второму выходу (, 1 + 1)-го операционного блока ( = 2, и, ) = 1, и -11), )-й вход первой группы ин 1464171формациОннььх входов устр ойсНа под" ключен з первому ин,оригцс 010.-, входу (и., 1)-го операцсо;.1 огс б 10:а (1 = 1, и), второй выход (.1) -1 о Операционного олока подкл очер: к (1. - 1) -му 11 формацио 111,тку тхот., первой группы устройств,:, (-.:.-2. 1 о т л и ч а и О е е с я т.м.чт- с целью рас:рекИя ук 1",:и с.а:ьнь; ВОЗМОжНОСТЕй За СЧЕТ Вт.тк СЛС 15 т-,т ОП" РЕДЕЛИТЕЛЯ Ппотной 11, П .:тст;,т:нт,т, 1 то"- , РОЙ ИНфОРМЗ.ЦИОННЬСй ЗХОд уСтрОйо тта ПОДКЛЮЧЕН К ВТОРОМУ 1 тфЗРМаГОН,О.тт входу и., и-ГО опера цт 0 ; гоотса ПЕРВЬП 1 ВЫХОД (т т ) - Го 0-К РатгноитОГО блока подкгючен к с-иу .аорматционному вьходу Второй.ту : ь утр 0. ". - .-ва (1. = 1, и), третий агход (1,- го ОПЕрацИОННОГО б 10 хг Пот-КСЮтт- К ТРЕТЬЕЬ ИнфоРМаднонС.;.У -.=ЬХт,ту РОйСтВа., ВтОРОИ ИйОРатттОН;:й Вт;ОД ( 1 1 ) Г 0 ОПЕРа ШО 1 т 0 ЛтОКН 01 тг Ф КЛЮЧЕН К ТРЕТЬЕКСУ 1 Ь:ССЛ,. С. ск 1, 1 + 1)-го оператжсного блока - 1 П - ) В Осот:т:.С;Н;твтй бЛСКРпервой группы внеса.:ы :Орой ре:стр,. УМНОжИТЕЛЬ ТР-Р, Д.а таьЕКТС И группа элекег:ов Ит с:екент 1 ГЕ, ПРИЧЕМ СИНХРО 1 ХО:;, СЕРап 101:,тоГО Х 0- Ка ПЕРВОЙ ГРУППЫ тСтЬСЛт - .Н К СттХРОВХОДУ ТРИГ 1 ЕРа И - .ЕРВЬЬ ХО 1 аМ Пзт-.- БОГО и ВтОрСГО эл зме ц с;,Б И ттьк О, ьКОТОРЫХ ПОДКЛЮтЕтт Соо. П ТСТВЕН.О СИНХРОБХОДН; тС ОВОГО т, Б ГОРОГОГИСТРОБ ИН 4)ОРМадтно"изС.;".СС:.,т К:ОТОрьХ ПОДКПКЧЕНЫ К т, ,: аэ",Я Саьт ГЕ ст 00 инф ормационног 0 в х о,:з ,окаи - разрядность Збраб-. .11 аскьпс д:"1-"ных) (т + 1)-й разря;, .;:Оторого подКЛЮЧЕН К ИНС 1)ОРМаЦИОНС 1 У ВХОДУ ТРИГГЕРа, ВТОРОМУ ВХОЦУ ИСРВат 0 ЭЛЕМЕНта И И тЕВЕЗ ОЛЕЕ 11 . К ВтирОМУвходу Втор 01 о эттеметтс 1 ттт:хо Пто" рого регистра гоцстсч,.:. к 1:ервт"-т вь; ходу блока, входу цели."епя и к шэ вому входу умножитепя, - :-тот с;й вход КОТОРОГО ПОДКЛСЧСН . ГсСРОУ тт.:фоР- маЦионномУ вхоДУ блока т т 1 эт)ыс; ВТОРОИ ВХОтЬ т: тэвхот Ст. -с ",пасига И группы подключены соответственно к вьгходу триггера, К-му разряду выхода делителя и к К-му разряду второго выхода блока, (К = 1, щ), выход утмножителя подключен к третьему выходу блока, в операционный блок второй группы введены третий регистр, два триггера, два элемента И, две группы элементов И, группа элементов .ЯИ и элемент НЕ, причем синхровход операционного блока второй группыподключе н к синхровх оду первого реГистра, синхровходам первого и рого триггеров, первым входам первого и второго элементов И. выходы коТОР-,Х ПОДКЛЮЧЕтЫ СООТВЕТСТВЕННО Ксинхровходам второго и третьего регистров, информационные входы которых поцключены к и разрядам первого информационного входа блока, (ш+1) -й разряд которого подключен к инфор апионному входу второго триггера, второму входу второго элемента И и через элемент ИЕ к второму входу тервого элемента И, выход третьего регистра подключен к входу уменьшаемого вычитстеля, К-й разряд выхода соторого подключен к первому входу К-го элемента И первой группы, второй вход и выход которго подключены соответственно к прямому вь 1 ходу второго триггера и первому входу К-го элемента ИЗП 1 группы выход и второй вход которого подключены со-, ответственно к первому выходу блока и к выходу 1(-го элемента И второй Группь;, первый и второй входы которого подключены соответственно к Кму разряду выхода второго регистра и к инверсному выходу второго триггера, прямой выход которого подклю:ек к информационному входу первого триггера, выход первого регистра подключен к второму выходу блока, второй информационный вход блока подключен к информационному входу первого регистра, выход первого триггера подключен к (ш+1)-.му разряду первого выхода блока.1464171 Составитель М.Силинктор Н.Яцола Техред А, КравчукКорректор А,Обручар Производственно-издательский комбинат "Патент", г, Ужгород, ул. Гагарина,101 Заказ 826/52 Тираж 667 ВНИИПИ Государственного комитета по изоб 113035, Москва, Ж, РаПодписноеениям и открытиям при ГКНТ СССРкая наб.д, 4/5