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

4

оо а ю

10

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

Цель изобретения - сокращение ап- паратур иъпс затрат и повышение быстродействия при извлечении квадратного корня.. ,

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

Устройство (фиг. 1) содер.жит группы из одноразрядных сумматоров 1 и элементов ИСЮТЮЧАЮЩЕЕ ИЛИ 2, группы 3-7 соответственно с первой по пятую 25 одноразрядных коммутаторов, одноразрядный сумматор 8, группы 9, 10 элементов НЕ, элемент НЕ 11, группу элементов И 12, элементы И 13-15j группу элементов И-НЕ 16, вход 17 знака ,„ устройства, разрядные входы 18 и 19 устройстваJ вход 2.0 настройки устройства, входы 21 и 22 соответственно логического О и логической 1 устройства, разрядные выходы 23 и 24 уст- . ройства..

В предложенном устройстве цифры -1 и +1 кодируются соответственно нулем и единицей, номера групп, содержащие одноразрядные сумматоры и элементы ИСКЛЮ ШОЩЕЕ ИЛИ возрастают сверху вниз, а номера элементов в группе - слева направо, аналогичная нумерация принята и в остальных группах,

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

Дпя возведения в квадрат на вход 20 настройки должен подаваться сигнал нулевого уровня. Мантисса операнда поступает на входы 18, а знак операнда - на вход 17. На выходах 23 и 24, с задержкой, равной времени переходного процесса в схеме, формируется 2Н-разрядный результат операции (на выходах 23 - N старших разрядов, - на выходах 24 - N млсдших), Сигнал уля на входе 20 настрачвдет все комутаторы групп 3-7 на передачу инфор40

45

Ю

0

,

.

мационных сигналов с вторых их входов (расположенных на отображениях коммутаторов снизу и справа). Этот же сигнал нуля на входе 20 закрывает элементы И группы 12, а также элементы И 13 и 14, Все это подготавливает элементы коммутации информационных потоков и настройки на выполнение операции возведения в квадрат, сами же арифметические действия выполняются в группах сумматоров 1 и элементов- ИСКгаОЧАЮЩЕЕ ИЛИ 2.

