Устройство для решения систем алгебраи-чЕСКиХ уРАВНЕНий Советский патент 1981 года по МПК G06F17/12 

(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ

1

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

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

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

Наиболее близким по своей технической сущности к предлагаемому является устройство, состоящее из первой- и второй группы сумматоров, первой и второй группы комбинационных масштабных узлов и инверторов, входы устройства соединены с входами инверторов и с первыми входами сумматоров первой группы, выходы инвен0торов соединены с первыми входами сумматоров второй группы, выходы первой и второй группы комбинационных масштабных узлов соединены соответственно с вторыми входаили сумма5торов первой и второй группы, выходы -сумматоров второй группы соединены с третьими входами сумматоров первой группы, а выходы сумматоров первой группы(Соединены с входами первой

0 и второй Группы комбинационных масш-, табных узлов 2.

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

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

Цель изобретения - расширение класса решаемых задач.

0 Поставленная цель достигается тем, что в устройство, содержащее первую и вторую группы сумматоров., первую и вторую грулпы масштабных узлов и элементы НЕ, причем входы устройства соединены непосредствен но с первыми входами сумматоров пер вой группы и через соответствующие элементы НЕ - с первыми входами сумматоров второй группы, выходы масштабных.узлов первой и второй группы соединены соответственно с вторыми входами сумматоров первой второй группы, выходы сумматоров второй группы соединены с третьими входами сумматоров первой группы, введены группа Д-триггеров, группа компараторов, коммутатор, группа элементов задержки и генератор оди ночных импульсов, причем выходы сумматоров первой группы соединены с первыми входами компараторов груп пы и с первыми входами Д-триггеров группы, выходы которых подключены к выходам устройства, к вторым вхо дам компараторов группы и к входам масштабных узлов первой, и второй группы, вь.ходы компараторов группы соединены с соответствующими входами компаратора, выходы которого под ключены к первЕлм входам элементов задержки группы, соединенных между собой последовательно, выход послед наго элемента задержки соединен с входом генератора одиночных импульсов, выход которого,соединен с вторыми входами Д-триггеров группы. На чертеже представлена блок-схе ма устройства. Устройство содержит входы 1 и 2 элементы НЕ 3, первую 4-7 и вторую 8-11 группы масштабных узлов, первую группу сумматоров 12 и 122, вторую группу сумматоров 12 и 12, группу Д-триггеров 15, группу компа раторов 16, коммутатор 17, группу элементов 18 задержки, генератор 19 одиночных импульсов и выходы 13 и 14 устройства. Устройство работает следующим образом. На входы 1 устройства поступают старшие разряды значений правой части F; - FYJ заданной системы уравнений, представленной в матричHO d виде X Bv + F /На входы 2 устройства поступают младшие разряды значений правой части F - F{ системы уравнений (1) На выходах 13 устройства вырабатыва ются значения старших разрядов искомого вектора неизвестных в уравнении (1) xt) - х а на выходах 14 устройства выраб.атываются значен младших разрядов х - х. На первой группе комбинационных масштабных узлов 4-7 прои.зводится умножени искомого вектора неизвестных х на коэффициенты матрицы В системы уравнений (1), а на второй группе комбинационных масштабных узлов 8-11 производится умножение искомого вектора переменных х на коэффициенты матрицы А, определяемой выражениемА Е - В (2) На сумматоре 12-j производится суммирование частичных произведений искомого вектора переменных х на коэффициенты первой строки матрицы А, определяемой выражением (2) с инвертированным значением компоненты свободных членов F . На сумматоре 12 производится суммирование частичных произведений искомого вектора переменных х на коэффициенты п-ой строки матрицы А с инвертированным значением компоненты свободных членов Р„,где п - порядок решаемой системы уравнений, На сумматоре 12 производится суммирование частичных произведений искомого вектора переменных х на коэффициенты первой строки матрицы В,определяемой выражением (1), с q младшими разрядами полученной суммы на сумматоре 12 . и со значением ко.мпоненты свободных членов F , На сумматоре 122 производится суммирование частичных произведений искомого вектора переменных х на коэффициенты п-ой строки матрицы В с q младшими разрядами полученной суммы на сумматоре 12 и со значением компоненты свободных членов F, В искомое состояние на выходах группы Д-триггеров 15 записан вектор начального приближения х°. При поступлении на входы: 1 и 2 устройства вектора .правой части F уравнения (1) , на выходах первой группы сумматоров 12. и 122 вырабатывается в течение времени переходного процесса в схеме устройства, промежуточное значение вектора х . Группа компараторов 16 производит поразрядное сравнение компонент вектора на выходе группы Д-триггеров 15 и- компонент вектора на входе группыД-триггеров 15 х , и как только происходит изменение какоголибо разряда на входе группы Д-триггеров 15 соответствующий компаратор 16 вырабатывает сигнал несоответствия , который поступает на коммутатор 17. Коммутатор 17 передает сигнал несоответствия к соответствующему входу последовательно соединенных, между собой элементов задержки. Задержанный сигнал несоответствия с выхода последовательно соединенной группы элементов 18 задержки поступает на вход генератора 19 одиночных импульсов, который вырабатывает управляющий синхроимпульс, поступающий на вторые входы (входы синхронизации) группы

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

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

р-1

Лр :Т-2д, -л

т Т .... р РН 3 -I

где Тр(,2...,р) - некоторый параметр j-ro информационного выхода первой группы сумматоров 12, и 12/j определяемый соотношением

( Чпчп bwin

.-iniax

Т; тах

t + о /

где

максимальное время пере1 WCSX ходного процесса по 1-ому выходу первой группы сумматоров 12 и 12,2 ; минимальное время переходw-inного процесса по выходу первой группы сумматоров 12 и 122;

минимальное время задержд W4H ки в группе компараторов 16 и генераторе 19 одиночных импульсов; максимальное время перек oixлючения Д-триггера; максимальный разброс временного интервала одновременного поступления информации на входы 1 и 2 устройства;

,: Ц)ш.5 наибольшее по величине время переходного процесса из всего множеств MaKCHMaAbHbix значений длительности переходных процессов по i-ому выходу

первой группы сумматоров (,2,...р) при ij j ; р - значение, численно равное произведению количества разрядов представления искомых переменных на порядок- решаемой системы уравнений.

2,Гонки между состояниями,вызванные тем, что в течение одного пере;ходнрго процесса в первой 4-7 и во

o второй 8-11 группах масштабных узлов и сумматоров 12 , 122, 2, 124 генератор 19 одиночных импульсов выдает серию синхроимпульсов, поступающих на вторые входы группы Д-триг5геров 15. Это ограничение снимается путем подбора длительности синхроимпульсов, вырабатываемого генератором 19 одиночных импульсов в соответствии со следующим соотношением

0

С (4r«ax-t,- jyi-in ,) + (ti,,) + T)vnoix Dmin

-D длительность синхроимгдепульсов с выхода генератора 19 одиночных импуль5сов ;

максимальное время переbWCJIXходного процесса в одном из компараторов группы компараторов 16 и генера0торе 19 одиночных импульсов;

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

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

5

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

Устройство для решения систем

0 алгебраических уравнений, содержащее первую и вторую группы сумматоров, первую и вторую группы масштабных узлов и элементы НВ, причем входы устройства соединены непосред5ственно с первыми входами сумматоров первой группы и через соответствую1щие элементы НЕ - с пврвы1 й1 входами сумматоров второй группы, выходы масштабных узлов первой и второй

0 группы соединены соответственно с вторыми входами сумматоров первой и второй группы, выходы сумматоров второй группы соединены с третьими входами сумматоров первой группы.

65 отличающееся тем

что,

f

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

Источники информации, принятые во внимание при экспертизе

.1. Авторское свидетельство СССР 428405, к-л. G 06 F 7/34. 1974.

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