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

pa {п-1)-ой группы, а выход - со вторым входом второго одноразрядного сумматора (п-1.) группы, первый. вход i-ro сумматора по модулю два группы соединен с входом (2 i-1)-го разряда входного кода устройства и с первым входом i-го элемента ИЛИ группы, выход которого соединен с входом переноса 2(п-i)-одноразрядного сумматора i-ой группы, а второй вход соединен с входом 2t-ro разряда входного кода и со вторым входом t-го элемента ИЛИ группы, а выход соединен со входом i-го элемента НЕ первой группы, выход котоforo соединен с первым входом 2(n-i) одноразрядного сумматора (-1)-ой группы, вход 1-го элемента НЕ второй Г-руппы соединен со вторым входом 1-го сумматора по модулю два группы, а выход с первым входом ч 2 (п - i ) +2 -го одноразрядного осумматора (|-1) группы, выходы переноса первых рдноразряд-ных сум 1аторов и выход п-го элемента ИЛИ группы являются выходами устрой ства, выход п-го элемента ИЛИ группы соединен со входом элемента НЕ.

На чертеже представлена схема устройства для извлечения квадратно го корня для случая .

U значение j-ro переноса

где

из (I-l -го в -и разряд (i

1Ь-- .PY-X, .2n, ,..., n/2-1), равное

Схема содержит разрядные входыо 1 устройства, одноразрядные сумматоры 2, сумматоры 3 и 4 по модулю два, элементы 5, 6, 7 НЕ, элементы 8 ИЛИ,выходы 9 устройства, элемент 4, 6, 7, 8, представляющие собой лгический блок 10.

Работу предлагаемого устройства можно пояснить на примере нахождения квадратного корня X из выражния тГТ Y, представленного в виде

Х- Хх Y, (1)

где X

разрядная матрица, представляющая собой разрядное изображение неизвестного X;

V

X.Y

разрядные векторы, представлякядие собой разрядное изображение X и Y, соответственно.

ч

Для получения неизвестного X . представляем систему разрядных уравнений (1) в развернутом виде с учетом единиц переноса из младших разрядов в старшие, при этом если точное значение квадратного корня представлено п двоичными разрядами, то величина 7 представлена соответственно в виде п разрядов, т.е.

V

гм Р

tt-1 iri-t

-XX

ай V

пп-г гп-i in-i

XX + Рч Pi.

i-n sn

ХХ-«-ХХ Р-1- -...Р«Д-1

in-t «.-1

n« X - XX-t-Vy РЧ...Р.,Ц-(

Y

1 tl-Hm-ttl

И

rty 1-ХХ+Р-|...Р-я/1-

Y

И/l -l.lM-J

Y

...P«/l-J

1

4 ч XX +РЧ

XX

(2)

2.

Y

I

X

5- 4 Ч t - . о

p, XX, ( и т.д. в частности, при выражение (2) может быть записано

8

Р-1

А г 1 7

X - ху р.

XX Чхх хххЬхххх

i

1 1 А

J. -11

1 X

ъ

JL

14 1г и. 1 1 э

г J 11 J

-I J г XX АХ

±

11 XX

(3)

JY

0

1 У

л X

57736176

На основании выражений (2, 3) вычис- -представлен „ 2,

лительный процесс нахождения старше-X Yv Y(Ц)

го п-го разряда вектора X может быть последующего (п-1 )-го разряда в в.иде

где знак®обозначает сложение по модулю два, а каждый i-й разряд

в частности, при можно записать

-:::-t

П

М4 aJa,JU|f4

. I а 7 .-X-Y-Y. Пример. Величина ,472656, или в области изображений Q v (о|о Nh Nhlolo М I оi о I о 11®о oei|(Hivi) l} 1 |i®T

г

о 1 i 1 1

t

.6875, о

,Ц.. р и м е р 2. Величина Y 6,660156, или соответственно в

100

ОКО

разрядной форме Y

10

|ieo((-ivo)| jo |o|i®i|i4(|

1 I о { 0 |o|i{-i{ 1 |i I |i|oto|o i ч IP I

5 oHI-tlohlX 0,8li5

15 -2, Г«-3,..., 1 соответственно

1 1

х®х

т

а,

1

о

Вектор X определяется аналогично по выражению (7) 155

0

1©0

1©0

-f®

1шоТК10||

11 1 Вычислительный процесс нахождения разрядов вектора в соответствии с выражением (7) может быть представлен, в виде х О V 1 1, О I |l|i| 1 Работа устройства по извлечении) квадратного корня начинается при подаче на его входы соответствуннцих значений раэр51дов вектора Y. После окончания переходного процесса в схе ме на выходе элемента ИЛИ групп по выражению (ii)образуется значение старшего п разряда искомой величины, а на выходе переноса каждого одноразрядного сумматора 2 первого разряда i-ой (, 2,..., п-1) группы образуются , соответственно, разряды X, А,... , X искомой величины в соответствии с выражениями (5) и (6). . . в предложенном устройстве благодаря структурной организации существенно увеличивается быстродействие, которое характеризуется временем переходного процесса в схеме, т.е. результат решения получается . за один такт. Формула изобретения Устройство для извлечения квадратного корня, содержащее сумматор, о т л и ч а so щ е е с я тем, что., с целью повышения быстродействия, в него введены элемент НЕ, (п-2) группы из 1(п - i ) последовательно соединенных одноразрядных сумматоров в каждой группе (где i- номер группы, а - разрядность выходного кода), группа из п сумматоров по модулю два, группа из п элементов ИЛИ первая и вторая группы элементов НЕ по п элементов в каждой, (п-2) дополнительных -групп из (n-i-l), (где ,...,п-2) сумматоров по моду лю два в- каждой группе, причем выход j-го одноразрядного сумматора -ой ГРУППЫсоединен с первым входом ,j-ro однорд13рядно1-о сумматора (5-1) группы, вторые входы j-ых (j«1,..., n-i+1) одноразрядных сумматоров (,t-1 группы соединены с выходомпереноса первого одноразрядного сумматора )-ой группы и с первыми входами сумматоров по модулю два (1-1) дополнительной группы, выходы которых соединены со вторыми входами j-ых ( -п-И2,...,2(п-1)-1) одноразрядных cy да aтopoв (-1)-ой группы, а вторые входы j-ых (....,п-i)сумматоров по модулю два (1-1)-ой дополнительной группы соединены с первыми входами первых одноразрядных сумматоров (n-j)-bix групп, вход элемента НЕ соединен со вторым входом первого одноразрядного сумматора (п-1)-ой группы, а выход - со вторым входом второго одноразрядного сумматора (п-1)-ой группы, первый вход i-го еумматбра по модулю два группы соеди нен с входом (2i-1)-ro разряда входного кода устройства и с первым входом i-го элемента ИЛИ группы, выход которого соединен с входом переноса 2(n-i)-ro одноразрядного сумматора -ой группы, а второй вход соединен с входом 2i-ro разряда входного кода и со вторым входом 1-го элемента ИЛИ группы, а выход соединен со входом -го элемента НЕ первой группы, выход которого соединен с перйым входом 2 (п- i )+l3 -го одноразрядного сумматора (1-1)-ой группы,вход -го элемента НЕ второй группы соединен со вторым входом i-го сумматора по модулю два группы, а выход - с первым входом 2(п-i) одноразрядного сумматора (1-1) группы, выходы переноса первых одноразрядных с ашаторов и выход п-го элемента ИЛИ группы являются выходами- устройства, выход п-го элемента ИЛИ группы соединен со входом-элемента НЕ. . Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 571807, кл. G 06 F 7/38, 1974. 2.Авторское свидетельство СССР 413479, кл. G 08 F 7/38, 19J1, (прототип).