Операн;ия возведения в квадрат начинается с преобразования (М+1)-раз- рядного операнда X ( , вьфаженного дополнительным кодом в двоичной системе счисления (0,1) и представленного дробью в виде , . , ,, в равное ему по величине число X / , но представленное в двоичной системе счисления (-1, +1) в форме

N

-Ь -и) у-(

1 0

(-1,м)х .(N-, ()

25 ,„ .

40

5

где X; - цифра, равная -1 или -t-li

IT(N+I) .„„

IJ-i- искусственньи весовой член.

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

Применяя формулу о квадрате числа к выражению (1), после упрощений получим решающую формулу, используемую в уст{эойстве,

-; 4N-1) (N-4)fi (-t,,, 5, - N-i2 -С. (2-.

4. ) + 2-2N- 2 + Х„2-2« (2)

где П . - 1-разрядное частичное произведение, равное по велиi-1

чине (Х(вХ,©51Х; + ), J,

которая может быть представлена разрядным вектором в виде

и формируется на выходах элементов ИСК. БОЧАЮЩЕЕ Ит 2 соответствующей i -й группы, причем инвертирование второго члена );здой поразряд314136

ной операции осуществляется посредством элементов НЕ 9 группы; (N-I )-разрядный корректирую-.

N-1 щий член,равный ЦСХ.Х )-2

N

ИЛИ отражаемый разрядным вектором в виде

который формируется на выходах элементов И-НЕ 16 группы и передается в группах сумматоров 1 через коммутаторы 6 (бит Xj, используемый в коде Сц| сформируется на выходе элемента НЕ 11). C|j,- одноразрядньш корректирующий член, равный конъюнкции

20

2- н

-«

X р I Х( и формируемый элементом И 15,

константные члены, формируе15

мые на выходах элементов НЕ 10 группы, а также путем свзи входов этих же элементов НЕ 10 с входами переносов сответствующих сумматоров 1 группы,

константный член, формируемый единичным уровнем на входе 21 устройства. Сформированные таким образом член выражения (2) по соответствующим це- пям поступают на входы одноразрядных сумматоров 1 всех соответствующих групп, в которых и Ьсуществляется их полное суммирование. Коммутаторы 5 обеспечивают здесь сквозное распрост ранение переносов между первыми сумматорами каждой группы (при этом элемент И 15 закрыт).

Код величины Х| . формируется на выходах первых сумматоров 1 каждой группы, а также на выходах сумматоров 1 последней группы и через коммутаторы 7 передается на выходы 23 и 24 устройства. Обратное преобразование их X|.,,j в Х(5,5 осуществляется заменой цифр -1 на нуль, а цифр +1 на единицы, сама же замена в силу избранного способа кодирования осуществляется непосредственно без дополнительных элементов.

Примеры на фиг. 2 иллюстрируют вычислительные процессы при возведенш в квадрат для N 6. Результаты полу

136

-.

10

20

15

50

35 55

45

50

274

чены от сум 1иройат{я информашюнных разрядов, отделенных от остальных двумя двoйны fи горизонтальньп {и линиями. Стрелками отображены связи между со- ответствующим разрядами операндов и формируемыми по их значениям кодов. Здесь же вьщелены такие группы разрядов;

,ХХ...X,- информационные разряды

частичных произведений,-- форьэтруемых элементами ИСКЛЮЧЛ1{Н1(ЕЕ ИЛИ 2 соответствующих групп, i. информационные разряды на входе и выходе соответствующего элемента НЕ 10, формируемые как результат поразрядного суммирования константных членов формулы (2) со всеми разрядами кодов П, и

.-п ;

X - информационный разряд,

поступающий в группы сум- f маторов непосредственно, единичный уровень, формируемый на входе 21. Для выполнения операции извлечения квадратного корня на вход настройки : должен быть подан сигнал единичного уровня. Мантисса подкоренного вьфаже- ния в 2N разрядов поступает на входы. 18 и 19 (на входы 18 - N старших разрядов, а на входы 19 - N младших). На выходах 23 формируется N-раэрядный корень. Сигнал единичного уровня на входах 20 настраивает все коммутаторы 3-7 на передачу сигналов с их первых входов (расположенных сверху и слева на отображениях коммутаторов). Сигнал единичного уровня на входах 2П открывает элементы И 12, а также элементы И 13 и 14, что обеспечивает прохож- дение через них сигналов. Таким образом обеспечивается настройка устройства на извлечение корня.

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

п

вычисляемого по формуле

Q. Q..b-,- 0-ViYin)2 -t- (0.11)-t-,(0.11).

,-(n-1)

+Z

h-1

(3)

для Q- Y, n 1,N, при этом

1, если Q f/ О О, если Q О,

де Q - остаток п-й итерации;

У| - бит i-ro разряда подкорен- ного вьфажения y(,2N);

Z J, - бит п-го разряда корня;

Z j - п-разрядный код, равный

{0,Z,Zj.Z.,)+Z ., , т.е. операции поразрядного ИСКЛЮЧАЮЩЕГО ИЛИ ()-го бита корня со всеми определенными до этого его цифра-15

10

ми,

включая и (п-1)-й разряд.

В предлагаемом устройстве используется модифицированная форма вьфажения (3) для вычисления Q , пред- ставленная в виде

Q Q П-, ...; (Y,j. +Yj, ) X

Z

h-1

(4) 25

для п 2, N и Q, Y-0,YiY5, при этом Z , т.е. дизъюнкция двух старших разрядов подкоренного вьфажения, формируемая фактичес1Ш на выходе переноса одноразрядного сумматора 8. .

Все члены формулы (4) суммируются с использованием сумматоров (п-1)-й группы, на выходах которых и формируется собственно очередной остаток Q.. При з том образование членов формулы (4) осуществляется следующим образом: бит , формируется на выходе (n-l)-ro элемента .НЕ 9 группы код Z n-i - на выходах элементов ИС- КЛОЧАЮЩЕЕ ИЛИ 2 (п-1)-й группы, код 1п-1 суммируется на последнем сумматоре (п-1)-й группы. Очередные цифры Zp, сформированные в соответствии с вьфажением (4) переносов первых сумматоров (п-1)-х групп, поступают далее на первые входы коммутаторов 7 группы и, пройдя через эти коммутаторы,передаются на выходы 24 устройства на выходах сумматоров последней (N- 1)-й группы формируется окончательный остаток операции извлечения корня.

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

15

10

20

25

35

30

40 45 ..

5

полускобкой. Вертикальные сплошные стрелки, идущие от разрядов подкоренного вьфажения, указывают на места этих разрядов в кодах, суммируемых в соответствующих итерациях. При этом штриховые стрелки указьгоают на инвертирование соответствующих разрядов (вьтолняемых элементами НЕ 9). Цифры корня Z, формируемые как переносы от суммирования кодов, отделены точкой и подчеркнуты нижней чертой. Горизонтальные стрелки, идущие от этих цифр, указывают на формируемые по их значению коды Ед.

Формула, изобретения Устройство для возведения в квадрат и извлечения квадратного корня, содержащее N-1 групп по i+2 одноразрядных сумматора и i элементов ИСКПЮ- ЧАЮиШЕ ИЛИ каждая (где N - разрядность мантиссы входного кода), а также первую и вторую группы по N-1 одноразрядных коммутаторов, третью группу из N-3 и четвертую и пятую группы из N одноразрядных коммутаторов соответственно, группу из N-2 элементов И, элемент НЕ и два элемента И, причем вход переноса j-ro (j Iji+l) одноразрядного сумматора i-й группы подключен к выходу переноса ((j+1)-ro одноразрядного сумматора этой же группы, первьш вход f-ro одноразрядного сумматора К-й группы (f 1,К К 2,N-1) подключен к выходу суммы (f+1)-ro одноразрядного сумматора (К-1)-й группы, выход i-ro элемента ИСКЛЮЧАЮЩЕЕ ИЛИ i-й группы соединен с вторым входом (i+1)-ro одноразрядного сумматора этой же группы, выход переноса одноразрядного сумматора К-ой группы подключен к первым информационным входам (1+2)-го одноразрядного коммутатора первой второй и пятой групп (L 1,...N-2), а также к второму информационному входу (1-1)-го одноразрядного коммутатора третьей группы, вьгход первого одноразрядного сумматора первой группы подключен к первым информационным входам вторых одноразрядных коммутаторов первой, второй и пятой ГРУПП, второй инфор- MaiyiOHHbm вход i-ro одноразрядного коммутатора второй группы подключен ji i-разрядному входу устройства, первый информационный вход Р-го (Р 1,N) одноразрядного коммута1;ора чет вертой группы подключен к (P+N-I)- разрядному входу устройства, первый

7lA

вход 1-го элемйнта И группы псшклю- че.н к (1 + 1)-разрядно ту входу устройства, вход элемента НЕ и 2 N-разряд- ный вьгход устройства соединены с N- разрядным входом устройства, первый вход первого элемента И подключен к 2 N-разрядному входу устройства, а вход настройки устройства соединен с входами управления всех одноразрядных коммутаторов с первой по пятую групп, с вторыми входами элементов И группы и вторыми входами первого и второго элементов И, выход Р-го одноразрядного -коммутатора пятой группы подключен к Р-разрядному выходу устройства, отличающееся тем, что, с целью сокращения аппаратурных затрат и повышения быстродейсвия при извлечении квадратного корня, в устройство введены первая и вторая группы соответственно из N-2 и N-1 элементов НЕ каждая, одноразрядный сумматор, третий элемент И и группа из N-1 элементов .И-НЕ, причем вход и выход 1-го элемента НЕ первой группы подключены соответственно к второму информационному вход 1-го одноразрядного коммутатора второй группы и второму информационному входу (1 + 1)-го одноразрядного коммут тора первой группы, вход знака устройства подключен к второму информационному входу первого одноразрядного коммутатора, первой группы и первому входу третьего элемента И, пер- вые информационные входы первых одноразрядных коммутаторов первой и второй групп соединены с выходом одноразрядного сумматора и с первым ин- формационньм входом одноразрядного коммутатора пятой группы, а входы одноразрядного сумматора подключены к первому и второму разрядным входам устройства, первый вход и выход i-ro элемента И-НЕ группы соединены соответственно с i-ым разрядным входом устройства и вторым информационным входом (i+l)-ro одноразрядного коммутатора четвертой группы, выход третьего элемента И подключен к второ му информационному входу первого одноразрядного коммутатора четвертой группы, вторые входы элементов И-НЕ группы и второй вход третьего элемента И подключены к выходу элемента НЕ выход i-ro одноразрядного коммутатора второй группы соединен с первым входом каждого элемента ИСЮТЮЧАЮЩЕЕ

.-

10

15

20

25

1362

т- ,55

30

40

45

50

78

И.ЧИ группы, перпьп информац1 онный ,хп;г, 1-го оиюразрядного комт-о таторл третьей группы подключен К выходу (1-1)-го одноразрядного кoм fyтятopa второй группы, второй вход второго элемента И соединен с выходом (N-1)- го одноразрядного коммутатора второй группы, выход i-ro одноразрядного ком- ryтaтopa первой группы подключен к второму входу i-ro элемента ИСКЛЮЧАЮ- 1ИЕЕ ИЛИ t-й группы (t i,N-1), выход i-ro элемента НЕ второй группы подключен к первому входу (i-f-l)-ro одноразрядного сум 1атора i-й группы, а вход переноса (1+2)-го одноразрядного сумматора 1-й группы соединен с входом (1+1)-го элемента НЕ второй группы, выход (2тп-1)-го элемента И группы

f-, t - 2.

ш 1,-J-) подключен к входу т-го

элемента НЕ второй группы, а выход , 2т-го элемента И группы подключен к первому входу (т+2)-го одноразрядного сумматора тп-й группы, выходы 2п-го и (2п+1)-го коммутаторов четвертой

/,

группы (п 1,-г-) подключены соответственно к первому входу и входу пере,N,,

носа (п + -г- + 1)-го одноразрядного

N

сумматора (п + -j- - 1)-й группы, выход первого коммутатора четвертой группы соединен с входом переноса

N ( + 1)-го одноразрядного сумматора

( - 1)-группы, второй вход (1+2)го одноразрядного сумматора 1-й группы и вторые входы первого и второго элементов И подключены к входу настройки устройства, выход первого одноразрядного сумматора (1+1)-й группы подключен к второму информационному входу 1-го одноразрядного коммутатор пятой группы, выходы суммы второго и третьего одноразрядных сумматоров (Ы-1)-й группы подключены к вторым информационным входам соответственно (N-l)-ro и N-ro одноразрядных коммутаторов пятой группы, выход (S+l)-ro одноразрядного сумматора (К-1)-й группы (S 3, N - 1) соединен с (N+S-2)- разрядным выходом устройства, (2 N-1)- разрядный выход устройства и вход переноса одноразрядного сумматора (N+ +1)-й группы подключены соответственно к входам логического кой 1 устройства.

z

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях и быстродействующих ЭВМ для однотактного выполнения операций возведения в квадрат и извлечения квадратного корня для дробных и целых двоичных чисел, причем первая из операций выполняется в дополнительном коде. Целью изобретения является сокращение аппаратурных затрат и повышение быстродействия при извлечении квадратного корня. Цель достигается за счет применения двоичной системы . счисления с и;ифрами -1, +1 для проме-. жуточного представления данных и использования этого представления для возведения в квадрат. Операнды и результат представлены в обычной двоичной системе счисления с цифрами О и 1, Для извлечения квадратного корня использован модифицированный алгоритм извлечения без восстановления остатка. Устройство содержит N-1 групп одно«, разрядных сумматоров и элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 2, .в которых собственно вьшолняются все арифметические действия (N - разрядность операндов) а также вспомогательные группы коммутаторов, элементов И, И-НЕ и НЕ, вьшолняющих функции когЛтутации информационных потоков и настройки, 3 ил. (Л с

/7 9(8 9/5 7/i 9/e 9fe 0/ oW f19 9/ 9/

I/I

/4 24

.;

/

Фие.2

lTM. Ш6

.011011WOWO

I

lol

J01

fOO

оГШ,

jon otot1

-f«oaof|

.00101

lOfoo

-OToTo

4-Ч.

4-Ч.

101010

ojotofH I

f.ooooooi,

0000000

-fo/otoo-J

.1

-0,1010101

«-- /0.уФ4 4 4

(f|) ,fOtOf0

Операнд

/-Я итерация

2-я итерации

3-Я итерация

4-я umepouuf

5-я итвроиия

6-я umBpauuft

Не Восстановленный остаток

Результат