SU1008736A1 - Устройство дл вычислени квадратного корн - Google Patents

Abstract

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

Description

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

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

Изобретение относитс  к вычислительной технике и может быть использовано в быстродействующих ЦВМ, а также при построеннв спепналиэированных процессов вычислительда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

Claims (4)

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

2. У стройство по π. 1, о т л и наго щ е е с я тем, что блок формирования сдвига состоит из η групп элементов И и ИЛИ (где п. -разрядность устройства), каждая из которых содержит первый и второй элементы И, элемент ИЛИ, причем первые входы первого и второго элементов · Й '1 -й группы ( < = 1,2,..., П) объединены и соединены с 1 -м разрядом первого входа блока формирования сдвига, а вторые входы первого и второго элементов И Λ -й группы соединены с вторым входом блока формирования сдвига, выходы второго элемента И < -й группы и первого элемента И ( ί +1)-й группы подключены соответственно к первому н второму входам элемента ИЛИ f -й группы, выход которого является выходом, ί -го разряда блока формирования сдвига,

3. Устройство по п. 1?о т л и чего щ е е с я тем, что блок формирования знака содержит η групп элементов И, ИЛИ и ИЛИ-HE (где П - разрядность устройства), каждая из которых содержит.· первый и второй элементы И, элемент ИЛИ и элемент ИЛ И-НЕ, причем в ί -й группе (4 =1,2,..., П ) первые входы первого и второго элементов И соединены с 1 -м разрядом информационного вхо-

3>

да блока формирования знака, вторые входы первого и второго элементов И

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

ИЛИ-HE ΐ -й группы, выход второго элемента И t -й группы соединен с вторыми входами элементов ИЛИ и ИЛИ-НЕ · ( -й группы, выходы элементов ИЛИ и

ИЛИ-HE ί —й группы соединены с выходом

1 -го разряда блока формирования знака.