Устройство для возведения в степень

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик (б1) Дополнительное к авт. свид-ву (22) Заявлено 18.11.76 (21) 2421567/18-24 (51) М. Кл. с присоединением заявки ¹

G 06 F 7/38

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

СССР но делам изобретений и открытий (23) Приоритет

Опубликовано 3006.80- Бюллетень ¹24

Дата опубликования описания 3006 80 (53) УДК 681 ° 327 (088. 8) В.И.Жабин, B.È.Kîðíåé÷óê, В.П.Тарасенко и A.A.Ùåðáèíà (72) Авторы изобретения

Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (11) Заявитель (54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В СТЕПЕНЬ

Изобретение относится к области вычислительной техники и может быть применено в цифровых вычислительных машинах и специализированных устройствах, работающих в реальном масштабе времени, à вычисления функций вида Y - = Хз(i = 2,3,4...n) .

Известны устройСтва для вычисления функций Y- = Х (1), (2) и (3).

Эти устройства представляют собой

ЦВМ, содержащие три регистра и сумматор, а вычисление каждого значения (i = 2,3,4...n) осуществляется в таких устройствах путем реализации программы i-1-кратного умножения 15 операнда Х на себя. При вычислении функций Y- = Х с помощью известных

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

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

Это устройство обладает более высоким быстродействием по сравнению с вышеуказанными, так как при вычислении функций, у - = Х здесь не требуется многократного умножения операнда Х и многократного обращения к запоминающему устройству.

Однако известное устройство обладает низким быстродействием, особенно для случая, когда числа на входе и выходе устройства представлены последовательными кодами. Действитель74 4556 но, поскольку известное устройство

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

У начиная со старших разрядов (например, когда имеются ограничения на пропускную способность каналов связи, ограничение на количество внеш-! них выводов при выполнении устройства в виде большой инт егральной Схе-" мы, для случая, когда операнд формируется поразряднО на внешнем устрой. стве, например на цифровом измерительном приборе с поразрядныМ уравновешиванием и т.п.) время полученйя результата для известного устройства определяется по формуле

НВОД1 " НЫЧ 4 Нов 1 где Т д„= Тн,® = дТ„- время ввода операнда вывода результатов; - раэрядность операнда и реэультатону

Т вЂ” период поступления на вход устройства очередных разрядов операнда и выдачи на выходе очередных разрядов результатов (в общем случае Тп определяется ннешними по отношению к устройству факторами, например, пропускной сцособностью канала связи, быстродействием внешних источников и потребителей информации и т. п.) .

В известном устройстве н результате выполнения одного цикла вычисления длительностью nt + в(где t>— время суммирования, t „— время сдвига

càü в регистрах) вычисляются очередные младшие цифры всех функций Yg = Х (i = 1,2,3...n), причем разрядность

У„ равна 1, следовательно Тн„,„ =

= n (nt> + t )

2 Т„+ пс (пТ.„, +, ).

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

Устройство содержит с+1 регистров

1 окончательных Результатов и g+2 регистров 2 промежуточных результатон. Конструктивно эти регистры могут быть выполнены, например, как динамические последовательные (n+1)— разрядные регйстры, либо как линии

40 задержки емкостью (и+1) бит, где

n — максимальное значение показателя степени, g,-- разрядность Х и У.

Устройство также содержит сдвигатель 3, реверсинный счетчик 4, ре45 гистр операнда Х 5 (для случая, когда Х представлен избыточным кодом с цифрами 1,0,I регистр 5 обладает также свойствами многовходового реверсивного счетчика), содержащие по ч+1 разрядов каждый, и (с1+4) -разрядный трехвходовой комбинационный сумматор 6. Выход каждого k-ro регистра 1 (k=1,2,...,с +1) соединен со входом k-го разряда сдвигателя 3 и (k+1) -го р эряда счетчика 4, каждый

k-ый разряд которого связан со входом k-ro регистра 1 (первыми считают старшие регистры и разряды). Выходы каждого k-.ro разряда сдвигателя

3 и k-го разряда регистра 5 подклю60 чены ко входам соответственно (k+2)— го и (k+3) -го разрядов сумматора 6..

Выход каждого f,-ro (6=1.2,3,. ° .,y+2) регистра 2 подведен ко входу +1-го разряда сумматора 6, выход 0+2 Г-го

65 разряда которого пойведен ко входу

5 (О

30 сЧ ет чи ка подключены ко входам регистров окончательных результатов, выходы которых подключены ко входам счетчика, а также ко входам сдвигателя, вторая группа входов сумматора подключена к выходам регистра операнда, а третья группа входов — к выходам сдвигателя, выходы прямых и инверсных значений трех старших разрядов сумматора подключены ко входам кодопреобразователя первый и второй выходы которого соединены со входами соответственно первого и второго триггеров цифр результата, другие входы которых подключены к первому выходу блока УПранления, входы которого соединены с выходами триггеров цифр результата, а также с управляющими входами счетчика и регистра операнда, выходы распределителя сигналон подключены ко входам младших разрядов регистра операнда и к упранляющим входам сдвигателя, входные шины устройства подключены к управляющим входам сднигателя и регистра операнда, второй выход блока управления соединен с управляющими входами регистра операнда и распределителя сигналов, остальные 2п выходов блока управ пения подключены к выходным шинам устройства.

На фиг. 1 изображена структурная схема устройства; на фиг. 2 — пример выполнения и подключения кодопреобраэонателя.

744556

8-го регистра 2. Кроме того, выход первого регистра 2 соединен со входом первого разряда сумматора б, выход первого разряда сдвигателя 3 связан со входами первого и второго разрядов сумматора, а выход первого 5 разряда регистра 5 подключен ко входам первых трех разрядов сумматора б.

Прямые и инверсные выходы трех первых разрядов сумматора.б подключены ко входам кодопреобразователя 7, содержащего элемента 8 И и 9 ИЛИ, связанные между собой в соответствии с системой переключательных функций (фиг.2) .

= "1>q ч а,,ат 15

fg = а1аЪ ч а„ат 1 где индексы соответствуют номерам разрядов сумматора и номерам выходов кодопреобраэователя 7, соединенных со входами триггеров цифры результат а 10 „и 10 т, выходы которых подведены к управляющим входам счетчика

4, регистра 5 и ко входам блока управления 11. Выходы q; — ðàçðÿäíîãî распределителя 12 сигналов, который может быть выполнен как сдвиговый регистр или счетчик с дешифратором, .подключены ко входам младших разря- дов регистра 5 и управляющим входам сдвигателя 3. К управляющим входам сдвигателя 3 и регистра 5 подведены 3(1 также входные шины устройства 13А и 13т. Кроме того, первый выход блока

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

К началу вычислений (цепи установки исходного состояния на чертеже не показаны) на выходе крайнего правого регистра 1 находится единица, в остальных разрядах регистров 1 и 2 и триггерах 10 устройства записаны нули.

В каждом j-ом цикле работы устройства (j=1,2,3...q+2n) на входные шины устройства 13 в избыточном двоичном коде с цифрами 1,0,1 поступает очередная цифра аргумента Х, имеющая вес 2 ð .где S — количество двоичных разрядов, после которых фиксируется запятая (Плюс единице соответствует наличие сигнала на ши- 60 не 13, минус единице — на шине 13> нулю соответствует отсутствие сигнала на обеих шинах, причем указанные сигналы присутствуют на входных шинах на протяжении всего цикла) . При 65 этом в распределителе 12 единица находится в j-ом разряде. Сигнал на втором выходе блока 11 управления выдается в начале, т.е. в первом такте -каждого цикла. По этому сигналу осуществляется. запрет выдачи кода С регистра 5, а единица с выхода

j-го разряда распределителя 12 посту пает на вход прибавления или вычитания единицы j+1-ãî разряда регистра

5, в зависимости от того, какое значение 1 или 1 принимает цифра операнда Х, поступающая на управляющие входы этого регистра. Таким образом, в начале j-го цикла в регистре 5 оказывается записанный код Xj т.е. число Х, представленное только j старшими разрядами, Каждый i-ый такт (i=1 2,3...nl

j-ro цикла начинается сигналом в первом выходе блока 11 управления, по которому в регистрах 1 и 2 происходит сдвиг, при котором на" входы.регистров 1 и 2 поступают коды, сформированные в счетчике 4 и сумматоре 6, в результате выполнения предществующего такта, а на триггеры 10 принимается код цифры результата У „ сформированный блоком 7 в предйдущем, i-1-ом такте. Далее, код У.„ „ выдается из устройства по соответствующим выходным шинам 14 и, одновременно с этим, прибавляется в счетчике 4 к сдвинутому на разряд влево коду У с выходом регистра 1 (2У .1 + У1-„, ), а также управляет выдачей прямого или дополнительного кода чисЛа Х1, хранимого на регистре 5 таким образом что"на сумматор, б выдается число

У .„„ Х -. Аналогичным образом, одновре менно с этим, цифра Х1 операнда Х, поступающая по входным шинам .13, управляет выдачей на сумматор 6 кода сдвигателя 3, который на протяжении всего j-го цикла осуществляет сдвиг влево на q+1-j разрядов кода чисел

У 1, то есть в каждом i-ом такте

j-ro цикла на сумматор б, кроме того, выдается число Х> 2 У,1 . На входы ьц( сумматора б поступает код с выходов регистров 2. Кодопреобразователь 7, анализируя три старших разряда сумматора 6 вырабатывает код очередной цифры результата У -, который будет

1 принят на триггеры 10 в начале следу-, ющего, i+1-го такта.

В i-ом такте каждого цикла в устройстве формируется и такт спустя выдается очередная цифра числа Х1

= Х", причем задержка появления на выходе первой (старшей) цифры составляет 2- циклов, т.е. для того, чтобы получить с разрядов число Y Х., необходимо выполнить 21+ц цйклов вычисления. Поскольку длительность цикла в предлагаемом устройстве равна

n(t + t ), то, следовательно, вре744556 мя вычисления всех функций У„ = Х „ (l=l „2, 3... n) для него составляет величину Т = (2n+g) i n ° (+ t. ), тогда как в известном устройстве для этого необходимо время Т ыц = n$(nt + . + сдв), т.е.> как легко убедиться

<< для любых и и с1. Данное устЬЫЮ ройство обладает еще большим преимуществом в случае, когда аргумент Х и функции могут поступать на вход устройства и выдаваться из устройства только последовательным кодом, поразрядно, начиная со старших разрядов. Действительно, поскольку предлагаемое устройство позволяет полностью совмещать во времени процессы поразрядного ввода, вывбда и вычис- 15 ления, то время вычисления в нем и для этого случая остается равным

Т = (2n + <у) n (t + t Q, тогда как в известном устройстве, позволяющем начинать процесс собственно вычисления только после завершения поразрядного ввода. Х, а процесс выдачи результатов (начиная со старших разрядов) — только после завершения вычисления, суммарное время для этого случая увеличивается и равно Т1 = Т ; +

+ ТВ + Тв в. Тогда тем более будет вью выл. выполняться условие Т < Т . Следо" ватепьно, время вычисления в предлагаемом устройстве всегда меньше чем в известном, причем для случая, когда числа на входе и выходе устройств представлены последовательными кодами, предлагаемое устройство дает выигрыш в быстродействии в †раэ.

Например, при разрядности < = 40 З5 предлагаемое устройство позволяет вычислить и выдать последовательным кодом значения функций Y Х" (i=

=1,2,3...20) в 7,8 раза быстрее, чем известное. При этом Т было принято равным длительности цикла вычисления в предлагаемом устройстве Т = п(+

+ t ), хотя в общем случае, Т„ Т,„ абсолютный выигрыш в быстродействии .может быть значительно больше.

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

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

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

1. Карцев М.A. Арифметика цифровых машин. И., Наука, 1969, с. 348-354.

2. Патент СЫА 93740722, кл. 340-172.5, 1973.

3. Акцептованная заявка Японии

948-7217, кл. 97 (7 Н 21, 1973.

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

9425 175, кл . 5 06 F 7/38, 1973 (прототип).