Устройство для решения систем алгебраических уравнений Советский патент 1984 года по МПК G06F17/12 

Изобретение относится к автоматике и вычислительной технике в может быть нспспьэовано в специализированных устройствах, предназначенных для решення систем алгебраических уравнений ви АЛ + В - О(1) Известно цифровое устройство для ре шешЕЯ систем алгебраических уравнений, которое содержит первую группу сумматора, выходы которых соединены с первым входом блока памяти, второй выход которого соединен с первым входом блока управления и второй группы -сумматоров, выходы которых через блок эле ментов НЕ соединены с блоком сдвига f 1 Недостатком устройства является низ кое быстродействие. Наиболее близким по технической сущ ности к изобретению является устройсо во, которое содержит п элементов И , f - входовой сумматор, двухвходовой сумматор, регистр.блок сравнения, блок формирования приращений и накопитель. причем выходы схем совпадения соединены с входами п -входового сумматора, выход которого соединен с первым входо двухвходового сумматору, второй вход которого соединен с выходом регистра, вход которого соединен с выходе двухвходового сумматора, кроме того, выход сумматора соединен с входом схемы сравнения, а выход - с первым входом блока формирования приращения, второй вход которого соединен с выходом регистра, выход блока формирования приращений соединен с входсщ накопителя 23. Недостатком известного устройства является низкое быстродействие , обусловленное малым весом ы,1ходного njfMрашения , равного 2 , где гл -длина разрядной сетки. В связи с этим дажняя оценка числа итерационных ша гов имеет вид где , х.2..... максималь ное значение неизвестной. . Целью изобретения является повышение быстродействия устройства. Указанная цель достигается тем, что в устройство,, содержащее группу вычислительных блоков по числу уравнений в системе, причем вычислительны блок содержит п одноразрядных умножителей, п - входовой сумматор, двухвхо- доБой сумматор, регистр, накопитель, пер вые вхоаов одноразрядных умно007жителей соединены с информационными входами вычислительного блока, выходы одноразрядных умножителей соединены с входами п -входового су «у1атора, выход которого подключен к первому входу двухвходового сумматора,, информационный вход регистра соединен с выходе двухнходового сумматора, а выход - с вторым входом двухвходового сумматора, вве ден элемент И, а в каждый вычислительный блок - два триггера, два элемента И, элемент ИЛИ , элемент НЕ, причем в каждом вычислительном блоке информационные входы триггеров соединены с выходом двухвходового сумматора, а управляющие. входы триггеров - с управ- ляюшим входом вычислительного блока, инверсный выход первого триггера соединен с первым входом первого .элемента И вычислительного блока, инверснь1й выход второго триггера - с первым входом второго элемента И вычислительного бло ка, прямой выход первого триггера - с вторым входом второго элемента И вычислительного блока, прямой выход второго триггера - с вторым входом первого элемента И вычислительного блока, прямой выход второго триггера - с вторым входом первого эле1менга И вычислительного блока, выходы элементов И числительного блока соединены с входаМИ элемента ИЛИ И с вторьши группами входов одноразрядных умножителей, с инфор хационными входами накопителя и с выходсш вычкслшелыюго блока, вход элемента НЕ соединен с выходом элемента ИЛИ, входы элемеш-а И соедииены с выходами инверторов каждого вычислительного блсжа, а выход - с управляюишми входами регистра и нагхягателя каждого вычиспитвпьиого блока. Исходная ,fe2,...,fc, ,,x,,..,xJ феобразуютсй к виду . . 0 , C-1 , .. десь Х,, 5,, 4 Х - вектГфа видa{vJ, один из перечисленных пааметров, Так как устойчивая работа возможна ишь при наличии отрицательной обратной свяэиз п З j должен быт,ь равен, . С другой стороны т S i j 4 То для устойчивой работы должно быть выполнено а « in На чертеже представлена структурная схема устройства для решения систем алгебраических управлений, где раскрыт один вычислительный блок устройства. Устройство в каждом вычислительном блоке содержит одноразрядные умножители 1 ,п -входовой сумматор 2, двухвходовой сумматор 3, регистр 4, триггеры 5 и 6, элементы И 7 и 8, элемент ИЛИ 9, накопитель 1О, элемент НЕ 11, а также элемент И 12. Выходь одноразрядных умножителей 1,. iy. соединены с входами многовходового сумматора 2, выход которого соеданен с первым входом двухвходового сумматора 3, второй вход которого соединен с выходом регистра 4, выход двухвходового сумматора 3 соединен с инфор-; мационнь1м входом регистра 4 и информационными входами триггеров 5 и б, управ ляющие входы которых соединены с внешними входами вычислительного блока, инверсный выход триггера 5-и прямой выход триггера 6 соединены относительно с первым и вторым входами элемента И 7, прямой выход триггера 5 и инверсный i выход триггера 6 соединены соответствен но с первым и вторым. входом элемента И 8, выходы элементов И соединены соответственно с первыми и вторыми входами элемента ИЛИ 9 и накопителя 10, выход элемента ИЛИ через инвертор 11 соединен с одним из п -входов элемента И 12, выход которого соединен с управляющим входами регистра 4 и накопителя 1О каждого вычислительного блока устройства. Одноразрядный умножитель представляет собой схему 2И-ИЛИ. Первый вход первой схемы соединен с выходом второго элемента И 8 (не показано),а на второй вход подаются биты соответствующего коэффициента еч. в дополнительном коде, первый вход второй схемы И соединен с выходом первого элемента И 7 (не показано), а на второй вход подаются разряды дополнительного 108 074 кода , АОП Vflo. ПредпопагаетI . ся, что коэффициент а{ поступает на вход умножителей последовательным кодом, т.е. разряд за разрядом, начиная с младшего. Таким образом, входы элементов И в одноразрядном умножителе образуют первую.группу входов, а другие входы тех же элементов И - вторую группу входов. Решение, т.е. неизвестная величина X,формируется в накопителе Ю, . гце реализуется операция .( К - номер итерации. Накопитель npeJacTa ляет собой обычный двоичный счетчвк. Устройство работает следуклцим образом. В регистры 4 каждого вычислительного блока заносятся, первоначально величины В {Ъ,Ъ ,,..,bf, в дальнейшем рассогласование. Знак чисел Ь«( j 0,п) (|н1ксируется перед самым старшим разря.-. дом. Старший разряд числа заносится в триггер 5 по сигналу , поступающему на управляющий вход триггера, знаковый разряд аналогично заносится в триггер 6. В зависимости от содержания атих раз рядов формируется либо положительное приращение (О1), либо отрицательное (10), либо нуль (00 или 11). Положительное: приращение . формируется на выходе элемента 8, а отрицательное прирагцешЕе появляется на выходе элемента И 7. Полученное -приращение посылается на управление соответствующего одноразря;( ного умножителя 1 ( i О, г ), на второй вход эпемешга 1 поступает . Информация в устройстве передается последовательным образом младшими разрядами вперед. Так, пришелшие младшие раэряды коэффициентов а-, или их допопнекий умножаются иа приращения (т.е. проходят на многовходовой сумматор 2, если приращение не нуль).,Поступившие младшие разряды Коэффициентов складываются, , /т.е. образуется величина ex..9X J . где ,0-1} . ЗатемсГ.вычитаегся из содержимого регистра 4 за счет того, что младший и все последующие разрядыtf c инвертируютйя, а в перенос двухвходового сумматора при прохождении младшего разряда добавляется единица. Таким образом, имеет Доп («Гд) Инв ((fg) + 2, которое и складывается с содержимым регистра. Далее описанный цикл повторяется, как только все приращения становятся равными нулю, то все протекает также, т.е. последовательво, начиная с младшего разряда регистра, его сопержимое поступает на двухвхоаовой сумматор ., а так как все приреопенвя равны нулю и, следовательно , tfg О, содержимое регистра не изменяется, за исключением того, что по сигналу с элемента 12 выключается схема сдвига последоватедтьного регистра. 1 О7« В соответствии с условием устойчивости рассогласование может менять знак, но,по амплитуде может только убывать в j вычислительном блоке, если на выходе этого устройства приращение не равно нулю. Следовательно , в результате вычитания 5; из содержимого регистра 4 возможны следуклдие случаи:

УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, содержащее группу вычислительных блоков по числу уравнений в системе, причем каждый вычислительный блок содержит п одноразрядных умножителей, Л -входовой су1иматор, двухвходовой сумматор, регистр.накопитель, первые входы одноразрядных умножителей соединены с инфсфмационными входами вычислительного блока, выходы одноразрядных умножителей соединены с входами п входового сумматора, выход которого подключен к первому входу двухвходового сумматора, информационный вход регистра соединен с выходом двухвходового сумматора, а выход - с вторым вхоЩ№л. двухвходового сумматора, отличающееся тем, что, с целью . -i Sfea.ihOViiHA повышения быстродействия, в него введен элемент И, а в каждый вычислительный блок - два триггера, два элагента И, элемент ИЛИ, элемент НЕ, причем в каждом м.1чиспительном блоке инфс маШЕОНные входы триггеров соединены с ш 1ходом двухвходового сумматора, а . равляющне входы триггеров - с управлякшщм входом вычислительного блотка, инверсный выход первого триггера соединен с первым входом первого злеМента И вычислительного блока, инверсный выход второго триггера - с первым входом второго элемента И вычислительного блока, прямой выхоц первого триггера - с,вторым входом второго элемента И вычислительного блока, пря(Л мой выход второго триггера - с вторым входом первого элемента И вычислительного блока, выходы элементов И вычислительного блока соединены с входами элемента ИЛИ, с вторыми входами однораэрядньтх умножителей, с информационными входами накопителя и с выходом р& вычислительного блока, вход элемента НЕ соединен с выходом элемента ИЛИ, 00 входы элемента И соединены с выходамги элементов НЕ каждого вычислительного блока, а выход - с управляющими входами регистра в наковпитепя каждого вычислительного блока.

О О

О

О Здесь X I ( - знак рассогласования в к-шаге, Х, (кн-1) - знак рассогласования в (K+l) -шаге, Х к-старший зна чащий разряд в К-шаге, Х (К+1)-стар ший значащий разряд в (К+1)-шаге. Звездочкой отмечена невозможная ситуа ция. +&Х (- ДХ|) - положительное (отрицательное) приращение на выходе i -го вычислительного блока. Старший и знаковые разряды сохраняют свое зна чение, в старшем разряде при положительном знаке появляется нуль или при отрицательном знаке - единица, и при изменении знака на отрицательный в ста шем знаковом разряде появляется нуль. В первом и третьем случае на следующе шаге вновь вырабатывается приращение на выходе вычислительного блока, а во втором приращение равно нулю. Полученное приращение, юЬк и предыдущее, поступает на соответствующие одноразрядные умножители , Г| и накопитель, где прибавляется к текущему значения неизвестного Х;. Этот процесс продолО О

О О

О О жается до тех пор, пока старшие разряды рассогласования во всех устройствах не станут равны нулю. Этот факт отмеч1ается тем, что на выходе элемента И 12 формируется сигнал, равный 1. Происходит это следующим образом. Приращения с выходов элементов И 7и 8 постзппают на элемент ИЛИ 9. На выходе этого элементу сигнал равен цулю только в том случае, если приращение равно нулю. Проходя через элемент НЕ , нулевой сигнал становится единичным И: если во всех вычислительных блоках приращения равны нулю, то на всех входах схемы совпадения стоят едишды и , следовательно, на выходе ее тоже будет единица. Эта единица сигнализирует о завершении итерационного процесса определения текущего разряда всех неизвестных. По этому сигналу, подаваемому на регистры 4 всех вычислительных блоков и накопители 10, происходит сдвиг содержимого регистра (рассогласования Зци накопителя (неизвестного) на один разряц в сторону старших разрядог. Далее прсщесс повторяется до тех й пока не будут получены неизвестные с з данной точностью. В качестве примера рассмотрим решение системы 0...9fo3 О.,.НЭ 1а,(о ;(-Q. 100000 . 0. X - 0.- 0tto Х H0.01-fO- 0 Точное решение Х 7,8, Х 4,7, В известие при использовании прИрашений весом 2° необходимо выполнит семь шагов и $эезупьтат будет равен X, .- - 5. Для данного устройства дварительно промасштабируем систему так, чтобы она не содержала рассогласований величиной больше двух. В наш на . Тогда случае в и в., умножим Л , 1,001111110, 5| %2 0110,011010, ДХ 1, ДЛ ° Подстаёляя в систему, получим новое значение рассогласования З -0,011101 Sg 2 0,100000010, ДХ 1,ДХ2 О. . На этом выполнение первого шага зака чивается. Так как старшие разртды Si si равны нулю, 1U -, ЛЛ2 ДХ О, ДХ 0 и второй шаг начинается со сдвига S 0,100011100,5 1,00000010 Х 1О, Х.2 00 система принимает W 0.100 000 Xji о.юрощоо. (ЮИХ -f О. Х 1.000000100 Приращения равныДХ - 0)С 1, подставляя в (2) и произведя вычисления , получим 5 « 1110ОО, S| 0.001010100. На этом выполнение вторсоо шага заканчивается. Третий шаг. начинается со сдвига, после сдв1(га пр1Н ращения остаются нулевые, производятся следукшшй сдвиг. В сумме их стало три, следовательно целая часть определена н после этого разряда фиксируется точка Х:, 1000. Х2 01QO. Однако приращения равны нулю, по этому производят еще один сдвиг. Приращения становятся равными Л Х 0, требуемая точность достигнута, то решение прекращается после выполнения операций третьего шага. Результат выпош1ения этого шага Х 10OO.O;Xj О1ОО..1 (Х; 8/ .5). Уже фактические на втором шаге требуемая точность достигнута (с учетом масштабного преобразований), но как пра вило, всегда выполняется на один шаг больше, чтобы заданная точность выполнялась наверняка. Таким образом, введение новьгх узлов и конструктивных связей позволило повысить быстродействие устройства. Чиоло шагов, необходимое дпя получения результата, приблизительно составляет логарифм от числа шагов в-известном устройстве.