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

 

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

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

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

РЕСПУБЛИК

3144 А1

09) . (11) (51) 4 G 06 F 7/552

Ь .

1 с

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

К A BTOPCHOMV СВИДЕТЕВЬСТВУ

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

ГО ДЕЛАМ ИЗОБРЕТЕНИЙ ИОТНРЫТИЙ (21) 3750819/24-24

{22),06.06.84 (46) 23.05.86. Бюл. ¹ 19 (72) А. Ю. Глазачев (53) 681.325(088.8) (56) Naj ithia I.Ñ. Cellular Aray for

Extraction of Squares and Square

Roots of Binary Numbers. — IEEE

Trans Comput, 1972, vol. С-21, № 9, р. 1023-1025.

Вычислительная техника. ЛГУ, 1977, ¹ 6, с.105-111, рис. 2, 1. (54) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ (57) Изобретение относится к вычислительной технике. Цель изобретения— повьппение быстродействия. Устройство

% является однотактным. Процесс извлечения корня в течение такта разбит на r ступеней, в каждой ступени определяется q разрядов п-разрядного результата r = n/q. Процессы во всех ступенях аналогичны, различие только в величине разрядности с увеличением номера ступени. Разрядность вычислений внутри ступени возрастает. Для определения q цифр корня в одной ступени одновременно определяются 2 -1

1 разностей остатка предыдущей ступени и соответствующих "углов" данной ступени. По знакам разностей данной ступени определяются q цифр корня данной ступени, Остаток ступени определяет- Ж ся в виде двух чисел. 1 з.п. ф-лы, 2 ил.

Диаграмма соответствия

О -1 -2 -3 -4 -5 -б -7 -8 -9-10-11-12-13

Вес

0 1 1 О 1 1 1

О 1 1 О 1 1 1

О О О О О О О у, О 1 1 О 1 1 1 уа

О 1 1 О 1 1 1

О О О О О О О уз

О 1 1 О 1 1 1

У4

О 1 1 О 1 1 1

У5

О 1 1 О 1 1 1

О 1 О 1 1 1 1 О 1 О О О 1

О 1 1 О О О О

1 О 1 1 1

О О 1 О О О О О О

1 1 1 1 1

1 1 1 О О 1 1 !

К, У f (I I I)

Ш, Ш (II) 1 строка 25

В =В а у„ (q) 1

12331

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

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

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

Функциональная схема устройства содержит суммирующие ячейки 1.1,1, 1.1.2. . .1.2.1,,1.r,k, шифраторы

2.1,...2.r, группы элементов HE

3.1,,3.(r-1), коммутаторы 4,1..1, 4.1.2,...,4.(r-1), входную шину 5 и шину 6 логического "О" устройства.

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

Вычисление квадратного корня в устройстве осуществляется за один такт. Подкоренное выражение A подает44 2 ся на входную шину 5 устройства.

После распространения сигнала на выходах шифраторов 2.1,...2.r появляется значение результата. Подкоренное выражение положительно и находится в пределах О A 1. Устройство содержит несколько строк. В каждой строке одновременно образуется о разрядов квадратного корня. Количество строк равно r = n/q, где n - -разрядность значащей части подкоренного выражения без учета знака. Разрядность и кратна q. Результат также ! имеет разрядность.

На диаграмме соответствия приведен пример извлечения квадратного корня иэ числа А =0,1 01111010001 для случая n=6 и q=2. Внизу на диаграмме соответствия ИЬображен процесс извлечения квадратного корня, а вверху показано УМножение Ш Ш = А и

"углы" У от приращения очередного разряда квадратного корня Ш.!

233!44

2 строка о о о о

У, У К о о о о в,=в, 0 l О О О О

О О

О О О О

Ш, Ш, О!

У (q) О О О

О О О О

О О О

О О О

О О О О

У (q) 3 строка

1 1 1

О О О, О О О О О О О О в,=в, д

Т а б л и ц а 1

Цифры квадратного корня

Остаток строки

Опережающие переносы

1 2

1 2 3

B,=A,+У, A, + У, О О

О 1

1 О

1 1 (q);

