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

 

1. УСТРОЙСТВО ДЛЛ ВЫЧИСЛЕНИЯ КВАДРАТНОГО КОРНЯ, содержащее накапливающий сумматор, регйстр аргумента, регистр резулыата, два блока сдвига, счетчик и дешифратор.- вход которого через счетчик соединен с тактовым входом устройства, выход регистра результата соединен с информационным входом первого блока сдвига и с входом накапливающего сумматора, выход регистра аргумента соэдинен с информационным входом второго блока сдвига, отличающееся тем. что. с целью повышения быстродействия, в него введ&ны первый и второй ксыбинадионные сумматоры , первый и второй блоки формирования знака, третий блок сдвига, блок анализа знака и блок формирования сдвига , первый и второй входы которого соединены соответственно с выходом дещи4 ратора в первым выходом блока анализа знака, второй выход которого соединен с управляющими входами первого и второго блоков формирования знака, ивфО змационные входы и выходы которых соединены соответственно с выходами соответствующих блоков сдвига в первыми входами соответствующих комбинационных сумматоров, выходы и вторые вхо ды которых соединены с входами и галходами регистров соответственно резуль тата и аргумента, выход старших разрядов последнего соединен с входом блока анализа знака, выход блока формирования сдвига соединен с управляющими входами блоков сдвига, выход и информационный вход третьего блока сдвига соединены соответственно с третьим входом второго комбинационного сумматора и выходом регистра аргумента. St.. Устройство по п. 1. о т л и ч а Ю1 щ е е с я тем, что блок формирования сдвига состоит из п групп элементов И и ИЛИ (где п. -разрядность устройства), каждая из которых содержит первый и второй СП элементы И. элемент ИЛИ. причем входы первого и второго элементов И 1-й группы ( 1.2,..., П) объединены и соединены с -м разрядом nej вого входа блока формирования сдвига, а вторые входы первого и второго элементов И Д -и группы соединены с вторым входсм блока формирования сдвига, выходы второго элемента И -и группы и первого элемента И ( i +1)-й группы 00 подключены соответственно к первому и второму входам элемента ИЛИ f -и со Г РУППЫ, выход которого является ВЬ1ХОДОМ, -го разряда блока формирования сдвига, О) 3. Устройство по п. т л и ч а ю щ е е с я тем, что блок формирования знака содержит п групп элементов И. ИЛИ и ИЛИ-НЕ (где П - разрядность устройства), каждая из которых содержит. первый и второй элементы И, элемент ИЛИ и элемент ИЛИ-НЕ, причем в -Д группе (,2,..., И ) первые входы первого и второго элементов И соединены с -i -м разрядом информационного вхо

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

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

