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

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

Иллюстрации

Показать все

Реферат

 

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