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

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

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

Устройство содержит л-разрлдный регистр /, (№-il)-разрядный регистр сдвига 2, п одноразрядных сумматоров 3, п элементов задержки па один такт 4, п поразрядных элементов И 5, элемент задержки на л та.ктов 6, первый элемент И7, второй элемент И§, выход устройства 9, входы устройства 10, 11, 12, п-) разряд регистра сдвига, л-ный одноразрядный сумматор 14, первый одноразрядный сумматор 15, п-ный, (п-1)-й и первый разряды регистра соответственно 16, п, 18, л-ный, (л-1)-й и первый элементы И соответственно 19, 20, 21, первый разряд регистра сдвига 22, (п-1)-й одноразрядный сумматор 23, л-ный, (п-1)-й и первый элементы задержки на один такт соответственно 24, 25, 26.

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

т

У ,n-. ...

... .+ Л.,Л-J-Л,Л +Ло, по алгоритму Горнера

У ((...((Л„Д + + А„,-,Х + ... ...,Х + А,,

где У - значение полино.ма;

X - а.ргумент;

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

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

задержки на л тактов 6 свободны.

В первой половине пер.вого цикла, т. е. в 1,2 .. . , л тактах «а первую входную ш. 10 подаются л .импульсов первой половины цикла, которые .разрешают передачу

числа из элемента задерл ки на л тактов 6 последовательным .кодом через .первый элемент И 7 на вход (п-.1)-го разряда регистра .сдвига -13. Т. к. в исходном положении элемент задержки на л тактов 6 свободен,

то к концу первой половины цикла регистра сдвига 2 он остается свободным.

Во второй половине первого аикла, т. е. в (л-f 1) .. . , 2л тактах на вторую входную шину // подаются п импульсов второй половины цикла, которые разрешают передачу числа, поступающего .по третьей входной шине 12, через второй элемент .И5 на второй вход л-ного сумматора 14. Поскольку регистр сдвига 2 свободен, поразрядные

элементы И5 заблокированы. Одновременно с подачей л импульсов второй половины цикла на третью входную шину J2 подается коэффициент А,п младшим.и разрядами вперед. В течение второй половины первого

цикла цифры коэффициента Am через второй элемент И8, цепочку сумматоров 3 поступают в элемент задержки на л тактов 6, где запоминаются до следующего цикла. В первой половине второго цикла, т. е.

в 1,2 . .., л тактах на первую входную шину JO подаются л импз льсов первой половины цикла, которые разрешают передачу .коэффициента Лт из элемента задержки на л тактов 6 последовательным кодом через

первый элемент И7 на вход (л-1)-го разряда регистра сдвига 13. Коэффициент Am. продвигается по сдвиговому регистру 2 младшими разрядами навстречу младшим разрядам аргумента X, записанного в перво,м регистре /. При этом в каждом такте на выходах поразрядных элементов И5 формируются поразрядные произведения одного веса, которые поступают в цепочку сумматора 3, где складываются с кодом переносов в данный разряд произведения, который сохранился от предыдущего такта на элем.ентах задержки на один такт 4. На выходе 9, выходе суммы первого сумматора 15 формируется точная цифра произведеоия данного веса, а переносы в следующий старший разряд произведения запоминаются .на элементах задержки на один такт 4. Таким образом, на выходе суммы первого сумматора 15 формируются, начиная с младщей, цифры произведения АтХ, которы-е поступают в элемент задержки иа п тактов 6, где запоминаются. Во второй половине второго цикла, т. е. в (п+ I),. . ., 2п тактах «а вторую входную шину J1 подаются п импульсов второй поло.аины цикла, которые разрещают передачу числа, поступающего по третьей входной шине 12, через второй элемент И8 на второй вход л-ного сумматора 14. Одновремен«о с подачей п импульсов второй половины цикла на третью входную шину 12 подается коэффициент младшими разрядами вперед. В течение второй половины цикла дифры коэффициента через второй элемент И8 поступают на второй вход «-НОГО сумматора М, в результате к старшим разрядам 2 л-разрядного произведения АтХ прибавляется л-разрядный коэффициент Ат-1, а на выходе 9 суммы первого сумматора /5 формируются, начиная с младщей, цифры л-разрядяого частичного значения полинома {АтХ+А,п-), .которые поступают в элемент задержки на л тактов 6, где запоминаются до следующего цикла. Пр.и заполнении элемента задержки на л тактов 6 во второй .половине цикла частич.ным значением полино.ма (АтХ+Ат } находивщиеся там младщие л разрядов произведения А,пХ выходят за пределы разрядной сетки, поскольку во второй половине цикла первый элемент И7 заблокирован. В третьем цикле происходит формирование л-разрядного частичного значения ((А„Х+А,„-1)Х + Ат-.ч).Е третьем и последующим .циклах устройство работает так же, как во втором цикле. В течение второй половины (т+1)-го цикла на выходе 9 первого сумматора 15 формируются, начиная с младщей, цифры «-разрядного значения полинома. После заверщения (т+1)-го .цикла в элем.енте задержки на л тактов 6 оказывается результат - вычисленное значение полинома. Время вычисления значения полинома лг-ной степени на предлагаемом устройстве составляет 2л(т+1)т. Эффективность изобретения заключается в расщирении функциональных возможностей за счет обеспечения вычисления полиномов т-ной степени с положительными коэффициентами. Формула и 3 iO б р е т е н и я Устройство для вычисления значения полинома т-ной степени, содержащее регистр, регистр сдвига, группу одноразрядных сумматоров, грзппу элементов задержки на один такт, группу поразрядных элементов И, причем выход переноса t-того сумматора группы через i-тый элемент задержки на один такт подключен к первому входу г-того сумматора группы (, . . . , п-1, л - число разрядов регистра), выход суммы t-Toro сумматора подключен ко второму входу (t-1)-го сумматора группы, выход t-Toro разряда регистра сдвига подключен к первому входу г-того поразрядного элемента И группы, выход которого подключен к третьему входу i-того сумматора группы, выход г-того разряда регистра подключен ко второму входу i-Toro поразрядного элемента И группы, вход (л-1)-го разряда регистра сдвига подключен к первому входу Л-.НОГО поразрядного элемента И группы, выход л-ного разряда регистра подключен к второму входу л-ного поразрядного элемента И группы, отличающееся тем, что, с .целью расщирения функцио.нальных возможностей, заключающегося в обеспечении вычисления полиномов с положительными коэффициентами, в него введены л-ный одноразрядный сумматор, л-ный элемент задержки ,на один такт, элемент задержки на п тактов, первый и второй элементы И, причем выход суммы первого сумматора группы подключен к выходу устройства « через элемент задержки на л тактов - к первО:Му входу первого элемента И, выход которого подключен к входу (л-1)-го разряда регистра сдвига, первый вход устройства подключен к второму входу первого элемента И, второй вход устройства подключен к первому входу второго элемента И, а третий вход устройства - к второму входу второго элемента И, второй вход (л-1)-го сумматора группы соединен с выходом суммы л-ного сумматора, выход переноса которого через л-ный элемент задержки на один такт подключен к первому входу л-ного сумматора, второй вход которого соединен с выходом второго элемента И, а третий вход - с выходом л-ного поразрядного элемента И группы. Источники информации, принятые во внимание при экспертизе: 1.Авторское свидетельство СССР М 326577, кл. G 06 F 7/38, 1970. 2.Авторское свидетельство СССР Ь 575648, кл. G 06 F 7/38, 1977. 3.Патент США Л 3582634, кл. 235-164, 1971 ппптптип