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

 

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

союз сонетсник

СОЦИАЛИСтИЧЕСНИК ЕСГВБЛИН (51)4 G 06 F 7/552 15/347 госудАгстаениый номитет ссс

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬ ТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ, -. (21) 4176454/24-24 (22) 06.01.87 (46) 30.07.88. Бюл. Р 28 ,(72) С.А.Волощенко (53) 68 1.325(088.8) (56) Авторское свидетельство СССР

В 1171787, кл. G 06 F 7/552, 1984.

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

Р 1107119, кл. С 06 F 7/552э 1983 ° (54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В

КВАДРАТ И ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислителях и быстродействующих 3ВМ для однотактного выполнения операций возведения в квадрат и извлечения квадратного корня для дробных и целых двоичных чисел, причем первая из операций выполняется в дополнительном ко де. Целью изобретения является сокра1,Л0„„1413627 д1 щение аппаратурных затрат и повьппение быстродействия при извлечении квадратного карня, Цель достигается эа счет применения двоичной системы счисления с цифрами -1, + 1 для промежуточного представления данных и использования этого представления для возведения в квадрат. Операнды и результат представлены в обычной двоичной системе счисления с цифрами 0 и

1. Для извлечения квадратного корня использован модифицированный алгоритм извлечения без восстановления остатка

Устройство содержит N-1 групп одно : разрядных сумматоров и элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ 2, в которых собственно выполняются все арифметические действия (N — разрядность операндов)

1 а также вспомогательные группы коммутаторов, элементов И, И-НЕ и НЕ, выполняющих функции коммутации инфор" мационных потоков и настройки. 3 кп.

1413627

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

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

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

Устройство (фиг. 1) содержит группы из одноразрядных сумматоров 1 и элементов ИСКЛ10ЧА1ОЩЕЕ ИЛИ 2, группы

3-7 соответственно с первой по пятую одноразрядных коммутаторов, одноразрядный сумматор 8„ группы 9, 10 элементов НЕ, элемент НЕ 11, группу элементов И 12, элементы И 13-15, группу элементов И-НЕ 16, вход 17 знака устройства, разрядные входы 18 и 19 устройства, вход 20 настройки устройства, входы 21 и 22 соответственно логического "0" и логической "1" устройства, разрядные выходы 23 и 24 уст- . ройства.

В предложенном устройстве цифры

"-1" и "+1" кодируются соответственно нулем и единицей„ номера групп, содержащие одноразрядные сумматоры и элементы ИСКЛ10ЧА101ЦЕЕ ИЛИ, возрастают сверху вниз, а номера элементов в группе — слева направо, аналогичная нумерация принята и в остальных группах.

Устройство работает следующим образом, Для возведения в квадрат на вход

20 настройки должен подаваться сигнал нулевого уровня. Мантисса операнда поступает на входы 18, а знак one-

>О ранда — на вход 17. На выходах 23 и

24, с задержкой, равной времени переходного процесса в схеме, формируется 2N-разрядный результат операции (на выходах 23 — N старших разрядов, а на выходах 24 — N младших) . Сигнал нуля на входе 20 настрачвает все коммута.торы групп 3-7 на передачу информационных сигналов с вторых их входов (расположенных на отображениях коммутаторов снизу и справа). Этот же сигнал нуля на входе 20 закрывает элементы И группы 12, а также элементы И 13 и 14, Все это подготавливает элементы коммутации информационных потоков и настройки на выполнение операции возведения в квадрат, сами же арифметические действия выполняются в группах сумматоров 1 и элементов

ИСКЛЮЧАЮЩЕЕ ИЛИ 2.

Операция возведения в квадрат начинается с преобразования (N+1)-разрядного операнда Х („,, выраженного

I дополнительным кодом в двоично,=. системе счисления (О, 1) и представленнorо дробью в виде X Х„Х,...,Хд, в равное ему по величине число Х (2,,), но представленное в двоичной системе счисления (-1, +1) в форме

i--О где Х; — цифра, равная — 1 или +1;

12 " - искусственный весовой член.

Код Х(„<1 получается иэ следующего (И+1)-разрядного кода Х X X ...Хм путем замены в последнем коде нулей на -i а единиц — на +t. В силу избранного способа кодирования цифр

"-1":и "+1" никаких дополнительных элементов в устройстве для преобразования не требуется.

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

Х = » П .1+С 2 +С+ $ (2 "+ (i +i1 . 1 М

+ 2-г -н ) + 2--гЯ- г + Х 2--» (2)

М 1 где П, — x-разрядное частичное про1 изведение, равное по величине (Х фХ Я,Е Х;+Х "2 ), ) 1 которая может быть представлена разрядным вектором в и формируется на выходах элементов ИСК.ПОУЧАЮЩЕЕ ИЛИ 2 соответствующей z-й г руппы, причем инвертирование второго члена каждой пораэряд1413627 ной операции осуществляется посредством элементов HE 9 группы;

Ся 1- (N-1) -разрядный корректирую-, 5 4-1 щий член, равный .(Х14Х,„) 2

i=1 или отражаемый разрядным вектором в виде 10 р который формируется на выхо. дах элементов И-НЕ 16 группы и передается в группах сумматоров 1 через коммутаторы

6 (бит X используемый в коде С>, формируется на выходе элемента НЕ 11).

С, — одноразрядный корр ектир ующий член, равный конъюнкции

Х (Х„ и формируемый элеО ментом И 15, X. (2- +

Фи!

+2 " — константные члены формируер !

5 мые на выходах элементов НЕ

10 группы, а также путем связи входов этих же элементов

НЕ 10 с входами переносов соответствующих сумматоров 1 группы, 30

2 ™-2 — константный член, формируемый единичным уровнем на входе 21 устройства.

Сформированные таким образом члены выражения (2) по соответствующим це- 35 пям поступают на входы одноразрядных сумматоров 1 всех соответствующих

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

Код величины Х,, формируется

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

23 и 24 устройства. Обратное преобразование их Х,,! в Х <,,> осущест- 50

\ вляется заменой цифр "-1" на нуль, а цифр "+1" на единицы, сама же замена в силу избранного способа кодирования осуществляется непосредственно без дополнительных элементов. 55

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

Стрелками отображены связи между соответствующими разрядами операндов и формируемыми по их значениям кодов.

Здесь же выделены такие группы разрядов: .ХХ...Х вЂ” инФормаеа онные разряди

«аетниныи произведеиид, формируемых элементами

ИСКЛЮЧЛВР(ЕЕ ИЛИ 2 соответствуюп,их групп", ХХ вЂ” информационные разряды на входе и выходе соответствующего элемента НЕ

10, формируемые как результат поразрядного суммирования константных членов формулы (2) со всеми разрядами кодов П и

fl- 1

Х вЂ” информационный разряд, поступающий в группы сумматоров непосредственно, /

Х вЂ” единичный уровень, формируемый на входе 21.

Для выполнения операции извлечения квадратного корня на вход настройки : должен быть подан сигнал единичного е уровня. Мантисса подкоренного выражения в 2N разрядов поступает на входы

18 и 19 (на входы 18 — N старших разрядов, а на входы 19 — N мпадших) . На выходах 23 формируется N-разрядный корень. Сигнал единичного уровня на входах 20 настраивает все коммутаторы

3-7 на передачу сигналов с их первых входов (расположенных сверху и слева на отображениях коммутаторов). Сигнал единичного уровня на входах 20 открывает элементы И 12, а также элементы

И 13 и 14, что обеспечивает прохождение через них сигналов. Таким образом обеспечивается настройка устройства на извлечение корня.

Извлечение квадратного корня s устройстве выполняется итеративно по алгоритму без восстановления остатка, в котором i-A разряд корня определяется по знаку n-ro остатка g>, вычисляемого по формуле

Qп = Q +(О У2 7 )2 +2ь, +

-(2о - Ц

+ (0. ») +(0.11) 2 (3) для О = Y n = 1 N, при этом

1413627

1, если Q„ 0

О, если Q (О, .) где (— остаток п-й итерации;

У ° — бит i.-ro разряда подкоренl ног о выр ажения У (i = 1, 2N);

Z „ — бит и-го разряда корня;

Z „, — n-разрядный код, равный 10 (О,Z Z) ...Z „, ) +Z „, т . е. операции поразрядного

ИСКЛЮЧАЮЩЕГО ИЛИ (n-1) -ro бита корня со всеми определенными до этого его цифра-1 ьи, включая и (п-1)-й разряд, В предлагаемом устройстве используется модифицированная форма выражения (3) для вычисления Q „, пред- 20 ставленная ь виде

-(и-21 (- Q „, +Y<„, 2 +(У „„+У„,„, ) °

-ln

<2 + Zh (4) 25

Пример на фиг, 3 иллюстрирует вы5 числительный процесс извлечения квадратного корня в устройстве. Пара разрядов, анализ которой осуществляется в каждой итерации, под-,гаркнута нижней для n = 2, N и Q, = Y 0.У У, при этом Z Y VY, т. е, дизьюнкция двух старших разрядов подкоренного выражения, формируемая фактически на 30 выходе переноса одноразрядного сумматора 8, Все члены формулы (4) суммируются с использованием сумматоров (п-1)-й группы, на выходах которых и формируется собственно очередной остаток

Q n, При этом образование членов формулы (4) осуществляется следующим образом: бит У „ формируется на выходе (n-1)-го элемента .НЕ 9 группы," код Z 1 — на выходах элементов ИСКЛ10ЧАЮЩЕЕ ИЛИ 2 (п-1)-й группы, код (У „, суммируется на последнем сум маторе (n-1)-й группы. Очередные цифры Z„, сформированные в соответствии с выражением (4) переносов первых сумматоров (n-1) -х групп, поступают далее на первые входы коммутаторов 7 группы и, пройдя через эти коммутаторы,передаются на выходы 24 устройства,. на выходах сумматоров последней (N1) -й группы формируется окончательный остаток операции извлечения корня, полускобкой. Вертикальные сплошные стрелки, идущие от разрядов подкоренного выражения, указывают на места этих разрядов в кодах, суммируемых в соответствующих итерациях. При этом штриховые стрелки указывают на инвертирование соответствующих разрядов (выполняемых элементами HE 9). Цифры корня Z„ формируемые как переносы от суммирования кодов, отделены точкой и подчеркнуты нижней чертой, Горизонтальные стрелки, идущие от этих цифр, указывают на формируемые по их значению коды Z„.

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

Устройство для возведения в квад— рат и извлечения квадратного корня, содержащее N-1 групп по i+2 opноразрядных сумматора и i элементов ИСКЛЮЧАЮЩЕЕ ИЛИ каждая (где N — разрядность мантиссы входного кода), а также первую и вторую группы по N-1 одноразрядных коммутаторов, третью группу из

N-3 и четвертую и пятую группы из N одноразрядных коммутаторов соответственно, группу из N-2 элементов И, элемент НЕ и два элемента И, причем вход переноса j ro (j = 1,i+1) одноразрядного сумматора i-й группы подключен к выходу переноса (()+1) -го одноразрядного сумматора этой же группы, первый вход f — ro одноразрядного сумматора К вЂ” и группы (f = 1,K К = — 2,N- 1) подключен к выходу суммы (f+1) -го одноразрядного сумматора (К-1) -й группы, выход i — го элемента

ИСКЛЮЧА10ЩЕЕ ИЛИ i — и группы соединен с вторым входом (i+1) -го одноразрядного сумматора этой же группы, выход переноса одноразрядного сумматора К-ой группы подключен к первым информационным входам (1+2) -го одноразрядного коииутатора первой второй и пятой групп (1 = 1,...N-2), а также к второму информационному входу (1-1) -ro одноразрядного коммутатора третьей группы, выход первого одноразрядного сумматора первой группы подключен к первым информационным входам вторых одноразрядных коммутаторов первой, второй и пятой групп, второй информационный вход i-го одноразрядного коммутатора второй группы подключен ,к 1-разрядному входу устройства, первый информационный вход Р-го (P=

1а,N) одноразрядного кол1мутятора четвертой Группы подключен к (P+N-1)— р а зр ядному входу ус тр ойс тва, первый

7 1 ».! 3627 Я вход 1-ro элемента И группы подклю- !!(i

1-го элемента ИСКЛЮЧАЮrpynn, c вторыми входами элементов И !!!ЕЕ И»5! t-й группы (t = i,N- ), i-ro элемента HF. второй группы подгруппы и вторыми входами первого и второго элементов И, выход Р— го од— ключен к пер ому ду вом вхо (i+1) -го одноноразрядного -коммутатора пятой груп- разрядного сумматора 1-й группы, а пы подключен к P-разрядному выходу вход перенос (1 ) р р, са (1+2) -го одноразрядного устройства, о т л и ч а ю щ е е с я сумматора 1-й группы соединен с вхо тем, что, с целью сокращения аппара- дом (1+1) — го элемента HE второй груптурных затрат и повышения быстродеист- пы, выход (2m-1) о

ых (2m-1)-го элемента И группы виЯ пРи извлечении квадРат о КоР 20 (и = 1 — -2) подключен к входу -го ня, в устройство введены первая и вторая группы соответственно из N-2 эпемента НЕ второй группы, а выход и N-1 элементов НЕ каждая, однораз— 2m-го элемента И группы подключен к рядный сумматор, третий элемент И и первому входу (m+2)-ro одноразрядного группа из N-1 элементов И-НЕ, при- 2 сумматора m-й группы, выходы 2п-го чем вход и выход 1-го элемента HE и (2n+1) -ro коммутаторов четвертой первой группы подключены соответступпы (n = 1 — -) подключены соответвенно к второму информационному входу

1-го одноразрядного коммутатора вто- ственно к первому входу и входу перерой группы и второму информационному 30 оса (n + — + 1) ГО Одноразрядного носа

2 входу (1+1)-го одноразрядного коммутаа п + — — — 1)-й группы, вытора первой группы, вход знака уст- сумматора (п -2 ) pyB ройства подключен к второму информа- ход первого коммутатора четвертои ционному входу первого одноразрядно- группы соединен с входом переноса

ГО комм татора первОй группы и пер вому входу третьего элемента И, пер- З5 2 информационные входы TIQpBblx одно- (N 1) „„„„(+2) разрядных коммутаторов первой и втогр уппь, рой групп соединены с выходом одно- го одноразрядного сумм р ммато а 1-й групразрядного сумматора и с первым ин- пы и вторые вход р хо ы пе вого и второго формационным входом одноразрядного элементов И подключен

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

45 выхо ы сумин.» второго и ветственно с i-ым разрядным входом третьего однора р д аз я ных сумматоров устройства и вторым информационным (N-1)-й группы подключены к вторым инвходом (i+1)-ro одноразрядного ком- формационным входам соответственно мутатора четвертой группы, выход тре- (N-1)-ro u N-ro одноразрядных о тьего элемента И подключен к второ- 50 таторов пятои группы, выход () о (8+1) -го с ммато а М-1 -и групму инфармапионному входу первого ад- одноразрнднаго сумм р 1 соединен с (N+S-2)норазрндного коммутатора четвертой пн (S = 3, N — 1) соединен с

r уппы вторые входы элементов И-НЕ разрядным выход м у р о ст ойства, (2 N-1)р . группы и второй вход третьего элемен- разрядный вых,, у р

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

11 11 хо ам логического О и логичес" ра второй группы соединен с первым входом каждого элемента ИСКЛЮЧАЮЩЕЕ

14l3627!

413627

14 13б27

Составитель С,Вопощенко

Редактор M.Келемеш Техред .П.Олийнык Корректор О.Кравцова

Заказ 3 78 7/52 Тираж 704 Подпис но е

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

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

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