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

Изобретение относится к вычислительной технике и предназначено для извлечения квадратного корня из двоичных чисел.

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

На фиг.1 приведена функциональная схема устройства для извлечения квадратного корня; на фиг.2 - функциональная схема суммирующей ячейки.

Функциональная схема устройства содержит суммирующие ячейки 1.1.1, 1.1.2,..,,1.2.1,...1.г,k, шифраторы 2.1,...2.г, группы элементов НЕ 3.1,...3. (г-1) , коммутаторы 4,1.1, 4.1.2,...J 4.(г-1) , входную шину 5 и шину 6 логического О устройства.

Функциональная схема суммирующей ячейки содержит сумматор 7 с сохранением переносов и формирователь 8 i опережающего переноса.

Вычисление квадратного корня в устройстве осуществляется за один такт. Подкоренное выражение А подает

Диаграмма соответстрия О -1 -2 -3 -4 -5 -6 -7 -8 -9-10-11-12-13

0110111 О 1 1 О 111

0000000 0110111 0110111 0000000 0110111 0110111 0110111

А А 25

0101 1 1 1010001 01 10000 10111..

001000000

11111

11100111

ся на входную шину 5 устройства. После расп15остранения сигнала на выходах шифраторов 2.1,...2.г пбяв- ляется значение результата. Подкоренное выражение положительно и находится в пределах . Устройство содержит несколько строк. В каждой строке одновременно образуется q разрядов квадратного корня. Количество

строк равно г n/q, где п - разрядность значащей части подкоренного выражения без учета знака. Разрядность п кратна q. Результат также имеет разрядность.

На диаграмме соответствия приведен пример извлечения квадратного корня из числаА 0,101111010001 для случая и . Внизу на диаграмме соответствия изображен процесс извлечения квадратного корня, а вверху показано умножение Ш- Ш А и углы У от приращения очередного разряда квадратного корня Ш.

р f 2 g

(I I I)

Ш, Ш (II)

строка

в, д

трока

Р

yjq)

Уе,(ч)

1233144 01010011

11001

,010000 0000 11010111

11001011 1110010011 10010-1 1 1 10010

1110010011 I, 1 2

0010

, . д

00 1 001 0000

1 I 1001 1 11 1 Ш Ш I1

7Ь

Примечание. Все углы,

не являются

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

В,А

А

R - Д V

14 2 2 1i4

в, А,. - (У,+У2),

1,

3 4,1

где А,4 значение четырех старших разрядов подкоренного выражения; верхний индекс О или 1 при втором угле У означает, что данный угол вычислен при значении первой цифры результата данного цикла, равном соответственно О или 1.

На выходах коммутаторов формируются остатки строк в виде двух положительных чисел. Значения углов У), Уу , У-,... берутся в дополнительном коде, поэтому первые три разности выглядят следуюпщм образом:

о

В, А,, + У, (q);

.1

BZ А„4 + У (q);

В А,, + (У, У )(q),

где используемые

У, (q) 111; У° (q) 11111; (y.+yjXq) 10111.

.

1 о о

Ш, Ш 01

используемые при вычислении разностей, нулевыми .

Опережающие переносы F, , Е и д, сформированные на выходах опережающих переносов суммирующих ячеек, поступают на вход шифратора данной строки и на входы управления коммутаторов. 35 Соответственно на выходе шифратора формируются первые две цифры Ш и Шг квадратного корня, а на выходах коммутаторов появляется реальный остаток данной строки в виде двух чисел 40 (см. табл.1).

Таблица 1

45

50

55

с выходов коммутаторов первой строки числа остатка первой строки подаются на входы суммирующих ячеек второй строки и на входы коммутато- ров второй строки, причем старший разряд остатка исключается. В сум- мирующих ячейках второй строки происходит образование углов второй строки УЗ (q), У4 (q) (Уэ+У4)(ч) в дополнительных кодах и их суммирование с двумя числами остатка В первой строки и приращением ЬА второй строки. При этом каждый первый угол строки в дополнительном коде образуется как удвоенное значение всех цифр корня предыдущих строк, взятых инверсными, плюс единица в младшем разряде, каждый второй угол строки в дополнительном коде образуется в двух вариантах - как удвоенное значение всех предыдущих ци4)р корня, взятых инверсными и при значении первой цифры корня этой же строки, равной нулю плюс единица в его младшем раз ряде, а также как удвоенное значение всех предыдущих цифр корня, взятых инверсными, при значении первой

