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

 

УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ КВАДРАТНОГО КОРНЯ, содержащее (n-m) Z групп, где m п, п -:г, Z - разрядность подкоренного числа в двоичном коде, изN(, где k - номер группы) последователь но соединенных одноразрядных, полньк сумматоров, отлийающ ее с я тем, что, с целью сокращения аппаратурных затрат, в него введены блок постоянной памяти, имекщий 2 m входов и 2 m выходов, (n+m-3)(n-m) Tj элементов сложения по модулю два и (n-m) злементов НЕ, причем входы блока постоянной памя ти подключены соответственно к ftep вым 2 m разрядам входа устройства, первый и второй входы N-ro сумматора k-й группы подключены соответственно к

СООЭ СООЕТСНИХ

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

РЕСПУБЛИН (19) (11) (51)4 G 06 F 7 5 2

ОПИСАНИЕ ИЗОБРЕТЕНИЯ н лвто СКоММ СВидктиЛьСтвМ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPbITHA (21) 3728292/24-24 (22) 16.04.84 (46) 23.09.85. Бюл. Р 35 (72) N.Н . Ложкин и P.Ä. Яхонтов (5") 681.325 (088.8) (56) Хемел. Применение небольших

ПЗУ для вычислений. — "Электроника", 1970, М 10, с. 19.

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

N 809174, кл. G 06 F 7/552, 1979. (54)(57) УСТРОЙСТВО ДЛЯ ИЗВЛЕЧЕНИЯ

КВАДРАТНОГО КОРНЯ, содержащее (и-ш) групп где m (и и = 2 z раз рядность подкоренного числа в двоичном коде, из N (N = m + k + 1, где k — номер группы) последователь но соединенных одноразрядных.полных сумматоров, о т л и 1 а ю щ ее с я тем, что, с целью сокращения аппаратурных затрат, в него введены блок постоянной памяти, имеющий

2 m входов и 2 m выходов, (п+ш-3)(п-т) элементов сложения по модулю два и (n-ш) элементов НЕ, причем входы блока постоянной памя ти подключены соответственно к йер вым 2 m разрядам входа устройства, первый и второй входы N-го сумматора k-й группы подключены соответственно к (2ш+Ж-1)-му и (2ш+21с) му разрядам входа устройства, вход переноса N-го сумматора k-й группы подключен к шине логической единицы устройства, первый и второй входы (N-1)-ro сумматора k-й группы подключены соответственно к шине логического нуля устройства и к выходу k-ro элемента НЕ, вход k-ro элемента НЕ подключен к (2ш+2Е-2)-му разряду входа устройства, выход сигнала переноса первого сумматора

k-й группы является (Е+ш)-и разрядом выхода устройства, первый вход

i-го сумматора (i=1 N-2) k-й группы (для 24 k) подключен к выходу j-ro ()=2,...,N) сумматора (k-1)"й группы, первый вход i-го сумматора первой группы подключен к (2ш-1.+1)-му выходу блока постоянной памяти, второй вход i-го сумматора (для 2 < i) х-й группы подключен к выходу р-го (р=1,...,m+k-2) элемента сложения по модулю два

k-й группы, второй вход первого сумматора k-й группы подключен к (k+m-1)-му разряду выхода устройства,. первые входы всех (m+k-2) элементов сложения по модулю два k-й группы подключены к (k+m-1)-му разряду выхода устройства, второй вход р-ro элемен.а сложения по модулю два

k-й группы подключен к р-му разряду выхода устройства, вход переноса

0-ro (8=1,...,N-1) сумматора k-й группы подключен к выходу переноса (6+1)-ro сумматора k-й группы.

8б

g), р, 0 1

4 2 1-2 г-z ge-2

1 11808

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

Целью изобретения является сокращение аппаратурных затрат.

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

