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

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

Иллюстрации

Показать все

Реферат

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Республик (n>807317

f©% (61) Дополнительное к авт. свид-ву р )м. к. (22) Заявлено 09,1078 (23) 2672502/18-24

G 06 F 15/324 с присоединением заявки ¹ (23) Приоритет

Государственный комитет

СССР по делам изобретений и открытий

Опубликовано 230281. Бюллетень М 7 (53) УДК 681. 14 (088. 8) Дата опубликования Описания 2302Â1 (72) Авторы изобретения

Л.В. Дербунович, В,Ф. Евдокимов, И.Ф. Зубен

Ю.А. Плющ и В.В. Шатилло! L$

1 ЕХИ;.рЦУ-",-.,;; d, )

Харьковский ордена Ленина политехнический нстиачт,, т им. B„H„ Ленина и институт электродинамики . "" "" -"" : - 4 .АН Украинской CCP (71) Заявители (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ

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

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

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

Наиболее близким по своей технической сущности к предлагаемому является устройство, состоящее иэ первой.и второй группы сумматоров, первой и второй группы комбинационных масштабных узлов и инверторов, вхо° ды устройства соединены с входами инверторов и с первыми входами сумматоров первой группы, выходы инвен торов соединены с первыми входами сумматоров второй группы, выходы первой и второй группы комбинационных масштабных узлов соединены соответственно с вторыми входами сумма45 торов первой и второй группы, выходы сумматоров второй группы соединены с третьими входами сумматоров первой группы, а выходы сумматоров первой группы, соединены с входами первой

20 и второй группы комбинационных масш-. табных узлов (2).

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

25 из-за возникновения и генерации вследствие состязаний в схеме,вызванное разбросом параметров задержек логических элементов.

Цель изобретения - расширение

30 класса решаемых задач.

807317

Поставленная цель достигается тем, что в устройство, содержаш е первую и вторую группы сумматор в., первую и вторую грулпы масштабных узлов и элементы НЕ, причем входы устройства соединены непосредственно с первыми входами сумматоров первой группы и через соответствующие элементы НŠ— с первыми входами сумматоров второй группы, выходы масштабных, узлов первой и второй группы соединены соответственно с вторыми входами сумматоров первой и второй группы, выходы сумматоров второй группы соединены с третьими входами сумматоров первой группы, введены группа д-триггеров, группа 35 компараторов, коммутатор, группа элементов задержки и генератор одиночных импульсов, причем выходы сумматоров первой группы соединены с первыми входами компараторов груп- 20 пы и с первыми входами Д-триггеров группы, выходы которых подключены к выходам устройства„ к вторым входам компараторов группы и к входам масштабных узлов первой. и второй

25 группы, вь.ходы компараторов группы соединены с соответствующими входами компаратора, выходы которого подключены к первым входам элементов задержки группы, соединенных между . собой последовательно, выход послед-. него элемента задержки соединен с входом генератора одиночных импульсов, выход которого соединен с вторыми входами Д-триггеров группы.

На чертеже представлена блок-схе- З5 ма устройства.

Устройство содержит входы 1 и 2, элементы НЕ 3, первую 4-7 и вторую

8-.11 группы масштабных узлов, первую группу сумматоров 12 и 122, 40 вторую группу сумматоров 12 и 124, группу Д-триггеров 15, группу компараторов 16, коммутатор 17, группу элементов 18 задержки, генератор

19 одиночных импульсов и выходы 13 и 14 устройства.

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

На входы 1 устройства поступают старшие разряды значений правой части F — F> заданной системы

4 4

4 уравнений, представленной в матричном виде

x = В„+ F (1) ,На входы 2 устройства поступают младшие разряды значений правой 55 части F — F системы уравнений (1) .

На выходах 13 устройства вырабатываются значения старших разрядов искомого вектора неизвестных в уравнении (1) х 4 — х„", а на выходах щ

14 устройства вйрабатываются значения младших разрядов х - х . На первой группе комбинационнйх масштабных узлов 4-7 производится умножение искомого вектора -неизвестных х на коэффициенты матрицы В системы урав= нений (1), а на второй группе комбинационных масштабных узлов 8-11 производится умножение искомого вектора переменных х на коэффициенты матрицы A определяемой выражением

A = Š—  (2)

На сумматоре 12 производится суммирование частичных произведений искомого вектора переменных х на коэффициенты первой строки матрицы

А, определяемой выражением (2) с инвертированным значением компонентЫ свободных членов Р„ . На сумматоре

124 производится суммировайие частичных произведений искомого вектора переменных х на коэффициенты и-ой строки матрицы A с инвертированным значением компоненты свободных членов Р„,где и — порядок решаемой системы уравнений, На сумматоре 12< производится суммирование частичных произведений искомого вектора переменных х на коэффициенты первой строки матрицы В,определяемой выражением (1), с младшими разрядами полученной суммы на сумматоре 12 и со значением компоненты свободнйх членов F

На сумматоре 12 производится сум2 мирование частичных произведений искомого вектора переменных х на коэффициенты и-ой строки матрицы

В с q младшими разрядами полученной суммы на сумматоре 124 и со значением компоненты свободных членов F

В искомое состояние на выходах группы Д-триггеров 15 записан вектор начального приближения х, При о поступлении на входы 1 и 2 устройства вектора, правой части F уравнения (1), на выходах первой группы сумматоров 12 и 12 вырабатывается в течение времени переходного процесса в схеме устройства, промежуточное значение вектора х".

Группа компараторов 16 производит поразрядное сравнение компонент вектора на выходе группы Д-триггеров 15 и- компонент вектора на входе группы Д-триггеров 15 х", и как только происходит изменение какоголибо разряда на входе группы Д-триггеров 15 соответствующий компаратор

16 вырабатывает сигнал несоответствия, который поступает на коммутатор 17, Коммутатор 17 передает сигнал несоответствия к соответствующему входу последовательно соединенных. между собой элементов задержки. Задержанный сигнал несоответствия с выхода последовательно соединенной группы элементов

l8 задержки поступает на вход генератора 19 одиночных импульсов, KOторый вырабатывает управляющий синхроимпульс, поступающий на вторые входы (входы синхронизации) группы

807317

Д-триггеров 15 и производит запись, промежуточного значения кода х в группу Д-триггеров 15. Новое состояние выходов группы Д-триггеров 15 х поступает. по цепи обратной свя1 зи на входы .первой и второй группы комбинационных масштабных узлов и по истечении времени переходных процессов в схеме устройства на выходах первой группы сумматоров 22< и 12 отрабатывает новое значение промежуточного кода х, которое сравниваЯ. ется на группе компараторов 16 со значением кода х" на выходах группы

Д-триггеров 15, и так далее. Процесс повторяется до установления равенства значений кодов на входах и выходах группы Д-триггеров 15.

Для исключения неправильной работы схемы необходимо соблюдать следующие ограничения на параметры группы элементов 18 задержки:

1. Передний. фронт импульса с выхода генератора 19 одиночных импульсов, определяемый временем задержки элементов 18 задержки, должен появляться по окончании переходных процессов на всех выходах первой группы сумматоров 12 и 12, Выполнение этого условия обеспечивается следующими соотношениями

Ь,, -1 д >т - д., (=1

>Т. -g -д„ Т )Т ».:T.»...y

Р-3 . 4 где Тр()=1,2...,р) — некоторый параметр j-го информационного выхода первой группы сумматоров 12 и 12@ определяемый соотношением (1

Т =max ltirnax) tg><> ьв и °

