Устройство для вычисления квадратного корня Советский патент 1983 года по МПК G06F7/552 

да блока формирования знака, вторые входы первого и второго элементов И j -и группы соединены с управляющим BTioaoM блока формирования знака, выход первого элемента И t -и группы соединен с первыми входами элементов ИЛИ и

ИЛИ-НЕ f -и группы, выход второго элемента И i -и группы соединен с вторыми входами элементов ИЛИ и ИЛИ-НЕ i -и группы, выходы элементов ИЛИ и ИЛИ-НЕ 1 -и группы соедине:ны с выходом i-ro разряда блока формирования знака.

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

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

Известно устройство ускоренного деления и вычисления квадратного корня, в которсяи количество выполняемых итераиий равно П , на каждой исполняемой итерации операция сложения (вычитания) выполняется без распространения переносов Sa П разрядов. Устройство выполняет операцию вычисления квадратHoix корня путем получения обратной

величииь) аргумента в итеративном процессе. При вычислении квадратного корня на пирамиде сумматоров с разделением переносов вычисляется корень обратной величины аргумента, а затем выполвяется умножение этого корня на аргумент. вычислений в этом устройстве пропорционально nt ij

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

Наиболее близким по технической

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

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

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

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

Поставленная цель достигается тем, что в устройство для вычисления квадрат ного корня, содержащее накапливающий сумматор, регистр аргумента, регистр результата, два блока сдвига, счетчик и дешифратор, вход которого через счетчик соединен с тактовым вхрдсял устройства, выход регистра результата соединен с информационным входом первого блока сдвига и с ВХОДСЖ1 накапливающего сумматора выход регистра аргумента соединен с ий форлационным входом второго блока сдвига, дополнительно введены первый и второй комбинационные сумматоры, первый и и второй блоки формирования знака, третий блок сдвига, блок анализа знака и блок формирования сдвига, первый и второй входы которого соединены соответственно с выходом дешифратора и первым выходсм блока анализа знака, второй выход которого соединен с управляющими входами первого и второго блоков формирования знака, информационные входы и выходы которых соединены соответственно с. выходами соответствующих бпоков сдвига и первыми входами соответствую щих комбинационных сумматоров, выходы и вторые входы которых соедийеныс Ьходами и выходами регистров соответственно результата и аргумента, выход старших разрядов поспеднего соединен с входом блока анализа знака, выход блока формирования сдвига соединен с уп- равляющими входами блоков сдвига, ш 1ход и информационный вход третьего блока сдвига соединены соответственно с третьим входом второго комбинационного сумматора и выходом регистра аргумента

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

Кроме того, блок формирования знака содержит п групп элементов И, ИЛИ и ИЛИ-НЕ (где Ц - разрядность устройства), каждая из которых содержит первый И второй элементы И, элемент ИЛИ и элемент ИЛИ-НЕ, причем в -и группе ( 1,2,...,И ) первые входы первого и второго элементов И соединены с 4 -м разрядом инфорк ационного входа блока формирования знака, вторые входы первого и второго элементов И i -и группы соединены с управляющим входом блока формирования знака, выход первого эл&мента И 1 -и группы соединен с первыми входами элементов ИЛИ и ИЛИ-НЕ i -и группы, вьтход второго элемента И 1 -и ррулпы соединен с вторыми входами элементов ИЛИ и ИЛИ-НЕ -i -и , выходы элементов ИЛИ и ИЛИ-НЁ -и / группы соединены с выходом i -го разряда фбрмврования знака.

