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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

Республик

«t>960806 (61) Дополнительное к авт. свид-ву (22) Заявлено 06.02.80 (21) 2879935/18-24 с присоединением заявки № (23) Приоритет

Опубликовано 2Х0982. Бюллетень ¹35 (51) М Nn з

G F 7/544

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

СССР по делам изобретений и открытий

)53) УДК 681 3 (088. 8) Дата опубликования описания 23.09 ° 82

В.И.Жабин, В.И.Корнейчук, В.С.Козак, Ю.6.Козлов, А.С. Покаржевский, В.П.Тарасенко, Е .М.ØâIE.ö . т,-,",, Д:ч .Й и ЛЛ Щербина

Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической Й ."т. революции (72) Авторы изобретения (71) Заявитель 54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МНОГОЧЛЕНОВ

Изобретение относится к цифровой вычислительной технике и может быть примененс, например,. в специализиу:"âàt;IIûõ вычислительных устройствах для вычисления многочленов.

Известно устройство, предназнаенное для вычисления многочленов, представляющее собой универсальную

„кфровую вычислительную машину. Вычисление многочленов осуществляется в иих путем выполнения соответст. ву.зщей программы t 1).

Однако для программного способа вычисления многочленов в ЦВМ требуются многократное умножение и сложение операндов, многократное обращен. -:=.: к запоминающему устройству, до .олнительные затраты времени на мсдификацию команд. Кроме того, возя кают трудности при получении результата повышенной точности, что обуславливает низкое быстродействие таких устройств, Наиболее близким по техническои сущности к изобретению является усТройство, содержащее последовательно соединенные умножители, связанные с тактирующей IHHoA устройства.

Это ус".ðîéñòâî обладает более высс ним быстродс.й.lT pHPI t так как при

1 .Ь вычислении многочлена вида « а..\

«Q здесь не требуется многократного обращения к запоминающему устройству, многократного умножения и сложения операндов (2).

Однако известное устройство также обладает невысоким быстродействием, которое может быть вычислено по фор10 муле

Т„= 1 n(t + т. ) где 1 — разрядность Х и а; ll — степен ь многочлен a; t z — время суммиРованиЯ, 1сАв — вРемЯ сдвига. КРоме того, в известном устройстве процесс вычислений может быть начат только тогда, когда имеются в наличии все разряды операнда \, что не позволяет совмещать во времени процессы вычисления и поразрядного ввода аргумента и обуславливает дополнительные затраты времени, если .Х может поступать в устройство только последовательным кодом (например, 25 когда имеются ограничения на число внешних выводов при выполнении устройства в виде большой интегральной схемы, когда имеются ограничения на пропускную способность канала связи, когда операнд Х формируется на ана960806 лого-цифровом преобразователе поразрядного уравновешивания и т.п.).

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

Поставленная цель достигается тем, что в устройство, содержащее и умножителей (n — степень многочлена), сумматор и и регистров коэффициентов, дополнительно введены сумматор остатка, регистр остатка, регистр константы, регистр цифры, 1О коммутатор, регистр коэффициентов и N = (Iog

1, 2, ..., N), кроме N-го блока, содержит 2" умножителей, 2л . квад1-л раторов, элемент задержки, 2 регистров коэффициентов и 2" " коммутаторов, причем ичформационный вход устройства соединен с управляющим входом коммутатора и входами элемен- 2О та задержки и квадратора первого вычислительного блока, выход j-го умножителя (3 = 1, 2, ..., 2 ) i-rî вычислительного блока соединен с входами (2j - 1) -ro и 2j -го умножителей 25 и 2j-го квадратора (i+1)-го вычислительного блока, выход k-го квадратора (k = 1, 2, ..., ) i-го вычислительногo блока соединен с входами (2k+1) -го и 2k-го умножителей и

2k-го квадратора (i+1)-го вычислительного блока, выход 2" -го квадратора 1-,го вычислительного блока соединен с входом элемента задержки, входом 1 го квадратора и 2 -го умножителя (i+1)-ãî вычислительного блока, выход элемента задержки i-ro вычислительного блока соединен с входом первого умножителя (i+1)-го вычислительного блока, выходы всех квадраторов и умножителей подключены к управляющим входам соответствующих коммутаторов, входы которых соединены с выходами соответствующих регистров коэффициентов, выходы всех коммутаторов, регистра цифры и регистра остатка соединены с oîoòâåòñòâóþщими входали сумматора остатка, выход остатка которого coåäèíåí с информационным входом регистра остатка, управляющий вход которого соеди- 50 нен с тактовым входом устройства и тактовыми входами всех умножителей, квадраторов и тактовым входом регистр цифры, информационный вход которого соединен с выходом сумматора, первый и второй входы которого соединены соответственно с выходами приращения сумматора остатка и регистра константы, выход регистра цифры является выходом устройства. 68

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

Устройство содержит вход 1, квадраторы 2, элементы 3 задержки, умножители 4, коммутаторы 5, ре; èñ òðû 6 коэффициентов, сумматор 7 остатка, регистр 8 остатка, сумматор 9, регистр 10 константы, регистр 11 цифры, выход 12 и тактовый вход 13.

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

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