+У, ) (q), В=А,4+(У, углы где используемые

У, (q) У2 (q) (У, +У,) (q) 111;

11111;

10111.

П р и м е ч а н и е. Все углы не являются

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

В, =А, - Уг 1 Вг А 1,4 У, в = A, — (s,+У ), где А, — значение четырех старших

1 разрядов подкоренного выражения; верхний индекс "0 1 или "lп при втором "угле" У означает, что данный

"угол" вычислен при значении первой цифры результата данного цикла, равном соответственно "О" или "1".

На выходах коммутаторов формируются остатки строк в виде двух положительных чисел. Значения "углов

У<, У, У,... берутся в дополнительном коде, поэтому первые три разности выглядят следующим образом:

О О ! ! Ш,Ш, l! используемые при вычислении разностей, нулевыми, Опережающие переносы F,, Р и Гз, сформированные на выходах опережающих переносов суммирующих ячеек, поступают на вход шифратора данной строки и на входы управления коммутаторов.

35 Соответственно на выходе шифратора формируются первые две цифры Ш „ и Ш квадратного корня, а на выходах коммутаторов появляется реальный остаток данной строки в виде двух чисел

40 (см. табл.l).

О О О

1 О О

55 1 1 О

1 1 1

123311 цифры корня данной строки, равной

1 единице плюс единица н младшем разряС выходов коммутаторов первой строки числа остатка первой строки подаются на входы суммирующих ячеек второй строки и .на входы коммутаторов второй строки, причем старший разряд остатка исключается. В сум- . мирующих ячейках второй строки происходит образование "углов" второй строки У (q), Ъ (с!) (Уэ+У ) (Ч) в дополнительных кодах и их суммирование с двумя числами остатка В„ первой строки и приращением ьА второй строки. При этом каждый первый нугол" строки в дополнительном коде образуется как удвоенное значение всех цифр корня предыдущих строк, взятых инверсными, плюс единица в младшем разряде, каждый второй угол строки в дополнительном коде образуется в двух вариантах — как удвоенное значение всех предыдущих цифр корня, взятых инверсными и при значении первой цифры корня этой же строки, равной нулю плюс единица в его младшем разряде, а также как удвоенное значение всех предыдущих цифр корня, взятых инверсными, при значении первой де.

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

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

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

Т а б л и ц а 2

Остаток

Цифры корня

Ш „, Ш

3 4...7„, 1 2

U! Ш

0 О О 0 0 О В

1 О 0 О 0 0

0 0 О 0 В г

1 0 О 0 В

1 1

1 1

1 1 О В„, ! 1 1 В

1 1

1 1

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

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

Опережающий перенос

k суммирующих ячеек (где г=n(q;

k=21 — 1,", n — разрядность аргумента; ц — количестBc oänîíðåìåíno определяемых цифр квадратного корня в каждой строке), о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введено 1 шифраторов, (r-1) групп по q элементов

НЕ и 2(r-1) коммутаторов, причем выходы опережающих переносов суммирующих ячеек i-й строки (где Я 1,..., r-1) подключены к входам i-ro шифратора и входам управления (2i-1)-ro 10 и 21-го коммутаторов, выходы опережа.— ющих переносов суммирующих ячеек r-й строки подключены к входам r-ro шифратора, выход j-ro разряда (где j =

1;...,q) z-ro шифратора подключен к входу j"ro элемента НЕ i-й группы, выходы разрядных переносов Z-й суммирующей ячейки (где Z=l,;,k) i-й строки подключены к Z-му информационному входу (2i-1)-го коммутатора, вы20 ходы разрядных сумм 2-й суммирующей ячейки i-й строки подключены к Z-му информационному входу 2i-ãî коммутатора, выход (2i-I)-го коммутатора под25 ключен к первым информационным входам ,суммирующих ячеек (1+1)-й строки, выход 21-го коммутатора подключен к вторым информационным входам суммирующих ячеек (i+1)-й строки, третьи информационные входы суммирующих яче30 ек (+1)-й строки подключены к вход ной шине устройства, выходы элементов

НЕ i-й группы подключены к старшим разрядам, начиная с (q-(i-I))-ro разряда четвертого информационного входа суммирующих ячеек (i+I)-й, ...,Z-й строки соответственно (k+I)-й информационный вход (2d-1)-ro (где d=2, r-I) коммутатора подключен к выходу (2d-3)-ro коммутатора, (k+1)-й информационный вход 2d-го коммутато-. ра подключен к выходу (2d-2)-ro коммутатора, (k+1) -е информационные входы первого и второго коммутаторов подключены к входной шине устройства, выход j-го разряда m-ro шифратора (где m = I,...,r) является ((ш-l)q+

+j) ì разрядом выхЬда результата устройства, первые информационные входы суммирующих ячеек первой стро ки подключены к шине логического нуля устройства, вторые информационные входы суммирующих ячеек первой строки подключены к шине аргумента устройства, третьи информационные входы суммирующих ячеек первой строки подключены к шине логического нуля устройства, четвертые информационные входы суммирующих ячеек первой строки подключены к входной шине устройства.

2. Устройство по и. 1, о т л и— ч а ю щ е е с я тем, что суммирующая ячейка содержит сумматор с сохранением переносов и формирователь опережающего переноса, причем первый, второй, третий и четвертый информационные входы сумматора с сохранением переносов являются соответственно первым, вторым, третьим и четвертым информационными входами суммирующей ячейки, первый и второй выходы сумматора с сохранением переносов подключены соответственно к первому и второму входам формирователя опережающего переноса и соответственно являются выходами разрядных переносов и разрядных сумм суммирующей ячейки, выход формирователя опережающего переноса является выходом опережающего переноса суммирующей ячей КИ1233144

Яiг. S

Puz, 2

Составитель С.Силаев

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

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

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

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

Производственно-полиграфическое предприятие, r.Óæãîðîä, ул.Проектная, 4