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

01.

со

00

J

00

315

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

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

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

Устройство содержит триггеры 1-9, элементы И 10-1, счетчики 15-17, блоки 18-21 памяти, группы 22 и 23 элементов И, элемент ИЛИ 2k, сумматоры 25 и 26, коммутаторы 27-30, регистр-мультиплексор 31, регистры 32- 35, умножители 36 и 37, входы и выходы 42 и 3 устройства.

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

Y i:a,

л

где J - Номер члена полинома;

п - максимальный показатель степени аргумента-,

а; - j-й коэффициента полинома. X - аргумент, по формуле

Y .х((...(а,|., н- а. )х;

X

Кр(

+ . . . + а, )х + а,) + Р -Kp-i

(. .. (ар X

е; г.е;

g, ;(

... + ag, )х +

р

п при четной степени по- 40 нома;

р

35

п 1 + 21. Ри нечетной степе(1

ни полинома, где а . - коэффициент полинома

п;

kj, 1; - коэффициенты, равные 2 или 4 Р - число членов разложения, п/4 в за8 1симости от числа нулевых коэффици- ентов.

Устройство работает следующим образом.

В исходном состоянии в блоке 21 памяти размещены значения коэффици- ентов полинома с нечетными индексами

р , а р..

U5:: k;

; 0

, а, исключая

коэффициенты с нулевыми значениями. Располагаются коэффициенты, начиная с нулевого адреса, в порядке убывания коэффициентов. По нулевому адр

су записан коэффициент а р ,

Аналогично в блоке 20 памяти размещены значения коэффициентов полинома

с четными индексами а р , а -, ,

..., а, а также исключая коэффициенты с нулевыми значениями. По нулевому адресу записан коэффициент

-S р. I f- 1

в блоках 18 и 19 памяти записан Р кодов, причем в первом разряде блока 18 хранится последовательность значений, соответствующих коэффициентам с четными индексами в порядке их убывания, начиная с коэффициента I ,

ар , и равных нулю для нулевых ко- Z-e;

1 1

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

К;

0

5

0

5

В первом разряде блока 19 хранится последовательность значений, соот- -ветствующих коэффициентам 1 в порядке их убывания, начиная с коэффициента 1р, и равных нулю, если коэффициент равен 2, и единице, если - k,

Во втором разряде блока 19 хранится аналогичная последовательность значений, поставленная в соответствие коэффициентам k; в порядке их убывания, начиная с коэффициента kp.

Счетчик 15 находится в нулевом состоянии.

На вход 40 устройства поступают . синхроимпульсы (си), тактирующие работу устройства. Выход заема счетчика 15 находится в нулевом состоянии и разрешает Прохождение СИ через элемент И на синхровходы регистра- мультиплексора 31 и регистра 33 и ус- тановку триггеров 7 и 8 в единичное состояние. На вход 39 поступает сиг-

нал Пуск, по которому триггер 1 вырабатывает импульс Т1 длительностью, равный периоду СИ. Импульс Т1 поступает на вход триггера 2, входы сброса регистров 32 и 3 и управляющие входы регистра-мультиплексора 31 и коммутатора 28. Триггер 2 под действием импульса Т1 вырабатывает импульс Т2, поступающий на соответствующие входы блоков 31 и 32, 3 и 28 и на вход триггера 3, импульс ТЗ с выхода которого устанавливает счетчики и триггеры k и S в исходное

20

состояние. При этом выхОд заема счет- |5 ков -20 и 21 памяти с началом следующего такта, код с выходов блоков 18 и 19 памяти поступает на информационные входы триггеров А, 5 и 7, 8 соответственно и записывается в них в новом такте.

Нулевое значение сигнала заема счетчика 15 вновь разрешает прохождение СИ на синхровход регистра-мультиплексора 31, принимающего к моменту времени t значение аргумента х1. Импульс т с выхода триггера 9 поступает на управляющий вход коммутатора 27, обеспечивая на время действия импульса т4 подключение выхода регистра 32 к входу сумматора 26, на другой вход которого поступает результат до- множения кода с выхода регистра З на значение аргумента х1. С выхода сумматора 2б значение полинома п-й сте- пени записывается в регистр 35 по заднему фронту импульса тА. Передний фронт импульса ТА сообщает о возможности подать на вход 38 аргумента устройства нового значения аргумента х2 для вычисления полинома п-й степени с прежними коэффициентами, о завершении вычисления полинома п-й степени.

чика 15 переходит из нулевого состояния в единичное и разрешает прохож- дение СИ через элемент И 10 на вычитающий вход счетчика 15, первые входы элементов И 1-1 и 12 и синхровходы блоков 18 и 19 памяти, а также запрещает прохождение .СИ на синхровход регистра-мультиплексора 31 в процессе счета счетчика 15. При этом, в момент времени t в регистр-мультиплексор 31 25 записывается значение аргумента х1, которое поступает на входы умножителя Зб, в результате чего значение х12 записывается в регистр-мультиплексор 31 через его второй информационный вход в момент времени t, одновременно значение х1 с выхода регистра-мультиплексора записывается в четвертый регистр 33.

Аналогично, во время tj с t t формируются значения х1 и xl.

Импульсами Т1 и Т2 регистры 32 и З обнуляются до момента tq. Коэффи30

циенты а р

е;

а р

I ц- 21 К ;

складыва40

ются на сумматорах 25 и 2б с нулевыми значениями, поступающими с выходов умножителей 36 и 37, и с приходом СИ (t) записываются в регистры 32 и 3 соответственно.

На каждом новом такте происходит домножение промежуточных результатов, получаемых на выходах регистров 32 и

45

Ф

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

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

3 на величину х12 или xl и их соот- sc сумматора, три регистра, два коммута ветственное сложение с новой парой тора, два умножителя, три счетчика,

полученных коэффициентов полинома.

Этот процесс продолжается до тех пор,

пока нулевое значение на выходе заема

счетчика 15 не запретит дальнейшее

поступление СИ на вычитающий вход

две группы элементов И и регистр-мультиплексор, выход которого соединен с первым информационным входом первого коммутатора, выход которого соединен с входом множимого первого умножителя, выход которого соединен с первым информационным входом регистра-мультиплексора и с входом первого слагасметчика 15. При этом по заднему фронту сигнала заема устанавливается триггер 6 (момент , а с приходом

очередного СИ единичное значение с выхода триггера 6 переписывается в триггер 9, сбрасывающий триггер 6. Следующий СИ сбрасывает триггер 9.

Разряды кодов с первого и второго выходов блока 18 поступают на вторые входы элементов И 11 и 12, запрещая нулевыми значениями прохождение СИ с выхода элемента И 10 на счетные входы счетчиков 1б и 17 соответственно.

Это препятствует изменению значения адресов на адресных входах бло20

|5

25

25

30

40

45

Ф

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

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

п 5 0 5

5

0

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

csi u

Изобретение относится к вычислительной технике и может быть использовано в измерительно-вычислительных системах, работающих в реальном масштабе времени. Цель изобретения - повышение быстродействия устройства при вычислении полиномов с большим количеством нулевых членов. С этой целью в устройство, содержащее триггеры 1, 3, 4, 5, 6, 9, элементы И 10-14, счетчики 15-17, блоки 18, 20 и 21 памяти, сумматоры 25 и 26, коммутаторы 27 и 28, регистр-мультиплексор 31, регистры 32, 34 и 35, умножители 36 и 37, введены триггеры 2, 7 и 8, блок 19 памяти, коммутаторы 29 и 30 и элемент ИЛИ. 2 ил.