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

 

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

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

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

РЕСПУБЛИК

„„Я0„„15751

j5))5 G 06 F 7/552

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

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

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГННТ СССР

1 (21) 4478538/24-24 (22) 25.08,88 (46) 30,06.90. Бюл, ¹ 24 (72) А.Д.Марковский, Г.Г.Меликов, О.И.Пустовойтов, В.M.Äåðåâÿíêèí, П.Ф.Иващенко и П,П,Афанасьев .(53) 681.325(088,8) (56) Авторское свидетельство СССР

¹ 732863, кл. G 06 F 7/552, 1980.

Авторское свидетельство СССР № 1381497, кл. 0 06 F 7/552, 1986. (54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ KBAgРАТНОГО КОРНЯ (57) Устройство относится к цифровой вычислительной технике и может быть

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

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

На фиг, l представлена структурная схема устройства; на Аиг,2,3 — варианты функциональных схем блока сдвига и блока управления соответственно.

Устройство (фиг, 1) содержит регистры 1-3, сумматоры 4 и 5, мультиплексоры 6 и 7, блоки сдвига 8-10, блок ll управления, блок 12 формиро- вания результата, сумматоры 13 и 14

2 использовано в универсальных и специализированных вычислительных системах для аппаратной реализации операции извлечения квадратного корня из чисел. представленных в двоичной системе счисления в форме с фиксированной и плавающей запятой. Цель изобретения — повьпление быстродействия устройства. Поставленная цель достигается тем, что в устройство, содержащее три регистра, два сумматора, три блока сдвига, два мультиплексора, блок управления, блок формирования результата, введены два сумматора по модулю два с соответствующими связями, 3 ил, б по модулю два, вход 15 задания порядка аргумента, вход 16 задания мантиссы аргумента, вход 17 запуска устройства, тактовый вход 18 устройства, выходы 19 и 20 порядка и мантиссы результата, выход 21 признака конца опер ации.

Блок сдвига (фиг. 2) содержит элеМ 4 б менты И 22, элементы ИЛИ 23, входы

24-26, выход 27, Блок управления (фиг,3) содержит элементы НЕ 28, элементы ИЛИ 29, элементы И 30-33, вход 34, выходы 35-40, В основе работы устройства лежит следующий способ вычисления значений

Аункции у= », Значение аргумента еЬ представляется в виде х=? М. Порядок

Р представляется (г+1)-разрядным дополнительным кодом аоа,а ...а, где а — знаковый, а а,,а .....,,,а,.—

0 числовые двоичные разряды. Мантисса

1575177

M представляется (и+! )-разрядным дво чиным кодом b b Ь ...b„, где Ь„- знаковый, Ь1,b< b» Ь | - числовые двоичные разряды (мантисса аргумента всегда неотрицательна), Значение результата вычисляется с использованием разложения приведенной мантиссы М аргумента х на множители вида (1+ Я к 2 ")", где

М при а„=О (1) М/2 при а„=!.Если aprумент х представить в,виде р l1 p+1)о „-к -

x=2 M=2 ° М =2 Г!(1+ Я„2 " ) К=1 (2) .где К = 1

P при а =О

Р+1 при а„=! е

Д,1 Д 1е «4 ° ° o ге ° ер (3) то значение искомой функции у можно определить выражением 25 у = Гх2Р / M=2 . ()(1ег 2 ) (4) К= l где Ц = Р /2

Ъ (5) 30

Вычисление мантиссы результата йроизводится с использованием итераци онных формул

-j К (2, k -) .-)

k 1 К е К К k

=Мк+ =к™к 2 (6)

sgn (1 — zк)

Порядок Q результата опрецеляется в соотвешствии с выражениями (3) и 40 (5). Начальные значения М и z, определяются в соответствии с выражениями

М = г =М»

1 1

Значение !к при выполнении К-ой итерации выбирается равным номеру 45 старшего нулевого (единичного) раз-! Яда дРобной части кода z< пРи Як (1 (з>1), если z<(j к) P z<(j"Ä+1) и на единицу меньше номера j+ старшего нук левого (единичного) разряда дробной части. кода Як, если z<{j )--z<(j„+1), где ег(1) — значение -го дноичиого разряда кода z<, Значение jк задается в устройстве унитарным m-разрядным двоичным кодом Tk 55 содержащим единицу в ) -ом разряде и нули в остальных разрядах, Величина п1 и +! определяется требуемой точностью вычислений, Логическое уравнение, определяющее значение $ -го разряда 2г(11 2(1,2...ml ), имеет нид

М. +

Х >(()=zk(p) Л z „(+1 )ag, z,(i) Vz „(p+

+1) Л z „. ((+2)hg z (ç-) в (7) где "(P)=я„(j)ez„(O)

Признаком окончания операции служит условие 1-z +,! <О.ОО... 1/ 1ед

/1, ) . 2-)е)

1 5

S Е (1,2,...о(2е1) (8)

Величина М +1 при этом используется в качестве мантиссы результата.

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

В исходном состоянии разряды с первого по ш-й ())+1)-разрядного регистра 1, используемого для хранения величины z, имеют одинаковое (либо нулевое, либо единичное), значение, Вследствие этого, значение признака "Конец операции" на третьем выходе блока

11 управления равно единице, а значе-. ние сигналов на первом и втором выхо.-. дах блока 11 управления равно нулю, На вход 18 устройства непрерывно поступают тактовые импульсы (TV).

На вход 15 и вход 16 устройства поступают значения порядка и мантиссы аргумента соответственно. Код порядка аргумента со входа 15 поступает на информационный вход третьего 3 регистра, код мантиссы аргумента — на первые информационные входы первого

6 и второго 7 мультиплексоров.

Младший разряд кода порядка а). поступает на первые управляющие входы первого б и второго 7 мультиплексоров.