tàåàõ где максимальное время пере max ходного процесса по i-ому выходу первой группы сумматоров 12 и 12,. — минимальное время переходного процесса по выходу ип первой группы сумматоров

12 и 12, — минимальное время задержки в группе компараторов

16 и генераторе 29 одиночных импульсов; максимальное время перек1) )%с1х лючения Д-триггера; — максимальный разброс временного интервала одновременного поступления информации на входы 1 и

2 устройства;

max1 наибольшее по величине время переходного процесса из всего множества максимальных значений длительности переходных процессов по i-oMy выходу первой группы сумматоров (i=1,2...,р) при iH $ р значение, численно равное произведению количества разрядов представления

5 искомых переменных ыа порядок решаемой системы уравнений.

2.Гонки между состояниями, вызванные тем, что в течение одного пере;ходного процесса в первой 4-7 и во второй 8-11 группах масштабных узлов и сумматоров 12, 12« и 12>, 12 генератор 19 одиночных импульсов выдает серию синхроимпульсов, поступающих на вторые входы группы Д-триг15 геров 15. Это ограничение снимается путем подбора длительности синхроимпульсов, вырабатываемого генератором 19 одиночных импульсов в соответствии со следующим соотношением

20 (1rntN t1 1 ?+ (х tb&1h +

+(t wax " ги в где 3 — длительность синхроимпульсов с выхода генера25 тора 19 одиночных импульсов;

„ — максимальное время переходного процесса в одном из компараторов группы

30 компараторов 16 и генераторе 19 одиночных импульсову — минимальное время переклю2 Ь и чения Д-триггера.

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

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

Формула изобретения Устройство для решения систем алгебраических уравнений, содержащее первую и вторую группы сумматоров, первую и вторую группы масштабных узлов и элементы НЕ, причем входы устройства соединены непосред. ственно с первыми входами сумматоров первой группы и через соответствую.щие элементы НŠ— с первымй входами сумматоров второй группы, выходы масштабных узлов первой и второй

60 группы соединены соответственно с вторыми входами сумматоров первой и второй, группы, выходы сумматоров второй группы соединены с третьими входами сумматоров первой группы, $5 о т л и ч а ю щ е е с я тем, что, 807317

1

1j

1ф

7Я

ВНИИПИ Заказ 294/75 Тираж 756 Подписное

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4 с целью расширения класса решаемых задач, в устройство введены гр пы

Д-триггеров, группа компараторов, коммутатор, группа элементов задержки и генератор одиночных импульсов, причем выходы сумматоров первой группы соединены с первыми входами компараторов группы и с первыми входами Д-триггеров группы, выходы которых подключены к выходам устройства,. к вторым входам компараторов группы и к входам масштабных узлов первой и второй группы, выходы компараторов группы соединены с соответствующими входами коммутатора, выходы которого подключены к первым входам элементов задержки группы, соединенных между собой последовательно, выход последнего элемента задержки соединен с входом генератора одиночных импульсов, выход которого соединен с вторыми входами Д-триггеров. группы.

Источники информации, принятые во внимание при экспертизе .1. Авторское свидетельство СССР

Р 428405, кл. G 06 F 7/34, 1974.

2.Авторское свидетельство СССР по заявке 9 2506823/18-24, кл. G 06 F 15/32, 1978 (прототип) .