В исходном состоянии в регистре

8 остатка, в последних регистрах 6 коэффициентов вычислительных блоков и квадраторе 2 первого вычислительного блока записаны соответственно коэффициенты р a„, p ° а„ и р .a, .

-г

B rHa pe 6 o U Hra n j-ом умножителе 1-го блока записан коэффициент р" a j + 2 — 1, а в регистре 6 коэффициента при -ом квадраторе i-ro блока записан коэффициент р à j + 2" (1 = 2, 3, 4,..., 1, 2, 3,...,2" ), где р — основание системы счисления, цифры которой принимают значения из множес:.—

)R„, R + 1; R, + Z,...,R (;

$ — задержка появления очередной цифры х (m=1,n) операнда Х на квадраторе 2, умножителе 4 и элементе

3 задержки, à r определяются и=> условия

V з 1+(„y рT6,1 -. Р

Задержка 5 зависит от вида операции и используемой систем.= c" .oë ния, Например, для операций умножел:я и возведения в квадрат при ::спользовании р-ичной системы счисления цифрами, принимающими зна-.ения .з множества Р, >Р„+1; ",1 ; л О Rz(g-й, +1 Р5, определяется по формуле " pq-(p- )Р,- „1 где () — функция округления до ближайшего большего целого ((х j = min къх

К = О, 1, 2,...).

Аналогично через г обозчачена выраженная в количестве циклов заи. держка формирования разрядов

I относительно поступления на вход устройства цифр Х с тем же весом.

В регистре константь: записан вход код величины R„jp!.

В каждом m-ом цикле вычисления (m = 1, n) на вход 1 поступает цифра х„„ операнда Х, имеющая в;с

p --,,которая управляет выдачей на сумматор 7 кода х, я„, напри;-.ер для двоичной системы с ц..фрами 11,0,1>, с регистра 6 ;;сoôènêентов

960806

Формула изобретения на сумматор 7 остатка выдается дополнительный код аА при ) = 1, прямой код а при х„„ = 1, код а< не выдается при х = О. Аналогичным оба. разом цифра операнда X,,имеющая вес р и формирующаяся на выходе квадратора 2 первого вычислительного блока, управляет выдачей кода, величины а ., а цифры операндов Х Lj +u i-(3 и К "," имеющий вес р " и формирующиеся на выходах j-ro умножителя и j-го квадратора 1-го вычислительного блока управляют, соответственно, выдачей кодов величин а 3 + *

1 и .a

8 остатка и в регистре 11 цифры. Код, сформированный на сумматоре 7 остатка, поступает на сумматор 9, где суммируется с кодом величины (Q/ð), поступающей из регистра 10 константы. Каждый m-й цикл вычислений заканчивается тактовым сигналом по тактовому входу 13, по которому величины, сформированные на сумматоре 7 остатка и сумматоре 9, записываются в регистр 8 остатка и регистр 11 цифры соответственно, а квадратор первой группы и каждый

j--й умножитель и j-й квадратор

i-ro блока подготавливается к

m+1-му циклу вычислений.

Иредлагаемoe устройство позволяет вычислять значение многочлена и-й степени с точностью до 1 цифр после запятой за время Т = (r + 1)(, + O ), следовательно, предлагае;".ое устройство превосходит по быстродействию известное в К раз т и-l

К = — = — X.

Т,„r +

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

Устройство для вычисления многочленов, содержащее и умножителей (n — степень многочлена), сумматор

:. п регистров коэффициентов, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены сумматор остатка, регистр остатка, регистр константы, регистр цифры, коммутатор, регистр коэффициентов и N = Elog и) вычислительных блоков, причем i-й вычислительный блок (11,2,...Х), кроме N-ro блошка, содержит 2" умножителей, 2" . квадраторов, элемент задержки, 2 -регистров коэффициен1-4

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

15 блока, выход 3-го умножителя (j=

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

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

25 квадратора i-го вычислительного блока соединен с входом элемента задержки, входом i-ro квадратора и 2" -го умножителя (i+1)-го вычислительного блока, выход элемента задержки i-го вычислительного блока соединен с входом первого умножителя (i+1)-го вычислительного блока, выходы всех квадраторов и умножителей подключены к управляюцим входам соответствующих коммутаторов, входы которых соединены с выходами соответствующих регистров коэффициентов, выходы всех коммутаторов, регистра цифры и регистра остатка соединены с соответствуюцими входами сумматора остатка, 4О выход остатка которого соединен с информационным входом регистра остатка, управляющий вход которого соеди ненн с тактовым входом устройства и тактовыми входами всех умножителей, квадраторов и тактовым входом регистра цифры, информационный вход которого соединен с выходом сумматора, первый и второй входы которого соединены соответственно с выходами приращения сумматора остатка и регистра константы, выход регистра цифры является выходом устройства.

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

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

9170218, кл. G 06 F 15/20, 1966.

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

9451088, кл. G 06 F 15/20, 1974.

960806

Составитель A.Зорин

Техред М Тепер Корректор E.poìêî

Редактор A.Øèøêèíà

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4

Заказ 7283/59 Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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