Устройство для вычисления квадрата числа

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТА ЧИСЛА,содержащее регистр аргумента ,регистр результата,сумматор,первую и вторую группы элементов И, группу элементов ИЛИ, генератор импульсов , первый входы i -х .элементов группы (i 1, П -2, где п разрядность . аргумента) соединены с выходами i -х элементов И первой группы, вторые входы 1 -X элементов ИЛИ группы соединены с выходами i -х элементов И второй труппы, выходы i-X элементов ИЛИ группы соединены с входами (i + +1)-х разрядов первого слагаемого сумматора, разрядные выходы которого соединены соответственно с разрядными .входами регистра результата, выходы -X разрядов которого ( Г, 2п-4) соединены с входами ( )-х разрядов второго слагаемого сумматора , i-e разрядные выходы регист1ра аргумента соединены с первыми входами ч-X элементов И первой группы, и-е разрядные выходы регистра аргумента (к. 2, п-2) соединены с прямыми входами

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН аю (и) за G 06 F 7/552

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬГПФ (21) 3602209/24 (22) 01.06.83 (46) 23.09.84. Бюл. Ф 35 (72) В.И. Жабин, В.И. Корнейчук, В.В. Макаров, В.П. Тарасенко и В.В. Ткаченко (71) Киевский ордена Ленина политехнический институт им. 50-летия Великой Октябрьской социалистической революции (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР

Ф 769537, кл. С 06 F ?/552, 1980.

2. Самофанов К.Г., Корнейчук В.И. и Тарасенко В.П. Электронные цифровые вычислительные машины. Киев, "Вища школа", 1976, рис. 280. (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

КВАДРАТА ЧИСЛА, содержащее регистр аргумента, регистр результата, сумматор,пе рвую и вторую группы элементов И, группу элементов ИЛИ, генератор импульсов, первый входы -х,элементов группы (=1, и -2, где п разрядность аргумента) соединены с выходами 1 -х элементов И первой группы, вторые входы 1 -х элементов ИЛИ группы соединены с выходами i --x элементов И второй группы, выходы 1 --х элементов

ИЛИ группы соединены с входами (1 +

+i)-х разрядов первого слагаемого сумматора, разрядные выходы которого соединены соответственно с разрядными, входами регистра результата, выходы j -х разрядов которого (=Г, 2п-4) соединены с входами (2)-х разрядов второго слагаемого сумматора,s --e разрядные выходы регистра аргумента соединены с первыми входами -х элементов И первой группы, к -е разрядные выходы регистра аргумента (=2, и -2) соединены с прямыми входами (L-1)-х элементов И второй группы, выход и -го разряда регистра аргумента соединен с прямым входом и-2 элемента И второй группы, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены триггер, первьпт, второй и третий элемент И, элемент НЕ, элемент ИЛИ, счетчик циклов, счетчик задержки, выход переполнения которого соединен с первым входом первого элемента И, выход которого соединен

И с входом установки нуля счетчика З задержки, тактовый вход которого сое- уу динен с вторым входом первого элемента И и выходом элемента НЕ, вход которого соединен с выходом генератора импульсов и прямым входом второго элемента И, инверсный вход которого соединен с первым входом третьего элемента И и выходом старшего разряда регистра аргумента, выход (n-i)-го разряда которого соединен с инверсными входами элементов

И второй группы, вторыми входами элементов И первой группы, входом первого слагаемого и -го разряда сумматора и вторым входом третьего элемента И, выход которого соединен со счетным входом триггера, выход которого соединен с входом первого слагаемого младшего разряда сумматора и входом выдачи кода регистра аргумента, вход второго слагаемого младшего разряда сумматора соединен с выходом младшего разряда регистра аргумента, вход сдвига информации

1115051 п(р с З

Известно устройство для вычисления квадрата числа, содержащее двоичный счетчик, элементы И и сумматор. Устройство предназначено для вычисления квадрата числа, представленного число-импульсным кодом (1). !0

Недостатком устройства является низкое быстродействие, например, для возведения в квадрат числа, равного И, необходимо выполнить И сложений. !5

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

Сдвигатель предназначен для выГ дачи кода с выхода регистра первого операнда на входы сумматора без сдвига, либо со сдвигом элементов И и группы элементов ИЛИ. 25

Выходы 1--х элементов И обеих групп подключены к входам < --ro элемента ИЛИ. ь

Первый вход --ro элемента И первой группы связан с выходом -го 30 разряда регистра первого операнда, а первый вход 1-го элемента И второй группы подключен ко входу (i-1) разряда регистра первого операнда. ТаI ким образом, код с выхода регистра первого операнда передается на входы сумматора без сдвига через элементы

И первой группы и со сдвигом влево через элементы И второй группы.

К вторым входам элементов И пер- 40 вой группы подключена управляющая шина (" Выдача кода") блока управления, а к вторым входам элементов И второй группы подключены управляющая шина (" Выдача кода и сдвиг") блока управления.

ТР мента И и счетным входом счетчика циклов, вход записи кода регистра результата соединен с вторым входом элемента ИЛИ и выходом переполнения счетчика задержки.

Вычисление у=х производится умножением у=х.x. При этом множитель представляется с помощью цифр 11, О, 1 ; группы разрядов множителя авда 011...10, преобразуют в группы к вида 10000...1., что позволяет уменьь у к шить среднее число суммированийвычитаний. Для вычисления у=х про5 изводится в среднем — операций

9 сдвига и — и операций суммирования3 вычитания (21.

Недостатком известного устройства является низкое быстродействие, Время вычисления квадрата числа составляет где 1с — время операции сдвига; с! — время операции сложения.

Цель изобретения — повышение быстродействия устройства.

Поставленная цель достигается тем, что в устройство для вычисления квадрата числа, содержащее регистр аргумента, регистр результата, сумматор, первую и вторую группы элементов И, группу элементов ИЛИ, генератор импульсов, первые входы е --х элементов ИЛИ группы (1=1, и -2, где и разрядность аргумента) соединены с выходами -х элементов И первой группы, вторые входы -х элементов ИЛИ группы соединены с выходами 3 --х элементов И второй группы; выходы 1-х элементов ИЛИ группы соединены с входами (1+1)-х разрядов первого слагаемого сумматора, разрядные выходы которого соединены оответственно с разрядными входами регистра результата -x разрядов которого (!=1, Zn-4) соединены с входами (j.+2)-х разрядов второго

1115051 4 слагаемого сумматора, 1 -е разрядные выходы регистра агрумента соединены с первыми входами s --х элементов И первой группы, к -е разрядные выходы регистра аргумента (К=2, и -2) соединены с входами (n-1)-х элементов И второй группы, выход и-го разряда регистра аргумента соединен с прямым входом Н-2 элемента И второй группы, цополнительно введены триггер, пер- 10 вый, второй и третий элементы И, элемент НЕ, элемент ИЛИ, счетчик циклов, счетчик задержки, выход переполнения которого соединен с первым входом первого элемента И, выход которого соединен с входом установки нуля счетчика задержки, тактовый вход которого соединен с вторым входом первого элемента И и выходом элемента НЕ, вход которого соединен 2р с выходом генератора импульсов и прямым входом второго элемента И, инверсный вход которого соединен с первым входом третьего элемента И и выходом старшего разряда регистра аргу- 25 мента, выход (и-1)-го разряда которого соединен с инверсными входами элементов И второй группы, вторыми входами элементов И первой группы, входом первого слагаемого и-го разряда сумматора и вторым входом третьего элемента И, выход которого соединен со счетным входом триггера, выход которого соединен с входом первого слагаемого младшего разряда сумматора и входом выдачи кода регистра аргумента, вход второго слагаемого младшего разряда сумматора соединен с выходом младшего разряда а сумматора соединен с выходом млад- 40 шего разряда регистра аргумента, вход сдвига информации регистра результата соединен с выходом второго элемента И и первым входом элемента

ИЛИ, выход которого соединен с входом сдвига регистра аргумента, третьим входом третьего элемента И и счетным входом счетчика циклов, вход записи кода регистра результата соединен с вторым входом элемента ИЛИ и выходом переполнения счетчика задержки.

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

Устройство для вычисления квад- 55 рата числа содержит регистр 1 аргумента, первую группу элементов И 2, вторую группу элементов И 3, группу элементов ИЛИ 4, сумматор 5, регистр

6 результата, элемент И 7, триггер

8, генератор 9 импульсов, элемент

НЕ 10, счетчик 11 задержки, элемент

И 12, элемент И 13, элемент ИЛИ 14, счетчик 15 циклов.

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

Сумматор 5 содержит (2п-2) разрядов и может быть построен в виде комбинационного сумматора, причем, в двух младших и (n-2) старших разрядах можно использовать полусумматоры. Это связано с тем, что на входы. двух младших разрядов не подается в качестве второго слагаемого содержимое регистра 6 результата, а на входы (11-2) старших разрядов подается только одно слагаемое с выходов регистра 6 результата. Нужно заметить, что в качестве второго слагаемого для младшего разряда сумматора 5 используется сигнал с выхода счетного триггера 8, но так как в младший разряд не подается сигнал переноса, то он также может быть реализован на основе полусумматора. Регистр 6 результата построен на основе триггеров с внутренней задержкой, прием информации в которые осуществляется только после окончания сигнала приема кода.

В регистре 6 результата предусмотрена цепь сдвига кода результата на два разряда влево по управляющему сигналу с выхода элемента И 13.

Счетчик 11 задержки представляет собой счетчик с коэффициентом пересчета где 1 д — .время сложения в сумматоре 5;

Сс — время сдвига кодов в регистре 1 аргумента и регистре 6 результата.

Управляющий вход счетчика 11 задержки представляет собой цепь установки в "0" счетчика (сигналом с выхода элемента И 12).

1115051

= 2 (7 +x„)+X „= 2"(1(;-L 1+Х„=Р„ Х„, Величина (х-2" ) должна быть просуммирована с учетверенным содержанием регистра 6 результата.

Счетчик 15 циклов представляет собой счетчик с коэффициентом пересчета К = "/2, если n — четное число или К = и/2+0,5, если и нечетное число. 5

Устройство предназначено для получения и старших разрядов = х .

Вес младшего разряда результата равен 2" в том случае, если операнд— целое и разрядное число.

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

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

1 аргумента находится исходное число х; регистр 6 результата, триггер 8, счетчик 11 задержки и счетчик

15 циклов обнулены.

С началом вычислений на входы элементов И. 13 и элемента НЕ 10 поступают тактовые импульсы, период которых равен времени сдвига () в регистрах 1 аргумента и результата 6. Операция возведения в квадрат числа х производится за /2 тактов работы устройства, для четных П и 25 за о /2+0,5 тактов для нечетных n ..

В каждом такте анализируется содержимое старшего разряда регистра

1 аргумента. Если а„ „ =О, то на выходах элементов ИЛИ 14, И 13 появ- Зп ляются управляющие сигналы сдвига, которые поступают на цепи сдвига регистров 1 аргумента и результата 6.

Кроме того, этим тактовым импульсам (с элемента ИЛИ 14) осуществляется изменение состояния счетчика 15 циклов на единицу.

Содержимое регистра 1 аргумента сдвигается на один разряд, что равносильно удвоению аргумента, а содер- 40 жимое регистра 6 результата сдвигается на два разряда — учетверению результата. Никаких других действий в случае, когда а „ =0 не производится.

В том случае, когда ап „ =1 вычисления производятся в зависимости от значения разряда а . Если же a> a. =0 (а„„, а„, =1 О), то для организации вычислений (в -м цикле) используем формулу

Содержимое регистра 1 аргумента передается на сумматор 5 в прямом или обратном коде, в зависимости от состояния триггера 8. Если триггер 8 находится в нулевом состоянии, то через группу элементов И 3 на сумматор 5 передается содержимое регистра 1 аргумента в прямом коде.

По единичному состоянию триггера 8 содержимое регистра 1 аргумента передается обратным кодом через группу элементов И 3 на сумматор 5, кроме этого в младший разряд сумматора

5 (по сигналу с триггера 8) прибавляется единица. Вычисление величины

n-t

2 1 = (» „-2 ) производится схемным образом, т.е. на позицию м -2 разряда сумматора 5 через и 2 элемент группы элементов И 3 передается содержимое старшего и -1 разряда регистра 1 аргумента (это равносильно вычитанию единицы из 2" -го разряда аргумента х" ). !

Например, еслиХ=1 ОXХХХХХ, roZ;= (Х;-2" )=О 1 Х Х X X Х Х.

В этом цикле в первом такте (цикл равен к тактов) срабатывает элемент НЕ 10 и запускается счетчик

11 задержки с коэффициентом пересчета К, на время суммирования величин регистра 1 аргумента и регистра 6 результата на сумматоре 5. По к -му импульсу (по заднему фронту инверсного тактового импульса с выхода элемента HE 10) на выходе счетчика

11 задержки появляется единичный потенциал (суммирование закончено).

В этом такте происходит прием кода на регистр 6 результата с выходов сумматора 5 (по сигналу с выхода счетчика задержки), сдвиг содержимого регистра 1 аргумента (по сигналу с выхода элемента ИЛИ 14) на один разряд влево, а также к содержимому счетчика 15 циклов прибавляется единица. По заднему фронту к-го импульса происходит срабатывание элемента И 12, на выходе которого появляется единичный потенциал, который является управляющим сигналом для счетчика 11 задержки, Счетчик

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

t,= (g(с сл1

25 п(/ (сл1 /4(ф, л "4 сл) 30

Если же старшие разряды аргумента а„, ац =- 1 1, то применяем формулу х =(1 -X„) =2 -ч х„-+х„=

= („„-Д у+Х; = „+Х,; к.учетверенному содержимому регистра

6 результата необходимо прибавить величину 2х; -2 ). Для получения величины (2х„. „ -2") на выходы сумматора 5 передается через группу элементов И 2 со сдвигом на один разряд влево Х „- 1, причем старший разряд содержимого регистра аргумента x „ игнорируется.

X„)= 1 1 XXXX, 1, =(2X<, 2 )О 1 Х Х Х Х.

Величина (2Х. ;2 ) постУпает на входы сумматора 5 в прямом коде, если триггер 8 находится в нулевом состоянии или s обратном коде — триггер 8 находится в единичном состоянии. Кроме этого, если состояние триггера 8 единичное, на вход мпадшего разряда сумматора 5 поступает единичный потенциал с выхода этого триггера; это равносильно прибавлению единицы к обратному коду (2Х; „ -2"). Таким образом формируется дополнение аргумента до числа 2".

Также, как и в предыдущем случае (когда a„ „, а„, =10), после окончания суммирования на сумматоре 5, происходит срабатывание счетчика 11 задержки с коэффициентом пересчета . л г

K =j — По к-му импульсу на вы

<с

115051 8 ходах счетчика 11 задержки и элемента ИЛИ 14 появляются сигналы приема кода на регистр 6 результата и сдвига кода регистра 1 аргумента, соответственно; счетчик 15 циклов переходит в следующее состояние, а триггер 8 переходит в противоположное состояние.

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

После окончания t1/2 циклов (момент окончания вычислений определяется по содержимому счетчика циклов 15) в и старших разрядах регистра 6 результата находится искомый результат

20 ЬйК

Время вычислений определяется

Кроме того, уменьшается время вычислений в

44

Пусть = 2 С; тогда с = —, T.e.

21

35 введение трех элементов И, триггера счетчика задержки, счетчика циклов, элемента ИЛИ позволяют увеличить быстродействие устройства в два раза.

1115051

Тираж 698 Подписное

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

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

Заказ 6771/35

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

Составитель А. Казанский

Редактор Е. Лушникова Техред А,Бабинец Корректор M. Максимишинец