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

 

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

СОЮЗ СОВЕТСКИХ

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

РЕСПУБЛИК

Зри 06 F 15/32

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬП ИЙ (2 1) 3460001/ 18-24 (22) 02. 07. 82 (46) 23.04.84.Бюп. М 15 (72) В.E.Çîëîòîâñêèé и P.В.Коробков (71) Таганрогский радиотехнический институт им.В.Д. Калмыкова (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР

34 682902, кл. G 06 F 15/32, 1979.

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

% 710044, кп. G 06 F 15/32,1980 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ

СИСТЕМ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, содержащее группу вычислительных блоков по числу уравнений в системе, причем каждый вычислительный блок содержит и одноразрядных умножителей, п»входовой сумматор, двухвходовой сумматор, регистр, накопитель, первые входы одноразрядных умножителей соединены с информационными входами вычис» литепьного блока, выходы одноразрядных умножителей соединены с входами пвходового сумматора, выход которого подключен к первому входу двухвходового сумматора, информационный вход регистра соединен с выходом двухвходового сумматора, а выход — с вторым входом. двухвходового сумматора, о т л и» чающее ся тем, что, сцелью, SU„„1088007 повышения быстродействия, в него введен элемент И, а в каждый вычислительный блок — два триггера, два элемента И, элемент ИЛИ, элемент НЕ, причем в каждом вычислительном блоке информационные входы триггеров соединены с выходом двухвходового сумматора, а управляющие входы триггеров - с управляющим входом вычислительного бло-. ка, инверсный выход первого триггера соединен с первым входом первого элемента И вычиспитепьного блока, инверс- т ный выход второго триггера - с первым входом второго элемента И вычислительного блока, прямой выхоа первого триггера - с,вторым входом второго элемента И вычислительного бпока, прямой выход второго триггера — с вторым входом первого эпемента И вычислительного блока, выходы элементов И вычислительного блока соединены с входами

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

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

1 1088007 3

Изобретение относится к автоматике жителей соединены с информационными

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

AX+ B 0 (1) вход регистра соединен с выходом двухИзвестно цифровое устройство для ре- входового сумматора, а выход — с вторым шеьщя систем алгебраических уравнений, входом двухвходового сумматора, ввекоторое содержит первую группу сумма- ð ден элемент И, а в каждый вычислительтора, выходы которых соединены с пер- ный блок - два триггера, два элемента И, вым входом блока памяти, второй вы- элемент ИЛИ, элемент НЕ, причем в ход которого соединен с первым входом каждс!м вычис!гитепьном блоке информаблока управления и второй группы.сум- ционные входы триггеров соединены с маторов, выходы которых через блок эле- 1 выходом двухвходового сумматора, а ментов НЕ соединены с блоком сдвига(13, управлякщ ие входы триггеров - с управНедостатком устрояства является низ- ляющим входом вычислительного блока, кое быстродействие. инверсный выход первого триггера соедиНаиболее близким по технической cym- нен с первым входом первого элемента И ности к изобретению является устройст- 20 вычислительного блока, инверсный выход во, amopoe содержит о элементов И, второго триггера — с первым входом д - входовой сумматор, двухвходовой второго элемента И вычислительного блосумматор, регистр, блок сравнения, блок Ка, прямой выход первого триггера - с формирования приращений и накопитель, вторым входом второго элемента И выпричем выходы схем совпадения соедине- g числительного блока, прямой выход втоны с входами и -входового сумматора, рого триггера - с вторым входом первовыход которого соединен с первым входом го элемента И вычислительного блока, двухвходового сумматора, второй вход прямой выход второго триггера - с втокоторого соединен с выходом регистра, рым входом первого элемента И вычисли» вход которого соединен с выходом двух«> тельного блока, выходы элементов И вы входового сумматора, кроме того, выход q числительного блока соединены с входасумматора соединен с входом схемы ми элемента! ИЛИ и с вторыми группами сравнения, а выход - с первым входом - входов одноразрядных умножителей, с блока формирования приращения, второй информациониыми входами накопителя и с вход которого соединен с выходом ре- выходом вычислительного блока, вход гистра, выход блока формирования при«

35 элемента НЕ соединен с выходом элеращений соединен с входом накопите- мента ИЛИ, входы элемента И соединены ля (23. с выходами инверторов каждого вычис

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

-fB ращения, равного 2, где m -дли- Исходная система на разрядной сетки. В связи с этим <+8 О В„у,, жняя оценка числа итерационных ша . 1 ф Я!* 5/ С 1! 2 1 бМ гов имеет вид, преобразую™ к виду

Н= Х,„„. 2", 4+1 где Х „= гои х,!, х2.. ... x„j- максималь5 =5 -dS

1с+М Ж 4+4 ! ное зйачение неизвестноя. +1 S

Целью изобретения является повыше- % Х ние быстродействия устройства. +1 O 0,<5 (1 ! $(Указанная цель достигается тем, что с- ! в устройство„ содержащее группу вычислительных блоков по числу уравнений 8+1 ф 9+1 1 ! в системе, причем каждый вычислительный Здесь Х, *->!,, Д Хк - вектора вида( к блок содержит и одноразрядных умножи- 55 V !.Y<,где У один из перечисленных пателей,:и — входовой сумматор, двухвхо раметров. довой сумматор, регистр, накопитель, irep. — Так как устойчивая работа возможна вые группы вхоцов одноразрядных умно- лишь при наличии отрицательной обратной

3 1088007- 4 свиэиф пд б +„должен быть Равен, укода,е ;., Доп Ь 2 . ПредполагаетМ пд"5 =ы 9

C другой стороны Stan Рх = gign5 и вход умножителей последовательным коХ к+1 4 к дом, т.е. Разряд за разрядом, начиная

\ Ь вЂ” с младшего. Таким образом, входы элеа p+p ъ „1 12 g1.g" 51 " д " у1., . ментов И в одноразрядном умножителе образуют первую. группу входов, а другие

То для устойчивой работы должно быть;, х ж входы тех же элементов И - вторую выполнено

I группу входов. Решение, т.е. неизвестная величина Х,формируется в накопителе 10, И 1=1 ) о " )О > rIIe реализуется операция Х1, =Х1+ X „ .О

- 1

К - номер итерации. Накопитель представНа чеРтеже пРедставлена стРУктУРнаЯ ляет собой обычный двоичный счетчик. схема устройства для решения систем Устройство работает следующим обраалгебраических управлений, где раскрыт

25 один вычислительный блок УстРойства. В регистры 4 каждого вычиспительУстРойство в каждом вычислительном ного блока заносятся, первоначально велибпоке содеРжит одноРазРЯдные Умножитепи ч22ны В fb g b 2 s дальнейшем

L „> 2. n) в дапьне шем

12, Q .. ° . 1„, -axoAoeoA сУмматор 2, рассогласование. Знак чисел + (=0,n)

20 5 двухвходовой сумматор 3, регистр 4, фиксируется перед самым старшим разряг» триггеры 5 и 6, элементы И 7 и 8, эле- дом. Старший разряд числа заносится в мент ИЛИ 9, накопитель 10, элемент ° триггер 5 по сигналу, поступающему на

НЕ 11, а также элемент И 12. управляющий вход триггера, знаковый

Выходы одноразрядных умножителей 5 разряд аналогично заносится в триггер 6.

1., 1......1, соединены с входами мно- В зависимости от содержания этих раэ-. говходового сумматора 2, выход которого рядов формируется либо положительное соединен с первым входом двухвходового приращение (01), либо отрицательное (10), сумматора 3, второй вход которого сое- либо нуль (00 или 11). Положительное: динен с выходом регистра 4, выход двух- приращение. формируется на выходе эле-.

30 входового сумматора 3 соединен с инфор-, . мента 8, а отрицательное приращение мационным входом регистра 4 и информа- появляется на выходе элемента И 7. По- ционными входами триггеров 5 и 6, управ- пученное-приращение посылается на упляющие входы которых соединены с равление соответствующего одноразрядвнешними входами вычислительного блока, . ного умножителя 1 (1 =О,п ), на вто-

» инверсный выход TpHrrepa 5 и прямой вы- рой вход элемента 1 поступает а". Ин1 . ход триггера .6 соединены относительно с формация в устройстве передается послепервым и вторым входами элемента И 7, довательным образом младаими разрядалрямой выход триггера 5 и инверсный i ми вперед. Так, пришелшие младшие развыход триггера 6 соединены соответстван- ряды коэффндяентов à нпн ux s>sasse40

3 но с первым н вторым. входом элемента "ннд умнопекпся на прн av>e>ss (т.е. проИ 8, выходы элементов И соединены со- . ходят на многовходовой сумматор 2, если ответственно с первыми и вторыми входа- приращение не нуль). Поступившие младми элемента ИЛИ 9 и накопителя 10, вы- шие разрядь2 коэффициентов складываются, ход элемента ИЛИ через инвертор 11 и соединен с одним нз п -входов элемента ..т.е. образуется вепненна убк с> .он

И 12, выход которого соединен с управляющим входами регистра 4 и накопите-,где ЬХ;=(+1,0-1 . Затем/,вычитае2 ля 10 каждого вычислительного блока ся из содержимого регистра 4 за счет устройства. Одноразрядный умножитель того, что младший и все последующие цредстажяет с бой схе у 2И-ИЛИ Пер- 50 разрядыд> иертируся а в перенос вый вход первой схемы соединен с вы- двухвходового сумматора при прохождеходом второго элемента И 8 (не показа- нии младшего разряда добавляется единино), а на второй вход подаются биты . ца. Таким образом, имеет J3oII (d"с;) соответствующего коэффициента )4„. ), д Инв (cfà ) + 2, которое и складываетв дополнИтельном коде, первый вход вто- 55 ся с содержимым регистра. Далее описан.Рой схемы И соединен с выходом первого ный цикл повторяется, как только все элемента И 7 (не показано), а на второй приращения становятся равными нулю, то вход подаются разряды дополнительного все протекает также, т.е. последователь1088007

Xgg .Х,(K+1) Xz= (K+1) + Д Х,.

-дХ °

Х1к

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

1

О

1, О

О

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

Здесь Х - знак рассогласования в к-шаге, Х„, (к+1) — знак рассогласования в (К+1) -шаге, Х -стараий значащий разряд.в К-шаге, Х2 (K+1)-старший значащий разряд в (К+1)-шаге.

Звездочкой отмечена невозможная ситуа. ция. + Ь Х; (- и Х ; ) - положительное

{отрицательное) приращение на выходе

i -ro вычислительного блока. Старший и знаковые разряды сохраняют свое зна-. чение, в старшем разряде при положительном знаке появляется нуль или при отрицательном знаке — единица, и при . изменении знака на отрицательный в старшем знаковом разряде появляется нуль.

В первом и третьем случае на следующем о шаге вновь вырабатывается приращение на выходе вычислительного блока, а во втором приращение равно нулю. Полученное приращение, к@к и предыдущее, поступает на соответствующие одноразрядные умножители I g накопитель, где прибавляется к текущему значения неизвестного Х;. Этот процесс продолВ соответствии с условием устойчивости рассогласование может менять знак, но,по амплитуде может только убывать

s j м вычислительном блоке, если на выходе этого устройства приглашение не равно нулю. Следовательно, в результате вычитаниями 5 из содержимого регистра 4 возможны следующие случаи:

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

И 7и 8 поступают на элемент ИЛИ 9.

На выходе этого элемента сигнал равен нулю только в том случае, если приращение равно нулю. Проходя через элемент НЕ, нулевой сигнал становится единичным и. если во всех вычислительных блоках приращения равны нулю, то на всех входах схемы совпадения стоят единицы,и, следовательно, на выходе ее тоже будет единица. Эта единица сигнализирует о завершении итерационного процесса определения текущего разряда всех неизвестных. По атому,сигналу, подаваемому на регистры 4 всех вычислительных блоков и накопители 10, происходит сдвиг содержимого регистра (рассогласования S K и накопителя (неизвесттного) 1088007

7 на один раэряц в сторону старших разрядов.

Далее процесс повторяется до тех nqp, пока не будут получены неизвестные с заданной точностью. В качестве прймера рассмотрим решение системы

ОЛ1 х +0.51Х =9.9ЬЗ

О 31х„+0,85х =Ь.И3

0,111 ИО Х„+ О, 100000 Х2= 1001.«« 0

0,010011 g „+ O.È0È0 X . = 110.01<010

Точное решение Х1 = 7,8, X2 = 4,7, В известном при использовании приращений весом 2о необходимо выполнить семь шагов и результат будет равен

Х =7, Х = 5. Для данного устройства предварительно промасштабируем систему так, чтобы она не содержала рассогла- ®О сований величиной больше двух. В нашем случае в. и в2 умножим на 2 9. Тогда

5„=Ь„= 1,001111110»

Я =Ъ2= 0110,011010, Х =1 6 =0.

Подставляя в систему, получим новое значение рассогласовш ия.9 =0,011101110

52 = Ъ2» 0.100000010, ЬХ = 1,М2= О.

На этом выполнение первого шага закан- З0 чивается. Так как старшие разряды 9 и

9 равны нулю, то дХ = О, hX2 =О, и второй шаг начинаетс.я со сдвига

S„ = О,10ОО11100, S =1,ОООООО1ОО, X 10, Х2 = 00 система принимает 35 вид

О.ФИ egg +0,100 000 х = 0,100011100. (i1

0.11011 X, + О. 110114 Х2 =.1. 000000100

- Приращения равными (1 = О,ЛКу 1, подставляя в (2) и произведя вычисления, получим S2 OeGO0111000, 32

= 0,001010100. На этом выполнение второго шага заканчивается. Третий шаг . начинается со сдвига, после сдвига приращения остаются нулевые, производится следукяций сдвиг. В сумме их стало три, следовательно целая часть определена и после этого разряда фиксируется точка

Х 1000, Х = 0100.

Однако приращения равны нулю, поэтому производят еще один сдвиг. Прира- щения становятся равными д Х1 О, ДХ2 = 1. Так. как требуемая точность . достигнута, то решение прекращается пооле выполнения операций третьего шага., Результат выполнения этого шага х„— 1ооо.о х - 01001 (х„— в, X2 = 4,5).

Уже фактические на втором шаге требуемая точность достигнута (с учетом масштабного преобразования), но как нраaimo„ece e eb e ee He e mar больше, чтобы заданная точность выпол нялась наверняка.

Таким образом, введение нощах узлов и конструктивных связей позволило поL высить быстродействие устройства. Чио;ло шагов, необходимое для получения результата, приблизительно составляет лога- рифм от числа шагов в-известном уст» ройстве.

1088007

Сост авитель И. Пчелинцев

РеДактор Н.Пушненкова Текред И.Метелева

Корректор Ю.Макаренко

Подписное

Филиал ППП Патент", г.Ужгород, ул.Проектная, 4

Закэ 2674/46 Тираж 699

BHHHIlH Государственного комитета СССР о делам изобретений и открытий

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