Устройство для вычисления значений полинома

 

Изобретение относится к ; ычислительной технике и может бъгть ис:пользовано для аппроксимации JYHKUV; м.:-тодом Горнера з устройствах (5брабг)Тки информации. Цель изобретения - расширение функциональных возможностей за счет вычисления обобщенных полиномов. С этой целью в устройство , содержащее регистры 1-3, триггеры 15-18, регистрльтиплексор 19, элементы И 20, 21, коммутатор 22, сумматор 23, блок 24 умножения, блоки 4, 6 памяти и счетчик 8, введены схемы 12, 13 сравнения, блоки 5, 7 памяти, счетчики 9-11 и вычитатель 14 единицы с соответствующими связями . Уст ройгтВ Т в1.;-1ИСЛ5|ет значение 5 o6o6i:ieHHoro полинома Г (х, «X, ... X, а,), где а, - i-й Kc:-)q tJiiime rr полинома; S (j 1,п)- с азателг) степени j-ro аргумента при i-M ко ффициенте. 3 ил. (Л с 00 00 to

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

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

РЕСПУБЛИН

А1

„„SU„„1348821 с 11 1 Г 06 Р 7/544

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К A BTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 4005353/24-24 (22) 03.01.86 (46) 30.10.87. Бюл. М- 40 (71) Одесский политехнический инстиу г (72} В.А.Парасо. кин, Е.Л.Пс лип, В.Г.Ткаченко и А.В.Дрозд (53) 681.325(088.8) (56) Авторское свидетельство СССР

Ф 962973, кл. G 06 F 15/31, 1982.

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

Р 1305670, кп. (06 ; 7/544, 1985. (5 ) устРойотво,ля зычисл1,н1,я ПА 1Р—

НИЙ ПОЛИНОМА (57) Изобретение относится к вычислительной технике и може быть н:и, льзовано для аппроксимации функций м-тодом Гориера в устройствах обраб тк информации. Пель изобретения расширение функциональных возможностей эа счет вычисления обобщенных полиномов. С этой целью в устройство, содержащее регистры 1-3, триггеры 15 — 18, регистр-мультиплексор 19, элем нты И 20, 21, коммутатор 22, сумматор 23, блок 24 умножения, блоки, 6 памяти и счетчик 8, введены схемы 12, 13 сравнения, блоки 5, 7 памяти, счетчики 9-11 и вычитатель

14 единицы с соответствующими связями. t р, йс тв Blьчи "и е г значение

5 обо ги нного полинома F = (х х,, ... х а), где а. к ".: . пциент гопинома; S (j = 1,п) — а

> 1 .. . - ь и ватель степени „1 — г аргументcl при ко=л;1 ициен ге 3 и

1348827

5 52, P = (х х

2 х а ), где а — -й коэффициент поли1 н(1!» } !

S (3=1„!!) и«!»за(F пь сгепени

- т-(i аргумента при . -м к«эффициенте.

Например, для случая трех аргументов х — х для IF« горьгх мак<.и1 r< 1 мальные показатели степени заданы равными соответственно 2, 1, 1, обобщенный полином имеет 12 членов с коэффицие!»тами à.(i =- 1, 12):

2 1 1 1 1 2 3

12 1 } 3 1. } а х

Ч а х х + }

+ а х

1(} о а а

+ а х х х + а х х х + (» 2 3 1 2. 3

1 а а

+ахх.х+ а„ххх+

6 - 3 5 1 2 3 о а 2 0 О

+ а х х х, + а х х х +

3 2 ь

+ а х } 1 (! O х, х о а а

+ а х х х

1 1 r} 3 вычисляемый TT устр«йст!»с и<. ф(1рмуле (((а х, - 7 ) х, !

2 1

+ а )х +

»о а 1 х + а)х+ ((а х + ь !

+ (а

Изобретение «г!»ое ится к вычислг1тельной технике и может быть использог<а!»о для аппроксимации функций ме.оцом Г(.„ нера « устройствах обработки информзции.

Цель изобретения — расширение фу«в

»

На фиг.1 показана функцио«альная схема устройства; на фиг.2 и 3 структура регистра-мультиплексора и первого триггера соответственно.

Устройство содержит регистры 1-3, блоки 4-7 памяти, счетчики 8-11, схемы 12, 13 сравнения, вычитатель

14 единицы, триггерь1 15-18,регистрмультиплексор 19, элементы И 20, 21, коммутатор 22, сумматор 23, блок 24 умножения, информационный выход 25 устройства и выход 26 сигнала окончания вычислений. Регистр-мультиплексор (фиг.2) и первый триггер (фиг.3) содержат регистры 27, 28, коммутатор

29, элемент ИЛИ 30 и триггер 31.

Устройство вычисляет значение обобщенного полинома

+ а )х + а )х + (а х + à )x +

5 1 4 1 2 с

+ а

Г

В процессе вычисления выделяется ряц этапов, количество которых равно числу аргументов.

На первом этапе в приведенном

10 примере вычисляется второе поколение коэффициентов полинома: Ь (j к„„.„, < ТЛ при этом Ь = (a х, + а,„ )х, + а, Ь = (ах +а)х +а

3 <3 1 8 1 7

b2 = (а,x, + а5)х1 + а4

b,=-(ах,+а)х,+а, ? I» и полином приобретает вид

Р = (Ь х + Ь )х + Ь х + Ь

3 3 2. 2

На втором этапе вычисляется третье поколение коэффициентов полинома (8 ма(<с ) (!<ма«30

+ 1)) При этом С вЂ” Ь x + Ь и С 3

Ь х2 + Ь, и!<олином P С x + С,.

2 3

На третьем этапе вычисляется следущее поколение (для данного примера окончательное значение полинома) коэффициентов полинома.

Перед началом работы устройства

40 в регистр 1 записывается число аргументов обобщенного полинома, в блоки

4, 5 памяти — последовательность максимальных показателей степеней

<(<:т .(еc Tвляp гс-я путем тактирования

".-л !ко«2-4, 8, 9, 11, 15-19 одной синхрочастот ой (на фиг. 1 цепи синхро-

«.!:зации не показаны) .

Разбиение процесса вычисления

IT,линома «а этапы происходит по состоянию счетчика 9: 1:.улевому состояаргументов, дополненная числом, на

45 единицу меньшим количества аргументов, в блок 6 памяти — последовательность коэффициентов полинома а, ан а, в блок 7 памяти — и эследователь;!ость аргументов х 1, х,...х и

Счетчики 8-11 и триггеры 15-18 сбрас(:«,»ются I! нулевое состояние.

Синхр«низация работы устройства

1с >488 нию соответствует первый этап, гc р вому — второй и т.д. На каждом этапе вычисляютсе< коэффициенты соответс гвующего поколения. Вычислением коэф5 фициентов управляет сигнал с вь<хо; 3

<-peããåðà 16. В течение интерва.тов с нулс вым значеттием сигнала вы 111 .— ляются отдельнь<е коэффициенты, к т. орые при последующем единичном зна те— нии сигнала записываются B блок 5 памяти. По окончании записи очеред-. ного ко-.-ффициента состояние счетчи-ка 1О, определяющего адрес записи, увеличивается на единицу. Считывание 1В коэффициентов происходит по адресам, определяемт.тм счетчиком 11. Этот счетчик изменяет свое состояние с частотой синхронизации, исключая время записи коэффициентов, когда восприятие у0 синхросигналов запрещено сигналом с выхода триггера 15.

Вычисление первого коэффит;иентя следующего поколения начинается сО считьгвания и< p1<ого коэффици < l а из ?. блока 6 памяти. К этому моменту регистр 2 сброшен в ночь сигналом с выхода элемента И 20 и нулевой код с выхода блока 24 умножения поступает на вход сумматора 23 . Считантп,<й к<ээ<1>- 30> фици нт с вы>.отта сумматора 2 > 3 я:тисывается в кс нцз такта в регll< тр

В следующем такте этот ко. ф<«.-,цттс нт домножается в блоке 24 умноже<1<н:та значение аргумента и pEçóëüò"=. складывается на сумматоре 23 с очерс <ным считанным из блока 6 гамяти коэффт

5 считывян>тсн коэффициенты, необходимые, тя определения очередного коэф- 4Б фициента следующего поколения. Таким образо"l, к началу режима записи регистр 2 принимает значение коэффивиен-.е следующего покления, В этот момент ит чал на управляющем вхо- 5р де бчока 5 памяти принимает единичнс е эетачеег<те, соответствующее режиму записи, Затем вычисленное значение коэффициента следующего поколения пе— реписывается из регистра 2 в блок 6 т амя -v, Запись происходит через старшие разряды коммутатора 22, на управляющий .-.ход которого поступает сигнал с 1<>c<> à триггера 16. Через

М Ч ацттт>1 Р i <а 3 Р Н Г< Ы > т» Г О Ж Р КОММ, т а Т ОР а н; блок 6 памяти подается адрес с выхс да с гетчика 10 или счетчика 11 при

3-,11<О>1 >тли считывании к;>-зффипиентов < тс твенн<>

< <рт ухтетттсзт «»Стут..ЕЮт На ВХОД бЛОКа

24 у><но>< е<гия иэ бл«ка 7 пат-тяттт. При

3 ".!M c ÷è Tûâà11èå аргумента происходит по, тдресу, поступакшему со счетчика

9,. На первом этапе считывается первы<1 аргумегтт, на втором этапе — второй аргумент и т.д.

Описанегый процесс вычисления полинома обеспечивается рядом управляющих сигналов, которые формируются в ходе обработки последовательности максимальных 1 окязателей степени, БЛ<>К 5 ПаМЯтн В ПРОЕ>РССЕ ВЬГЧИСЛЕ1:.ин полиномя работает только в режим с<титывяния. Блок 4 памяти под дей—

Г гнием синхросигналов, управляющих р:-жимом записи и чтения, выполняет с.. игьтвятнте и запись информации соотве т. <:и< ><но . пс рвой и второй половитакта работы устройства. Считаняс < значение показателя степени н",. 111 шается на единицу на вычитателе

14 единицы >т в конце первой полови1<ы тя -.тя запиГ.» аетГя через первый

111 .13<<но .ный в.сод в регигтр-муль-ттг< <с н .. < 1"-. +E. ðc"3 . т(р<>й информа<ь и т=..с-, B р< г< .с .; ÷ льтип.<ексор тс Ч (Э 1<С1 сЕ< а < т- Н Мст Н Гттт <Я>т l, I<(<3 3 Нсз стевЂ! 1 . K < зсзтС с< 1 Г ГРГ<< НИ. <1сз т<ыход ги<.тра-мул ьтиплексс ря 19 выдается

Одно из значений ;оказателя степени в эависимОсти от значения поступающег<.- тт<т управляющий вход сигнала.

Этот сттгнал формируется триггером

13, ;отс:рый Объединяет »а входе ИЛИ сит палы к<>да с выхс<да блока 4 памяти, и устанавливается по фронту синхросиг нала в единичное состояние, если результат объединения равен нулю.

Во второй половине такта осуществляется запись показателя степени с в !>с< да регистра-мультиплексора 19 в блок 4 гамяти. Таким образом с каждым тактсм считываемое из блока 4 памяти -(начение показателя степени уменьшается на едитттттту, а при достижентттт нулевого значения в блок 4 памяти записываетсн исхо,.нс Р максималькое энячеттие показателя степени, считяннс.е из блока 5 гтямяти. I ëèíè÷íîå зт ачение сигнала на вьтх<эдР триггера

13,и, зтттткяк>1<ее H результате Гчитьт5

134 вания нулевого показателя степени) поступает на вход разрешения счета счетчика 8, который под действием синхросигналов, увеличивает свое значение на единицу. Значение счетчика

8 поступает на адресные входы блоков 4, 5 памяти. Увеличение значения адреса приводит к обработке показателя степени следующего аргумента.

Если значение этого показателя также равно нулю, то триггер 15 остается в единичном состоянии, разрешая дальнейшее увеличение адреса на выходе счетчика 8 и переход к показателю степени следующего аргумента. Если значение показателя степени отлично от нуля, то триггер 15 переходит в нулевое состояние. Вслед за ним переходят в нулевое состояние триггер 1б и затем триггер 17, сдвигающие сигнал с выхода триггера 15 соответственно на полтакта и на такт. При этом первый элемент И 20 выделяет единичный импульс на интервалах времени, когда триггеры 16 и 17 принима ют соответственно нулевое и единичное значение. Этот импульс используется для записи в счетчик 8 значения с выхода счетчика 9. Записываемое значение с,,впадает с номером этапа вычисления полинома. Кроме того, импульс сбрасывает в ноль регистр 2 в начале вычисления каждого коэффициента следующего поколения.

Каждый этап заканчивается после считывания из блока 4 уменьшенного до нуля показателя степени последнего аргумента. При этом значение адреса блока 4 с выхода счетчика 8 сравнивается на схеме 12 сравнения со значением регистра, храьяше"o количе— ство аргументов. Б результате совпадения этих значений схема 12 сравне-с: ния вырабатывает импульс, поступающйй на вход разрешения счетa счетчика 9 и информационный вход триггера

18. С выхода триггера 18 сигнал поступает на вход элемента И 21, на котором стробируется сигналом с выход» элемента И 20. Полученный сигнал с выхода элемента И 21 поступает на входы сброса счетчиков 10, 11, обеспечивая запись и считывание коэффициентов всех последующих поколEний с нулевого адре а блока б памяти. С приходом на вход разрешения счета счетчика 9 импульса с вь хода схемы

12 сравнения,:.че- *II «;величивает

8827

40

35 свое значение, что означает начало нового этапа. Значение с выхода с-летчика 9 поступает на вход схемы 13 сравнения, где сравнивается со значением кода на выходе регистра 1. При совпадении значений вырабатывается признак окончания вычисления полинома. По переднему фронту этого признака значение полинома переписывается из регистра 2 в регистр 3, формул а изобретения

Устройство для вычисления значений полинома, содержащее три регистра, четыре триггера, регистр-мультиплексор, первый и второй элементы

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

Bl tl,>îI о блока I<;lMÿòè, с инверсным вхопервого элемента И и с информа.,иончым входом третьего триггера, выход которого соединен с прямым вхо-

;,ом первого элемента И, выход которогп соединен < входом приема информации первого счетчика, с входом

1348827

Составитель Н.Матвеев

Техред А.Кравчук

Корректор И.Демчик

Редактор Н.Слободяник

Заказ 5191/48 Тираж б70 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

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

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

10 четвертого триггера соединен с вторым входом второго элемента И, выход второго регистра соединен с третьим информационным входом коммутатора и с информационным входом третьего ре15 гистра, выход первого регистра соединен с вторыми входами первой и второй схем с равнения, в ыход в то рой схемы сравнения соедине) с синхровходом тре— тьего регистра и являетсявыходом призр0 нака окончаниявычисления устройства.