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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

Союз Советских

Социалистических

Республик

<„,922735 (61) Доаолнительное к авт. свид-ву (22) Заявлено 3Q11.79 (21) 2845435/18-24 с присоединением заявки ¹ (23) Приоритет

Опубликовано 230482 Бюллетень ¹15

Дата опубликования описания 23.04.82 (51) М. Ки.з

G F 7/552

Государственный комитет

СССР по делам изобретений и открытий (53) УДК 681 ° 325 (088.8) (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КВАДРАТНОГО

КОРНЯ

Устройство относится к вычислительной технике и предназначено для использования в универсальных и специализированных ЦВМ.

Известно устройство для вычисления квадратного корня, которое со-. держит счетчик циклов, дешифратор, сдвигатель, регистр результата, промежуточный регистр, первый, второй, третий и четвертый сумматоры (1).

Недостатком устройства является низкое быстродействие.

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

Быстродействие устройства не превышает тд = (n + 2)(t „ + tq) где n — число разрядов входного регистра; ТА- время возведения в квадрат; t q +tg- суммарное время срабатывания схемы сравнения и блока подбора цифр результата (2) .

Недостатком известного устройства является низкое быстродействие.

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

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

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

Устройство (фиг. 1) содержит входной регистр 1, дешифраторы 2 и 3 (объединенные в блок управления сдвигом), сдвиговые регистры 4 и 5 (объединенные в блок сдвига), регистры б — 18; выходной регистр 19, сумматор 20 и 21, блок 22 возведения в квадрат, блоки 23 и 24 сдвига, блоки 25 и 26 памяти, дешифратор 27 и блок 28 синхронизации.

Блок управления сдвигом предназначен для определения четного количества разрядов, на которые надо сдвинуть аргумент, чтобы интервал его изменения был в пределах 1/4,1.

Сдвиг 16-разрядных входных чисел производится в два этапа, поэтому указанный блок содержит две ступени управления — дешифраторы 2 и 3 (фиг. 2 и -3),состоящие из элемента

ИЛИ 29 и элемента И 30.

Блок сдвига — регистры 4 и 5 сдвига обеспечивает сдвиг аргумента на указанное блоком количество разрядов и также содержит две ступени регистры 4 и 5 сдвига, состоящие из элемента И 30 и элемента И-ИЛИ 31 (фиг ° 4 и 5) .

Блоки 25 и 26 служат для хранения констант, которые используются в процессе вычисления квадратного корня.

Емкость блока зависит от требуемой точности вычислений. Адресация к блоку осуществляется по К старшим разрядам входного числа. (О Блок 24 сдвига осуществляет сдвиг на указанное дешифратором 27 количество разрядов, которое зависит от, кода, хранимого в регистре 14.

Регистры устройства служат для промежуточного запоминания результатов вычислений и для обеспечения конвейерного способа обработки данных, Устройство предназначено для обработки ненормализованных данных, представленных в формате с ФИксированной запятой.

Нормализация данных производится дешифраторами 2, 3 и регистрами 4 и 5 сдвига следующим образом. Аргумент Хl, поступивший в регистр 1, преобразуется к виду Х Х 2 где Х - сдвинутый на Р разрядов влево аргумент Хl, P - -количество разрядов, на которое сдвигается аргумент

Хl для его приведения к интервалу (1/4, l) причем Р всегда четное.

Приведения интервала изменения аргумента (О,l) к интервалу (l/4,1) производится в два этапа. На первом этапе первый дешифратор 2 анализирует состояние разрядов входного регистра

1 группами по четыре разряда и вырабатывает управляющиесигналы у,,у>,у и

yq,которые служат для управления сдви40 гом на 0,4,8 и12 разрядов соответственно и которые описываются формулами

Y q = a vaqvaqUa+., Y 1 — — Y< (agVa)

У уа(agUa g Ua «Va q)

45 Y, = у.,- 7 . 7 (а < Ua „ Ча„5 Va (), Схемное цостроение этих уравнений представлено на фиг. 2. Таким образом производится приведение интервала изменения аргумента как минимум

5() к интервалу 1/16, 11.

На втором этапе второй дешифратор 3 анализирует состояние четырех старших разрядов сдвинутого числа.

Дешифратор 3 вырабатывает управляю55

Yg = а„ ч, а .

° УЕ = а1 м-аа где а - -й разряд сдвинутого числа, 1 схемная реализация которого представлена- на фиг. 3. Но данным сигналам осуществляется сдвиг на 0 -:или 2 разряда влево, в результате чего получаем аргумент, приведенный к интервалу (1/4, 1) .

Регистры 4 и 5 сдвига осуществляют сдвиг аргумента по сигналам уп922735 равления дешифраторов 2, которые по. казаны на фиг. 4 и 5.

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

9 Гх„= Гх.2 = 1х 2 "-.

Поскольку

P = Y>- 2 +Y ° 2 +Y>-2 +У+(2 +2 ) то

2 5+У0. 2 +73 2 +74(2 + 2 ), 1 ll 1 а. (0, 000625) )p = (О, 0000000000101000) .

В первом такте, после записи этого числа во входной регистр 1 дешифраторы 2 и 3 вырабатывают следующие

15 управляющие сигналы

У„= О; V<= О; К = 1> „= О; = 1

Сдвиговые регистры 4 и 5 производят сдвиг числа влево на

P = У5. 2 "+У0. 2 +УЗ 2. +Yg(2 + 2 j = 10 разрядов. Во ьгором такте в регистр

9 записывается число — =(5) о= (101)1

1 в регистр 14 со схемы сдвига поступает число (0,1010000000000000)1 ..(О 635)!О

По адресу, указанному 5 старшими разрядами, из блока 25 считывается константа В = †(1,890108027) 0 (-1,1110001111011110) 1 °

На сумматоре 20 производится форми30 рование суммы (Х + В), равной .

1 "65108027)о=(1 0100001111011.110)

В третьем такте это число записывается в регистр 12, в регистр 7 записывается число (101) и в регистр

35 15 - число (10100) ) . В блоке, 22 формируется выражение (Х + В), равное Е (1, 60049831997)(p (1, 1001100110111010 $

B четвертом такте это выражение за" писывается в регистр 13, в регистр

4р 8 записывается число (101)g и в регистр 14 — число (10100)0, по которому в дешифраторе 27 вырабатывается сигнал, управляющий. сдвигом на два разряда вправо в блоке 24 сдвига, 45 по которому из блока 26 выбирается константа A = (1>190693202)gp (1,0011000011010001) . В блоке 24 сдвига производится сдвиг, и в пятом такте в регистр 16 записывается число (-0,401245)„, =(-0,0110011ОО1101НО) .

В регистр 9 записывается число (101$, и в регистр 17 — константа А, На сумматоре 21 формируется сумма

A + (Х + В) 1, равная (0,790568622)qp =, 55 = (01100101001100010)y .

В шестом такте это число записывается в регистр 18, в регистр 10 записываетСя число (101)0, которое управляет сдвигом в блоке 23 сдвига.

60 В седьмом такте из блока 23 сдвига в выходной. регистр. 19 поступает число (О 0249999749)(0 (О 0000011001100110 которое и является искомым результатом. Поскольку 0,000625 = 0,025 = (0,0000011001100110)у, то ошибка

Данное число поступает с выходов дешифраторов по регистрам 6 — 10 на блоки 23 сдвига, который и осуществляет сдвиг на Р/1 разрядов вправо.

Блок 23 тоже может быть построен в две ступени, в первой из которых осуществляется сдвиг на 0,1,2,3 разряда вправо» на второй — на 0,4 разряда вправо.

Вычисление функции Y = 1ГХ произ-. водится на основе метода сегментной .аппроксимации выражением

Y = А+ W(X+ B) где коэффициенты A и В выбираются из условия минимизации абсолютной погрешности, а коэффициент W задается в виде константы вида +1, + 2, 3, + 1/2, + 1/4, + 1/8 и т.д. Диапазон изменения аргумента (1/4,1) разбивается на интервалы, количество которых определяется требуемой точностью, причем границы интервалов выражаются К старшими двоичными разрядами аргумента. На разных интервалах константы имеют равные значения, которые рассчитываются на ЭВМ для

16-разрядных входных чисел.

Приведенный к диапазону fl/4,1) операнд X с регистра 5 сдвига поступает на регистр 11 и далее на сумма тор 20. Одновременно из блока 25 по. адресу, укаэанному К старшими разрядами аргумента Х регистра 11, выбирается константа В и поступает на сумматор 20, в котором вырабатывается сумма (Х+В). Полученная сумма через регистр 12 поступает в блок

22, где возводится в квадрат, и за-писывается в регистр 18.. Одновременно К с-.àðøèõ разрядов аргумента Х проходят через регистры 15 и 14 и поступают на дешифратор 27 и блок 26

Дешифратор 27 в зависимости от интервала формирует требуемую константу W которая представляет собой степень числа 2, и на блоке 24 сдвига формируется выражение W(X+B) которое поступает на регистр 16.

Одновременно производится выборка константы А из блока 26 на регистр

17. B сумматоре 21 производится выработка суммы A + W(X+B) кото" рая поступает на регистр 18, а из него — на блок 23 сдвига где

Р

1 сдвигается на — разрядов вправо, а оттуда поступает на выходной регистр

19. Выработка управляющих сигналов производится в блоке 28 синхронизации.

Для примера рассмотрим процесс извлечения квадратного корня из числа

922735 не превышает 2 ", т ° е. устройство обеспечивает вычисление функции с ошибкой, меньшей единицы младшего разряда °

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

Быстродействие устройства при выполнении одиночных операций равно = К 1 где К вЂ” количество межрегистровых промежутков.

В данном устройстве К 7, тогда

Т1=. 7t .

Быстродействие в предлагаемом устройстве увеличено по сравнению с известным при обработке .массивов данных в

10 (n+2 )(t + д, Я

25 а при выполнении одиночных one@a " ций — в — — — — 1

T 7t

Для 15-разрядных входных чисел, принимая типовые значения „=165 нс, 600 нс, имеем — (15+2) - (1+ ) = 78,8 (раэ) 3> тд 15+2 600

7 7 (1+ — ) = 11,26 (раз).

165

- -). раэ;.

t a

30 — (1+

С увеличением разряДности входных чисел преимущество увеличивается.

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

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

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

s: квадрат, выход которого подключен к информационному входу восьмого регистра, выход которого подключен к информационному входу второ о блока сдвига,.управляющий вход которого соединен с выходом третьего дешифратора, вход которого и вход второго блока памяти соединены с выходом девятого регистра, .информационный вход которого подключен к выходу десятого регистра, соединенного информацион-. ным входом с выходом старших разрядов шестого регистра, выход второго блока сдвига подключен к инФормационному входу одиннадцатого регистра, выход которого соединен с первым входом второ|о сумматора, второй вход которого подключен к выходу двенадцатого регистра, информационным вхо-. дом соеднненного с выходом второго блока памяти, Выход втсрого сумматора подключен к информационному входу тринадцатого регистра, выход которого подключен к информационному входу первого блока сдвига, выход которого соединен с информационным входом выходного регистра, выход блока синхронизации подключен к управляющим входам всех регистров.

Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР

Р 239665, кл. G 06 F 7/38, 1969.

2. Авторское свидетельство СССР

Р 611208, кл. б 06 F 7/38, 1975 (прототип) .