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

Саюе Советских Социалистических Республик:ССС Р по делам иеобретеиий и открытий(23) Приорите (43) Опублико (45) Дата опуб ано 07.10.80. Бюллетень37икования описания 05.02,81(72) Авторы изобретения А, Н. Чуватин и В вати Кировский политехнический институ 71) Заявит(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИ ЗНАЧЕНИЯ ПОЛИНОМА т-ной СТЕПЕ осится Изобретение отн к вычислительной технике.Известно арифметическое устройство 111 позволягощее вычислять значения полиномов пг-ной степени, содержащее регистры, одноразрядные сумматоры и элементы И. Его недостатки - сложность и низкое быстродействие,Известно устройство 121, содержащее регистры сдвига, счетчик, одноразрядный сумматор, обладающее простой конструкцией, но низким быстродействием. Время вычисления полинома т-ной степени на этом устройстве составляет 4 и(т+1)т, где т - задержка на одном разряде регистра сдвига, а и - разрядность.Наиболее близким по технической сущности к изобретению является устройство 131, содержащее и-разрядный регистр, регистр сдвига, блок одноразрядных сумматоров, блок элементов задержки на один такт, блок поразрядных элементов И, причем выход переноса г-того сумматора (г=1 и - 1) через г-тый элемент задержки на один такт подключен к первому входу г-того сумматора, выход суммы г-того сумматора подключен ко второму входу (г - 1) -го сумматора, выход г-того разряда регистра сдвига подключен к первому входу поразрядного элемента И г-того разряда, выход которого подключен к третьему входу г-того сумматора, выход г-того разряда регистра подключен ко второму входу поразрядного элемента И г-того разряда, вход (и - 1) -го разряда регистра сдвига подключен к первому входу поразрядного элемента И и-ного разряда, выход которого подключен ко второму входу (и - 1)-го сумматора, выход и-ного разряда регистра подключен ко второму входу поразрядного элемента И и-ного разряда.Устройство обладает простой конструкциеЙ, поскольку количество используемых элементов пропорционально и, и высоким быстродействием с временем выполнения операции умножения двух положительных двоичных чисел, пропорциональным 2 ит.Однако данное устройство не,позволяетвычислять полипом с положительными ко. о эффициентами по алгоритму Горнера, т. к.,в каждом цикле работы для вычисления полинома необходимо выполнить операцию А=В С+0, совмещая во времени выполнение операций сложения и умножения, где 5 А, В, С, й - положительные числа.Целью изобретения является расширение функциональных возможностей устройства, заклочаощесся в обеспечении вычис ления полино.,гов с положительными коэффициентаи.50 55 60 65 Поставленная цель достигается тем, что в устройство, содержащее, регистр, регистр сдвига, группу одноразрядных сумматоров, группу элементов задержки на один такт, группу поразрядных элементов И, причем выход переноса -того сумматора группы через -тый элемент задержки на один такт подключен к первому, входу -того сумматора группы (=1 а - 1, в - число разрядов регистра), выход суммы -того сумматора подключен ко второму входу ( - 1) -го сумматора группы, выход -того разряда регистра сдвига подключен к,первому входу -того поразрядного элемента И группы, выход когорого подключен к третьему .входу -того сумматора группы, выход 1-того разряда регистра, подключен ко второму входу -того поразрядного элемента И группы, вход (и - 1)-го разряда регистра сдвига ,подключен к первому входу а-ного поразрядного элемента И группы, выход и-ного разряда регистра подключен ко второму входу п-ного поразрядного элемента И группы, введены одноразрядный сумматор, иный элемент задержки на один такт, элемент задержки на и тактов, первый и второй элементы И, причем выход суммы первого сумматора группы подключен к выходу устройства и через элемент задержки на и тактов - к первому входу первого элемента И, выход которого подключен к входу (и - 1)-го разряда регистра сдвига, первый вход устройства подключен к второму входу первого элемента И, ,второй вход устройства подключен к первому входу второго элемента И, а третий вход устройства - к второму входу второго элемента И, второй вход (л - 1) -го сумматора группы соединен с выходом суммы и-ного сумматора, выход переноса которого через и-ный элемент задержки на один такт подключен и первому входу гг-ного сумматора, второй вход которого соединен с выходом второго элемента И, а третий вход - с выходом лного поразрядного элемента И группы. На чертеже показана блок-схема устройства,Устройство содержит и-разрядный регистр 1, (и - 1)-разрядный регистр сдвига 2, и одноразрядных сумматоров 3, и элементов задержки на один такт 4, п поразрядных элементов И б, элемент задержки на п тактов б, первый элемент И 7, второй элемент И 8, выход устройства 9, входы устройства 10, 11, 12, (и - 1)-й разряд регистра сдвига, п-ный одноразрядный сумматор 14, первый одноразрядный сумматор 1 б, п-ный, (и - 1)-й и,первый разряды регистра соответственно 1 б, 17, 18, а-ный, (и - 1) -й и первый элементы И соответственно 19, 20, 21, первый разряд регистра сдвига 22, (г - 1) -й одноразрядный сумматор 23, п-ный, (и - 1)-й и первый элементы задержки на один такт соответственно 24, 2 б, 2 б. 5 10 15 20 25 зо 35 40 45 Устройство вычисляет полином с положитсльными коэффициентами- ЛХ = А Х - ; - А,Х-++ Л.,Л -А, Х -1- Апо алгоритму Горнера+ 11) Х Ао)где 1 - значение полинома;Х - аргумент;1 - номер члена полинома, показатель степени аргумента;лг - степень полинома,Устройство работает циклически. Каждый цикл состоит из 2 п тактов (импульсов), где и - разрядность Х и А;.В исходном положении в регистре 1 находится аргумент Х, Регистр сдвига 2, элементы задержки на один такт 4 и элемент задержки на и тактов б свободны.В первой половине первого цикла, т. е. в 1,2, и тактах на первую входную ши,ну 10 подаются п,импульсов первой половины цикла, которые разрешают передачу числа из элемента задержки на и тактов б последовательным кодом через, первый элемент И 7 на вход (а - 1)-го разряда регистра сдвига 13. Т. к. в исходном положении элемент задержки на и тактов б свободен, то к концу первой половины цикла регистра сдвига 2 он остается свободным.Во,второй половине первого цикла, т. е. в (и+ 1) , 2 л тактах на вторую входную шину 11 подаются и импульсов второй половины цикла, которые разрешают передачу числа, поступающего по третьей входной шине 12, через второй элемент И 8 на второй вход и-ного сумматора 14. Поскольку регистр сдвига 2 свободен, поразрядные элементы Иб заблокированы. Одновременно с подачей п,импульсов, второй половины цикла на третью входную шину 12 подается коэффициент А, младшими разрядами вперед. В течение второй половины первого цикла цифры коэффициента А, через второй элемент И 8, цепочку сумматоров 3 поступают в элемент задержки на и тактов б, где запоминаются до следующего цикла.В первой половине второго цикла, т. е, в 1,2, и тактах на первую входную шину 10 подаются и импульсов первой половины цикла, которые разрешают передачу коэффициента Аиз элемента задержки на и тактов б последовательным кодом через первый элемент И 7 на вход (и - 1) -го разряда регистра сдвига 13. Коэффициент А продвигается по сдвиговому регистру 2 младшими разрядами навстречу младшим разрядам аргумента Х, записанного в первом регистре 1. При этом в каждом тактена выходах поразрядных элементов И 5 формируются ,поразрядные произведения одного веса, которые поступают в цепочку сумматора 3, где складываются с кодом переносов,в данный разряд произведения, который сохранился от предыдущего такта на элементах задержки на один такт 4. На выходе 9, выходе суммы первого сумматора 15 формируется точная цифра произведения данного веса, а переносы в следующий старящий разряд произведения запоминаются на элементах задержки на один такт 4.Таким образом, на выходе суммы первого сумматора 15 формируются, начиная с младшей, цифры произведения А Х, кото рые поступают в элемент задержки на п тактов б, где запоминаются.Во второй половине второго цикла, т, е. в (и+1) 2 и тактах на вторую входную шину 11 подаются п импульсов второй половины цикла, которые разрешают передачу числа, поступающего по третьей входной шине 12, через второй элемент И 8 на второй вход и-ного сумматора 14. Одновременно с подачей п импульсов второй. половины 2 Б цикла на третью входную шину 12 подается коэффициент Ая -младшими разрядами вперед, В течение второй половины цикла цифры коэффициента А -через вто.рой элемент И 8 поступают на второй вход ЗО и-ного сумматора 14, в,результате к стар. шим разрядам 2 и-разрядного произведе ния А,Х прибавляется п-разрядный коэффициент А , а на выходе 9 суммы первого сумматора 15 формируются, начиная 85 с младшей, цифры и-разрядного частичного ,значения полинома (А,Х+А ), которые поступают в элемент задержки на п тактов б, где запоминаются до следующего цикла. При заполнении элемента задержки на и 40 тактов б во второй, половине цикла частич,ным значением полинома (А,Х+А ) находившиеся там младшие п разрядов произведения А,Х выходят за пределы разряд. ной сетки, поскольку во второй половине 45 цикла первый элемент И 7 заблокирован. Источники информации, принятые вовнимание при экспертизе:1, Авторское свидетельство СССРМ 326577, кл, 6 06 Г 7/38, 1970.2. Авторское свидетельство СССРЪЪ 575648, кл. 6 06 )." 7/38, 1977.3. Патент США Хо 3582634, кл. 235 в 1,1971 (ттпототип 1 В третьем цикле происходит формирование и-разрядного частичного значения полинома А,Л+А, )Х А). В третьем 60 ,и последующим циклах устройство работает так же, как во втором цикле.В течение второй половины (т+ 1)-го цикла на выходе 9 первого сумматора 15 формируются, начиная с младшей, цифры 55 и-разрядного значения полинома. После завершения (т+1) -го цикла в элементе задержки на п тактов б оказывается результат - вычисленлое значение полинома.Время вычисления значения полинома 60 т-ной степенч на предлагаемом устройстве составляет 2 п(т+1) т.Эффективность изобретения заключается в расширении функциональных возможностей за счет обеспечения вычисления по линомов т-ной степени с положительнымикоэффициентами. Формула изобретения Устройство для вычисления значения полинома т-ной степени, содержащее регистр, регистр сдвига, группу одноразрядных сумматоров, группу элементов задержки на один такт, группу поразрядных элементов И, причем выход, переноса -того сумматора группы через -тый элемент задержки на один такт подключен к первому входу -того сумматора группы (=1 и - 1, и - число разрядов регистра), выход суммы -того сумматора подключен ко второму входу ( - 1)-го сумматора группы, выход -того разряда регистра сдвига подключен к первому входу -того поразрядного элемента И группы, выход которого,подключен к третьему, входу -того сумматора группы, выход -того разряда регистра подключен ко второму входу -того поразрядного элемента И группы, вход (и - 1)-го разряда регистра сдвига подключен к первому входу и-ного поразрядного элемента И группы, выход п-ного разряда регистра подключен к второму входу и-ного поразрядного элемента И группы, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных, возможностей, заключающегося в обеспечении вычисления полиномов с положительными коэффициентами, в него введены п-ный одноразрядный сумматор, п-ный элемент задержки,на один такт, элемент задержки на п тактов, первый и второй элементы И, причем выход суммы первого сумматора группы подключен к выходу устройства и через элемент задержки на п тактов - к первому входу лервого элемента И, выход которого подключен к входу (и - 1) -го разряда регистра сдвига, первый вход устройства подключен к второму входу первого элемента И, второй вход устройства подключен к первому входу второго элемента И, а третий, вход устройства - к второму входу второго элемента И, второй вход (и - 1) -го сумматора группы соединен с выходом суммы и-ного сумматора, выход переноса которого через и-ный элемент задержки на один такт подключен к первому .входу и-ного сумматора, второй вход которого соединен с выходом второго элемента И, а третий вход - с выходом и-ного поразрядного элемента И группы.769536 Составитель В. Венпель Корректор С. Файн Техред Б, Заболотнова Редактор Б. Федотов Заказ 1289295 Изд. Уз 484 Тираж 772 Подписное11 ПО Поиск Государственного комитета СССР по делам изобретений и открытий113035, Москва, Ж, Раугпская наб., д. 4/5 Тип. Харьк, фил. пред. Патент