о о о

О

о о о

о о о о

о о о о

о 1

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

. Устройство для извлечения квадратного корня, содержащее матрицу

10

15

20

25

цифры корпя данной строки, равной единице , плюс единица н младшем разряде. .

Все действия в соответствующих блоках различных строк осуществляются аналогично.

При большем количестве q одновременно оцределяемых цифр корня в каждой строке нужно одновреметп1о определять (2 -1) разностей. Например, для той же разрядности цри для второй строки нужно вычислять семь разностей остатка соответственно с углами :, Уе , У , (У° +У°) ,

У4,, (У4 1, У е (У. .+ УЗ). (У4 + + У5 + Уб ), где двойные верхние индексы определяют,при каких значениях первой и второй цифр корня данной строки взято значение третьего утла данной строки (У ) .

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

Таблица 2

о о о о

о о

1

о 1 о

в,., в.

г . k суммируюи№1Х ячеек -(где -1; л - разрядность арг-умента; q - количество одновременно определяемых цифр квадратного корня п каждой

строке), отличающееся тем, что, с целью повышения быстродействия , в ycTpofJCTBO введено г шифраторов, (г-1) групп по q элементов НЕ и 2(г-1) коммутаторов, причем выходы опережающих переносов суммирующих ячеек i-й строки (где i4 1 , г-1) подключены к входам i-ro шифратора и входам управления (21-1)-го и 2i-ro коммутаторов, выходы опережающих переносов суммирующих ячеек г-й строки подключены к входам г-го шифратора, выход j-ro разряда (где j Г, ...,q) i-ro шифратора подключен к входу j-ro элемента НЕ i-й группы, выходы разрядных переносов Z-й суммирующей ячейки (где ,...,k) i-й строки подключены к Z-му информационному входу (2i-l)-ro коммутатора, выходы разрядных сумм Z-й суммирующей ячейки i-й строки подключены к информационному входу 2i-ro коммутатора, выход (2i-1 )-го коммутатора под ключен к первым информационным входам ,суммирующих ячеек (i+l)-ft строки, выход 2i-ro коммутатора подключен к вторым информационным входам суммирующих ячеек (+1)-й строки, третьи информационные входы суммирующих ячеек (i+l)-й строки подключены к входной шине устройства, выходы элементов НЕ i-й группы подключены к старшим разрядам, начиная с (q-(i-I))-ro раз

ряда четвертого информационного вхо- да суммирующих ячеек (i+1)-й, ...,2-й строки соответственно (и+1)-й информационный вход (2d-l)-го(где ,... г-1) коммутатора подключен к выходу (2d-3)-ro коммутатора, (,k+l )-й ин- формационньй вход 2d-ro коммутато-- ра подключен к выходу (2d-2)-ro ком50

5

0

мутатора, (k+)-e информационные входы первого и второго коммутаторов подключены к входной шине устройства, выход j-ro разряда т-го шифратора (где m 1,...,г) является ((m-l)q+ +j)-м разрядом выхЬда результата устройства, первые информационные 9ХОДЫ суммирующих ячеек первой стро- ки подключены к шине логического нуля устройства, вторые информационные входы суммирующих ячеек первой строки подключены к шине аргумента устройства, третьи информационные входы суммирующих ячеек первой строки подключены к шине логического нуля устройства, четвертые информационные входы суммирующих ячеек первой строки подключены к входной шине устройства.

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

т

т

kU

Изобретение относится к вычислительной технике. Цель изобретения - повышение быстродействия. Устройство является однотактным. Процесс извлечения корня в течение такта разбит на г ступеней, в каждой ступени определяется q разрядов п-разрядного результата г n/q. Процессы во всех ступенях аналогичны, различие только в величине разрядности с увеличением номера ступени. Разрядность вычислений внутри ступени возрастает Для определения q цифр корня в одной ступени одновременно определяются 2 -1 разностей остатка предыдущей ступени и соответствующих углов данной ступени. По знакам разностей данной ступени определяются q цифр корня данной ступени. Остаток ступени определяется в виде двух чисел. 1 з.п. ф-лы, 2 ил. (Л

ш

--r-g

.гк(

«.2.2

,/

Составитель С.Силаев Редактор И.Николайчук Техред Л.Олейних Корректор Л.Патан

Заказ 3023Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г.Ужгород, ул.Проектная, 4