Устройство для решения систем линейных алгебраических уравнений

Устройство для решения систем линейных алгебраических уравнений

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике, предназначено для решения систем линейных алгебраических уравнений и может быть использовано при построении специализированных устройств, функционирующих в реальном масштабе времени. Целью изобретения является увеличение быстродействия. Цель достигается тем, что устройство содержит матрицу размером N <SP POS="POST">.</SP> (N + 1) операционных блоков 1, где N - порядок решаемой системы линейных алгебраических уравнений. 6 ил.

СООЭ СОВЕТСКИХ

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

РЕСПУ6ЛИН (Я)5 G 06 Р 15/32

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

Н А ВТ0РСНОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗО6РЕТЕНИЯМ И (ЛНРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4488133/24-24 .(22) 28,09.88 ;(46) 07,06,90, Бюл. М 21 (72) А.П.Царев, И.И.Чебак и А..Г.Шенешеуцкий (53) 681.325 (088.8) (56) Авторское свидетельство СССР

У 940167, кл. G 06 F 15/32, 1979.

Авторское свидетельство СССР

06 5 32 1986.

Р 1394218, кл. G F 1 / (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ CHCTEN

ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

„.SU,» 5 9 46 А1

2 (57) Изобретение относится к вычисли- тельной технике, предназначено для решения систем линейных алгебранческих уравнений и может быть исполь но при построении специализирован.;ь х устройств, функционирующих в реально:масштабе времени, Целью изобретения является увеличение быстродействия, Цель достигается тем, что устройство содержит матрицу размером N>(N+1) операционных блоков 1, где N — порядок решаемой системы линейных алгебраических уравнений. 6 ил.

1569846 (; fn-»

< ) (м- i1

1,( (и-<3

С, (n- 1

g,)+ (n- ь

С,, i.-1,N-1,j — 1,N+i-п(о) с;

).=Ns j=1 sN+1-п, Изобретение относится к вычислительной технике и может быть испольэовано при построении специализированных вычислительных систем функциs онирующих в реальном масштабе времени, Цель изобретения — увеличение быстродействия.

На-фиг.1 представлена схема устройства; на фиг.2 — схема операционного блока первого столбца матрицы,* на фиг,З вЂ” схема операционного блока первой строки с второго по N-й столбцов матрицы, на фиг.4 — схема операционного блока первой строки ((1+1)— го столбца матрицы;.»а фиг.5 — схема операционного блока с второго по И-й столбцов и с второй по Б-ю строк матрицы; на фиг.6 — схема операционного, блока (0+1)-го столбца и с второй по

N-þ строк матрицы (N — порядок решаемой системы линейных алгебраических уравнений).

Устройство содержит матрицу размером N>(N+1) операционных блоков 1, вход 2 режима устройства, вход 3 синх онизации устройства, входы 4 коэффициентов устройства, выходы 5 операци- нгых блоког матрицы, выходь. 6„-бц .п-;ðîéñòâà, Каждый операционный блок

1 первого столбца матрицы содержит мупьтиппексор 7 и регистр 8. Каждый операционный блок 1 первой строки с (n)

Ha N-й итерации матрица С „ „(„ < „(вы(л) рождается в вектор-столбец С,„

=(« — С (С ... > С ) ) являющиися ре

s g, s ° Ф 4 s шением системы линейных алгебраичес(й ких уравнений, т,е. X=C „,„„.

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

C синхровхода 3 на входы записичтения регистров 8 поступает первый тактовый импульс, а на вход 2 устройства подается единица, откуда она поступает на управляющий вход мультиплексора 7 операционного блока I,:,, гце i j =1 N и, таким образом, с информационного входа 4,„ на выход мульти»лексора 7 поступает информаци второго по Н-й столбцов матрицы содержит мультиплексор 7, регистр 8 и делитель 9.

Каждый операционный бЛок 1 с второго. по N-й столбцов и с в "орого по

N-ю строк матрицы содержит мультиплексор 7, регистр 8, умножитель 10, сумматор 11. Каждьй операционный блок 1 (N+1)-го столбца с второй no N-ю строк матрицы содержит регистр 8, умножитель 1О и сумматор 11.

Устройство осуществляет решение системы из N линейных алгебраических о уравнений вида АХ=В, где A-(а1 матрица коэфФициентов, Х=(Х,,..., Х ц — вектор-столбец неизвестных, -3 т

)3=fb„,. s.,Ь, — вектор-столбец, свободных членов, на основе метода исключения. Решение системы из N линейных алгебраических уравнений с "N неизвестными происходит за N итераций.

На каждой итерации вычисляется новая

I (kl ) матрица С „„ „,, где n=1,N, причем (e) исходная матрица С(„(((1 =(А:В), т.е,: (o1 (о1

С =а, где i,j=1,N С; >„=b;, / (б

=1,((. Элементы матриц С „(t(„1вы- числяются следующим образом и.записывается в регистр 8. В операционном блоке 1, „, информация записывается в регистр 8 непосредственно с входа 4„ +(° Таким образом,в региI страх 8 операционных блоков 1;, где i-=1,N, 1=1,N+i > будут записаны

fo) элементы С, исходной матрицы (о) ь)

С,„„((„1 . С выхода блока 1, „элемен: (о1

С „, поступает на одни информационные входы делителей .9 операционных блоков

1,(, где j=2 N+1 на другие информационные входы которых нэ регистров 8 поступают соответствуюшие элементы

С, Бя 13ьГХОд дехжтеля 9 Операционного блока 1, поступает «acòное (о1 (о) ()

С,; /С,,:, =С, °, . к торов далее пс ст

S 1569846 6 пает на соответствующий информацион- ньв(выход 5 поступает элеменг (; " .

»L ный вход умножителя 10 операционногО Затем элементы столбца С;, С . блока 1; °, где i 2 ß, и на выход 5» (,11 ..э ° Ч где i=1,N, поступают на информационные выходы ; устройства, являющиеся ционного блока 1 элемент С ° г. с<<(t,f " решением системы линейных алгебраитупает на информационный вход умножи- ческих уравнений. теля 10 операционного блока 1„ . С выхода умножителя 10 операционного блока 1 произведение С(С (/С ф,) 1Î поступает на один йнформационный вход Устройство для решения систем лнсумматора 11, на другой информационный нейных алгебраических уравнений, совход которого с выхода регистра. 9 держащее матрицу размером N (N+1) поступает элемент С(о . На выход сум- операционных блоков, где N — - порядок матора 11 операционйого блока 1, и 15 решаемой системы линейных алгебраи4,1 далее на выход 6, поступает элемент ческих уравнений, при этом вход синх-(о1

С, ° (о (О1 ронизации устройства подключен к вхоС, =С ° -С °

,),1 (О дам синхронизации всех операционных

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

-по N-ю, столбцов с первого по N-й на выход мультиплексора 7 операциоиноматрицы, выход операционного блока го блока 1, где i=1,N-1 j=1 N первого столбца i-й строки матрицы )

Э ° II 9 чнформацию с информационного выхода (где i=1,...,N) подключен к первому

5(,((+, операционных волоков и на вы- информационному входу операционного ход мультиплексора 7 операционного блока второго столбца i-й строки матблока 1И информацию с информацион- рицы, входы с первого по N-й первой ного выхода 5,, операционных блоков., группы коэффициентов устройства подНа последующих тактах на выход муль- 30 ключены соответственно к первому интиплексора 7 информация пропускается формационному входу операционного только с информационных выходов 5, . блока первой строки первого столбца

С выхода мультиплексора 7 информацйя матрицы и к вторым информационны . з. исывается в регистр 8, Таким обра- входам операционных блоков первой зом, в регистрах 8 операционных бло- З5 строки со второго по И-й столбцов ма:— ков 1,, где,j=1,N, записаны эле (1 рицы, первый выход операционного бло= менты „. Далее устройство работает ка первой строки (-го столбца матрицы ачалогичйо первому такту. В конце (где j--2,...,N+ 1) подключен к третьетакта на информационные выходы 5,, му информационному входу операционногде i=2 И, j=2 И поступают элементы gg ro блока второй строки j-го столбца

С;,, и на информационные выходы матрицы, о т л и ч а ю щ е е с я тем, (1 что, с целью, увеличения быстродейст5,, поступают элементы Си вия, выход операционного блока перНа и-м такте в регистры 8 операци- . вого столбца i-й строки матрицы подонного блока 1,,где i=1,N, j=1,N+1-п 4S ключен к первым информационным входам (n- 1 записываются элементы С; . Далее операционных блоков с третьего по

»( устройство работает аналогично преды- (N+1) é столбцов i-й строки матрицы

1 дущим тактам. В конце и-го такта на первые входы коэффициентов групп с информационные выходы 5;, где i=2,N, второй по N-ю устройства подключены

)=2,М 1-п,поступают элементы С, 5(1 соответственно к первым информацион2 + Л

< t>g и на информационные выходы 5» посту- ным входам операционных блоков перво(г)

) пают элементы С„ ro столбца строк с второй по М-ю

Ha N-м такте в регистры 8 операци- матрицы, j-й вход коэффициентов k-A онного блока 1;, где i=1 N, 1=1,2., группы (где k=2, N) устройства

;И- записываются элементы С; После подключен к второму информационному 4 аналогичнь(х действий, как на предыду-. входу операционного блока k-й строки

"„их тактах, в конце такта на информа- j-ro столбца матрицы, первый выход ционные выходы 5 z, где i=2,N посту- операционного блока первой строки

Ф» лают элементы С(,„ и на информациои- j-ro столбца матрицы подключен к тре15б 9846 тьнм информационным входам операционных блоков j-го столбца с третьей по

N-ю строк матрицы, третий информационный вход операционного блока первой строки k-го столбца матрицы подключен

5 к выходу операционного блока второй строки (k+1)-го столбца матрицы, четвертый информационный вход операционного блока k-ro столбца 1-й

10 строки (где 1=2,. ° .,N-1) матрицы подключен к выходу операционного блока (1+1)-й строки (k+1)-го столбца мат.рицы, второй выход" операционного блока первой строки m-ro столбца (где m= 15 .*=:3 ; .,N+1) подключен к четвертому информационному входу операционного блока N-й строки (m-1)-ro столбцаматрицы, выход операционного блока второго столбца К-й строки матрицы 20 подключен к второму информационному входу операционного блока первого столбца |,k-1)-й строки матрицы и к (k-1)-му выходу устройства, второй выход операционного блока первой стро-25 ки второго столбца матрицы подключен ,к второму информационному входу операционного блока первого столбца N-й

;троки матрицы и к N-му выходу устройства, при этом каждый операционный 30 блок первого столбца матрицы содержит мультиплексор и регистр, причем в каждом операционном блоке первого столбца матрицы управляющий вход, вход синхронизации, первый и второй инфор- 35 мационные входы .операционного блока первого столбца матрицы подключены соответственно к управляющему входу мультиплексора, к входу записи-чтения регистра, к пеРвому и втоРому инфор- 40 мационным входам мультиплексора, выХод которого подключен к информационному входу регистра, выход которого подключен к выходу операционного блока первого столбца матрицы, при этом каждый операционный блок первой строки с второго по N-й столбцов матрицы содержит мультиплексор, регистр и делитель, причем в каждом операционном блоке первой строки с второго по N-й столбцов матрицы первый, второй и третий информационные входы, вход синхронизации и управляющий вход операционных блоков первой строки с второго по Й-й столбцов матрицы подклю55 чены соответственно к первому информационному входу делителя, к первому и второму информационным входам мультиплексора, к входу записи-чтения регистра и к управляющему входу мультиплексора, выход которого подключен к информационному входу регистра, выход которого подключен к второму информационному входу делителя, выход которого подключен к первому и второму выходам операционных блоков первой строки со второго по N-й столбцов матрицы, йри этом операционный блок . первой строки (N+1)-ro столбца матрицы содержйт регистр и делитель, причем в операционном блоке первой строки,(N+1)-го столбца матрицы первый и второй информационные входы и вход синхронизации операционного блока первой строки (И+1)-го столбца матрицы подключены соответственно к первому информационному входу делителя, к информационному входу регистра и к входу записи-чтения регистра, выход которого подключен к второму информационному входу делителя, выход которого подключен к первому и второму выходам операционного блока первой строки (N+1)-го столбца матрицы, причем каждый операционный блок с второго no N-й столбцов и с второй по N-ю строк матрицы содержит мультиплексор, регистр, сумматор и умножитель, причем в каждом операционном блоке с второго по N-й столбцов и с второй по М-ю строк матрицы первый, второй, третий и четвертый информационные входы, вход синхронизации и управляющий вход операционного блока с второго no N-й столбцов и с второй по N-ю строк матрицы подключены соответственно к первым и вторым информационным входам умножителя и мультиплексора, к входу записи-чтения регистра и к управляющему входу мультиплексора, выход которого подключен к информационному входу регистра, выходы регистра и умножителя подключены к первому и . второму информационным входам сумматора, выход которого подключен к выходу операционного блока с второго no N-й столбцов и с второй по N-ю строк матрицы, причем каждый операционный блок (N+1)-гс столбца с второй по N-ю строк матрицы содержит регистр, умножитель и сумматор, причем в операционном блоке (N+1)-го столбца с второй по N-ю строк матрицы первый, второй и третий информационные входы и вход синхронизации операционного блока.(И+1)-ro столбца с второй по

N-ю строк матрицы подключены соответ9 1569846 1О ственио к первому информационному ственно к первому и второму информавходу умножителя, к информационному ционным входам сумматора, выход котовходу РегнстРа, к втоРому инфоРма-. рого подключен к выходу операционного ционному входу Умножителя и к входу блока (И+1)-го столбца с второй по

5 записи-чтения регистра, выходы реги- И-ю строк матрицы. стра и умножителя подключены соответФю5

Составитель В.Смирнов

Л.Патай

Редактор И.Бланар Техред H.Õoäàíè÷ . Корректор

Закaç 145 1 Тир,:.ж 569,Подписное

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

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

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