Введенные в устройство первый и второй комбинационные сумматоры, третий блок сдвига, :первый и второй блоки фор- мтфования знака, блок формирования сдавга и блок анализа зна1ш позволяют провзводить вычисления в знакоразрядной системе счисления с осндавниа 2 и разрядными цифрами, принимающими значения {-3, -2, -1, О, +1, +2. +3 . Это

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

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

0 второго комбинационного сумматора.

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

5 щий сумматор 6, счетчик 7, дешифратор 8, первый 9 и второй Ю комбинационные сумматоры, блок 11 формирования сдвига, блок 12 анализа знака, первый 0 13 и второй 14 блоки формирования знака,

Блок 12 анализа знака содержит четырнадцать элементов И 15 и .элемента ИЛИ 16.

Блок 11 формирования сдвига соде1 5жит у групп логических элементов, каждай группа содержит первый 17, второй 18 элемент И и элемент ИЛИ 19. На фкг. 3 изображены три разряда блока формирования сдвига.

0

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

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

Сумматор 9 содержит / разрядов. На , 5 изображены два 1:эзряда, каждый разряд содержит первый Й4 и второй 25 знакоразрядные сумматоры.

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

Вычисление корны в предлагаемом устройстве вшпопняется в знакоразрядвой системе счисления. В этой систеMe счисления пюбое ц -разрядное числ X ) предсгавляется в виде х.Дгг-(7(%о.-1.г, где Г 0,1 Л - младшая цифра 1 разряда; efO, - старшая цифра Г разряда;6 {ОДЗ знак Г-го разряд ЭТС)М f соответствует знаку г 1 3 соответствует знаку - Процесс вычисления квадратного ко У (1 X - 2) основывается на сл дующих равенствах. Аргумент X предс ляется в e,. ХИ/.П( Тогда значение функции представит .n{Ue;.). Запишем тождество x№. Подставляя (3) в (4) получим ..п(ие,.). Из (2) получаем равенство х.п(ие,.. На основании (5) и (6) процесс вы числения Чх представится следующим рекуррентными выражениями: х...2,.(е;. : -1(1+), 2(х.ег2-х,)П Y- у.П4е--2 )у-4е-.2-.у 141 S V м -1 .где Г 1,2,...,П; Е € С-1,О,+ ee{o.ii; ( -е). Начальные условия: X, У X Результат: У - -fX. Переменные и в (7) и (8) .каждой -и итерации определяются по значениям старших разрядов Xj таким образом, чтобы первый после запятой разряд Х в результате выполнения (7 принимал нулевое значение. При этом ременная Xf стремится к значению а переменная значению -.i--/xi в .табл. 1 приведена зависимость значений и от значений старших разрядов переменной , В табл. 1 введены следующие обозначения: 5 - двоичная переменная, принимающая значение 1, если +1, двоичная переменная, принимающая значе-. кие 1, если j -1, при О, 5 О и В О. Прочерк означает неопределенное значение, В предлагаемом устройстве регистры 2 аргумента и 1 результата предназначены для хранения переменных Х;, и У, представленных в знакоразрядной системе счисления. Каждый регистр содержит И разрядов дробной части и один разряд целой части переменных, каждый разряд содержит три триггера для хранения знака у - , старшей цифры и младшей цифры oi;,. Счетчик 7 предназначен для счета номера итерации , дешифратор 8 - для дешифрации кода номера интерации. Блоки 3 и 4 сдвига осуществляют параллельный сдвиг содержимого регистров 1 и 2 на i ( - Р ) и на ( j +1) разрядов вправо соответственно. Блок 5 сдвига осуществляет параллельный сдвиг содержимого регистра на 2 (j +1) разрядов вправо. При i 1,2,3,,,., П в блоке 3 производятся сдвиги на 1,2,3,..,, И разрядов, в блоке 4 - на 2,3,4,..., |1 разрядов, в блоке 5 - на 4,6,8,.,., h разрядов. Блоки 3-5 выполнены однотипно, на матрицах элементов И, ИЛИ. Сумматор 6 предназначен для преобразования результата -вычислений У {х хра.нящегося на регистре 1 из знакоразрядной системы счисления в двоичную Z У, и для хранения результата. Выполнен в виде параллельного сумматора накапливающего типа с распространением переноса на п разрядов. Функционирование каждого разряда сумматора 9 описывается следующими уравнениями. I этап - выполняется на знакоразряднсм сумматоре 24: If/гЬ.Р Рh i ,гГр1 - )уКйРа й у П этап - выполняется на знакоразрядном сумматоре 25: f(.p4 n-yp co- f;p;- yp t функционирование каждого разряда сумматора 10 описывается следующими уравнениями. . 1 этап. г/л f г г г r+i rtf h Jf((,;).,06j4)j X Рх.. выполняется на знакоразрядном суммато . ре 26, г/ Р г гАг Jf2(2f) Р X Р X , выполняется на знакоразрядном суммато ре 27. И этап 1 р2 выполняется на знакоразрядном суммато ре 28, 111 этап ,Р-И,..р4-1 1 л2, ,Г ,,. выполняется на знакоразрядном суммато ре 29. Знакоразрядный сумматор производит суммирование трех одноразрядных чисел со знаками в прямом коде и является стандартным узлом вычислительной техники. Результаты вычисления переменных . . с иы ходов сумматоров 9 и 10 поступают на входы регистров 1 и 2, где они хранятся на (i +1)-й итерации., Устройство для вычисления квадратного корня работает следующим образом Вычисление начинается с занесения в регистры 1 результата и 2 аргумента значения аргумента X. Счетчик 7 обнуляется. Далее производится выполнение итераций в соответствии с-уравнениями (7) и (8). На каждой итерации выполняются следующие действия. В счетчике 7 производится прибавление единицы, в дещифраторе 8 дешифруется номер итерации. В блоке 12 анализа знака по значеш ям трех старших разрядов регистра 2 формируются значения двоичных перемен ных Р , S и В; значение переменной В поступает на вход блока 11 фopмнp Jвaни сдвига, значения 5 и В - на управлян щие вхбды первого 13 и второго 14 бло ков формирования знака. В блоке форми рования сдвига 11 формируется величина сдвига j (i -Р), которая поступает : на соответствующие входы блоков сдвига 3-5. 1 7зе8 В блоке 3 сдвига происходит на { { - +1) разряд, в блоке 4 сдвига на (-i - 6 ) разряд, в блоке 5 сдвига на 2(i -0 + 1) разряд вправо. Причем на информационный вход блока 3 сдвига поступает переменная У с регистра 1, на информационный вход блоков 4 и 5 сдвига поступает переменная X, с регистра 2. В первом 13 и втором 14 блоках формирования знаков производится формирование знаков сдвинутых переменных У и с учетом значения переменйых 5 и В. Таким образсы, на выходах блоков формируются вторые слагаемые в уравнениях (8) и (7). На выходе блока 5 сдвига формируется третье слагаемое уравнение (7). Далее в сумматоре 9 происходит формирование суммы в соответствии с уравнением (8) первого и второго слагаемых поступивших соответственно с выходов разрядов регистра 1 и выходов блока 13. Во втором сумматоре 10 происходит формирование суммы в соответствии с ура&нением (7) первого, второго и третьего слагаемых, поступающих с выходов регистра 2, второго блока 14 формирова.;шш знака и с третьего блока 5 сдвига. Затем результаты . суммирования У и с выходов блоков 9 и 1О записываюгся на регистры 1 и 2. При этом на регистр 2 переменная . записывается со сдвиге на один разряд влево, а очередной старший нулевой разряд переменной теряется. Однако оставшиеся значения разрядов дробной части обеспечивают правильное выполнение алгоритма вычисления корня. После выполнения п итераций в регистре 1 хранится результат--.вычисления. У -fA представлен в знакоразрядной системе счислений. Преобразования результата в обычную двоичную систему производится на сумматоре 6 с распространением переноса. Преобразование на сумматоре сводится к алгебраическому суммированию двух положительных и двух отрицательных чисел, представленных на триггерах регистра 1. Использование новых элементов сумматоров, блоков формирования знака, третьего блока сдвига, €лока формирования сдвига и блока ашпвза сокращает время выполнешш втерацин в предлагаемом устройстве по сравнению с указанньм npoTOTHnftvii В прототипе на каждой итерации производятся суммирование двух 9i.oo 1 -резрядвых чисел на tf разрядном сумматоре с распросгране1шем переносов через все разряды. Таквм образом, обшее время вычисления квадратного корня, выпопненное в единицах задержка на эпе;менте, пропорционально П . В пр1едлагаем(Я«{ устройстве суммирование на каждой итерации производится в знакоразрядной системе счисления, при 8ТОМ распространение переноса ограничено

Т а б л и ц а 2 aelo разрядами:. Поэтому суь«мар1к е врё мя вычвспенвя корня в предлагаемом устройстве, вь раженное в единицах задержки на элементе, пропорционально rt В табл. 2 приведены расчетные значения времени вычисления квадратного корня в прототипе Т(| и в предлагаемом устройстве Т для различных значений разрядности П и соответствующие им значения коэффициента увеличения быстродействия К. Таблица

/3 ,

/

I

it

fpae.i

n

/ f (pira.J

И

19

/7

17

19

J-3

IS

77

(pus. 5

фиг.6