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

 

t:

Саюе Советских

Социалистических

Республик

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву— (22) Заявлено 14.08.78 (21) 2658966/18-24 с присоединением заявки— (23) Приоритет— (43) Опубликовано 07.10.80. Бюллетень № 37 (45) Дата опубликования описания 05.02.81 (51) М.Кл 6 06 F 7/38

Государствеиимй комитет

:GCC P по делам иеобретеиий и открытий (53) УДК 681.325 (088.8) (72) Авторы изобретения

А. Н. Чуватин и В. А. Чуватина

Кировский политехнический институт (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

ЗНАЧЕНИЯ ПОЛИНОМА т-ной СТЕПЕНИ

Изобретение относится,к вычислитель,ной технике.

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

И. Его недостатки — сложность и низкое быстродействие.

Известно устройство (2), содержащее регистры сдвига, счетчик, одноразрядный сумматор, обладающее простой конструкцией, но низким быстродействием. Время вычисления полинома m-.íîé степени на этом устройстве составляет 4n (т+ 1) т, где т — задержка на одном разряде регистра сдвига, а n — разрядность.

Наиболее близким по технической сущности к изобретению является устройство (3), содержащее п-разрядный регистр, регистр сдвига, блок одноразрядных сумматоров, блок элементов задержки на один такт, блок поразрядных элементов И, причем выход переноса i-того сумматора (i=1,..., n — 1) через i-тый элемент задержки на один такт подключен к первому входу i-того сумматора, выход суммы i-того сумматора подключен ко второму входу (i — 1) -го сумматора, выход -того разряда регистра сдвига подключен к первому входу поразрядного элемента И i-того разряда, выход которого подключен к третьему входу i-того:сумматора, выход 1-того разряда регистра подключен ко второму входу поразрядного элемента И i-того разряда, вход (и — 1)-го разряда регистра сдвига подключен к первому входу поразрядного элемента И и-ного разряда, выход которого подключен ко второму входу (и — 1) -го сумматора, выход и-ного разряда регистра подключен ко второму входу поразрядного элемента И и-ного разряда.

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

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

А=В C+D, совмещая во времени выполнение операц. и сложения и умножения, где

25 А, В, С, D — положительные числа.

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

769536

+ Л2/ А!х + АО по алгоритму Горнера

Поставленная цель достигается тем, что в устройство, содержащее, регистр, регистр сдвига, группу одноразрядных сумматоров, группу элементов задержки на один такт, группу поразрядных элементов И, причем выход переноса -того сумматора группы через i-тый элемент задержки на один такт подключен к первому, входу -того сумматора группы (i=1,, n — 1, в — число разрядов регистра), выход суммы i-того сумматора подключен ко второму входу (i — 1) -го сумматора группы, выход i-того разряда регистра сдвига подключен к,первому входу

i-того поразрядного элемента И группы, выход когорого подключен к третьему .входу -того сумматора группы, выход 1-того разряда регистра, подключен ко второму входу i-того поразрядного элемента И группы, вход (и — 1)-го разряда регистра сдвига подключен к первому входу и-ного поразрядного элемента И группы, выход и-ного разряда регистра подключен ко .второму входу и-ного поразрядного элемента И группы, введены одноразрядный сумматор, иный элемент задержки на один такт, элемент задержки на и тактов, первый и второй элементы И, причем выход суммы первого сумматора группы подключен к выходу устройства и через элемент задержки на и тактов — к первому входу первого элемента И, выход которого подключен к входу (и — 1)-го разряда регистра сдвига, первый вход устройства подключен к второму входу первого элемента И,,второй вход устройства подключен к первому входу вто.рого элемента И, а третий вход устройства — к второму входу второго элемента И, второй вход (n — 1) -го сумматора группы соединен с выходом суммы и-ного сумматора, выход переноса которого через п-.íûé элемент задержки:на один такт подключен и первому входу и-ного сумматора, второй вход которого соединен с выходом второго элемента И, а третий вход — с выходом иного поразрядного элемента И группы.

На чертеже показана блок-схема устройства.

Устройство содержит и-разрядный регистр 1, (n — il)-разрядный регистр сдвига

2, и одноразрядных сумматоров 8, и элементов задержки на один такт 4, и поразрядных элементов И б, элемент задержки íà и тактов б, первый элемент И7, второй элемент И8, выход устройства 9, входы устройства 10, 11, 12, (n — 1)-й разряд регистра сдвига, и-ный одноразрядный сумматор 14, первый одноразрядный сумматор 15, п-ный, (и — 1) -й и,первый разряды регистра соответственно 1б, 17, 18, п-ный, (и — 1) -й и первый элементы И соответственно 19, 20, 21, первый разряд регистра сдвига 22, (n — 1)-й одноразрядный сумматор 28, п-ный, (n — 1) -й и первый элементы задержки на один такт соответственно 24, 25, 2б.

25 зо

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

V ==, kiri = Arm А,„,Xm m— + .=О

У = ((...((А„,Х -+- А„,,)Х -> А„, )Y +

". + А )Х: Ао) где Y — значение полинома;

Х вЂ” аргумент;

j — .номер члена полинома, показатель степени аргумента;

m — степень полинома.

Устройство работает циклически. Каждый цикл состоит из 2п тактов (импульсов), где и — разрядность Х и А;.

В исходном положении в .регистре 1 находится аргумент Х, Регистр сдвига 2, элементы задержки на один такт 4 и элемент задержки на и тактов б свободны.

В первой половине первого цикла, т. е. в 1,2..., n тактах на первую входную ши,ну 10 подаются п,импульсов первой половины цикла, которые разрешают передачу числа из элемента задержки на и тактов б последовательным .кодом через, первый элемент И 7 на вход (n — 1)-го разряда регистра сдвига 18. Т. к..в исходном положении элемент задержки на и тактов б свободен, то к концу первой половины цикла регистра сдвига 2 он остается свободным.

Во,второй половине первого цикла, т. е. в (и+1) ..., 2n тактах на вторую входную шину 11 подаются и импульсов второй половины цикла, которые разрешают передачу числа, поступающего по третьей входной шине 12, через второй элемент И8 на второй вход и-ного сумматора 14. Поскольку регистр сдвига 2 свободен, поразрядные элементы Иб заблокированы. Одновременно с подачей п,импульсов .второй половины цикла на третью входную шину 12 подается коэффициент А„, младшими разрядами вперед. В течение второй половины первого цикла цифры коэффициента А„, через второй элемент И8, цепочку сумматоров 8 поступают в элемент задержки на и тактов б, где запоминаются до следующего цикла.

В первой половине второго цикла, т. е, в 1,2..., и тактах на первую входную шину 10 подаются и импульсов первой половины цикла, которые разрешают передачу .коэффициента А, из элемента задержки на и тактов б последовательным кодом через первый элемент И7 на вход (и — 1)-ro разряда регистра сдвига 18. Коэффициент А. продвигается по сдвиговому регистру 2 младшими разрядами навстречу младшим разрядам аргумента Х, записанного в первом регистре 1. При этом в каждом такте

769536 на выходах поразрядных элементов И5 формируются, поразрядные произведения одного .веса, которые поступают в цепочку сумматора 8, где складываются с кодом переносов,в данный разряд произведения, который сохранился от предыдущего такта на элементах задержки на один такт 4. На выходе 9, выходе суммы первого сумматора

15 формируется точная цифра .произведения данного веса, а переносы в следующий старший разряд произведения запоминаются .на элементах задержки на один такт 4.

Таким образом,:на выходе суммы первого сумматора 15 формируются, начиная с младшей, цифры произведения А Х, которые поступают в элемент задержки на и тактов б, где запоминаются.

Во второй половине.второго цикла, т. е. в (и+ 1),..., 2n тактах на вторую входную шину 11 подаются п импульсов второй половины цикла, которые разрешают передачу числа, поступающего по третьей входной шине 12, через второй элемент И8 на второй вход и-ного сумматора 14. Одновременно с подачей п импульсов второй половины 2Б цикла на третью входную шину 12 подается коэффициент А„, младшими разрядами вперед. В течение второй половины цикла цифры коэффициента Am — ) через вто.рой элемент И8 поступают на второй вход ЗО и-ного сумматора 14, в,результате к стар.шим разрядам 2 и-разрядного произведе. ния А,„Х прибавляется п-разрядный коэффициент Am > а на выходе 9 суммы первого сумматора 15 формируются, начиная Зб с младшей, цифры п-разрядного частичного ,значения полинома (А Х+А,, ), которые поступают в элемент задержки на п тактов б, где запоминаются до следующего цикла.

При заполнении элемента задержки на и 4О тактов б во второй, половине цикла частич,ным значением полинома (A»X+4m 1) находившиеся там младшие п разрядов произведения А»Х выходят за пределы разрядной сетки, поскольку во второй половине 4 цикла первый элемент И7 заблокирован.

В третьем цикле происходит формирование и-разрядного частичного значения полинома ((А,„Л +А» )Х-:-А, ). В третьем ,и последующим циклах устройство работает так же, как во втором цикле.

В течение второй половины (т+1)-го цикла на выходе 9 первого сумматора 15 формируются, начиная с младшей, цифры 55 и-разрядного значения полинома. После завершения (m+ 1) -го цикла в элементе задержки на и тактов б оказывается результат — вычисленное значение полинома.

Время вычисления значения полинома 60

m-ной степенч HB предлагаемом уcTpoHcTBQ сост а вл я ет 2п (т+ 1) т.

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

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

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

И, причем выход, переноса i-того сумматора группы через i-тый элемент задержки на один такт подключен к первому входу

i-того сумматора группы (i=1,..., и — 1, п — число разрядов регистра), выход суммы -того сумматора подключен ко второму входу (i — 1)-го сумматора грулпы, выход

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

И, второй вход (n — 1)-го сумматора группы соединен с выходом суммы п-.íîãî сумматора, выход переноса которого через и-ный элемент задержки на один такт подключен

:к первому .входу и-ного сумматора, второй вход которого соединен с выходом второго элемента И, а третий вход — с выходом п-ного поразрядного элемента И группы.

Источники информации, принятые во внимание при экспертизе:

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

М 326677, кл. G 06 F 7/38, 1970.

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

М 576648, кл. G 06 F 7/38, 1977.

3. Патент США Хе 3582634, кл. 235 — 164, ) 971 (ттпототип1

769536

Составитель В. Венцель

Корректор С. Файн

Техред H. Заболотнова

Редактор Б. Федотов

Тип. Харьк, фил. пред. «Патент»

Заказ 1289/!295 Изд. № 484 Тираж 772 Подписное

11ПО «Поиск» Государственного комитета СССР по делам изобретений и открытий

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