РЕСПУБЛИК (50 Q 06 F 7/552

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

H ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 3262693/18-24 (22) 24.03.81 (46) 30.03.83. Бюл. ¹ 12 (72) А.A.Ìaõàíîâ (71) Кировский политехнический институт (53) 681.325 (088.8) (56) 1. Авторское свидетельство СССР № 640290, кл. 9 06 F 7/552, 1978.

2. Байков В.Д., Смолов В. Б.

Аппаратурная реализация элементарных функций в IlBN. Л., изд-во ЛГУ, 1975, . с. 22 (прототип). (54)(57) 1. УСТРОЙСТВО ДЛ. ВЫЧИСЛЕНИЯ КВАДРАТНОГО КОРНЯ, содержащее накапливающий сумматор, ре-гистр аргумента, регистр резуль1 ата, два блока сдвига, счетчик и дешифратор, вход которого через счетчик соединен с тактовым входом устройства, выход регист ра результата соединен с информационным входом первого блока сдвига и с входом накапливающего сумматора, выход регистра аргумента сседьнен с информационным входом второго блока сдвига, о т л ич а ю ш е е с я тем, что, с целью повышения быстродействия, в него введены первый и второй комбинационные сумматоры, первый и второй блоки формирования знака, третий блок сдвига, блок анализа знака и блок формирования сдвига, первый и второй входы которого соединены соответственно с выходом дешифратора и первым выходом блока анализа знака, второй выход которого соединен с управляющими входами первого и втсьрого блоков формирования знака, инфсфкационные входы и выходы которых соединены соответственно с выходами соответствующих блоков сдвига к,первыми входами соответствующих.комбинапи„„SU„1008736 А онных сумматоров, выходы и вторые вхо ды которых соединены с входами и выходами регнстров соответственно резуль тата и аргумента, выход старших разря дов последнего соединен с входом- блока анализа знака, выход блока формирования сдвига соединен с управляющими входами блоков сдвига, выход и информационный вход третьего блока сдвига соединены соответственно с третьим входом второго комбинационного сумматора и выходом регистра аргумента.

2. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок формирования сдвига состоитиз групп элементов И и

ИЛИ (где ю -разрядность устройства), каж» ф дая нз которых содержит первый и втор@ элементы И, элемент ИЛИ, причем пер вые входы первого и второго элементов г

И i -й группы { < = 1,2,..., й) обьедиФ пены и соединены с < -м разрядом первого входа блока формирования сдвига, а вторые входы первого и второго элемен тов И 4 -й группы соединены с вторым входом блока формирования сдвига, выходы второго элемента И -й группы и 4 первого элемента И (1+1)-й группы (ай подключены соответствекно к первому 90 н второму входам элемента ИЛИ < -й ) группы, выход которого является выходом. фф (-го разряда блока формирования сдвига, ф .

3. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок формирования знака содержит g групп элементов а

И, ИЛИ и ИЛИ-НЕ (где и — разрядность устройства), каждая из которых соцержнт с первый и второй элементы И, элемент

ИЛИ и элемент ИЛИ-НЕ, причем в -,й группе (4 1,2,..., tl ) первые входы первого и второго элементов И соединены с -м разрядом информационного sxo1006736 да блока формирования знака, вторые . ИЛИ-НЕ < -й группы, выход второго входы первого и второго элементов И элемента И 1 -й группы соединен с вто -й группы соединены с управляющим рыми входами элементов ИЛИ и ИЛИ-НЕ входом блока формирования знака, выход f -й группы, выходы элементов ИЛИ и первого элемента И t -й группы соеди- ИЛИ-HE < -й группы соединены с выходом нен с первыми входами элементов ИЛИ и 1-го разряда блока формирования знака.

5 рым входам второго сумматора, выходы которого подключены к входам регистра т5

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

Известно уст ройство ускоренного деления и вычисления квадратного корня, в котором количество выполняемых итераций равно П, на каждой исполняемой итерации операция сложения (вычитания) выполняется без распространения переносов на A разрядов. Устройство выполняет операцию вычисления квадратного корня путем получения обратной величинь1 аргумента в итеративном процессе. При вычислении квадратного корня на пирамиде сумматоров с разделением сумм:.и переносов вычисляется корень обратной величины аргумента, а затем выполняется умножение этого корня на аргумент. Время вычислений в этом устройстве пропорционально П < (1)

Недостатком данного устройства являются значительные аппаратурные затраты, поскольку количество используе мых Р -разрядных сумматоров пропорционально Ft, Наиболее близким по технической

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

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

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

11ель изобретения - увеличение быстродействия устройства.

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

f- ° - — = °

-3, -2, -1, О, +1, +, +3) . Это

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

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

1$ анализа знака; на фиг. 3 - функциональная схема блока формирования сдвига; на фиг. 4 - функциональная схема блока формирования знака; на фиг. 5 - функциональ ная схема первого комбинационного сум2g матора; на фиг. 6 - функциональная схема второго комбинационного сумматора.

Устройство для вычисления квадратно-. го корня содержит регистр 1 результата, регистр 2 аргумента, первый 3, второй

2$ 4 и третий 5 блоки сдвига, накапливающий сумматор 6, счетчик 7, дешифратор .8, первый 9 и второй 10 комбинационные сумматоры, блок 11 формирования сдвига, блок 12 анализа знака, первый

$й 13 и второй 14 блоки формирования знаKG, Блок 12 анализа знака содержит четырнадцать энементов И 15 и четыре элемента ИЛИ 16.

3$

Блок 11 формирования сдвига содержит П групп логических элементов, каж» дай группа содержит первый 17, второй

18 элемент И и элемент ИЛИ 19. На фиг. 3 изображены три разряда блока

40 формирования сдвига.

Блоки 13 и 14 формирования знака содержат и групп логических элементов.

На фиг. 4 изображены три разряда, каждый из которых содержит первый 20 и . второй 21 элемент И, элемент ИЛИ 22

4$ н элемент ИЛИ-НЕ 23.

56

3 100 но с выходами соответствующих блоков сдвига и первыми входами соответствующих комбинационных сумматоров, выходы и вторые входы которых соедийены с входами и выходами регистров соответственно результата и аргумента, выход старших разрядов последнего соединен с входом блока анализа знака, выход блока формирования сдвига соединен с управляющими входами блоков сдвига, выход и информационный вход третьего блока сдвига соединены соответственно с третьим входом второго комбинационного сумматора и выходом регистра аргумента.

При этом блок формирования сдвига содержит П групп элементов И и ИЛИ (где ц - разрядность устройства), каждая из которых содержит первый и второй элементы И, элемент ИЛИ, причем первые входы первого и второго элементов И 1 -й группы (. = 1,2,...,П ) объединены и соединены с 1 -м разрядом первого входа блока формирования сдвига, а вторые входы первого и второго элементов И g -й группы соединены с вторым входом блока формирования сдвига, выходы второго элемента И j -й группы и первого элемента И () + 1 )-й группы подключены-соответственно к пер виму и второму входам элемента ИЛИ 1 -й группы, выход которого является выходом 1 -го разряда блока формирования сдвига.