Устройство содержит входы 1, на которые подаются разряды входного числа а1,...,а4„, блок 2 постоянной памяти, выходы 3, с которых сни" 15 маются разряды выходноro числа р<, ...,р, выходы 4 блока 2 .постоянйой памятй, с которых снимаются разряды остаточного числа, одноразрядные полные сумматоры 5, элементы б сложе- 20 ния по модулю два, элементы НЕ 7, шину 8 логической единицы, шину 9 логического нуля.

Устройство позволяет извлекать квадратный корень из чисел, имею- 25 щих 2"n двоичных разрядов с представлением результата в виде п-разрядного двоичного числа, при этом разрядность входного числа может быть любой и не ограничивается 30 разрядностью блока постоянной памяти.

Пусть подкоренное выражение представлено в прямом двоичном коде в виде числа А, имеющего разряд" ность 2п, так что выполняется усло-. вие: 0 А 1, а число А = O,а4,а а,,,а „, где а4„- младший разряд исходного числа.

Операция извлечения квадратного 0 корня состоит из п шагов, причем первые m шагов выполняются с помощью. блока постоянной памяти.

1-й шаг. Сложение а и а2 с логической единицей.

При этом сигнал переноса р опре1 деляет первый, старший разряд результата, а cpI HBJI суммы g1 1 является старшим разрядом первого слагаемого второго шага. 50

Производится сложение а, + а2

Р Ч

2-й шаг. Формируется первое слагаемое, старший разряд g< < формируется при 1-м шаге, второй разряд определяется как инверсия второго разряда исходного числа (а ), третий разряд первого слагаемого — а, .

Второе слагаемое формируется в виде р О 1.

Производится сложение

Сигнал переноса р, определяет второй разряд результата.

3-й шаг. Первое слагаемое формируется в виде с(2 )э а4а . Второе .слагаемое формируется в виде р, р,®р, 0 1, где р,8p> — сложение по модулю два cHFHBJIQB 2 и

Производится сложение 2-2 З-2 р, ррр,,О 1 а

3 13 23 ЗЯ 4-3

Сигнал переноса р определяет третий разряд результата.

4-й шаг. По аналогии производится сложение 2 < 4 <" Баем з Ръ Р1 з®Р 0< ав

I 4 $1-4 32-4 3 У-4 Ч 4-4 Ч 6-4

В общем случае для j --ro шага следует производить операцию сложения вида 1 2-(j ) (Ь-(1-t) " 5j ()- 1 2) 2 2j-1

Р, Р,ОР, ...,., p;.,ОР;., О 1 а2.

Pj 1-j q2-) " "q(j-)-3 %-3 q(j И

Рассмотрим работу устройства в предположении, что 2 „=8.

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

Разряды подкоренного выражения поступают на входы 1, при этом первые 2ш старших разрядов поступают на входы блока 2 постоянной памяти в качестве адресных сигналов.

С помощью блока 2 постоянной памяти вычисляются первые m шагов алгоритма (для рассматриваемого случая -первые четырешага алгоритма.

С выходов блока 2 постоянной памяти снимается m-разрядный резуль1180886 тат, который поступает на первые

m шин выходных разрядов 3, (т.е. значения р -р ), а с,выходов 4-тп-разрядный остаток (т.е. значения q

С1 ь-4 14-4 1 5-1 ) (в+1)-й шаг алгоритма совершается с помощью последовательно соединенных сумматоров 5 первой группы, элементов 6 сложения по модулю два первой группы и элемента НЕ 7, подСоставитель С. Силаев

Редактор Г. Волкова Техред M.Ãåðãåëü Корректор M. Демчик

Тираж 709 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная,4

Заказ 5926/47 п аг

Из и<

Иф 7 ав

4 ключенного к входу а, (а„) устрой1 7nl Я ства.

Аналогично (m+k)-й шаг алгоритма (k=1,...,n-m) совершается с помощью последовательно соединенных сумматоров 5 k-й группы, элементов 6 сложения по модулю два

К-й группы и элемента Л". 7, подключенного к входу (а +Ж-2) устройст2ы

10 ва.