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

Изс 5ретекие относится к цифровой вычислительной технике и может быть гримененс, например, в специалиэиговакных вычислительных устройствах для вычисления многочленов. Известно устройство, предназначенное для вычисления многочленов, представляющее собой универсальную цифровую вычислительную машину. Вычисление многочленов осуществляется в хгих путем выполнения соответст; чуюгчвй программы 111« Однако для программного способа вычисления многочленов в ЦВМ требуются многократное умножение и сложа нме операндов, многократное обращенье к запоминающему устройству, до.:о 1нительные затраты времени на модификацию команд. Кроме того, воз Нйкают трудности при получении результата повышенной точности, что обуславливает низкое быстродействие таких устройств. Наиболее близким по технической сущности к изобретению является уст , содержащее последовательно соединенные умнох(ители, связанные с тактирующей 1 1иной устройства. Это .устройство обладает более вы солИм быстродтс-йстрием, так как при вычислении многочлена вида .S х здесь не требуется многократного обращения к запоминающему устройству, многократного умножения и сложения операндов 2. Однако известное устройство также обладает невысоким быстродействием, которое может быть вычислено по формулеч - -- ч - -сдц), 1-(Ч Чв где 1 - разрядность X и а; и - степень многочлена; t - время суммирования, tcд0- время сдвига. Кроме того, в известном устройстве процесс вычислений может быть начат только тогда, когда имеются в наличии все разряды операнда X, что не позволяет совмещать во времени процессы вычисления и поразрядного ввода аргумента и обуславливает дополнительные затраты времени, если X может поступать в устройство только последовательным кодом например, когда имеются ограничения на число внешних выводов при выполнении устройства в виде большой интегральной схемы, когда имеются ограничения на пропускную способность канала связи, когда операнд X формируется на аналого-цифровом преобразователе поразрядного уравновешивания и т.п.).

Целью изобретения является увеличение быстродействия.

Поставленная цель достигается тем, что в устройство, содержащее п умножителей (п - степень многочлена) , cy.мaтop и п регистров коэффициентов, дополнительно введены сумматор остатка, регистр остатка, регистр константы, регистр цифры, коммутатор, регистр коэффициентов и N , log, вычислительных блоков, причем а-и вычислительный блок (i N), кроме N-ro блока,

- 1, 2, ..

содержит умножителей, 2 г квадт- -граторов, элемент задержки,. регистров коэффициентов и коммутаторов, причем информационный вход устройства соединен с управляющим входом коммутатора и входами элемента задержки и квадратора первого вычислительного блока, выход j-ro умножителя (J 1, 2, ,.., 2-) i-ro вычислительного блока соединен с входами (2J- 1)-го и 2j-ro умножителей и 2j-ro квадратора (i+l)-ro вычислительного блока, выход k-ro квадратора, (k 1, 2, ..., 2) i-ro вычислительного блока соединен с входами 2k+l)-ro и 2k-ro умножителей и 2k-ro квадратора (i+l)-ro вычислительного блока, выход 2 -го квадратора i-ro вычислительного блока соединен с входом элемента э держки, входом i-ro квадратора и умножителя (i+l)-ro вычислительного блока, выхо.д элемента задержки i-ro вычислительного блока соединен с входом первого умножителя (i-i-l)-ro вычислительного блока, выходы всех квадраторов и уг-етожителей подключены к управляющим входам соответствующих коммутаторов, входы которых соединены с выходами соответствующих регистров коэффициентов, выходы всех коммутаторов, регистра цифры и регистра остатка соединены с соответствующими нходзами сумматора остатка, выход остатка которого соединен с информационным входом регистра остатка, управляющий вход которого соединен с тактовым входом устройства и тактовыми входами всех умножителей, квадраторов и тактовым входом регистр4 цифры, информационный вход коTopdtro соединен с выходом cyм 1aтopa, первый и второй входы которого соединены соответственно с выходами приращения сумматора остатка и регистра константы, выход регистра цифры является выходом устройства.

На чертеже изображено предлагаемое устройство.

Устройства содержит вход 1. квадраторы 2, элементы 3 задержки, умножители 4, коммутаторы 5, регистры 6

коэффициентов, сумматор 7 остатка, регистр 8 остатка, сумматор 9, регистр 10 константы, регистр 11 цифры, выход 12 и тактовый вход 13.

В качестве умножителей 4 и квадраторов 2 могут быть использованы любые арифметические устройства, позволяющие совмещать во времени процессы поразрядного ввода операндов и поразрядной выдачи результата

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

В исходном состоянии в регистре 8 остатка, в последних регистрах 6 коэффициентов вычислительных блоков и квадраторе 2 первого вычислительного блока записаны соответственно

., Г о ,. .

и р .а,

коэффициенты р Ej.

