Устройство для вычисления значений полинома Советский патент 1987 года по МПК G06F7/544 

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

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

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

Устройство содержит регистры 1-3, блоки 4-7 памяти, счетчики 8-11, схемы 12, 13 сравнения, вычитатель 14 единицы, триггеры 1 5--18,регистр- мультиплексор 19, элементы И 20, 21, комк татор 22, сумматор 23, блок 24 умножения, информационный выход 25 устройства и выход 26 сигнала окончания вычислений. Регистр-мультиплексор (фиг.2) и первый триггер (фиг.З) содержат регистры 27, 28, коммутатор 29, элемент ИЛИ 30 и триггер 31.

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

р Е: (х/

X,

X

г де

J(

а -

(,n)

коэффициент полинома 5

1эате,пь степени j-TО аргумента при i-M коэффициенте. Например для случая т рех аргу- , для которых макс.и- мальные показатели заданы равными соответственно 2, 1, 1, общенный полином угмеет 12 членов с

ментов X Р

вычисляем1.1Й в устройстрзе nt, фс муле

Р - (((а„х, - а ) X, а )х - (a,jX, п) х,4 а,)х, ((а,х, 3488272

+ а5)х,+ а)х (, + а,)х,

а,.

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

На первом этапе в приведенном примере вычисляется второе поколение коэффициентов полинома: b (j Т,(3,„ -ь и... ( + 1)), при этом Ь (а,,х + а )х, -(- а , ,

Ч Т 2 (а, X, -ь а.)х, а,

Ь, (, -1- а)х -(- а,

и полином приобретает вид Р (, -- b,|)Xj -н , -«- Ь .

25 На втором этапе вычисляется третье поколение коэффициентов полинома

С., (k 1, (S

30

+ 1)...(8„,,,

+ 1

При этом С Ь х -t- bj и С 3 - Ь, и полином Р С X ,.

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

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

в регистр 1 записывается число аргументов обобщенного полинома, в блоки 4, 5 памяти - последовательность максимальных показателей степеней аргументов, дополненная числом, на

единицу меньшим количества аргументов, в блок 6 памяти - последовательность коэффициентов полинома а , а , .,., а , в блок 7 памяти - последовательность аргументов х, x,j, ...х

четчики 8-11 и триггеры 15-18 сбра- смваются н нулевое состояние.

Синхронизация работы устройства ас чиествляегея путем тактирования локов 2-4, 8, 9/11, 15-19 одной

синхрочастоюй (на фиг.1 цепи синхро- н -;зации не показаны) .

Разбиение процесса вычисления олинома на этапы происходит по сотоянию счетчика 9: нулевому состоя

нию соответствует первый этап, первому - второй и т.д. На каждом этапе вычнсляютс.ч коэффициенты соответствующего поколения. Вычислением коэффициентов управляет сигнал с Bbrxoad триггера 16. В течение интервалов с ну, значением сигнала вычисляются отдельные коэффициенты, KI то- рые при последующем единичном эначе- НИИ сигнала записываются в блок 6 памяти. По око)чании записи очередного коэффициента состояние счетчика 10, определяющего адрес записи, увеличивается на единицу. Считывание коэффи11 1ентов происходит по адресам, определяем1.1м счетчиком 1 1 . Этот счетчик изменяет свое состояние с частотой синхронизации, исключая время записи коэффициентов, когда восприятие синхросигналов запрещено сигналом с выхода триггера 15.

Вьшисление первого коэффициента следующего поколения начинается со считьтания nei;r-oro коэффицтгсч i а из блока 6 памяти. К этому моменту регистр 2 сброшен в ноль сигналом с выхода элемента И 20 и нулевой код с выхода блока 24 умножения поступает на вход сумматора 23. Считанный коэф фициент с выхода сумматора 23 сывается в конц такта в регистр 2. В следующем такте этот )..:ц11С:Нт домножается в блоке 24 умножен1;я па значение аргумента и результа: скла-- дывается на сумматоре 23 с очередным считанным из блока 6 памяти коэффициентом. Полученная сумма записывается в конце такта в регистр 2,

На управлений вход (заггись/чтс- н::е) блока 6 памяти подается сигнал с выхода триггера 16. При нулевых знчениях этого сигнала из блока памяти 6 считывакугся коэффициенты, необходимые , определения очередного коэф фициента следующего поколения. Таким образом, к началу режима записи регистр 2 принимает значение коэффи- ш :ен71 следующего покления. В этот момент сигчал на управляющем вхо- де блока 6 памяти принимает единичное значение, соответствующее режиму записи. Затем вычисленное значение коэффициента следующего поколения переписывается из регистра 2 в 6 ггамятИг Запись происходит через старшие разряды ко гмутатора 22, на управляющий чход которого поступает сигнал с выхода триггера 16. Через

2

5

5 0

0 5 g g

7

/разряды этого же коммутатора lUi блок 6 памяти подается адрес с выхода счетчика 10 или счетш1ка 11 при :1-Ч11Иси или считывании К(,)эффиц11ентов i U ;гпет: твенно .

Аргументы 11осту1т- ют на вход блока 24 умноже1гия из блока 7 памяти. При эт;.м считывание аргумента происходит по адресу, поступающему со счетчика 9,. Па первом этапе считывается первый аргумент, на втором этапе - второй аргумент и т.д.

Описан}&1Й процесс вычисления полинома обеспечивается рядом управляющих сигналов, которые формируются в ходе обработки последовательности максимальных показателей степени.

Блок 5 памяти в процессе вычисле- -ия полинома работает только в режиме считывания. Блок 4 памяти под действием синхросигналов, управляюш 1х режимом записи и чтения, выполняет счит)11ван1ге и запись информации соот- ррт; Tj. MiHo в пс-рвой и второй полови- К(-. т акч-а работы устройства. Считанное: значение показателя степени .щaeтcя на единицу на вычитателе 14 единицы И в конце первой полови- fci такта запиг ирлетгя через первьй и|;.п 1:1мят;ионнь й вход в регистр-муль- игпсксср 1. .т- рой информа1;гГ ч;;|,Й ВХОД В р Р ) ИС Тр -bivji ьТИЦЛеКС ор

14ч; пись вас тся максимальи е чначе- :. казателя степени. На иыход ре- гигтрл-мультиплексора 19 выдается одно из значений показателя степени в зависимости от значения поступаю- щег о на упрлвляюиуий вход сигнала. Этот сигнал фор№1руется триггером 15, котс:рый объединяет на входе ИЛИ сигналы кода с выхода блока 4 памяти, и устанавливается по фронту син- хросигнапа в единич:ное состояние, если результат объединения равен нулю.

Во второй половине такта осуществляется запись показателя степени с выхода регистра-ьгультиплексора 19 в блок 4 памяти. Таким образом с каждым тактом считываемое из блока 4 памяти значение показателя степени уменьшается на единицу, а при дости- жеь:ии нулевого значения в блок 4 памяти записывается исходное максимальное значение показателя степени, считанное из блока 5 пямяти. Елиничное 31 ачрние сигнала на выходе триггера

15(г лзникаю .цсе н результате гчитывания нулевого показателя степени) поступает на вход разрешения счета счетчика 8, который под действием синхросигналов, увеличивает свое значение на единицу. Значение счетчика 8 поступает на адресные входы блоков 4, 5 памяти. Увеличение значения адреса приводит к обработке показателя степени следующего аргумента. Если значение этого показателя также равно нулю, то триггер 15 остается в единичном состоянии, разрешая дальнейшее увеличение адреса на выходе счетчика 8 и переход к показателю степени следующего аргумента. Если значение показателя степени отлично от нуля, то триггер 15 переходит в нулевое состояние. Вслед за ним переходят в нулевое состояние триггер 16 и затем триггер 17, сдвигающие сигнал с выхода триггера 15 соответственно на полтакта и на такт. При этом первый элемент И 20 выделяет единичный импульс на интервалах времени, когда триггеры 16 и 17 принима ют соответственно нулевое и единичное значение. Этот импульс используется для записи в счетчик 8 значения с выхода счетчика 9. Записываемое значение ГУ.впадает с номером этапа вычисления полинома. Кроме того, импульс сЬрлсывает в ноль регистр 2 в начале вычисления каждого коэффициента следующего поколения. Каждый этап заканчивается после считывания из блока 4 уменьшенного до нуля по1 зателя степени последнего аргумента. При этом значение адреса блока 4 с выхода счетчика 8 сравнивается на схеме 12 сравнения со значением регистра, хранящего количество аргументов. В результате совпадения этих значений схема 12 сравнеШ1Я вырабатывает импульс, поступаю- щ1тй на вход разрешения счета счетчика 9 и информационный вход триггера 18. С выхода триггера 18 сигнал поступает на вход элемента И 21, на котором стробируется сигналом с выхода элемента И 20. Полученный сигнал с выхода элемента И 21 поступает на входы сброса счетчиков 10, 11, обеспечивая запись и считывание коэффициентов всех последуюп1их поколений С нулевого адре а блока 6 памяти. С пртсодом на вход разрешения счета счетчика 9 импульса с выхода схемы

12 сравнения,

счетчик

1величивает

5

0

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

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

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

информационным входом устройства, отличающееся тем, что, с целью расширения функциональных возможностей за счет вычисления обобщенных полиномов, в него введены две схемы сравнения, третий и четвертый блоки памяти, с второго по четвертый счетчики и вычитатель единицы, выход которого соединен с первы 1 информационным входом регистра-мультиплексора, выход которого соединен с информационным входом первого блока памяти, выход которого соединен с информа1Ц1оннь1ми входами вьгчитателя единицы и первого триггера, выход второго триггера соединен со счетным входом третьего счетчика, первыми уп- райляющими входами коммутатора и BTCjiJ oi o блока памяти,.: инверсным вхо- ,; перврго элемента fi и с информа- 1ИОННЫМ входом третьего триггера, выход которого соединен с прямым вхо- ;i,oM первого элемента И, выход которого соединен г входом приема информации первого счетчика, с входом

0

Ь

0

5.

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

СИ

19

5

10

, 15 20

3488278

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

4

27

Г

29

li

28

(Риг. 2

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

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

Техред А.Кравчук Корректор М.Демчик

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

ВЫИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москзп, Ж-35, Раушская наб., д.4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4

Фиг. 3

Изобретение относится к ; ычисли- тельной технике и может бъгть ис:поль- зовано для аппроксимации 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