Кроме того, блок формирования знака содержит д групп элементов И, ИЛИ и

ИЛИ-НЕ (где O - разрядность устройства), каждая из которых содержит -nepmaN и второй элементы И, элемент ИЛИ и элемент ИЛИ-НЕ, причем в q -й группе (1 = 1,2,...,п ) первые входы первого и второго элементе в И соединены с Ф -м разрядом инфорь3ационного входа блока формирования знака, вторые входы первого и второго элементов И 1 -й группы соединены с управляющим входом блока формирования знака, выход первого элемента И «й группы соединен с первыми входами элементов ИЛИ и ИЛИ-НЕ < -й группы, выход второго элемента И 1. -й группы соединен с вторыми входами элементов ИЛИ и ИЛИ-НЕ 3 -й группы, выходы weMeHroB ИЛИ и ИЛИ-HE 1 -й группы соединены с выходом < -го разряда фбрмирования знака. Введенные в устройство первый и второй комбинационные сумматоры, третий блок сдвига, первый и второй блоки формйрования знака, блок формирования сдвига и блок анализа знака позволяют проСумматор 9 содержит 4 разрядов. На фиг. 5 изображены два разряда, каждый разряд содержит первый 24 и второй 25 знакоразрядные сумматоры.

Сумматор 10 содержит tI. разрядов.

На фиг. 6 изображены два, разряда, каж дый из которых содержит первый 26, второй 27, третий 28 и четвертый 29 знакоразрядные сумматоры.

Вычисление корни в предлагаемом устройстве выполняется в знакоразрядной системе счисления. В этой систеS . 1008 ме счисления любое )1 -разрядное число

Х (/Х/ + 1 ) представпяется в виде и х=E у (p"+ж").a ", (1