Если значение младшего разряда ко; да порядка а> равно нулю, то код мантиссы, поступивший на первые информационные входы первого 6 и второго

7 мультиплексоров, проходит на входы мультиплексоров без преобразования.

При единичном значении а> код мантиссы, поступивший на первые информационные входы первого б и второго

7 мультиплексоров, проходит на входы мультиплексоров со сдвигом на один разряд в стррону младших разрядов, Сформированное на выходе первого б и второго 7 мультиплексоров прчведенное значение мантиссы аргу+ мента М поступает на информационные входы первого 1 и второго 2 регистров.! 575177 6

Для выполнения вычислений синхронно с одним из ТИ на вход 17 устройства подается сигнал "Пуск", который поступает на вход блока I I yn.равления, а также на вход разрешения записи третьего 3 регистра, осуществляя занесение на третий регистр 3 значения порядка аргумента р, По сигналу "Пуск" на первом выходе блока 11 управления формируется сигнал "3анесение", который поступает на входы разрешения записи первого 1 и второго 2 регистров и осуществляет занесение в первый регистр 1 величины z =Yi и

4f во второй 2 регистр — величины М1=N.

+.

Если значение мантиссы аргумента

М не равно нулю (единице), то процесс вычислений .реализуется следующим образом, При выполнении первой итерации значение z (О) равное нулю при Я,=1 и единице при,=-1, поступает с выхода первого регистра 1 на первые входы первого 13 и второго 14 сумматоров по модулю два, на вторые входы которых с выходов первого 1 и второго 2 регистров поступают значения М и z< соответственно, Первый 13 и второй. 14 сумматоры по модулю два производят поразрядное суммирование по модулю два кодов M .и z< соответственно с кодом в1 (0), формируя на своих выходах значения Я М, и P M„, С выхода первого 13 сумматора по модулю два значение Я» z поступает на первый вход первого блока 8 сдвига и на третий вход блока 11 управления. С выхода второго сумматора 14 по модулю два значение,f - M посту1 1 пает на первый вход третьего блока 10 сдвига, Поступление отличного от нуля (единицы) кода p, z на третий вход блока 11 управления приводит к появлению на третьем выходе блока 11 управления нулевого уровня признака "Конец операции", а на втором выходе — единичного уровня сигнала "Выбор входа".

Кроме того, первый выход блока 11 уп-,. равления подключается к его второму входу, обеспечивая прохождение оче- редных ТИ на входы разрешения записи первого 1 и второго 2 регистров.

По коду Г, z на четвертом, пятом и шестой выходах блока 11 управления формируется (m +I -разрядные коды, содержащие единицу в (j +1)-м (j )-м и (2j 1+2)-м разряде соответственно и нули в остапьных разрядах, которые по5

30 типлексоров, в результате чего коды

z и М поступают íà информационные входы первого 1 и второго 2 регистров соответственно. С приходом оче40 редного ТИ значения z и М заносятся. в первый i и второй 2 регистры соответственно. На этом выполнение пер вой итерации завершается.

В процессе выполнения второй ите45 рации >о 3H<

Итерационный процесс продолжается до тех пор, пока в результате вы" полнения очередной S-ой итерации все

m старших числовых разрядов числа

55 с, о з „не станут одновременно равныI ми единице. При этом блок 11 управления запрещает прохождение ТИ со своего второго входа на первый выход и ступают на вторые выходы третьего 10 первого Я и второго 9 блоков сдвига соответственно (значение j определяется в соответствии с приведенным вывыше алгоритмом), Первый 8, второй 9. и третий 10 блоки сдвига осуществляют умножение поступающего на их первь е входы коды на 2, 2 и 2 соответственно путем сдвига в сторону младших разрядов, В освобождающиеся разряды записывается значение, поступающее на третий вход соответствующего блока сдвига, Код z поступает на второй вход второго 9 блока сдвига с выхода первого регистра 1. С выхода второго регистра 2 значе же М поступает на второй вход блока 12 формирования ре-. зультата, на первый вход которого с выхода третьего регистра 3 поступает значение порядка, Первый 4 и второй 5 сумматоры производят вычисление значений z z и М согласно выражениям (6) . С выходов первого 4 и второго 5 сумматоров значение величин z и М поступают на вторые информационные входы первого

6 и второго 7 мультиплексоров соответственно. Наличие единичного значения сигнала "Выбор входа" на вторых управляющих входах первого 6 и второго 7 мультиплексоров обеспечивает прохождение информации с вторых информационных входов на выходы муль1575177 формирует на третьем выходе единичное значение признака "Конец операции" и на втором выходе — нулевое значение сигнала "Выбор входа".

По окончании процесса вычислений

5 на первом выходе блока 12 формироваНие результата формируется значение порядка результата в соответствии выражениями (3) и (5) а на втоУ 10 ром выходе блока 12 формирования результата — округленное до и числовых азрядов значение мантиссы результата, Сформированные блоком 12 форми1)ования результата порядок и мантисса