Б регистре 6 коэффициента при j-ом умножителе i-ro блока записан коэффициент , - 1, а в регистре 6 коэффициента при j-ом квадраторе 1-го блок.а записан коэффициент . + 2 (1 2, 3, 4,. . .,

j 1, 2, 3, . . . ,2) , где р - основание системы счисления, цифры которой принимают значения из множес ва: IR,-, R., + 1 ; R, -н 2,. . .,R2{; S - задерх(:ка появления очередной цифры x() операнда X на квадраторе 2, умножителе 4 и элемента 3 задержки, а г определяются из условия

r n Bog-pi taflP -.

J-i

Задержка S зависит от вида операции и используемой системг.-. счислени Например, для операций умножения и возведения в ква.драт при ;спользовании р-ичной системы счисления с цифрами, принимающими зна -гения .13 множества

|R,,5l2ViMO R2 R2-Ki lP,S, определяется по

s rEog:-p p.,,i,

где Г функция округления до блжайшего большего целого (Сх inin

к « К О, 1, 2,...) .

Аналогично через г обозначена выраженная в количестве циклов заU f

формирования разрядов

держка

f-o

относительно поступления на вход устройства цифр X с тем же весом. В регистре КОнстанты записан вход код величины Г i/Р

В каждом т-ом цикле вычислеьшя (т 1, п) на вход 1 поступает цифра х операнда X, имеющая вес р , которая управляет выдачей на cyMi iaTOp 7 кода Х|„ а , например для двоичной системы с Цг:фрами l,0,l}, с регистра 6 коэффициенто

на сумматор 7 остатка выдается дополнительный код а при х 1, прямой код а при 1, код а не выдается при х 0. Аналогичным образом цифра операнда Х% имеющая вес формирующаяся на выходе квадратора 2 первого вычислительног блока, управляет выдачей кода.ве.личины, а, а цифры операндов имеющий вес формирующиеся на выходах j-ro умножителя и j-го квадратора i-ro вычислительного блока управляют, соответственно, выдачей кодов величин + + 1 и -ь . Кроме того, на сумматор 7 остатка поступают коды величин, записанных в регистре 8 остатка и в регистре 11 цифры. Код, сформированный на сумматоре 7 остатка, поступает на сумматор 9, где суммируется с кодом величины (R,/p), поступающей из регистра 10 константы. Каждый ifi-ft цикл вычислений заканчивается тактовым сигна лом по тактовому входу 13, по которому величины-, сформированные на сумматоре 7 остатка и сумматоре 9, записываются в регистр 8 остатка и регистр 11 цифры соответственно, а квадратор первой группы и каждый j-fi умножитель и j-й квадратор i-ro блока подготавливается к m+i-My циклу вычислений.

Предлагаекое устройство позволяет вычислять значение многочлена п-й степени с точностью до 1 цифр после запятой за время Т (г 1) (t -t- ) , следовательно, предлагаемое устройство превосходит по быстродействию известное в К раз

Ti п-1

X.

К

В цифровом примере, поясняющем работу устройства, S 3, г 4. Таким образом, предлагаемое устройство, например, при разрядности операнда п 32, -позволяет вычислить многочлен 3-й степени в 2,6 раза, 7-й степени - 6,2 раза, 15-й степени - в Д3,3 раза быстрее известного.

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

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

5 блока, выход j-ro умножителя (j 1,2,.. .,2 i-ro вычислительного блока соединен с входами (25-1)-го и 2j-ro умножителей и 2j-ro квадратора (i+l)-ro вычислительного блока,

0 выход k-ro квадратора ( , 2 , . .. ,2) i-ro вычислительного блока соединен с входами (2k+l)-ro и 2k-ro умножителей и 2k-ro квадратора (i-i-1) вычислительного блока, выход

5 квадратора i-ro вычислительного блока соединен с входом элемента задержки, входом i-ro квадратора и умножителя (i+1)-ro вычислительного блока, выход элемента задержки i-ro вычислительного блока соединен с

0 входом первого умножителя XiO i o вычислительного блока, выходы всех квадраторов и умножителей подключены к управляющим входам соответствующих коммутаторов, входы которых

соединены с выходами соответствующих регистров коэффициентов, выходы всех коммутаторов, регистра цифры и регистра остатка соединены с соответствующими входами сумматора остатка,

0 выход остатка которого соединен с информационным входом регистра остатка , управляющий вход которого соедиIнен с тактовым входом устройства и тактовыми входами всех умножителей,

5 квадраторов и тактовьлм входом регистра цифры, информационный вход которого соединен с выходом сумматора, первый и второй входы которого соединены соответственно с выходами

0 приращения сумматора остатка и регистра константы, выход регистра цифры является выходом устройства.

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

5 1 Авторское свидетельство СССР №170218, кл. G Об F 15/20, 1966.

2. Авторское свидетельство СССР 451088, кл. G 06 F 15/20, 1974.