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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 8007 А ив 8 д 06 Р 15/3 ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССПО ДЕЛАМ ИЗОБРЕТЕНИЙ ИОТНРЫТ(72) В.Е.Золотовский и Р.В.Коробков (71) Таганрогский радиотехнический институт им.В.Д. Калмыкова(56) 1, Авторское свидетельство СССР % 682902 кл. С 06 Р 15/32, 1979.2. Авторское свидетельство СССР % 710044, кл. 6 06 Р 15/32,1980 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, содержащее группу вычислительных блоков по числу уравнений в системе, причем каждый вычислительный блок содержит и одноразрядных умножителей, пвходовой сумматор, двухвходовой сумматор, регистр, накопитель, первые входы одноразрядных умножителей соедИ- иены с информационными входами вычис литепьного блока, выходы одноразрядных умножителей соединены с входами ивходового сумматора, выход которого подключен к первому входу двухвходового сумматора, информационный вход регистра соединен с выходом двухвходового сумматора, а выход - с вторым входом. двухвходового сумматора, о т л и чающее ся тем, что, сцелью повышения быстродействия, в него введенэлемент И, а в каждый вычислительныйблок - два триггера, два элемента И,элемент ИЛИ, элемент НЕ, причем вкаждом вычислительном блоке информационные входы триггеров соединены свыходом двухвходового сумматора, ауправляющие входы триггеров - с управляющим входом вычислительного блока, инверсный выход первого триггерасоединен с первым входом первого элемента И вычислительного блока, инверс- "тный выход второго триггера - с первымвходом второго элемента И вычислительного блока, прямой выхоа первоготриггера - с,вторь 1 м входом второгоэпемента И вычислительного бпока, прямой выход второго триггера - с вторымвходом первого эпемента И вычислительного блока, выходы элементов И вычислительного блока соединены с входамиэлемента ИЛИ, с вторыми входами одноразрядных умножителей, с информацион.ными входами накопителя и с выходомвычислительного блока, вход элементаНЕ соединен с выходом элемента ИЛИ,входы элемента И соединены с выходайиэлементов НЕ каждого вычислительногоблока, а выход - с управляющими входами регистра и накатитепя каждого вычислительного блока,1 1088007 3Изобретение относится к автоматике жителей соединены с информационными и вычиспительной технике и может быть входами вычислительного блока, выходы испсщьэовано в специализированных одноразрядных умножителей соединены с устройствах, предназначенных для реше- входами о -входового сумматора, выход ния систем алгебраических уравнений ви которого подключен к первому входу двухда входового сумматора информационный АХ+В 0 (1) вход регистра соединен с выходом дву- Известно цифровое устройство для ре- входового сумматора, а выход - с вторым шеьшя систем алгебраических уравнений, входом двухвходового сумматора, ввекотоРое содержит первую группу сумма ден элемент И, а в каждый вычиспительтора, выходы которых соединены с пер- ный блок - два триггера, два элемента И, вым входом блока памяти, второй вы- элемент ИЛИ, элемент НЕ, причем в ход которого соединен с первым входом каждом вычислительном блоке информаблока управления и второй группы сум- ционные входы триггеров соединены с маторов, выходы которых через блок эле выходом двухвходового сумматора, а ментов НЕ соединены с блоком сдвига 13. управлякицие входы триггеров - с управНедостатком устрояства является низ- ляющим входом вычислительного блока, кое быстродействие. инверсный выход первого триггера соедиНаибопее близким по технической сущ- нен с первым входом первого. элемента И ности к изобретению является устройст вычислительного блока, инверсный выход во, которое содержит ь элементов И, второго триггера - с первым входом- входовой сумматор, двухвходовой второго элемента И вычислительного блосумматор, регистр, блок сравнения, блок ка, прямой выход первого триггера - с формирования прйращений и накопитель, вторым входом второго элемента И выпричем выходы схем совпадения соедине-числительного блока, прямой выход втоны с входами п -входового сумматора, рого триггера - с вторым входом перво- выход которого соединен с первым входом го элемента И вычислительного блока, двухвходового сумматора, второй вход прямой выход второго триггера - с втокоторого соединен с выходом регистра, рым входом первого элемента И вычисли вход которого соединен с выходом двух 0 тельного блока, выходы элементов И вы входового сумматора, кроме того, выходчислительного бпока соединены с входа- сумматора соединен с входом схемы ми элемента ИЛИ и с вторыми группами сравнения, а выход - с первым входом входов одноразрядных умножителей, с бпока формирования приращения, второй информациониыми входами накопителя и с вход которого соединен с выходом ре- выходом вычислительного блока, вход гистра, выход блока формирования при 35элемента НЕ соединен с выходом элеращений соединен с входом накопите- мента ИЛИ, входы элемента И соединены ля 23.с выходами инверторов каждого вычис"Недостатком известного устройства дительного блока, а выход - с управляю" . является низкое быстродействие, обус- щими входами регистра и накопителя кажловленное малым весом выходного при- дого вычислительного блока.40 ращения, равного 2, где щ -дли- Исходная система на разрядной сетки. В связи с этим+8 О ву( ьажняя оценка числа итерационных ша, ,.Ю 2"ЬЗС 1 2"1 б 3 гов имеет вид , пРеобразуются к видуМ = Хна)(. 2, Ж+1 Ф где Х =.тахх, х ., х- максималь- Ь = -сН1 с+ Ж 1+4 .ное зйачение неизвестноя. +1 5/Белью изобретения является повыше- %Х ние быстродействия устройства. 1+1 О О,сб (1Указанная цель достигается тем, что св устройствосодержащее группу вычислительных блоков по числу уравнений +Ха 9 ХФ, % г в системе, причем каждый вычислительный Здесь Хк, - с, Д Хк - вектОра видак блок содержит и одноразрядных умножи У".У ,где У один из перечисленных пателей, :и - входовой сумматор, двухвхо раметров. довой сумматор, регистр, накопитель, пер, - Так как устойчивая работа возможна вые группы вхооов одноразрядных умно- лишь при наличии отрицательной обратной-дХ0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 О 0 0 0 0 1 0 0 О 0 О О 0 0 101,0 0 0 0 но, начиная с младшего разряда регистра, его содержимое поступает на двухвхоаовой сумматор ., а так как все прира 3 цения равны нулю и, следовательно,д щО, содержимое регистра не изменяется, за исключением того, что по сигналу с элемента 12 выключается схемасдвига последовательного регистра. Здесь Х - знак рассогласования в к-шаге, Х, (к+1) - знак рассогласомнив в (К+1) -шаге, Х-стараний значащий разряд в К-шаге, Х 2 (К+1)-старший значащий разряд в (К+1)-шаге.Звездочкой отмечена невозможная ситуа.ция, " + ЬХ; (- д Х;) - положительное (отрицательное) приращение на выходе1 -го вычислительного блока. Старшийи знаковые разряды сохраняют свое зна-. чение, в старшем разряде при положительном знаке появляется нуль или при отрицательном знаке - единица, и при . изменении знака на отрицательный в старшем знаковом разряде появляется нуль. В первом и третьем случае на следующемО шаге вновь вырабатывается приращение на выходе вычислительного блока, а во втором приращение равно нулю, Полученное приращение, вйк и предыдущее, поступает на соответствующие одноразрядные умножитеди 1; и накопитель, где прибавляется к текущему значения неизвестного Х;. Этот процесс продолВ соответствии с условием устойчивости рассогласование может менять знак,но,по амплитуде может только убыватьв 1 м вычислительном блоке, если навыходе этого устройства приглашение неравно нулю, Следовательно, в результатевычитаниями 5 из содержимого регистра 4возможны следующие случаи: 1жается до тех пор, пока старшие разряды рассогласования во всех устройствах не станут равны нулю, Этот факт отмечается тем, что на выходе элемента И 12 формируется сигнал, равный 1. Происходит это следуюшим образом. Приращения с выходов элементов И 7 и 8 поступают на элемент ИЛИ 9, На выходе этого элемента сигнал равен нулю только в том случае, если приращение равно нулю. Проходя через элемент НЕ, нулевой сигнал становится единичным и, если во всех вычислительных блоках приращения равны нулю, то на всех входах схемы совпадения стоят единицы,и , следовательно, на выходе ее тоже будет единица. Эта единица сигнализирует о завершении итерационного процесса определения текущего разряда всех неизвестных. По атому, сигналу, подаваемому на регистры 4 всех вычислительных блоков и накопители 10, происходит сдвиг содержимого регистра (рассогласования 8и накопителя (неизвестного),Палее процесс повторяется до тех Йрпока не будут получены неизвестные с за-данной точностью, В качестве примерарассмотрим решение системы 0,97 х + 0.51 Х = 9.9 ЬЗ1гО,Э 1 х+0,85 х=Ь,ИЗ0,111 ИО Х 1+ О, 100000 Х =1001 111+400,010011 Х 1+ О.И 0110 Х. = МО.011010Точное решение Х 1= 7,8, Хг = 4,7,В известном прн использовании приращений весом 2 о необходимо выполнитьсемь шагов и результат будет равенХ =7, Х = 5. Для данного устройства предварительно промасштабируем системутак, чтобы она не содержала рассогла- Осований величиной больше двух. В нашемслучае в. и вг умножим на 2 9. Тогдабг =Ъг= 0.110,011010,Х =1 Х =О,Ф г25Подставляя в систему, получим новоезначение рассогласования.5 =0,0111011105 =Ъг. 0.1 оооооо 10,ДХ = 1.жг= ОНа этом выполнение первого шага закан- ЗОчивается, Так как старшие разряды 5 иравны нулю, то дХ - О, ЬХ -О,и второй шаг начинает.я со сдвига31 О 10001 1 100 г 100 00 100Х= 10, Х 2 = 00 система принимает 35 0,111 11 дх +0,100 000 х: 0,100011100.3 гц)0.11011 Х, + 0 11011 О хг -1.00000010 ОПриращения равны 3 Х = О,ля 1, подставляя в (2) и произведя вычисления, получим Эг = 000111000 Зг= 0,001010100. На этом выполнениевторого шага заканчивается. Третий шаг.начинается со сдвига, после сдвига приращения остаются нулевые, производитсяследукяций сдвиг. В сумме их стало три,следовательно целая часть определена ипосле этого разряда фиксируется точкаХ 1000, Х= 0100,Однако приращения равны нулю, поэтому производят еще один сдвиг. Прира-щения становятся равными д Х 1 О,Д Хг = 1. Так. как требуемая точностьдостигнута, то решение прекращается после выполнения операций третьего шага., Результат выполнения этого шагах= 1000.0;х = 01001 (= 8,Хг = 4,5).Уже Фактические на втором шаге требуемая точность достигнута (с учетоммасштабного преобразования), но как правило всегда выполняется на один шагбольше, чтобы заданная точность выполнялась наверняка.Таким образом, введение новых узлови конструктивных связей позволило повысить быстродействие устройства. Чио;ло шагов, необходимое для получения результата приблизительно составляет лога-:рифм от числа шагов в-известном устройстве.1088007 акаренко орре ал ППП Патентф, г.Ужгород, ул.Проектн Сост авитель И.ПчелинцевРедактор Н.Пушненкова Техред И.Метелева 6 Тираж 699ВНИИПИ Государственного комитетпо делам изобретений и открыти 113035, Москва, Ж, Раушская одписное