15 результата поступают на выходы 19 и 20, 20 устройства, Если при начале вычислений значейия всех m разрядов z равно едини .1

Це или значение всех m разрядов z равно нулю, то значение признака "Ко- нец операции" на выходе 21 устройства остается равным единице и вычислейий по формулам (6 ) не производится.

В качестве результата используются 25

Значения порядка и мантиссы сформи1 кованные блоком 12 формирования реЗультата по поступившим на его входы значениям Р и М

Блоки 8-1.0:сдвига работают следую- Зг, Щим образом, На первый 24 вход блока поступает

V-разрядный информационный код, на второй вход 25 блока — (V-1)-разряд-. ный управляющий код, имеющий единицу а i-ом раараде (iE Cl,2...,V-) )) и нули в остальных, Единичный разряд управляющего. кода поступает на вторые входы j -х элементов И 22 кажДой )ой ГРУппы (2 е Cl 21... У) ) 4Р йа первые входы которых поступают (j-i)-ые разряды информационного кода (при 1 1) или значение сигнала с третьего входа 26 блока (при i Оj).

В результате входыой информационный йод сдвигается на i ðàýðÿäoâ вправо и освобождающиеся разряды заполняются значением, поступившим на третий 26 вход блока, Блок 11 управления работает следующим образом, .Сигнал "Пуск", поступая на первый вход 17 блока, проходит через m-й элемент ИЛИ 29 и далее на первый 35 выход блока в качестве сигнала "Занесейие", Старшие ш разрядов поступающего на третий вход 34 блока (m+1)-разрядного кода передаются на входы первого элемента И 33 четвертой группы и через инверторы 28 — на входы второго элемента И 33 четвертой группы, Если все m старших разрядов кода

l поступающего на третий вход 34 блока, равны единице (нулю), то на выходе первого (второго) элемента И 33 чет вертой группы фррмируется единичный сигнал, который проходит через (m+1)-ый элемент ИПИ 29 и поступает на .третий выход 21 блока в качестве сигнала "Конец операции".

При наличии хотя бы одной единицы и хотя бы одного нуля одновременно в m старших разрядов третьего 34 входа блока сигнал ",Конец операции" на третьем выходе 21 блока имеет нулевое значение, а на выходе (ш+2)-ro элемента НЕ 28 — единичное значение которое поступает на второй выход

36 блока, а также на второй вход тре-. тьего элемента И 33 четвертой группы, разрешая прохождение через третий элемент И 33 четвертой группы ТИ, поступающих с второго входа 18 блока.

С.выхода третьего элемента И 33 четвертой группы ТИ через m-ый элемент ИЛИ 29 поступают на первый выход 35 блока в качестве сигналов "Занесение"

Единичное значение (-го разряд .1( да кода g „на выходе (P -1)-ro элемента И 30 первой группы (a.g (2,3, ...m ) формируется при наличии единичных значений во всех разрядах, номер которых меньше и нулевого значения в -ом разряде кода, поступившего на третий вход 34 блока, При

=-1 единичное значение 1-го разря° М да кода j „ формируется первым элемен- . том НЕ 28„

Ециничное значение P --ro разряда (рЕI ),2,...,ш-)) ) кода j4 Формир(уется на выходе Р -го элемента ИЛИ

29 при равенстве нулю (,P +1)-ro u (у +2)-ro разрядов кода, поступающего на третий вход 34 блока с использованием j)-го элемента И 31 второй группы, и при равенстве нулю р -го и единице ((3 +1)-го разрядов кода, поступающего на третий 34 вход блока с использованием p --ro элемента И 32 третьей группы, Единичное значение m-го разряда кода j формируется ш ым элементом И 32 третьей группы. Остальные разряды кода ) „ принимают нулевое значение.

По коду, поступившему иа третий вход 34 блока, на четвертом 37, пя10

1575177

21 том 38 и шестом 39 выходах блока формируются коды, имеющие единичное значение в (P+I)-м Р -м и (2 P +2)-м разрядах соответственно и нули в ос.тальных разрядах.

Формула изобретения

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

1575177

Z4,V

24И

1 i I

1 !

1575177

Зд. 5

М,2

Мn7

8лм1

& 8

38 v-f

Ял 1

Заказ 1785

Тираж 569

Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101

Составитель А.Марковский

Редактор Н,Киштулинец Текред Л. Сердюкова Корректор С,Шекмар,ЭУ $

7.2

373

Л 1

37лмя

579- f