rye g" Е (0,1 — младшая цифра 1 -го разряда; " q (0,1 — старшая иифра Г -тс разряда;

gt 4 (0,1 - знак Г -ro разряда, при атом It О соответствует знаку

«+" g" = l сфответствует знаку "-".

Процесс вычисления квадратного корня

У Х (1 Х<2) основывается на следующих равенствах. Аргумент Х представ- >5 ляется в виде

Х=1! П («C„"2 ), »=»

Тогда значение функции представится 20

WX=

»ш1

Запишем тождество

25 x= х/ (7. (4)

Подставляя (3) в (4) получим

: )Х=Х П (4тс; 2 ). (X) !

Иэ (2) получаем равенство

Х,П ((tE; 2 ) =1. (6)

»-1

На основании (5) и (6) процесс вычисления ГХ представится следующими рекуррентными выражениями: а

=2(Х»+ ; 2 Х» ф2 x, F ); (r) (8) .где ) 1,2...,,И; Е, 6)„,-1,0,+1 ;

БЕ 0,1); =(» -Я).

Нащльные условия: Х1 = Х, У = Х.

Результат: Уп = X.

Переменные » и 6 в (7) и (8) на ,каждой» -й итерации определяются по значениям старших разрядов X таким образом, чтобы первый после запятой разряд Х» в результате выполнения (7) принимал нулевое значение. При этом переменная Х» стремится к значению

Хф1 = 2, а переменная У» к значению и

У)) = .

В,табл. 1 приведена зависимость значений Я и от значений старших разрядов переменной Х».

В табл. 1 введены следующие обозначения: 5 — двоичная переменная, принимающая значение 1, если E» = +1, Ф двоичная переменная, принимающая значе-. ние 1, если Е; = -l, при Е„= О, 5 = О и В = О. Прочерк означает неопределенное значение.

В предлагаемом устройстве регистры

2 аргумента и 1 результата предназначены для хранения переменных Х; и У„, представленных в знакоразрядной системе счисления. Каждый регистр содержит

t1 разрядов дробной части и один разряд целой части переменных, каждый разряд содержит три триггера для хранения знака $ „-, старшей цифры ) „ и младшей

Г t; цифры ф", Счетчик 7 предназначен для счета но- т мера итерации» дешифратор 8 — для де. шифрации коца номера интерации.

Блоки 3 и 4 сдвига осуществляют параллельный сдвиг содержимого регистров

1 и2 на»=(i -() ина(j+1) разрядов вправо соответственно. Блок 5 сдвига осуществляет параллельный сдвиг содержимого регистра на 2() +1) разрядов вправо. При» =1,2,3,..., П в блоке

3 производятся сдвиги на 1,2,3,...; П разрядов, в блоке 4 — на 2, 3, 4,, р разрядов, в блоке 5 — на 4, 6, 8,..., g разрядов. Блоки 3-5 выполнены однотипно, на матрицах элементов И, ИЛИ.

Сумматор 6 предназначен для преобразования результата вычислений У = Д хра.нящегося на регистре 1 из знакоразрядной системы счисления в двоичную

= У,11 и для хранения результата. Выпопнен в виде параллельного сумматора накапливающего типа с распространением переноса на ) ) разрядов.

Функционирование каждого разряда сумматора 9 описывается следующими уравнениями.

