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

 

Изобретение относится к вычислительной технике и может быть использовано в измерительно-вычислительных системах, работающих в реальном масштабе времени. Цель изобретения - повышение быстродействия устройства при вычислении полиномов с большим количеством нулевых членов. С этой целью в устройство, содержащее триггеры 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 ил.

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

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

РЕСПУБЛИК (5I> 4 G 06 F 7/544

3 Л.. 1БМ3

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

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ т-", г (-1

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

ПО ИЗОБРЕТЕНИЯМ И OTHPbITHAM

ПРИ ГКНТ СССР (21) 4342428/24-24 (22) 14.12.87 (46) 23.09.89. Бюл. I." 35 (71) Одесский политехнический институт (72) В.А.Парасочкин, Е.Л.Полин, В.Г.Ткаченко, Лн.В.Дрозд, Ал.В.Дрозд и IO.È.Êîñòåëîâ (53) 681.325(088.8)

1 (56) Авторское свидетельство СССР

N 1305670, кл. С 06 F 7/544, 1985.

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

N 1432509, кл. G 06 F 7/544, 1986.

-(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ПОЛИН0Н0В

„„SU„„1509878 А 1

2 (57) Изобретение относится к вычислительной технике и может быть использовано в измерительно-вычислительных системах, работающих в реальном масштабе времени. Цель изобретения повышение быстродействия устройства при вычислении полиномов с большим количеством нулевых членов. С этой целью в устройство, содержащее триг" геры 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 ил.

30 р

n = 1 +,> k и ри нечетной степе1-! ! ни полинома, где а — коэффициент полинома О» 1« . (n;

k;, 1; - коэффициенты, равные 2 или 4;

P - число членов разложения, nj4 Рс n/2 в зависимости от числа нулевых коэффици- 50 ентов.

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

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

1ф,» k i 1...» k

1«i ;=о з 150987

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

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

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

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

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

Y-- 7 ах

1--о где j - номер члена полинома;

n - максимальный показатель степени аргумента; а„ вЂ” j-й коэффициента полинома. х — аргумент, по формуле

7=х((...(а ., х р+а р )х1

1»:, . К; 1+K. К ! 1 I кр1 К х + ... + а + )х + а,) +

1+К1

+ (...(ар х +ар- )х + ке, zе, «!

+ ... +а.,)х +а ! о р

n =,» 1 при четной степени по- 40 ! линома; коэффициенты с нулевыми значениями.

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

1+Е к, !

«!

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

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

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

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

1 а р и ра вных нулю для нулевых ко .:е; эффициентов и единице в противном случае, во втором разряде блока 18 хранится аналогичная последовательность значений, поставленная s соответствие коэффициентам с нечетными индексами в порядке их убывания, на1 чиная с коэффициента à р

1!- k

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

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

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

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

5 150987 нал "Пуск", по которому триггер 1 вырабатывает импульс Тl длительностью, равный периоду СИ. Импульс Т! поступает на вход триггера 2, входы сброса регистров 32 и 34 и управляющие входы регистра-мультиплексора 31 и коммутатора 28. Триггер 2 под действием импульса Tl вырабатывает импульс Т2, поступающий на соответству- 10 ющие входы блоков 31 и 32, 34 и 28 и на вход триггера 3, импульс Т3 с выхоДа которого устанавливает счетчики 15-17 и триггеры 4 и 5 в исходное состояние. При этом выхОд заема счет- 15 чика 15 переходит из нулевого состояния в единичное и разрешает прохож- . дение СИ через элемент И 10 на вычитающий вход счетчика 15, первые входы элементов И 11 и 12 и синхровходы блоков 18 и 19 памяти, а также запрещает прохождение.СИ на синхровход регистра-мультиплексора 31 в процессе счета счетчика 15. При этом, в момент времени t в регистр-мультиплексор 31 записывается значение аргумента хl, которое поступает на входы умножителя 36, в результате чего значение х12 записывается в регистр-мультиплексор 31 через его второй информационный вход в момент времени t одновременно значение xl с выхода регистра-мультиплексора записывается в четвертый регистр 33.

Аналогично, во время t< c t c t > формируются значения хl и xl2.

Импульсами Т1 и Т2 регистры 32 и

34 обнуляются до момента t<. Коэффи" циенты а е и а складываI е; к;

1=1 i=1 ются на сумматорах 25 и 26 с нулевыми значениями, поступающими с выходов умножителей 36 и 37, и с приходом СИ (t ) записываются в регистры 32 и 34 4> соответственно.

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

34 на величину х1 или xl и их соот- 5 t ветственное сложение с новой парой полученных коэффициентов полинома.

Этот процесс продолжается до тех пор, пока нулевое значение на выходе заема счетчика 15 не запретит дальнейшее поступление СИ на вычитающий вход счетчика 15. При этом по заднему фронту сигнала заема устанавливается триггер 6 (момент t ), а с приходом очередного СИ единичное значение с выхода триггера 6 переписывается в триггер 9, сбрасывающий триггер 6.

Следующий СИ сбрасывает триггер 9.

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

Это препятствует изменению значения адресов на адресных входах блоков -20 и 21 памяти с началом следующего такта, код с выходов блоков l8 и 19 памяти поступает на информационные входы триггеров 4, 5 и 7, 8 соответственно и записывается в них в новом такте.

Нулевое значение сигнала заема счетчика 15 вновь разрешает прохождение СИ на синхровход регистра-мультиплексора 31, принимающего к моменту времени t значение аргумента хl. Импульс Т4 с выхода триггера 9 поступает на управляющий вход коммутатора

27, обеспечивая на время действия импульса Т4 подключение выхода регистра 32 к входу сумматора 26, на другой вход которого поступает результат домножения кода с выхода регистра 34 на значение аргумента xl С выхода сумматора 26 значение полинома п-й степени записывается в регистр 35 по заднему фронту импульса Т4. Передний фронт импульса Т4 сообщает о возможности подать на вход 38 аргумента устройства нового значения аргумента х2 для вычисления полинома и-й степени с прежними коэффициентами, о завершении вычисления полинома и-й степени ° формула изобретения

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

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

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

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

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

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

1509878

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

Техред А.Кравчук Корректор С.Черни

Редактор А.Шандор

Заказ 5813/46 Тираж 668 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Иосква, Ж-35, Раушская наб., д. 4/5 т ,1Производственно-издательский комбинат Патент", г.Ужгород, ул. Гагарина,101