I атап — выполняется на знакоразрядном сумматоре 24: (Р Г, b Г ° Р» -г (Lt 43 ) = I| Ж „»- II" )3 „4 у „с „.

П этап - выполняется на знакоразрядном сумматоре 25:

7 1008

Функционирование каждого разряда сумматора 10 описывается следующими уравнениями.. 1 этап

r < г г» г < г г-1,6 (Р< = к"х Т х I х +3 х Х» выполняется на знакораэрядном суммато.ре 26, р - Г Г w 1 4(Эр+1 h ГЛГ h p qh Р4-1»й

3 (2 о 1=3 х Р х 3 х 4х 25 õ .Р х» выполняется на знакоразрядном суммато ре 27.

11 этап выполняется на энакоразрядном сумматоре 28, 1П этап

» " 2 « )= " " +» " " " " "I "," выйолняется на знакоразрядном сумматоре 29.

Знакоразряд ый сумматор производит суммирование трех одноразрядных чисел со знаками в прямом коде и является стандартным узлом вычислительной техники.

Результаты вычисления переменных 30

У 4, Х1+1 с выходов сумматоров 9 и

10 поступают на входы регистров 1 и

2, где они хранятся на (i +1)-й итерации.

Устройство для вычисления квадрат- З5 ного корня работает следующим образом.

Вычисление начинается с занесения в регистры l результата и 2 аргумента значения аргумента Х. Счетчик 7 обнуляется. Далее производится выполне- ф» ние итераций в соответствии с уравнениями (7) и (8).

На каждой итерации выполняются следующие действия.

В счетчике 7 производится прибавление единицы, в дешифраторе 8 дешифруется номер итерации.

В блоке 12 анализа знака по значениям трех старших разрядов регистра 2 формируются значения двоичных переменных 0, 5 и В; значение переменной 3 поступает на вход блока 11 формирования сдвига, значения 5 и  — на управляющие вхбды первого 13 и второго 14 блэ ков формирования знака. В блоке формирования сдвига 11 формируется величина сдвига j = (i - P), которая поступает на соответствующие входы блоков сдвига

3-5. 7M 8 В блоке 3 сдвига происходит сдвиг на ((— 8 +1) разряд, в .блоке 4 сдвигана (i - ) разряд, в блоке 5 сдвигана 2 (-8+1) разряд вправо. Причем на информационный вход блока 3 сдвига поступает переменная У< с регистра 1, на информационный вход блоков 4 и 5 сдвига поступает переменная Х, с регист. ра -2.

В первом 13 и втором 14 блоках фор. мирования знаков производится формирование знаков " сдвинутых переменных

У и Х с учетом значения переменйых

5 иВ.

Таким образом, на выходах блоков

13 и 14 формируются вторые слагаемые в уравнениях (8) и (7}. На выходе блока

5 сдвига формируется третье слагаемое уравне-ние (7}.

Далее в сумматоре 9 происходит формирование суммы в соответствии с уравнением (8) первого и второго слагаемых поступивших соответственно с выходов разрядов регистра 1 и выходов блока 1 3.

Во втором сумматоре 10 происходит формирование суммы в соответствии с уравнением (7) первого, второго и третьего слагаемых, поступающих с выходов ре- гистра 2, второго блока 14 формирования знака и с третьего блока 5 сдвига.

Затем результаты . суммирования У и

Х << < с выходов блоков 9 и 10 записываются на регистры 1 и 2. При этом на регистр 2 переменная Х +< записывается со сдвигом на один разряд влево, а очередной старший нулевой разряд переменной Х + теряется. Однако оставшиеся значения разрядов дробной части обеспечивают правильное выполнение алгоритма вычисления корпя.

После выполнения п итераций в регистре 1 хранится результат;.вычисления.

У»» =- Х представлен в знакораэрядной системе счислений. Преобразования результата в обычную двоичную систему производится на сумматоре 6 с распространением переноса. Преобразование на сумматоре сводится к алгебраическому суммированию двух положительных и двух отрицательных чисел, представленных на триггерах регистра 1.

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

Та блица l

Таблица 2

10 2,40

20 . 4 90

8,15

8,10 30 7,41

60.80

40 9,90

50 1 2,41

8,08

100 8 06

8,05 60 1 4,91

120

9 100 р-разрядных чисел íà ff.-разрядном сумматоре с расНросТраВВВН8М переносоВ че рез все paapsw. Так нм образом, общее время вычисления квадратного корня, выполненное в enwssaax задержки на эле менте, пропорционально rl..

И предлагаемом устройстве суммирование на каждой итерации производится

В знакоразрядной системе счисления, прн этом распространение переноса ограничено

8738 10 двумя разрядамн. Поэтому суммарное время вычисления корня в предлагаемом устройстве, выраженное в единицах задер. жки на элементе, пропорпионально Qr

В табл. 2 приведены расчетные значения времени вычисления квадратного корня в прототипе Т и в предлагаемом устройстве Т для различных значений разрядности fl и соответствующие им

10 значения коэффициента увеличения быстродействия К.

9Ри8. f

1003736 А

1008736

1008736

l008736

1008736 Г г

Х

ref

Х

+wf

Х Г+

Х Рог.б

ВНИИПИ Заказ 2339/59 Тираж 704 Подписное

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